HashSet

在前篇博文中（Java 提高篇（二三）—–HashMap）詳細講解了 HashMap 的實現(xiàn)過程，對于 HashSet 而言，它是基于 HashMap 來實現(xiàn)的，底層采用 HashMap 來保存元素。所以如果對 HashMap 比較熟悉，那么 HashSet是 so easy!!

一、定義

    public class HashSet<E>
        extends AbstractSet<E>
        implements Set<E>, Cloneable, java.io.Serializable

HashSet 繼承 AbstractSet 類，實現(xiàn) Set、Cloneable、Serializable 接口。其中 AbstractSet 提供 Set 接口的骨干實現(xiàn)，從而最大限度地減少了實現(xiàn)此接口所需的工作。Set 接口是一種不包括重復(fù)元素的 Collection，它維持它自己的內(nèi)部排序，所以隨機訪問沒有任何意義。

基本屬性

    //基于HashMap實現(xiàn)，底層使用HashMap保存所有元素
            private transient HashMap<E,Object> map;

            //定義一個Object對象作為HashMap的value
            private static final Object PRESENT = new Object();

構(gòu)造函數(shù)

    /**
             * 默認構(gòu)造函數(shù)
             * 初始化一個空的HashMap，并使用默認初始容量為16和加載因子0.75。
             */
            public HashSet() {
                map = new HashMap<>();
            }

            /**
             * 構(gòu)造一個包含指定 collection 中的元素的新 set。
             */
            public HashSet(Collection<? extends E> c) {
                map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
                addAll(c);
            }

            /**
             * 構(gòu)造一個新的空 set，其底層 HashMap 實例具有指定的初始容量和指定的加載因子
             */
            public HashSet(int initialCapacity, float  loadFactor) {
                map = new HashMap<>(initialCapacity, loadFactor);
            }

            /**
             * 構(gòu)造一個新的空 set，其底層 HashMap 實例具有指定的初始容量和默認的加載因子（0.75）。
             */
             public HashSet(int initialCapacity) {
               map = new HashMap<>(initialCapacity);
            }

            /**
             * 在API中我沒有看到這個構(gòu)造函數(shù)，今天看源碼才發(fā)現(xiàn) （原來訪問權(quán)限為包權(quán)限，不對外公開的）
             * 以指定的initialCapacity和loadFactor構(gòu)造一個新的空鏈接哈希集合。
             * dummy 為標識 該構(gòu)造函數(shù)主要作用是對LinkedHashSet起到一個支持作用
             */
            HashSet(int initialCapacity, float loadFactor, boolean dummy) {
               map = new LinkedHashMap<>(initialCapacity, loadFactor);
            }

從構(gòu)造函數(shù)中可以看出 HashSet 所有的構(gòu)造都是構(gòu)造出一個新的 HashMap，其中最后一個構(gòu)造函數(shù)，為包訪問權(quán)限是不對外公開，僅僅只在使用 LinkedHashSet 時才會發(fā)生作用。

二、方法

既然 HashSet 是基于 HashMap，那么對于 HashSet 而言，其方法的實現(xiàn)過程是非常簡單的。

    public Iterator<E> iterator() {
            return map.keySet().iterator();
        }

iterator() 方法返回對此 set 中元素進行迭代的迭代器。返回元素的順序并不是特定的。底層調(diào)用 HashMap 的 keySet 返回所有的 key，這點反應(yīng)了 HashSet 中的所有元素都是保存在 HashMap 的 key 中，value 則是使用的 PRESENT 對象，該對象為 static final。

    public int size() {
            return map.size();
        }

size() 返回此 set 中的元素的數(shù)量（set 的容量）。底層調(diào)用 HashMap的 size 方法，返回 HashMap 容器的大小。

    public boolean isEmpty() {
            return map.isEmpty();
        }

isEmpty()，判斷 HashSet() 集合是否為空，為空返回 true，否則返回false。

    public boolean contains(Object o) {
            return map.containsKey(o);
        }

contains()，判斷某個元素是否存在于 HashSet() 中，存在返回 true，否則返回 false。更加確切的講應(yīng)該是要滿足這種關(guān)系才能返回true：(o==null ? e==null : o.equals(e))。底層調(diào)用 containsKey 判斷 HashMap 的 key 值是否為空。

    public boolean add(E e) {
            return map.put(e, PRESENT)==null;
        }

add() 如果此 set 中尚未包含指定元素，則添加指定元素。如果此 Set 沒有包含滿足 (e==null ? e2==null : e.equals(e2)) 的 e2 時，則將 e2 添加到 Set 中，否則不添加且返回 false。由于底層使用 HashMap 的 put 方法將 key = e，value=PRESENT 構(gòu)建成 key-value 鍵值對，當此 e 存在于 HashMap 的 key 中，則 value 將會覆蓋原有 value，但是 key 保持不變，所以如果將一個已經(jīng)存在的 e 元素添加中 HashSet 中，新添加的元素是不會保存到 HashMap 中，所以這就滿足了 HashSet 中元素不會重復(fù)的特性。

    public boolean remove(Object o) {
            return map.remove(o)==PRESENT;
        }

remove 如果指定元素存在于此 set 中，則將其移除。底層使用 HashMap 的 remove 方法刪除指定的 Entry。

    public void clear() {
            map.clear();
        }

clear 從此 set 中移除所有元素。底層調(diào)用 HashMap 的 clear 方法清除所有的 Entry。

    public Object clone() {
            try {
                HashSet<E> newSet = (HashSet<E>) super.clone();
                newSet.map = (HashMap<E, Object>) map.clone();
                return newSet;
            } catch (CloneNotSupportedException e) {
                throw new InternalError();
            }
        }

clone 返回此 HashSet 實例的淺表副本：并沒有復(fù)制這些元素本身。

后記：

由于 HashSet 底層使用了 HashMap 實現(xiàn)，使其的實現(xiàn)過程變得非常簡單，如果你對 HashMap 比較了解，那么 HashSet 簡直是小菜一碟。有兩個方法對 HashMap 和 HashSet 而言是非常重要的，下篇將詳細講解 hashcode 和 equals。