資訊專欄INFORMATION COLUMN
摘要：如果不重復，判斷是否是類型，如果是紅黑樹，直接插入。條件為時執行鏈表轉紅黑樹，然后插入。為了避免尾部遍歷。添加元素時，如果超過閾值，就要進行擴容，如果兩個元素同時添加，線程和線程可能同時擴容。
1.HashMap結構
????HashMap是存鍵值對(key-value)映射的數據結構，由數組+鏈表組成的，數組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的，如果定位到的數組位置不含鏈表（當前entry的next指向null）,那么對于查找，添加等操作很快，僅需一次尋址即可；如果定位到的數組包含鏈表，對于添加操作，其時間復雜度為O(n)，首先遍歷鏈表，存在即覆蓋，否則新增；對于查找操作來講，仍需遍歷鏈表，然后通過key對象的equals方法逐一比對查找。通過下圖可以對HashMap有一個直觀的認識。
put操作（JDK1.8版）
????1）計算key的hash值（計算過程下面會詳細介紹）。
????2）如果數組table是否為null或長度是否等于0，條件為true時進行數據table擴容（實際執行resize方法）。
????3）根據hash值計算Value將要存放的位置，即計算數組table索引（計算過程下面會詳細講）。
????4）判斷table[i]是否是null，如果是null直接進行Value插入。
????5）如果table[i]不是null，接著判斷key是否重復，如果重復直接進行覆蓋插入。
????6）如果key不重復，判斷table[i]是否是TreeNode類型，如果是紅黑樹，直接插入。
????7）如果不是TreeNode就遍歷鏈表，遍歷時預判斷插入新的Value后，鏈表長度是否大于等于8。條件為True時執行鏈表轉紅黑樹，然后插入Value。
????8）如果上面鏈表長度小于8執行鏈表插入。
????9）最后檢查數組是否需要擴容。
詳細代碼：
public V put(K key, V value) {
//調用putVal方法
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node[] tab; //緩存底層數組用,都是指向一個地址的引用
Node p; //插入數組的桶i處的鍵值對節點
int n; //底層數組的長度
int i; //插入數組的桶的下標
//剛開始table是null或空的時候，初始化個默認的table；為tab和n賦值，tab指向底層數組，n為底層數組的長度
if ((tab = table) == null || (n = tab.length) == 0){
n = (tab = resize()).length;
}
//(n - 1) & hash：根據hash值算出插入點在底層數組的桶的位置，即下標值；為p賦值，也為i賦值（不管碰撞與否，都已經賦值了）
//如果在數組上，沒有發生碰撞，即當前要插入的位置上之前沒有插入過值，則直接在此位置插入要插入的鍵值對
if ((p = tab[i = (n - 1) & hash]) == null){
tab[i] = newNode(hash, key, value, null);//插入的節點的next屬性是null
} else { //發生碰撞，即當前位置已經插入了值
Node e; //中間變量吧，跟冒泡排序里面的那個中間變量似的，起到個值交換的作用
K k; //同上
//hash值相同，key也相同，那么就是更新這個鍵值對的值。同 jdk 1.7
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){ //注意在這個if內【e != null】
e = p;//這地方，e = p 他們兩個都是指向數組下標為i的地方，在這if else if else結束之后，再把節點的值value給更新了
} else if (p instanceof TreeNode){ //這個樹方法可能會返回null。
//jdk 1.8引入了紅黑樹來處理碰撞，上面判斷p的類型已經是樹結構了，
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);//如果是，則走添加樹的方法。
} else { //注意在這個else內，當為添加新節點時，【e == 】；更新某個節點時，就不是null
for (int binCount = 0; ; ++binCount) {//還未形成樹結構，還是jdk 1.7的鏈表結構
//差別就是1.7:是頭插法，后來的留在數組上，先來的鏈在尾上；1.8:是先來的就留在數組上，后來的鏈在尾上
//判斷p.next是否為空，同時為e賦值，若為空，則p.next指向新添加的節點，這是在鏈表長度小于7的時候
if ((e = p.next) == null) {
//這個地方有個不好理解的地方：在判斷條件里面，把e指向p.next，也就是說現在e=null而不是下下一行錯誤的理解。
//這也就解釋了更新的時候，返回oldValue，新建的時候，是不在那地方返回的。
p.next = newNode(hash, key, value, null);//e = p.next,p.next指向新生成的節點，也就是說e指向新節點（錯誤）
//對于臨界值的分析：
//假設此次是第六次，binCount == 6,不會進行樹變，當前鏈表長度是7；下次循環。
//binCount == 7，條件成立，進行樹變，以后再put到這個桶的位置的時候，這個else就不走了，走中間的那個數結構的分叉語句啦
//這個時候，長度為8的鏈表就變成了紅黑樹啦
if (binCount >= TREEIFY_THRESHOLD - 1){// -1 for 1st //TREEIFY_THRESHOLD == 8
treeifyBin(tab, hash);
}
break;//插入新值或進行樹變后，跳出for循環。此時e未重定向，還是指向null，雖然后面p.next指向了新節點。
//但是，跟e沒關系。
}
//如果在循環鏈表的時候，找到key相同的節點，那么就跳出循環，就走不到鏈表的尾上了。
// e已經在上一步已經賦值了，且不為null,也會跳出for循環，會在下面更新value的值
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
break;
}
//這個就是p.next也就是e不為空，然后，還沒有key相同的情況出現，那就繼續循環鏈表，
// p指向p.next也就是e，繼續循環，繼續，e=p.next
p = e;
//直到p.next為空，添加新的節點；或者出現key相等，更新舊值的情況才跳出循環。
}
}
//經過上面if else if else之后，e在新建節點的時候，為null；更新的時候，則被賦值。在樹里面處理putTreeVal（）同樣如此，
if (e != null) { // existing mapping for key//老外說的對，就是只有更新的時候，才走這，才會直接return oldValue
V oldValue = e.value;
//onlyIfAbsent 這個在調用hashMap的put()的時候，一直是false，那么下面更新value是肯定執行的
if (!onlyIfAbsent || oldValue == null){
e.value = value;
}
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold){
resize();
}
afterNodeInsertion(evict);
return null;
3.尋址過程（怎么由key值轉換成數組下標）
借用網上的圖，先比較直觀的看下這個轉換過程：
????第一步：key值--->32位的哈希值
????這個就是key值調用hashCode()函數，生成一個32位的哈希值。
????第二步：32位哈希值--->混合哈希值
????這一步將32位哈希值的高16位與低16位做異或操作。為什么要這樣做呢，因為后面還要進行一次indexFoe()操作截取低位信息（高位信息將會丟失），因此高低位異或操作后，低16位也能摻雜高16位的信息，高位的信息變相被保存下來了，可以增加隨機性，減小沖突的可能性。
1,2兩步的操作在put函數源碼中合并成了一行代碼，如下：
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
????第三步：混合哈希值--->數組下標
鏈表數組的初始長度是16。顯然這個32位的混合哈希值不能直接和鏈表數組直接對應起來，會照成大量沖突。這里采用了一次取模運算。HashMap 通過 hash 值與 length-1 (容器長度-1)進行取模（%）運算。可能有人會問：明明源碼中 indexFor() 方法進行的 按位與（&）運算，而非取模運算。實際上，HashMap 中的 indexFor() 方法就是在進行取模運算。利用位運算代替取模運算，可以大大提高程序的計算效率。位運算可以直接對內存數據進行操作，不需要轉換成十進制，因此效率要高得多。需要注意的是，只有在特定情況下，位運算才可以轉換成取模運算（當 b = 2^n 時，a % b = a & (b - 1) ）。也是因此，HashMap 才將初始長度設置為 16，且擴容只能是以 2 的倍數（2^n）擴容。
在擴容操作時可能形成環形鏈表。
原因：
在HashMap擴容時，會改變鏈表中的元素的順序，將元素從鏈表頭部插入。（為了避免尾部遍歷）。而環形鏈表就在這一時刻發生。添加元素時，如果超過閾值，就要進行擴容，如果兩個元素同時添加，線程A和線程B可能同時擴容。線程A準備擴容時，線程B開始執行，擴容完畢，產生新的hashMap. 此時A—>B?null變成B—>A ?null，先將A復制到新的hash表中，然后接著復制B到鏈頭（A的前邊：B.next=A），本來B.next=null，到此也就結束了（跟線程二一樣的過程），但是，由于線程二擴容的原因，將B.next=A，所以，這里繼續復制A，讓A.next=B，由此，環形鏈表出現：B.next=A; A.next=B。本來應該通過 A.next=B來讓A指向null 的，但是線程A已經把A.next變成B的位置了。所有行成回環。
因為hashSet底層也是利用hashMap實現的，所以這里一起分析下。
HashSet 是一個沒有重復元素的集合，它是由HashMap實現的，不保證元素的順序，而且HashSet允許使用 null 元素。
HashSet是非同步的。如果多個線程同時訪問一個哈希 set，而其中至少一個線程修改了該 set，那么它必須 保持外部同步。這通常是通過對自然封裝該 set 的對象執行同步操作來完成的。如果不存在這樣的對象，則應該使用 Collections.synchronizedSet 方法來“包裝” set。最好在創建時完成這一操作，以防止對該 set 進行意外的不同步訪問：Set s = Collections.synchronizedSet(new HashSet(...));
HashSet偽代碼實現：
