? ? ? ? ? HashMap底層實(shí)現(xiàn)
目錄索引
1.java中Map相關(guān)結(jié)構(gòu)體系
2.HashMap源碼中的細(xì)節(jié)
3.JDK1.8中對(duì)HashMap的改進(jìn)
4.高并發(fā)下的HashMap
1 Map結(jié)構(gòu)體系簡(jiǎn)單介紹
? ? ? ? ? ? 上文ArrayList相關(guān)介紹中有提到j(luò)ava中除了單個(gè)元素成“列”存儲(chǔ)的列表容器以外归敬，還提供了存儲(chǔ)? key-value 成對(duì)格式的對(duì)象容器真屯。Map的實(shí)現(xiàn)類有HashMap衷蜓、Hashtable取试、LinkedHashMap和TreeMap纫骑，類繼承關(guān)系如下圖所示：
注：圖中LinkedHashMap少了一個(gè)字母‘h’? 哈哈以现，摳細(xì)節(jié)
2.1 HashMap定義
? ? ? ? ? HashMap 繼承了 AbstractMap 抽象類實(shí)現(xiàn)了Map接口隔显，用于存儲(chǔ)Key-Value鍵值對(duì)的集合项鬼，它的主干是一個(gè)存儲(chǔ)Entry對(duì)象（1.8中改為了Node）的數(shù)組侦厚，初始值都被設(shè)置為null.耻陕。當(dāng)每次插入一個(gè)新的Entry對(duì)象，首先根據(jù)該對(duì)象的 key 值計(jì)算一個(gè) hashcode 刨沦，然后通過一個(gè) hash 函數(shù)計(jì)算出該元素應(yīng)該放在 Entry 應(yīng)該放在哪個(gè)桶中诗宣。
? ? ? ? 如上圖所示，整個(gè)? HashMap 相當(dāng)于一個(gè) table,每個(gè) table 由若干個(gè)桶組成想诅，每個(gè)桶中存儲(chǔ)一個(gè)單向鏈表召庞，在JDK 1.8中某個(gè)桶中的鏈表長(zhǎng)度超過 8時(shí)，將會(huì)把該桶中的元素構(gòu)建為一顆紅黑樹来破。
2.2 HashMap源碼中的一些細(xì)節(jié)
? ? ? ? ? 每次想在HashMap中存儲(chǔ)一個(gè)鍵值對(duì)時(shí)篮灼，第一步先創(chuàng)建一個(gè)Entry(java8中改成了Node)對(duì)象，然后將該對(duì)象鍵的 hashcode 值通過 hash 函數(shù)映射計(jì)算出該 Entry 應(yīng)該存儲(chǔ)在HashMap中的具體位置下標(biāo)徘禁；通常情況下 诅诱，多個(gè)不同的對(duì)象可能會(huì)計(jì)算出相同的hashcode 值，這樣就會(huì)出現(xiàn)散列沖突送朱，為了解決沖突娘荡，具有相同hashcode值的不同對(duì)象會(huì)通過鏈表的形式存儲(chǔ)在同一個(gè)索引上,當(dāng)一個(gè)索引的長(zhǎng)度超過8時(shí)，會(huì)把鏈表轉(zhuǎn)換為紅黑樹骤菠。關(guān)于紅黑樹是個(gè)大專題在這里不瞎談它改，改天單獨(dú)認(rèn)真聊。
put? 時(shí)值的注意的一些細(xì)節(jié)：? 為什么要求hashMap的默認(rèn)長(zhǎng)度以及擴(kuò)? ? 容后的 Node桶的個(gè)數(shù)必須是 2 的次冪
? ? ? 簡(jiǎn)單的說是為了避免出現(xiàn)過多的hash沖突商乎，舉個(gè)例子說明? 假設(shè) key = "Apple"的hashcode值為：? 1111 1111 1111 1111 1111 0000 1110 1010? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? &
假設(shè)table的Node桶的個(gè)數(shù) length 為10：? ? 0000 0000 0000 0000 0000 0000 0000 1010
? 計(jì)算結(jié)果是：? ? ? 0000 0000 0000 0000 0000 0000 0000 1010
? ? ? ? ? 如果下一個(gè)要存入的 Node 對(duì)象的key的 hashcode 最低四位是： 1111? 那么和 1010 取 & 運(yùn)算結(jié)果仍然是 1010央拖，明顯 hashcode 的最后四位值不相同，結(jié)果經(jīng)過 hash 后卻獲得了相同的索引鹉戚；還有一個(gè)問題就是在上面的例子中鲜戒，有些索引值是永遠(yuǎn)不會(huì)出現(xiàn)的：比如1111 0101 0001 0100? ? ? 這樣會(huì)導(dǎo)致更多的hash沖突不說還會(huì)導(dǎo)致某些索引值所在的位置永遠(yuǎn)不會(huì)存入元素，這些都是我們不希望看到的抹凳。然后把問題回到起點(diǎn)遏餐，發(fā)生更多的hash沖突的原因是table中的node桶個(gè)數(shù)的二進(jìn)制低位上有 0，這樣取 & 運(yùn)算 0 所在的位置當(dāng)然不會(huì)計(jì)算出 1赢底，為了解決這個(gè)問題java設(shè)計(jì)師將Node 桶個(gè)數(shù)規(guī)定為 2 的次冪失都，這樣 hashcode 值和 length-1 取 & 運(yùn)算就會(huì)使得每次計(jì)算出的索引值都和 hashcode 的低位值一致（上面例子中的最后四位）柏蘑。 并且不會(huì)出現(xiàn)某些索引被遺忘的情況，繼續(xù)上面的例子：
? ? ? ? key = "Apple"的 hashcode 值為：? ? ? ? ? 1111 1111 1111 1111 1111 0000 1110 1010
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? &
假設(shè)table的Node桶的個(gè)數(shù)length-1為15： 0000 0000 0000 0000 0000 0000 0000 1111
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 計(jì)算結(jié)果是：? ? ? ? 0000 0000 0000 0000 0000 0000 0000 1010?
如果下一個(gè)要存入的Node對(duì)象key的hashcode最后四位是： 1111 那么和 1010 取 & 運(yùn)算結(jié)果是1111粹庞，這樣就很大程度上減少了hash沖突咳焚，同時(shí)也不會(huì)出現(xiàn)某些桶不會(huì)存入Node對(duì)象的情況 JDK1.7中的hash函數(shù)就是這樣實(shí)現(xiàn)的，但是在JDK 1.8 中又做了進(jìn)一步的改進(jìn)庞溜，假設(shè)有兩個(gè)Node對(duì)象的 hashcode 值計(jì)算出來低16位完全相同革半，但是高 16 位值不同，當(dāng)table的桶個(gè)數(shù)較小的時(shí)候這兩個(gè)對(duì)象的hashcode值直接和length - 1取 &流码，求得的索引是相同的又官，但是如果在取 & 之前，將兩個(gè)對(duì)象的hashcode值右移16位漫试，再和原來的 hashcode 值取異或六敬，這樣就會(huì)使得原來相同的低16 變?yōu)椴煌又?length-1 取&商虐，求得的索引值是不相同的兩個(gè)數(shù)觉阅，很好地解決了這種沖突，但是這樣也會(huì)有不好的情況秘车，就是可能會(huì)把之前低 16 不相等 hashcode 值變?yōu)橄嗟鹊溆拢贿^出現(xiàn)的幾率會(huì)很小。
putVal 中 的片段說明叮趴，雖然沒有了1.7 中 的 indexOf 方法單獨(dú)確定下標(biāo)割笙，但是在做插入判斷的時(shí)候依然是 和 length-1 做 & 運(yùn)算
*? if ((p = tab[i = (n - 1) & hash]) == null)
舉個(gè)例子說明一下前面說到的“不足”：
? hashcode值1：1111 1111 1111 1010 1111 0000 1110 1010
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ^
? >>>16? ? 0000 0000 0000 0000 1111 1111 1111 1010
? 異或結(jié)果? 0000 0000 0000 0000 1111 1111 1111 0000
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? &?
? length-1：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1111
hash? 結(jié)果：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0000
*? hashcode值2：1111 1111 1111 0101 1111 0000 1110 0101
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ^
? ? ? ? ? ? ? ? >>>16? ? 0000 0000 0000 0000 1111 1111 1111 0101
? ? ? ? ? ? ? ? ? 異或結(jié)果? 1111 1111 1111 1111 0000 1111 0001 0000
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? &
? ? ? ? ? length-1 ：? ? ? ? ? ? ? ? ? ? ? ? ? ? 1111? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? hash 結(jié)果：? ? ? ? ? ? ? ? ? ? ? ? ? 0000? ? ? ? ? ? ? ?
如上面的例子所示，本來不相同兩個(gè) hashcode 值眯亦，卻計(jì)算出了相同的下標(biāo)伤溉；不過這種情況出現(xiàn)的概率是很小的，總得來說每一次改進(jìn)都只是更好的一種優(yōu)化權(quán)衡妻率，而不是直接消除 hash 沖突乱顾，因?yàn)閔ash沖突只能盡量避免而不能完全消除。不然鏈地址法就完全沒有用武之地了宫静。
接下來談?wù)則able中很重要的一個(gè)字段 threshold：
? ? ? ? threshold? = Load factor負(fù)載因子(默認(rèn)值是0.75)* length;引入負(fù)載因子的目的是用它來衡量一個(gè) table 到底能裝多滿走净，負(fù)載因子很大則說明內(nèi)存空間被充分利用，由于查找效率和table中的桶個(gè)數(shù)有關(guān)孤里，table? 裝的越滿伏伯，則查找效率越低；相反如果負(fù)載因子很小則說明一個(gè)table中有很多的空桶捌袜，這樣會(huì)造成內(nèi)存空間浪費(fèi)说搅，除非在對(duì)內(nèi)存空間和執(zhí)行效率把控特別到位的時(shí)候才可以適當(dāng)調(diào)整默認(rèn)值 0.75，否則慎改虏等。
put具體步驟：（摘自Java 8系列之重新認(rèn)識(shí)HashMap - ）
①.判斷鍵值對(duì)數(shù)組table[i]是否為空或?yàn)閚ull弄唧，否則執(zhí)行resize()進(jìn)行擴(kuò)容适肠；
②.根據(jù)鍵值key計(jì)算hash值得到插入的數(shù)組索引i，如果table[i]==null候引，直接新建節(jié)點(diǎn)添加迂猴，轉(zhuǎn)向⑥，如果table[i]不為空背伴，轉(zhuǎn)向③；
③.判斷table[i]的首個(gè)元素是否和key一樣峰髓，如果相同直接覆蓋value傻寂，否則轉(zhuǎn)向④，這里的相同指的是hashCode以及equals携兵；
④.判斷table[i] 是否為treeNode疾掰，即table[i] 是否是紅黑樹，如果是紅黑樹徐紧，則直接在樹中插入鍵值對(duì)静檬，否則轉(zhuǎn)向⑤；
⑤.遍歷table[i]并级，判斷鏈表長(zhǎng)度是否大于8拂檩，大于8的話把鏈表轉(zhuǎn)換為紅黑樹，在紅黑樹中執(zhí)行插入操作嘲碧，否則進(jìn)行鏈表的插入操作稻励；遍歷過程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value即可；
⑥.插入成功后愈涩，判斷實(shí)際存在的鍵值對(duì)數(shù)量size是否超多了最大容量threshold望抽，如果超過，進(jìn)行擴(kuò)容履婉。
JDK1.8 中 的擴(kuò)容優(yōu)化：
? ? ? 首先會(huì)創(chuàng)建原table兩倍大小的新table煤篙，然后將舊數(shù)組中的元素通過再hash插入到新的數(shù)組中，與1.7 不同的是在移動(dòng)舊元素時(shí)1.8中會(huì)根據(jù)元素在舊數(shù)組中索引位 判斷出該元素在新數(shù)組中應(yīng)該插入的位置而不需要再次 hash毁腿，因?yàn)樾聰?shù)組的長(zhǎng)度是原數(shù)組的 2 倍辑奈，所以假如再次進(jìn)行? hash 變化的只是第三步和 length-1 做 & 運(yùn)算的時(shí)候，由于 length-1 比之前多了一位 1狸棍，多出來的一位和 hashcode 高低位異或后對(duì)應(yīng)的那一位要么是 0 要么是 1 身害； 如果是 0，那么該元素應(yīng)該插入到與舊數(shù)組索引值相同的位置草戈，如果是 1塌鸯，那么該元素應(yīng)該插入到在舊數(shù)組索引值加上舊數(shù)組的總長(zhǎng)度的位置。這樣就很好的避免了再次求 hash 值唐片，只需要查看原來的 hash 值中異或后多出來的一位時(shí) 0 還是 1丙猬。舉例見下圖：
3? 最后聊聊 HashMap 的線程不安全
大家都知道在多線程環(huán)境下 HashMap 是線程不安全的涨颜，最可怕的是如果兩個(gè)線程同時(shí)并發(fā)執(zhí)行同一個(gè) HashMap 時(shí)有可能形成一個(gè)隱藏起來的環(huán)，就像一個(gè)定時(shí)炸彈一樣茧球，在某個(gè)時(shí)刻隨時(shí)爆發(fā)庭瑰。下面舉個(gè)例子，簡(jiǎn)單說明一下形成換的過程：
下圖是JDK 1.7 中擴(kuò)容時(shí)將舊數(shù)組中的元素移動(dòng)到新數(shù)組的具體過程抢埋，從源碼中可以看出每移動(dòng)一個(gè)元素都要重新 hash 求得在新數(shù)組中的索引值弹灭。插入時(shí)若索引沖突將會(huì)按頭插法插入到對(duì)應(yīng)桶的鏈表中
? ? ? ? ? 現(xiàn)在模擬一個(gè)并發(fā)場(chǎng)景，有兩個(gè)線程同時(shí)對(duì)一個(gè) HashMap 對(duì)象進(jìn)行擴(kuò)容操作揪垄，線程一新建一個(gè)長(zhǎng)度為兩倍的新 table穷吮，接下來線程二搶奪CPU同樣新建了一個(gè)新 table；然后線程一繼續(xù)獲得CPU執(zhí)行到 transfer 方法中的 next = e.next 時(shí)線程二再次搶奪了CPU執(zhí)行完整個(gè)轉(zhuǎn)移操作饥努。此時(shí)兩線程的狀態(tài)如下圖所示：
線程二執(zhí)行完了轉(zhuǎn)移操作捡鱼，線程一獲得CPU，由于線程一上次執(zhí)行到了 next = e.next酷愧，所以此時(shí)繼續(xù)執(zhí)行驾诈，當(dāng)前為線程一的第一次循環(huán)：
e = 3? ? next? = 7? ? e.next = newTable[i] = null? ? newTable[i] = e = 3? ? ? ? ? e = next = 7
注意：原先的舊數(shù)組已經(jīng)被線程一置空了，所以線程一指向的 e = 3 和 next = 7 都已經(jīng)被移動(dòng)到了線程二創(chuàng)建的新 table 中溶浴。
接下來執(zhí)行第二次循環(huán)：
e = 7? ? ? next = 3? ? e.next = newTable[i] = 3? ? ? newTable[i] = 7? ? e = next = 3
第三循環(huán)見證奇跡：
e = 3? ? next = null? ? e.next = newTable[i] = 7? ? newTable[i] = 3? e = null? 插入完畢
e 最終指向了null 就這樣悄無聲息的轉(zhuǎn)移完成了乍迄，然而如上圖所示索引值為 3 的桶中的鏈表出現(xiàn)了一個(gè)環(huán)，3 指向了 7 ====》7 指向了3戳葵；這樣在以后某個(gè)時(shí)刻當(dāng)調(diào)用get方法時(shí)就乓，查找的元素索引值剛好是3，但是該元素在鏈表中不存在拱烁，這樣執(zhí)行g(shù)et的線程將會(huì)在一個(gè)環(huán)中查找一個(gè)不存在的生蚁，永不停歇直到世界末日，哈哈戏自。
好了邦投，今天就先寫到這，關(guān)于HashMap還有很多值得聊的地方擅笔，下次再說志衣。
晚安，牧羊十二
