JDK1.7HashMap多線程擴(kuò)容為什么會(huì)死循環(huán)示例詳解
一、前言
在 Java 中，HashMap 是非常常用的數(shù)據(jù)結(jié)構(gòu)。它底層主要由：
數(shù)組 + 鏈表
組成。
在 JDK 1.8 之后，HashMap 又加入了紅黑樹結(jié)構(gòu)：
數(shù)組 + 鏈表 + 紅黑樹
但是在 JDK 1.7 中，HashMap 有一個(gè)經(jīng)典問(wèn)題：多線程環(huán)境下同時(shí)擴(kuò)容，可能導(dǎo)致鏈表形成環(huán)，從而出現(xiàn)死循環(huán)。
這個(gè)問(wèn)題的核心原因是：
JDK 1.7 HashMap 擴(kuò)容時(shí)使用頭插法； 頭插法會(huì)修改節(jié)點(diǎn)的 next 指針； 多個(gè)線程同時(shí)擴(kuò)容時(shí)，會(huì)操作同一批節(jié)點(diǎn)對(duì)象； 最終可能導(dǎo)致 A.next = B，B.next = A，形成環(huán)。
二、HashMap 擴(kuò)容是不是在原數(shù)組上改？
不是。
HashMap 擴(kuò)容不是把原來(lái)的數(shù)組直接變大。因?yàn)?Java 數(shù)組長(zhǎng)度是固定的，一旦創(chuàng)建之后，長(zhǎng)度不能改變。
比如原來(lái)是：
Entry<K,V>[] table = new Entry[16];
這個(gè)數(shù)組長(zhǎng)度就是 16，不能原地變成 32。
所以 HashMap 擴(kuò)容時(shí)會(huì)：
1. 創(chuàng)建一個(gè)更大的新數(shù)組 2. 遍歷舊數(shù)組中的節(jié)點(diǎn) 3. 把舊節(jié)點(diǎn)重新掛到新數(shù)組中 4. 最后讓 table 指向新數(shù)組
也就是：
oldTable 長(zhǎng)度 16 擴(kuò)容后創(chuàng)建 newTable 長(zhǎng)度 32 最后 table = newTable
但是這里有一個(gè)非常重要的點(diǎn)：
數(shù)組是新的，但是節(jié)點(diǎn)對(duì)象不是新的。
也就是說(shuō)，擴(kuò)容不是重新創(chuàng)建節(jié)點(diǎn)副本，而是把舊數(shù)組里的節(jié)點(diǎn)對(duì)象拿出來(lái)，重新掛到新數(shù)組里。
例如舊數(shù)組中有：
oldTable[3] -> 節(jié)點(diǎn)1 -> 節(jié)點(diǎn)2 -> null
擴(kuò)容后不是變成：
newTable[3] -> 新節(jié)點(diǎn)1 -> 新節(jié)點(diǎn)2 -> null
而是：
newTable[3] -> 原來(lái)的節(jié)點(diǎn)1 / 原來(lái)的節(jié)點(diǎn)2
節(jié)點(diǎn)對(duì)象是復(fù)用的。
三、為什么放到新數(shù)組里還要修改 next？
因?yàn)閿?shù)組里面每個(gè)位置只能存一個(gè)頭節(jié)點(diǎn)。
如果多個(gè)元素落到同一個(gè)桶里，就必須靠鏈表連接起來(lái)。
比如：
newTable[5] -> 節(jié)點(diǎn)1 -> 節(jié)點(diǎn)2 -> null
這里真正維護(hù)鏈表關(guān)系的是：
節(jié)點(diǎn)1.next = 節(jié)點(diǎn)2 節(jié)點(diǎn)2.next = null
所以擴(kuò)容遷移時(shí)，一定會(huì)重新整理節(jié)點(diǎn)之間的 next 指針。
這也是問(wèn)題產(chǎn)生的根源。
四、JDK 1.7 的頭插法是什么？
JDK 1.7 HashMap 擴(kuò)容遷移時(shí)使用的是頭插法。
核心代碼可以簡(jiǎn)化理解為：
Entry<K,V> next = e.next; // 先保存舊鏈表中的下一個(gè)節(jié)點(diǎn) int i = indexFor(e.hash, newCapacity); // 計(jì)算新數(shù)組下標(biāo) e.next = newTable[i]; // 當(dāng)前節(jié)點(diǎn)指向新桶原來(lái)的頭節(jié)點(diǎn) newTable[i] = e; // 當(dāng)前節(jié)點(diǎn)成為新桶的新頭節(jié)點(diǎn) e = next; // 繼續(xù)處理下一個(gè)舊節(jié)點(diǎn)
最重要的是這句：
e.next = newTable[i];
這句話會(huì)修改當(dāng)前節(jié)點(diǎn)的 next 指針。
五、單線程下頭插法為什么沒問(wèn)題？
假設(shè)舊鏈表是：
節(jié)點(diǎn)1 -> 節(jié)點(diǎn)2 -> null
擴(kuò)容時(shí)使用頭插法。
一開始新數(shù)組桶為空：
newTable[i] = null
先遷移節(jié)點(diǎn)1：
節(jié)點(diǎn)1.next = newTable[i]; newTable[i] = 節(jié)點(diǎn)1;
因?yàn)?nbsp;newTable[i] 是 null，所以：
節(jié)點(diǎn)1.next = null
新鏈表變成：
newTable[i] -> 節(jié)點(diǎn)1 -> null
然后遷移節(jié)點(diǎn)2：
節(jié)點(diǎn)2.next = newTable[i]; newTable[i] = 節(jié)點(diǎn)2;
此時(shí) newTable[i] 是節(jié)點(diǎn)1，所以等價(jià)于：
節(jié)點(diǎn)2.next = 節(jié)點(diǎn)1
最終新鏈表變成：
newTable[i] -> 節(jié)點(diǎn)2 -> 節(jié)點(diǎn)1 -> null
可以看到，原來(lái)的鏈表：
節(jié)點(diǎn)1 -> 節(jié)點(diǎn)2 -> null
被反轉(zhuǎn)成了：
節(jié)點(diǎn)2 -> 節(jié)點(diǎn)1 -> null
單線程下這沒問(wèn)題，只是順序反了，但是鏈表最后仍然指向 null。
六、多線程擴(kuò)容為什么會(huì)出問(wèn)題？
問(wèn)題出在：兩個(gè)線程同時(shí)擴(kuò)容同一個(gè) HashMap。
假設(shè)舊數(shù)組某個(gè)桶中有兩個(gè)節(jié)點(diǎn)：
oldTable[3] -> 節(jié)點(diǎn)1 -> 節(jié)點(diǎn)2 -> null
現(xiàn)在兩個(gè)線程同時(shí)觸發(fā)擴(kuò)容：
線程A：創(chuàng)建 newTableA 線程B：創(chuàng)建 newTableB
注意：
newTableA 和 newTableB 是兩個(gè)不同的新數(shù)組。
但是：
節(jié)點(diǎn)1 和 節(jié)點(diǎn)2 是同一批舊節(jié)點(diǎn)對(duì)象。
也就是說(shuō)，兩個(gè)線程操作的是同一個(gè)節(jié)點(diǎn)1和同一個(gè)節(jié)點(diǎn)2。
七、詳細(xì)模擬多線程擴(kuò)容過(guò)程
第一步：線程A開始擴(kuò)容
線程A準(zhǔn)備遷移節(jié)點(diǎn)1。
它先執(zhí)行：
e = 節(jié)點(diǎn)1; next = e.next;
此時(shí)：
e = 節(jié)點(diǎn)1 next = 節(jié)點(diǎn)2
也就是說(shuō)，線程A已經(jīng)記住了節(jié)點(diǎn)1后面是節(jié)點(diǎn)2。
但是這時(shí)候，線程A突然被 CPU 暫停了。
當(dāng)前舊鏈表還是：
節(jié)點(diǎn)1 -> 節(jié)點(diǎn)2 -> null
第二步：線程B開始并完成擴(kuò)容
線程B也開始處理同一條舊鏈表：
節(jié)點(diǎn)1 -> 節(jié)點(diǎn)2 -> null
線程B先遷移節(jié)點(diǎn)1
線程B的新數(shù)組桶為空：
newTableB[i] = null
執(zhí)行頭插法：
節(jié)點(diǎn)1.next = newTableB[i]; newTableB[i] = 節(jié)點(diǎn)1;
因?yàn)?nbsp;newTableB[i] 是 null，所以：
節(jié)點(diǎn)1.next = null
線程B的新鏈表變成：
newTableB[i] -> 節(jié)點(diǎn)1 -> null
線程B再遷移節(jié)點(diǎn)2
此時(shí)：
newTableB[i] = 節(jié)點(diǎn)1
線程B遷移節(jié)點(diǎn)2：
節(jié)點(diǎn)2.next = newTableB[i]; newTableB[i] = 節(jié)點(diǎn)2;
因?yàn)?nbsp;newTableB[i] 是節(jié)點(diǎn)1，所以等價(jià)于：
節(jié)點(diǎn)2.next = 節(jié)點(diǎn)1
于是線程B的新鏈表變成：
newTableB[i] -> 節(jié)點(diǎn)2 -> 節(jié)點(diǎn)1 -> null
此時(shí)真實(shí)節(jié)點(diǎn)關(guān)系已經(jīng)變成：
節(jié)點(diǎn)2.next = 節(jié)點(diǎn)1 節(jié)點(diǎn)1.next = null
也就是：
節(jié)點(diǎn)2 -> 節(jié)點(diǎn)1 -> null
注意，這里修改的是節(jié)點(diǎn)對(duì)象自己的 next，不是只修改線程B的新數(shù)組。
八、線程A恢復(fù)執(zhí)行，問(wèn)題出現(xiàn)
線程A之前暫停時(shí)保存的是：
e = 節(jié)點(diǎn)1 next = 節(jié)點(diǎn)2
現(xiàn)在線程A恢復(fù)執(zhí)行。
它繼續(xù)遷移節(jié)點(diǎn)1。
線程A自己的新桶為空：
newTableA[i] = null
執(zhí)行頭插法：
節(jié)點(diǎn)1.next = newTableA[i]; newTableA[i] = 節(jié)點(diǎn)1;
因?yàn)?nbsp;newTableA[i] 是 null，所以：
節(jié)點(diǎn)1.next = null
線程A的新鏈表現(xiàn)在是：
newTableA[i] -> 節(jié)點(diǎn)1 -> null
然后線程A執(zhí)行：
e = next;
因?yàn)榫€程A之前保存的 next 是節(jié)點(diǎn)2，所以現(xiàn)在：
e = 節(jié)點(diǎn)2
九、線程A處理節(jié)點(diǎn)2
線程A處理節(jié)點(diǎn)2時(shí)，先取：
next = 節(jié)點(diǎn)2.next;
但是節(jié)點(diǎn)2的 next 已經(jīng)被線程B改過(guò)了。
線程B之前執(zhí)行過(guò)：
節(jié)點(diǎn)2.next = 節(jié)點(diǎn)1
所以線程A現(xiàn)在拿到的是：
next = 節(jié)點(diǎn)1
然后線程A把節(jié)點(diǎn)2頭插到自己的新數(shù)組中：
節(jié)點(diǎn)2.next = newTableA[i]; newTableA[i] = 節(jié)點(diǎn)2;
此時(shí)：
newTableA[i] = 節(jié)點(diǎn)1
所以等價(jià)于：
節(jié)點(diǎn)2.next = 節(jié)點(diǎn)1
線程A的新鏈表變成：
newTableA[i] -> 節(jié)點(diǎn)2 -> 節(jié)點(diǎn)1 -> null
然后線程A執(zhí)行：
e = next;
而剛才：
next = 節(jié)點(diǎn)1
所以線程A又回到了節(jié)點(diǎn)1。
十、線程A再次處理節(jié)點(diǎn)1，形成環(huán)
此時(shí)線程A的新桶頭節(jié)點(diǎn)是節(jié)點(diǎn)2：
newTableA[i] = 節(jié)點(diǎn)2
線程A再次處理節(jié)點(diǎn)1，執(zhí)行頭插法：
節(jié)點(diǎn)1.next = newTableA[i]; newTableA[i] = 節(jié)點(diǎn)1;
因?yàn)?nbsp;newTableA[i] 是節(jié)點(diǎn)2，所以等價(jià)于：
節(jié)點(diǎn)1.next = 節(jié)點(diǎn)2
但是前面已經(jīng)有：
節(jié)點(diǎn)2.next = 節(jié)點(diǎn)1
于是鏈表變成：
節(jié)點(diǎn)1 -> 節(jié)點(diǎn)2 -> 節(jié)點(diǎn)1 -> 節(jié)點(diǎn)2 -> ...
環(huán)形鏈表形成了。
十一、為什么形成環(huán)后會(huì)死循環(huán)？
HashMap 查詢?cè)貢r(shí)，會(huì)沿著鏈表一直往后找。
類似邏輯：
while (e != null) {
if (e.key.equals(key)) {
return e.value;
}
e = e.next;
}
正常鏈表最后會(huì)走到：
null
比如：
節(jié)點(diǎn)1 -> 節(jié)點(diǎn)2 -> null
但是如果鏈表形成了環(huán)：
節(jié)點(diǎn)1 -> 節(jié)點(diǎn)2 -> 節(jié)點(diǎn)1 -> 節(jié)點(diǎn)2 -> ...
那么 e 永遠(yuǎn)不會(huì)變成 null。
程序就會(huì)一直循環(huán)，CPU 占用可能飆高，看起來(lái)像程序卡死。
這就是 JDK 1.7 HashMap 多線程擴(kuò)容死循環(huán)問(wèn)題。
十二、關(guān)鍵問(wèn)題：為什么各自擴(kuò)容還會(huì)互相影響？
因?yàn)椋?/p>
線程A有自己的 newTableA 線程B有自己的 newTableB
但是：
newTableA 和 newTableB 里面放的是同一批舊節(jié)點(diǎn)對(duì)象的地址
不是復(fù)制節(jié)點(diǎn)。
所以線程A和線程B雖然數(shù)組不同，但是它們修改的是同一個(gè)節(jié)點(diǎn)對(duì)象里的 next 字段。
可以把節(jié)點(diǎn)理解成這個(gè)類：
class Entry<K,V> {
K key;
V value;
Entry<K,V> next;
}數(shù)組只是保存節(jié)點(diǎn)地址：
Entry<K,V>[] table;
擴(kuò)容時(shí)這句代碼：
e.next = newTable[i];
修改的是節(jié)點(diǎn)對(duì)象內(nèi)部的 next。
所以即使沒有修改舊數(shù)組 oldTable[i]，也會(huì)改變舊節(jié)點(diǎn)之間的鏈表關(guān)系。
十三、JDK 1.8 是怎么改進(jìn)的？
JDK 1.8 對(duì) HashMap 做了幾個(gè)重要優(yōu)化。
1. 擴(kuò)容時(shí)不再使用 JDK 1.7 那種頭插法
JDK 1.8 擴(kuò)容時(shí)會(huì)把原桶中的鏈表拆成兩條鏈表：
lo 鏈表：留在原位置 hi 鏈表：移動(dòng)到 原位置 + oldCap
判斷方式是：
if ((e.hash & oldCap) == 0) {
// 留在原位置
} else {
// 移動(dòng)到 原位置 + oldCap
}
2. JDK 1.8 使用尾插法，保持鏈表順序
JDK 1.7 頭插法會(huì)反轉(zhuǎn)鏈表：
節(jié)點(diǎn)1 -> 節(jié)點(diǎn)2
遷移后可能變成：
節(jié)點(diǎn)2 -> 節(jié)點(diǎn)1
而 JDK 1.8 使用尾插法，盡量保持原來(lái)的順序。
這樣就避免了 JDK 1.7 頭插法反轉(zhuǎn)鏈表時(shí)帶來(lái)的典型成環(huán)問(wèn)題。
3. JDK 1.8 加入紅黑樹
JDK 1.8 中，如果一個(gè)桶里的鏈表太長(zhǎng)，并且數(shù)組長(zhǎng)度達(dá)到一定條件，鏈表會(huì)轉(zhuǎn)成紅黑樹。
這樣可以避免鏈表過(guò)長(zhǎng)導(dǎo)致查詢效率下降。
JDK 1.7：
數(shù)組 + 鏈表
JDK 1.8：
數(shù)組 + 鏈表 + 紅黑樹
十四、但是 JDK 1.8 的 HashMap 線程安全嗎？
不安全。
雖然 JDK 1.8 優(yōu)化了擴(kuò)容邏輯，避免了 JDK 1.7 中典型的頭插法死循環(huán)問(wèn)題，但是 HashMap 本身依然不是線程安全的。
多線程環(huán)境下，如果多個(gè)線程同時(shí)讀寫 HashMap，仍然可能出現(xiàn)：
數(shù)據(jù)覆蓋 數(shù)據(jù)丟失 size 不準(zhǔn)確 結(jié)構(gòu)異常
所以多線程環(huán)境下不要使用普通 HashMap。
應(yīng)該使用：
ConcurrentHashMap
十五、面試總結(jié)版
如果面試官問(wèn)：
JDK 1.7 HashMap 為什么多線程擴(kuò)容會(huì)死循環(huán)？
可以這樣回答：
JDK 1.7 的 HashMap 在擴(kuò)容時(shí)會(huì)創(chuàng)建一個(gè)新的數(shù)組，然后把舊數(shù)組中的節(jié)點(diǎn)遷移到新數(shù)組中。數(shù)組是新的，但節(jié)點(diǎn)對(duì)象是舊的，遷移時(shí)會(huì)復(fù)用這些節(jié)點(diǎn)，并修改節(jié)點(diǎn)的 next 指針。
JDK 1.7 擴(kuò)容遷移鏈表時(shí)使用頭插法。頭插法會(huì)把鏈表順序反轉(zhuǎn)。單線程下沒有問(wèn)題，但是在多線程同時(shí)擴(kuò)容時(shí)，多個(gè)線程會(huì)操作同一批節(jié)點(diǎn)對(duì)象。如果線程A暫停，線程B完成擴(kuò)容并把鏈表反轉(zhuǎn)，線程A恢復(fù)后繼續(xù)使用之前保存的節(jié)點(diǎn)引用，就可能把節(jié)點(diǎn)之間的 next 改成互相指向，比如 節(jié)點(diǎn)1.next = 節(jié)點(diǎn)2，節(jié)點(diǎn)2.next = 節(jié)點(diǎn)1。這樣鏈表就形成了環(huán)。
當(dāng)后續(xù)執(zhí)行 get() 操作時(shí)，HashMap 會(huì)沿著鏈表不斷查找，如果鏈表形成環(huán)，就永遠(yuǎn)走不到 null，最終導(dǎo)致死循環(huán)，CPU 飆高。
JDK 1.8 之后，HashMap 擴(kuò)容改用了尾插法和高低位鏈表拆分，避免了 JDK 1.7 頭插法導(dǎo)致的典型成環(huán)問(wèn)題。但 HashMap 仍然不是線程安全的，多線程環(huán)境下應(yīng)該使用 ConcurrentHashMap。
十六、一句話總結(jié)
JDK 1.7 HashMap 多線程擴(kuò)容死循環(huán)的本質(zhì)是：新數(shù)組是各線程自己的，但節(jié)點(diǎn)對(duì)象是共享的；頭插法遷移會(huì)修改節(jié)點(diǎn)的 next 指針，多個(gè)線程交叉修改后可能形成環(huán)形鏈表，導(dǎo)致查詢時(shí)永遠(yuǎn)走不到 null。
到此這篇關(guān)于JDK1.7HashMap多線程擴(kuò)容為什么會(huì)死循環(huán)的文章就介紹到這了,更多相關(guān)JDK HashMap多線程擴(kuò)容死循環(huán)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了java單鏈表逆序用法代碼示例，小編覺得還是挺不錯(cuò)的，具有一定借鑒價(jià)值，需要的朋友可以參考下2018-01-01
這篇文章主要介紹了SpringBoot日志框架如何使用，幫助大家更好的理解和使用springboot日志框架，感興趣的朋友可以了解下2021-01-01
SpringBoot中優(yōu)化if-else語(yǔ)句的七種方法
if-else語(yǔ)句是控制流程的基本工具,但過(guò)度使用會(huì)使代碼變得復(fù)雜且難以維護(hù),在SpringBoot , SpringCloud項(xiàng)目中,優(yōu)化if-else結(jié)構(gòu)變得尤為重要,本文將深入探討七種策略,旨在減少SpringBoot , SpringCloud項(xiàng)目中 if-else的使用,需要的朋友可以參考下2024-07-07
MyBatis的9種動(dòng)態(tài)標(biāo)簽詳解
大家好，本篇文章主要講的是MyBatis的9種動(dòng)態(tài)標(biāo)簽詳解，感興趣的同學(xué)趕快來(lái)看一看吧，感興趣的同學(xué)趕快來(lái)看一看吧2021-12-12
這篇文章主要介紹了scala中常用特殊符號(hào)詳解，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-06-06
在Java中使用Redis實(shí)現(xiàn)緩存優(yōu)化的操作步驟
在現(xiàn)代高并發(fā)的應(yīng)用中,數(shù)據(jù)庫(kù)訪問(wèn)的性能往往成為瓶頸,為了提高性能,我們通常會(huì)使用緩存機(jī)制,Redis 是一種開源的內(nèi)存數(shù)據(jù)存儲(chǔ)系統(tǒng),廣泛應(yīng)用于緩存系統(tǒng)的構(gòu)建中,本文將深入探討如何在Java中使用Redis實(shí)現(xiàn)緩存優(yōu)化,需要的朋友可以參考下2025-07-07
Eclipse中Properties和yml配置文件注釋亂碼的解決
這篇文章主要介紹了Eclipse中Properties和yml配置文件注釋亂碼的解決，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-10-10
解決mybatis-plus自動(dòng)配置的mapper.xml與java接口映射問(wèn)題
這篇文章主要介紹了解決mybatis-plus自動(dòng)配置的mapper.xml與java接口映射問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-08-08
SpringBoot基于Sentinel在服務(wù)上實(shí)現(xiàn)接口限流
這篇文章主要介紹了SpringBoot基于Sentinel在服務(wù)上實(shí)現(xiàn)接口限流,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-10-10
SpringSecurity之SecurityContextHolder使用解讀
這篇文章主要介紹了SpringSecurity之SecurityContextHolder使用解讀，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-03-03