Java中Set集合是如何實現添加元素保證不重覆的？ Set集合是一個無序的不可以重覆的集合。今天來看一下為什麼不可以重覆。 ...
Java中Set集合是如何實現添加元素保證不重覆的？
Set集合是一個無序的不可以重覆的集合。今天來看一下為什麼不可以重覆。
Set是一個介面，最常用的實現類就是HashSet，今天我們就拿HashSet為例。
先簡單介紹一下HashSet類
HashSet類實現了Set介面， 其底層其實是包裝了一個HashMap去實現的。HashSet採用HashCode演算法來存取集合中的元素，因此具有比較好的讀取和查找性能。
先看下HashSet的幾個構造方法。
// 預設構造函數 底層創建一個HashMap
public HashSet() {
// 調用HashMap的預設構造函數，創建map
map = new HashMap<E,Object>();
}
// 帶集合的構造函數
public HashSet(Collection<? extends E> c) {
// 創建map。
map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
// 將集合(c)中的全部元素添加到HashSet中
addAll(c);
}
// 指定HashSet初始容量和載入因數的構造函數
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<E,Object>(initialCapacity, loadFactor);
}
// 指定HashSet初始容量的構造函數
public HashSet(int initialCapacity) {
map = new HashMap<E,Object>(initialCapacity);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}再來看HashSet中的聲明。
private transient HashMap<E,Object> map;
// 用來匹配Map中後面的對象的一個虛擬值
private static final Object PRESENT = new Object();接下來就是我們的重點HashSet的add()方法，貼上源碼。
/**
* 將元素e添加到HashSet中，也就是將元素e作為Key放入HashMap中
*
* @param e 要添加到HashSet中的元素
* @return true 如果不包含該元素
*/
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}從源碼我們可以看出HashSet的add()方法又調用了HashMap中的put()方法，那我們再跳轉到HashMap中的put()方法中。
public V put(K key, V value) {
// 倒數第二個參數false：表示允許舊值替換
// 最後一個參數true：表示HashMap不處於創建模式
return putVal(hash(key), key, value, false, true);
}HashMap中的put()方法又調用了putVal()方法來實現功能，再看putVal()的源碼。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K, V>[] tab;
Node<K, V> p;
int n, i;
//如果哈希表為空，調用resize()創建一個哈希表，並用變數n記錄哈希表長度
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/**
* 如果指定參數hash在表中沒有對應的桶，即為沒有碰撞
* Hash函數，(n - 1) & hash 計算key將被放置的槽位
* (n - 1) & hash 本質上是hash % n，位運算更快
*/
if ((p = tab[i = (n - 1) & hash]) == null)
//直接將鍵值對插入到map中即可
tab[i] = newNode(hash, key, value, null);
else {// 桶中已經存在元素
Node<K, V> e;
K k;
// 比較桶中第一個元素(數組中的結點)的hash值相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 將第一個元素賦值給e，用e來記錄
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;
}
// 鏈表節點的<key, value>與put操作<key, value>相同時，不做重覆操作，跳出迴圈
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 找到或新建一個key和hashCode與插入元素相等的鍵值對，進行put操作
if (e != null) { // existing mapping for key
// 記錄e的value
V oldValue = e.value;
/**
* onlyIfAbsent為false或舊值為null時，允許替換舊值
* 否則無需替換
*/
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 訪問後回調
afterNodeAccess(e);
// 返回舊值
return oldValue;
}
}
// 更新結構化修改信息
++modCount;
// 鍵值對數目超過閾值時，進行rehash
if (++size > threshold)
resize();
// 插入後回調
afterNodeInsertion(evict);
return null;
}從源碼中，我們可以看出將一個key-value對放入HashMap中時，首先根據key的hashCode()返回值決定該Entry的存儲位置，如果兩個key的hash值相同，那麼它們的存儲位置相同。如果這個兩個key的equals比較返回true。那麼新添加的Entry的value會覆蓋原來的Entry的value，key不會覆蓋。且HashSet中add()中 map.put(e, PRESENT)==null 為false，HashSet添加元素失敗。因此,如果向HashSet中添加一個已經存在的元素，新添加的集合元素不會覆蓋原來已有的集合元素。
推薦閱讀
