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