    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();
    }

其實(shí)在英文注釋中已經(jīng)說(shuō)的比較明確了。首先有一個(gè)HashMap的成員變量，我們?cè)?HashSet 的構(gòu)造函數(shù)中將其初始化，默認(rèn)情況下采用的是 initial capacity為16，load factor 為 0.75。

HashSet 的實(shí)現(xiàn)

對(duì)于 HashSet 而言，它是基于 HashMap 實(shí)現(xiàn)的，HashSet 底層使用 HashMap 來(lái)保存所有元素，因此 HashSet 的實(shí)現(xiàn)比較簡(jiǎn)單，相關(guān) HashSet 的操作，基本上都是直接調(diào)用底層 HashMap 的相關(guān)方法來(lái)完成，我們應(yīng)該為保存到 HashSet 中的對(duì)象覆蓋 hashCode() 和 equals()

構(gòu)造方法

/**
 * 默認(rèn)的無(wú)參構(gòu)造器，構(gòu)造一個(gè)空的HashSet。
 *
 * 實(shí)際底層會(huì)初始化一個(gè)空的HashMap，并使用默認(rèn)初始容量為16和加載因子0.75。
 */
public HashSet() {
    map = new HashMap<E,Object>();
}

/**
 * 構(gòu)造一個(gè)包含指定collection中的元素的新set。
 *
 * 實(shí)際底層使用默認(rèn)的加載因子0.75和足以包含指定collection中所有元素的初始容量來(lái)創(chuàng)建一個(gè)HashMap。
 * @param c 其中的元素將存放在此set中的collection。
 */
public HashSet(Collection<? extends E> c) {
    map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

/**
 * 以指定的initialCapacity和loadFactor構(gòu)造一個(gè)空的HashSet。
 *
 * 實(shí)際底層以相應(yīng)的參數(shù)構(gòu)造一個(gè)空的HashMap。
 * @param initialCapacity 初始容量。
 * @param loadFactor 加載因子。
 */
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<E,Object>(initialCapacity, loadFactor);
}

/**
 * 以指定的initialCapacity構(gòu)造一個(gè)空的HashSet。
 *
 * 實(shí)際底層以相應(yīng)的參數(shù)及加載因子loadFactor為0.75構(gòu)造一個(gè)空的HashMap。
 * @param initialCapacity 初始容量。
 */
public HashSet(int initialCapacity) {
    map = new HashMap<E,Object>(initialCapacity);
}

/**
 * 以指定的initialCapacity和loadFactor構(gòu)造一個(gè)新的空鏈接哈希集合。此構(gòu)造函數(shù)為包訪問(wèn)權(quán)限，不對(duì)外公開(kāi)，
 * 實(shí)際只是是對(duì)LinkedHashSet的支持。
 *
 * 實(shí)際底層會(huì)以指定的參數(shù)構(gòu)造一個(gè)空LinkedHashMap實(shí)例來(lái)實(shí)現(xiàn)。
 * @param initialCapacity 初始容量。
 * @param loadFactor 加載因子。
 * @param dummy 標(biāo)記。
 */
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}

add 方法

/**

 * @param e 將添加到此set中的元素。
 * @return 如果此set尚未包含指定元素，則返回true。
 */
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

如果此 set 中尚未包含指定元素，則添加指定元素。更確切地講，如果此 set 沒(méi)有包含滿足(e==null ? e2==null : e.equals(e2)) 的元素 e2，則向此 set 添加指定的元素 e。如果此 set 已包含該元素，則該調(diào)用不更改 set 并返回 false。但底層實(shí)際將將該元素作為 key 放入 HashMap。思考一下為什么？

由于 HashMap 的 put() 方法添加 key-value 對(duì)時(shí)，當(dāng)新放入 HashMap 的 Entry 中 key 與集合中原有 Entry 的 key 相同（hashCode()返回值相等，通過(guò) equals 比較也返回 true），新添加的 Entry 的 value 會(huì)將覆蓋原來(lái) Entry 的 value（HashSet 中的 value 都是PRESENT），但 key 不會(huì)有任何改變，因此如果向 HashSet 中添加一個(gè)已經(jīng)存在的元素時(shí)，新添加的集合元素將不會(huì)被放入 HashMap中，原來(lái)的元素也不會(huì)有任何改變，這也就滿足了 Set 中元素不重復(fù)的特性。

該方法如果添加的是在 HashSet 中不存在的，則返回 true；如果添加的元素已經(jīng)存在，返回 false。其原因在于我們之前提到的關(guān)于 HashMap 的 put 方法。該方法在添加 key 不重復(fù)的鍵值對(duì)的時(shí)候，會(huì)返回 null。

其余方法

    /**
     * 如果此set包含指定元素，則返回true。
     * 更確切地講，當(dāng)且僅當(dāng)此set包含一個(gè)滿足(o==null ? e==null : o.equals(e))的e元素時(shí)，返回true。
     *
     * 底層實(shí)際調(diào)用HashMap的containsKey判斷是否包含指定key。
     * @param o 在此set中的存在已得到測(cè)試的元素。
     * @return 如果此set包含指定元素，則返回true。
     */
    public boolean contains(Object o) {
    return map.containsKey(o);
    }
    /**
     * 如果指定元素存在于此set中，則將其移除。更確切地講，如果此set包含一個(gè)滿足(o==null ? e==null : o.equals(e))的元素e，
     * 則將其移除。如果此set已包含該元素，則返回true
     *
     * 底層實(shí)際調(diào)用HashMap的remove方法刪除指定Entry。
     * @param o 如果存在于此set中則需要將其移除的對(duì)象。
     * @return 如果set包含指定元素，則返回true。
     */
    public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
    }
    /**
     * 返回此HashSet實(shí)例的淺表副本：并沒(méi)有復(fù)制這些元素本身。
     *
     * 底層實(shí)際調(diào)用HashMap的clone()方法，獲取HashMap的淺表副本，并設(shè)置到HashSet中。
     */
    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();
        }
    }
}

HashSet 的實(shí)現(xiàn)原理

HashSet 概述