對(duì)于 HashSet 而言,它是基于 HashMap 實(shí)現(xiàn)的,底層采用 HashMap 來(lái)保存元素,所以如果對(duì) HashMap 比較熟悉了,那么學(xué)習(xí) HashSet 也是很輕松的。
我們先通過(guò) HashSet 最簡(jiǎn)單的構(gòu)造函數(shù)和幾個(gè)成員變量來(lái)看一下,證明咱們上邊說(shuō)的,其底層是 HashMap:
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。
對(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()
/**
* 默認(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);
}
/**
* @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();
}
}
}