上一期我們介紹了HashMap的基本原理毅厚。
這一期我們來講解高并發(fā)環(huán)境下耘子，HashMap可能出現(xiàn)的致命問題。
HashMap的容量是有限的壳猜。當(dāng)經(jīng)過多次元素插入，使得HashMap達(dá)到一定飽和度時(shí)滑凉，Key映射位置發(fā)生沖突的幾率會(huì)逐漸提高统扳。
這時(shí)候喘帚，HashMap需要擴(kuò)展它的長度，也就是進(jìn)行Resize咒钟。
影響發(fā)生Resize的因素有兩個(gè)：
1.Capacity
HashMap的當(dāng)前長度吹由。上一期曾經(jīng)說過，HashMap的長度是2的冪朱嘴。
2.LoadFactor
HashMap負(fù)載因子倾鲫，默認(rèn)值為0.75f。
衡量HashMap是否進(jìn)行Resize的條件如下：
HashMap.Size? ?>=? Capacity * LoadFactor
1.擴(kuò)容
創(chuàng)建一個(gè)新的Entry空數(shù)組腕够，長度是原數(shù)組的2倍级乍。
2.ReHash
遍歷原Entry數(shù)組舌劳，把所有的Entry重新Hash到新數(shù)組帚湘。為什么要重新Hash呢？因?yàn)殚L度擴(kuò)大以后甚淡，Hash的規(guī)則也隨之改變大诸。
讓我們回顧一下Hash公式：
index =? HashCode（Key） &? （Length- 1）
當(dāng)原數(shù)組長度為8時(shí)，Hash運(yùn)算是和111B做與運(yùn)算贯卦；新數(shù)組長度為16资柔，Hash運(yùn)算是和1111B做與運(yùn)算。Hash結(jié)果顯然不同撵割。
Resize前的HashMap：
Resize后的HashMap：
ReHash的Java代碼如下：
/**
* Transfers all entries from current table to newTable.
*/
voidtransfer(Entry[] newTable,booleanrehash) {
intnewCapacity = newTable.length;
for(Entry e :table) {
while(null!= e) {
Entry next = e.next;
if(rehash) {
e.hash=null== e.key?0: hash(e.key);
}
inti =indexFor(e.hash, newCapacity);
e.next= newTable[i];
newTable[i] = e;
e = next;
}
}
}
注意：下面的內(nèi)容十分燒腦贿堰，請小伙伴們坐穩(wěn)扶好。
假設(shè)一個(gè)HashMap已經(jīng)到了Resize的臨界點(diǎn)啡彬。此時(shí)有兩個(gè)線程A和B羹与，在同一時(shí)刻對(duì)HashMap進(jìn)行Put操作：
此時(shí)達(dá)到Resize條件，兩個(gè)線程各自進(jìn)行Rezie的第一步庶灿，也就是擴(kuò)容：
這時(shí)候纵搁，兩個(gè)線程都走到了ReHash的步驟。讓我們回顧一下ReHash的代碼：
假如此時(shí)線程B遍歷到Entry3對(duì)象往踢，剛執(zhí)行完紅框里的這行代碼腾誉，線程就被掛起。對(duì)于線程B來說：
e = Entry3
next = Entry2
這時(shí)候線程A暢通無阻地進(jìn)行著Rehash峻呕，當(dāng)ReHash完成后利职，結(jié)果如下（圖中的e和next，代表線程B的兩個(gè)引用）：
直到這一步瘦癌，看起來沒什么毛病猪贪。接下來線程B恢復(fù)，繼續(xù)執(zhí)行屬于它自己的ReHash佩憾。線程B剛才的狀態(tài)是：
e = Entry3
next = Entry2
當(dāng)執(zhí)行到上面這一行時(shí)哮伟，顯然 i = 3干花，因?yàn)閯偛啪€程A對(duì)于Entry3的hash結(jié)果也是3。
我們繼續(xù)執(zhí)行到這兩行楞黄，Entry3放入了線程B的數(shù)組下標(biāo)為3的位置池凄，并且e指向了Entry2。此時(shí)e和next的指向如下：
e = Entry2
next = Entry2
整體情況如圖所示：
接著是新一輪循環(huán)鬼廓，又執(zhí)行到紅框內(nèi)的代碼行：
e = Entry2
next = Entry3
整體情況如圖所示：
接下來執(zhí)行下面的三行肿仑，用頭插法把Entry2插入到了線程B的數(shù)組的頭結(jié)點(diǎn)：
整體情況如圖所示：
第三次循環(huán)開始，又執(zhí)行到紅框的代碼：
e = Entry3
next = Entry3.next = null
最后一步碎税，當(dāng)我們執(zhí)行下面這一行的時(shí)候尤慰，見證奇跡的時(shí)刻來臨了：
newTable[i] =Entry2
e = Entry3
Entry2.next = Entry3
Entry3.next = Entry2
鏈表出現(xiàn)了環(huán)形！
整體情況如圖所示：
此時(shí)雷蹂，問題還沒有直接產(chǎn)生伟端。當(dāng)調(diào)用Get查找一個(gè)不存在的Key，而這個(gè)Key的Hash結(jié)果恰好等于3的時(shí)候匪煌，由于位置3帶有環(huán)形鏈表责蝠，所以程序?qū)?huì)進(jìn)入死循環(huán)！
這種情況萎庭，不禁讓人聯(lián)想到一道經(jīng)典的面試題：
1.Hashmap在插入元素過多的時(shí)候需要進(jìn)行Resize，Resize的條件是
HashMap.Size? ?>=? Capacity * LoadFactor驳规。
2.Hashmap的Resize包含擴(kuò)容和ReHash兩個(gè)步驟肴敛，ReHash在并發(fā)的情況下可能會(huì)形成鏈表環(huán)。
