Set集合的不重復(fù)性是怎么做到的（Set集合的不重復(fù)原理）
因為當(dāng)我們向Set集合加入數(shù)據(jù)時，要加入的數(shù)據(jù)會和集合里的數(shù)據(jù)比較
會先比較hashCode()的值，如果不同那么jvm就會認(rèn)為這是兩個不同的數(shù)據(jù) 就會直接加入，
而如果hashCode()的值相同，jvm會調(diào)用equals()來比較，如果相同就認(rèn)為是一個數(shù)據(jù)，否則 就是兩個數(shù)據(jù)。（當(dāng)hashCode()的值不同時就不會繼續(xù)調(diào)用equals()了）
Set集合是一個無序的不可以重復(fù)的集合。
Set是一個接口，最常用的實現(xiàn)類就是HashSet，今天我們就拿HashSet為例。
HashSet的底層實現(xiàn)是HashMap ---> （HashSet的值不可重復(fù)；而HashMap中key不可以重復(fù)，值可以重復(fù)。從這一點推測的話，HashSet的底層實現(xiàn)是HashMap是可以理解的）
private transient HashMap<E,Object> map;
// 用來匹配Map中后面的對象的一個虛擬值
private static final Object PRESENT = new Object();
HashSet如何檢查重復(fù)？ ：hashCode()和equals(): //相同的對象必須hashCode()相同并且equals()返回true，但hashCode()相同的對象不一定相同。
必須覆蓋hashCode()和equals(): hashCode()的默認(rèn)行為是對在heap上的對象產(chǎn)生獨特的值，如果沒有override過hashCode()，則該class的兩個對象怎樣都不會被認(rèn)為是相同的。
（1）先來看看 HashSet 的幾個構(gòu)造方法
Copy// 默認(rèn)構(gòu)造函數(shù) 底層創(chuàng)建一個HashMap
public HashSet() {
// 調(diào)用HashMap的默認(rèn)構(gòu)造函數(shù)，創(chuàng)建map
map = new HashMap<E,Object>();
}
// 帶集合的構(gòu)造函數(shù)
public HashSet(Collection<? extends E> c) {
// 創(chuàng)建map。
map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
// 將集合(c)中的全部元素添加到HashSet中
addAll(c);
}
// 指定HashSet初始容量和加載因子的構(gòu)造函數(shù)
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<E,Object>(initialCapacity, loadFactor);
}
// 指定HashSet初始容量的構(gòu)造函數(shù)
public HashSet(int initialCapacity) {
map = new HashMap<E,Object>(initialCapacity);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}
（2）HashSet 中的聲明
Copyprivate transient HashMap<E,Object> map;
private static final Object PRESENT = new Object(); // 用來匹配Map中后面的對象的一個虛擬值
（3）HashSet的add（）方法
將元素e添加到HashSet中，也就是將元素e作為Key放入HashMap中
/**
* 將元素e添加到HashSet中，也就是將元素e作為Key放入HashMap中
*
* @param e 要添加到HashSet中的元素
* @return true 如果不包含該元素
*/
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
（4）可以看出HashSet的add()方法又調(diào)用了HashMap中的put()方法，那我們再跳轉(zhuǎn)到HashMap中的put()方法
//HashSet的add()方法又調(diào)用了HashMap中的put()方法
public V put(K key, V value) {
// 倒數(shù)第二個參數(shù)false：表示允許舊值替換
// 最后一個參數(shù)true：表示HashMap不處于創(chuàng)建模式
return putVal(hash(key), key, value, false, true);
}
（5）HashMap中的put()方法又調(diào)用了putVal()方法來實現(xiàn)功能，再看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;
//如果哈希表為空，調(diào)用resize()創(chuàng)建一個哈希表，并用變量n記錄哈希表長度
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/**
* 如果指定參數(shù)hash在表中沒有對應(yīng)的桶，即為沒有碰撞
* Hash函數(shù)，(n - 1) & hash 計算key將被放置的槽位
* (n - 1) & hash 本質(zhì)上是hash % n，位運算更快
*/
if ((p = tab[i = (n - 1) & hash]) == null)
//直接將鍵值對插入到map中即可
tab[i] = newNode(hash, key, value, null);
else {// 桶中已經(jīng)存在元素
Node<K, V> e;
K k;
// 比較桶中第一個元素(數(shù)組中的結(jié)點)的hash值相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 將第一個元素賦值給e，用e來記錄
e = p;
// 當(dāng)前桶中無該鍵值對，且桶是紅黑樹結(jié)構(gòu)，按照紅黑樹結(jié)構(gòu)插入
else if (p instanceof TreeNode)
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
// 當(dāng)前桶中無該鍵值對，且桶是鏈表結(jié)構(gòu)，按照鏈表結(jié)構(gòu)插入到尾部
else {
for (int binCount = 0; ; ++binCount) {
// 遍歷到鏈表尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 檢查鏈表長度是否達到閾值，達到將該槽位節(jié)點組織形式轉(zhuǎn)為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 鏈表節(jié)點的<key, value>與put操作<key, value>相同時，不做重復(fù)操作，跳出循環(huán)
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;
// 訪問后回調(diào)
afterNodeAccess(e);
// 返回舊值
return oldValue;
}
}
// 更新結(jié)構(gòu)化修改信息
++modCount;
// 鍵值對數(shù)目超過閾值時，進行rehash
if (++size > threshold)
resize();
// 插入后回調(diào)
afterNodeInsertion(evict);
return null;
}
從源碼中，我們可以看出將一個key-value對放入HashMap中時
- 首先根據(jù)key的hashCode()返回值決定該Entry的存儲位置，如果兩個key的hash值相同，那么它們的存儲位置相同。如果這個兩個key的equals比較返回true。那么新添加的Entry的value會覆蓋原來的Entry的value，key不會覆蓋。且HashSet中add()中 map.put(e, PRESENT)==null 為false，HashSet添加元素失敗。因此,如果向HashSet中添加一個已經(jīng)存在的元素，新添加的集合元素不會覆蓋原來已有的集合元素。
- 看hashmap的put 方法的返回值，map對象在調(diào)用put的時候傳入一個key和val，會對其key進行一個算法得到一個位置，會把put的數(shù)據(jù)放到其位置上，如果該位置上已經(jīng)存在當(dāng)前key，會對其key映射的val給替換掉，并且返回之前的val，否則返回null。
好了，既然put的返回值原理搞清楚了，就要去看看 set 的add方法的實現(xiàn)，add方法是調(diào)用了put方法，并且把key放在了put的key上，val放了一個hashset類的靜態(tài)常量present：- 如果put 返回的是null，不是present，就說明 put的key是不存在的，add也會返回true
- 如果put返回的是present，就說明之前的key是存在的，并不是說沒有put上，所以add方法返回的false并不是存失敗的意思，而是map.put的key是已經(jīng)存在的，而且已經(jīng)把val給替換了。
