HashSet原始碼分析

原始碼分析 · 發表 2019-05-02 17:36:45

摘要： HashSet是一個HashMap的一個例項，它不保證它的元素們的相對順序始終是一樣的。它也允許null元素的存在。和其他的集合一樣，它也是執行緒不安全，具有fail-fast機制的。 private transient HashMap<E,Object> map; // 這...

HashSet是一個HashMap的一個例項，它不保證它的元素們的相對順序始終是一樣的。它也允許null元素的存在。和其他的集合一樣，它也是執行緒不安全，具有fail-fast機制的。

private transient HashMap<E,Object> map;

// 這裡構造了一個虛擬的物件來充當HashMap中的value值。
//這個物件是用final修飾的，所以這個value值也是保持不變的
private static final Object PRESENT = new Object();
複製程式碼

上面是它的2個屬性。

public HashSet() {
map = new HashMap<>();
}

public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}

public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}

複製程式碼

上面是4種構造本類例項的方法。

public Iterator<E> iterator() {
return map.keySet().iterator();
}
複製程式碼

HashSet的迭代器也是來自HashMap。從這裡可以看出HashSet中的元素其實是HashMap中的key的集合，因為該迭代器就是遍歷的HashMap的key集合。

public boolean add(E e) {
return map.put(e, PRESENT)==null;
}複製程式碼

上面是他的add方法。從這裡也可以看出value就是用這個虛擬的物件來充當的。

其他的方法也都是基於HashMap來實現的。

另外，HashSet是怎麼保證元素不重複的呢？因為它的add方法其實就是HashMap的put方法實現的，所以它的這個性質也是由這個方法來保證的。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;

if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}複製程式碼

上面就是底層方法的實現，說明下期中一些變數的作用。p節點是用來接收集合中的第一個元素以及利用它來呼叫next來遍歷集合中的其他元素，而e節點則是來接收p節點。用K k來接收集合中元素的key值。

if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;複製程式碼

從上面這段程式碼可以看出先是比較集合中的元素的hash值是否與要新增的元素的hash值相等，以及他們的key是否相等（此處是用==來判斷的）；然後用元素的equals方法比較key值是否相等。如果條件成立則把p節點賦給e節點，此時說明要加入的元素的hash值與集合中的一個元素的hash值相等了，也就是說對於key有了相同的對映。今兒判斷e是否為null，若不為null，就把集合中的這個元素的value值賦給oldValue作為返回值，然後把要新增的元素的value值賦給e節點。

從上面的分析可以看出它是怎麼保證元素的不重複的性質，也知道了其實HashMap本身的元素們也是具有不重複的性質的。

Set<String> set = new HashSet();
set.add(null);
set.add("null");
System.out.println(set);//[null, null]複製程式碼

最後發現了一個有趣的地方。

HashSet原始碼分析

您可能也會喜歡…