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