HashMap 死循環(huán)發(fā)生在 JDK 1.8 之前的版本中，它是指在并發(fā)環(huán)境下，因為多個線程同時進行 put 操作，導致鏈表形成環(huán)形數(shù)據(jù)結(jié)構(gòu)，一旦形成環(huán)形數(shù)據(jù)結(jié)構(gòu)，在 get(key) 的時候就會產(chǎn)生死循環(huán)。如下圖所示：

死循環(huán)原因

HashMap 導致死循環(huán)的原因是由以下條件共同導致的：

• HashMap 使用頭插法進行數(shù)據(jù)插入（JDK 1.8 之前）；
• 多線程同時添加；
• 觸發(fā)了 HashMap 擴容。

什么是頭插法

頭插法是指新來的值會取代原有的值，插入到鏈表的頭部，如下圖所示。

原鏈表如下圖所示：

此時使用頭插入插入一個元素 Z，如下圖所示：

頭插法會導致 HashMap 在進行擴容時，鏈表的順序發(fā)生反轉(zhuǎn)，如下圖所示：

因為在 HashMap 擴容時，會先從舊 HashMap 的頭節(jié)點讀取并插入到新 HashMap 節(jié)點中，舊節(jié)點的讀取順序是 A -> B -> C，于是插入到新 HashMap 中的順序就變成了 C -> B -> A，這樣就破壞了鏈表的順序，導致了鏈表反轉(zhuǎn)。

死循環(huán)產(chǎn)生過程

死循環(huán)執(zhí)行步驟1

死循環(huán)是因為并發(fā) HashMap 擴容導致的，并發(fā)擴容的第一步，線程 T1 和線程 T2 要對 HashMap 進行擴容操作，此時 T1 和 T2 指向的是鏈表的頭結(jié)點元素 A，而 T1 和 T2 的下一個節(jié)點，也就是 T1.next 和 T2.next 指向的是 B 節(jié)點，如下圖所示：

死循環(huán)執(zhí)行步驟2

死循環(huán)的第二步操作是，線程 T2 時間片用完進入休眠狀態(tài)，而線程 T1 開始執(zhí)行擴容操作，一直到線程 T1 擴容完成后，線程 T2 才被喚醒，擴容之后的場景如下圖所示：

從上圖可知線程 T1 執(zhí)行之后，因為是頭插法，所以 HashMap 的順序已經(jīng)發(fā)生了改變，但線程 T2 對于發(fā)生的一切是不可知的，所以它的指向元素依然沒變，如上圖展示的那樣，T2 指向的是 A 元素，T2.next 指向的節(jié)點是 B 元素。

死循環(huán)執(zhí)行步驟3

當線程 T1 執(zhí)行完，而線程 T2 恢復執(zhí)行時，死循環(huán)就建立了，如下圖所示：

因為 T1 執(zhí)行完擴容之后 B 節(jié)點的下一個節(jié)點是 A，而 T2 線程指向的首節(jié)點是 A，第二個節(jié)點是 B，這個順序剛好和 T1 擴完容完之后的節(jié)點順序是相反的。T1 執(zhí)行完之后的順序是 B 到 A，而 T2 的順序是 A 到 B，這樣 A 節(jié)點和 B 節(jié)點就形成死循環(huán)了，這就是 HashMap 死循環(huán)導致的原因。

解決方案

HashMap 死循環(huán)的常用解決方案有以下幾個：

1.升級到高版本 JDK（JDK 1.8 以上），高版本 JDK 使用的是尾插法插入新元素的，所以不會產(chǎn)生死循環(huán)的問題；

2.使用線程安全容器 ConcurrentHashMap 替代（推薦使用此方案）；

3.使用線程安全容器 Hashtable 替代（性能低，不建議使用）；

4.使用 synchronized 或 Lock 加鎖 HashMap 之后，再進行操作，相當于多線程排隊執(zhí)行（比較麻煩，也不建議使用）。

小結(jié)

HashMap 死循環(huán)發(fā)生在 JDK 1.7 版本中，形成死循環(huán)的原因是 HashMap 在 JDK 1.7 使用的是頭插法，頭插法 + 多線程并發(fā)操作 + HashMap 擴容，這幾個點加在一起就形成了 HashMap 的死循環(huán)，解決死循環(huán)可以采用線程安全容器 ConcurrentHashMap 替代。

到此這篇關(guān)于深入探究Java中的HashMap為什么會產(chǎn)生死循環(huán)的文章就介紹到這了,更多相關(guān)Java HashMap死循環(huán)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論