一.問題
眾所周知，HashMap是線程不安全的后专，在并發(fā)使用HashMap時(shí)很容易出現(xiàn)一些問題划鸽，其中最典型的就是并發(fā)情況下擴(kuò)容之后會(huì)發(fā)生死循環(huán)，導(dǎo)致CPU占用100%。同時(shí)裸诽，這也是一個(gè)高頻面試題嫂用。因此，本文通過解讀HashMap源碼并結(jié)合實(shí)例丈冬，來具體分析HashMap擴(kuò)容發(fā)生的死循環(huán)問題嘱函。
二.源碼解讀
下面這段代碼是JDK 1.7中HashMap的resize方法，即擴(kuò)容時(shí)調(diào)用的代碼埂蕊，作用是創(chuàng)建新的Entry數(shù)組newTable往弓，然后調(diào)用transfer方法將原來的Entry數(shù)組中的節(jié)點(diǎn)都轉(zhuǎn)移到newTable中，最后將HashMap的成員變量table指向newTable蓄氧，所以擴(kuò)容機(jī)制的核心代碼在transfer方法中函似。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
下面這段代碼是JDK1.7中HashMap的transfer方法，作用是遍歷原來table中每個(gè)位置的鏈表喉童，并對(duì)鏈表中的每個(gè)節(jié)點(diǎn)重新進(jìn)行hash缴淋，在新的Entry數(shù)組newTable中找到歸宿，并插入泄朴。
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
//獲取鏈表的頭節(jié)點(diǎn)e
while(null != e) {
//獲取要轉(zhuǎn)移的下一個(gè)節(jié)點(diǎn)next
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//計(jì)算要轉(zhuǎn)移的節(jié)點(diǎn)在新的Entry數(shù)組newTable中的位置
int i = indexFor(e.hash, newCapacity);
//使用頭插法將要轉(zhuǎn)移的節(jié)點(diǎn)插入到newTable原有的單鏈表中
e.next = newTable[i];
//將newTable的hash桶的指針指向要轉(zhuǎn)移的節(jié)點(diǎn)
newTable[i] = e;
//轉(zhuǎn)移下一個(gè)需要轉(zhuǎn)移的節(jié)點(diǎn)e
e = next;
}
}
}
其中，transfer方法的核心代碼分為以下四個(gè)步驟：
1.獲取要轉(zhuǎn)移的下一個(gè)節(jié)點(diǎn)next;
2.使用頭插法將要轉(zhuǎn)移的節(jié)點(diǎn)插入到newTable原有的單鏈表中;
3.將newTable的hash桶的指針指向要轉(zhuǎn)移的節(jié)點(diǎn);
4.轉(zhuǎn)移下一個(gè)需要轉(zhuǎn)移的節(jié)點(diǎn)e露氮。
三.實(shí)例分析
1.單線程擴(kuò)容
假設(shè)單線程場(chǎng)景下要對(duì)下圖中的table進(jìn)行擴(kuò)容：
擴(kuò)容初始情況如下：
轉(zhuǎn)移A節(jié)點(diǎn)之后的情況如下：
為了便于理解祖灰，簡(jiǎn)化上圖如下：
轉(zhuǎn)移B節(jié)點(diǎn)之后的情況如下：
轉(zhuǎn)移C節(jié)點(diǎn)之后，oldTable中的節(jié)點(diǎn)就都轉(zhuǎn)移到newTable中了畔规，HashMap成功完成了擴(kuò)容的過程：
觀察擴(kuò)容之前的oldTable中的單鏈表和擴(kuò)容之后的newTable中的單鏈表局扶，不難發(fā)現(xiàn)，oldTable中的單鏈表和newTable中的單鏈表的節(jié)點(diǎn)的順序是相反的叁扫。由于擴(kuò)容過程中使用頭插法將oldTable中的單鏈表中的節(jié)點(diǎn)插入到newTable的單鏈表中三妈，所以newTable中的單鏈表會(huì)倒置oldTable中的單鏈表。
2.多線程擴(kuò)容
假設(shè)有兩個(gè)線程同時(shí)對(duì)HashMap進(jìn)行擴(kuò)容莫绣，在某一時(shí)刻這兩個(gè)線程都進(jìn)行到如下狀態(tài)：
之后線程1執(zhí)行了transfer方法的核心代碼中的第1步和第2步畴蒲，時(shí)間片就用完了，執(zhí)行后的情況如下：
這時(shí)輪到線程2開始執(zhí)行对室，執(zhí)行transfer方法的核心代碼中的第1步之后模燥，情況如下：
線程2執(zhí)行第2，3掩宜，4步之后蔫骂，情況如下：
線程2執(zhí)行下一輪循環(huán)的第1辽旋，2，3，4步之后补胚，線程2的擴(kuò)容過程成功結(jié)束：
可以看到伐坏，線程2擴(kuò)容之后的newTable中的單鏈表形成了一個(gè)環(huán)，后續(xù)執(zhí)行g(shù)et操作的時(shí)候握联，會(huì)觸發(fā)死循環(huán)桦沉，引起CPU的100%問題。
四.總結(jié)
通過解讀HashMap源碼并結(jié)合實(shí)例可以發(fā)現(xiàn)金闽，HashMap擴(kuò)容導(dǎo)致死循環(huán)的主要原因在于擴(kuò)容過程中使用頭插法將oldTable中的單鏈表中的節(jié)點(diǎn)插入到newTable的單鏈表中纯露，所以newTable中的單鏈表會(huì)倒置oldTable中的單鏈表。那么在多個(gè)線程同時(shí)擴(kuò)容的情況下就可能導(dǎo)致擴(kuò)容后的HashMap中存在一個(gè)有環(huán)的單鏈表代芜，從而導(dǎo)致后續(xù)執(zhí)行g(shù)et操作的時(shí)候埠褪，會(huì)觸發(fā)死循環(huán)，引起CPU的100%問題挤庇。所以一定要避免在并發(fā)環(huán)境下使用HashMap钞速。
