一、問題描述

經(jīng)常有些面試官會問，是否了解過 HashMap 在多線程環(huán)境下使用時(shí)可能會發(fā)生死循環(huán)，導(dǎo)致服務(wù)器 cpu 100% 的線上故障？

關(guān)于這個(gè)問題，很多年前，在淘寶內(nèi)網(wǎng)里就有很多的程序員發(fā)過這種帖子說一個(gè)CPU 被100%了，原因竟是多線程環(huán)境下使用 HashMap 造成的死循環(huán)，并且這個(gè)事發(fā)生了很多次。

雖然 Java 官方明確表示，在多線程環(huán)境下不推薦使用 HashMap，但是對于這種問題，小編其實(shí)也比較意外，如果不是深入的去了解 HashMap，都不知道有這樣的問題。

為什么會產(chǎn)生死循環(huán)呢？下面我們來還原一下問題的經(jīng)過。

二、問題重現(xiàn)

在之前的集合系列文章中，我們了解到 HashMap 是一個(gè)哈希數(shù)組 + 鏈表的數(shù)據(jù)結(jié)構(gòu)，在實(shí)際的程序開發(fā)中，我們經(jīng)常會使用到 HashMap，如果對 HashMap 不是很了解，大家可以看小編之前寫的《深入淺出分析 HashMap 》一文。

HashMap 是一個(gè)非線程安全的集合操作類，如果我們的程序操作是單線程的，那么一切都沒問題。當(dāng)我們的程序是多線程操作 HashMap 類時(shí)，那么問題就來了，我們一起來復(fù)現(xiàn)一下。

測試代碼，如下：

使用了4個(gè)線程來向 HashMap 中添加元素，可能一次運(yùn)行不一定有效果，可以反復(fù)運(yùn)行幾次！

控制臺輸出結(jié)果：

可以清晰的看到，在遍歷 map 的內(nèi)容時(shí)，已經(jīng)死循環(huán)了！

再來看看，活動監(jiān)視器，結(jié)果如下：

cpu 的使用率，直接接近 200%！

接下來我們?nèi)ゲ榭聪?java 中剛剛運(yùn)行的 HashThreadTest 類堆棧情況：

可以看到，HashMap 的擴(kuò)容操作導(dǎo)致了死循環(huán)！

通過測試，我們發(fā)現(xiàn) HashMap 在多線程環(huán)境下進(jìn)行操作，的確會產(chǎn)生死循環(huán)，并且會導(dǎo)致 CPU 100%！

這是為什么呢？我們一起來閱讀一下源碼！

三、源碼閱讀

注意注意，小編在進(jìn)行測試的時(shí)候，使用的是 JDK1.7 的版本！

如果你使用 JDK1.8 的版本，不好意思，不一定能復(fù)現(xiàn)這個(gè)問題！因?yàn)?JDK1.8 已經(jīng)修復(fù)了這個(gè)問題，但是依然不建議在多線程環(huán)境下使用 HashMap！

我們繼續(xù)來看看為什么使用 JDK1.7 會出現(xiàn)這個(gè)問題！

既然是 put 階段造成的數(shù)據(jù)問題，我們不妨一起來看看 HashMap 的 put 過程！

1.HashMap 添加過程

HashMap 的 put 源碼實(shí)現(xiàn)如下：

接著我們來看看addEntry()方法，將元素插入到數(shù)組中，并且檢查容量是否超標(biāo)，源碼實(shí)現(xiàn)如下：

上面例子中，我們初始化的時(shí)候給定的容量是 2，所以在添加元素時(shí)必定會擴(kuò)容！如果超出閥值，就進(jìn)行擴(kuò)容處理，創(chuàng)建一個(gè)更大容量的 hash 表，然后把從老的 Hash 表中遷移到新的 Hash 表中，源碼如下：

將舊 hash 表中的元素復(fù)制到新的 hash 表中，源碼如下：

整個(gè) put 過程，大致可以分如下幾個(gè)步驟：

• 第一步是通過 key 計(jì)算出來的 hash 和 equals 來判斷元素是否存在，如果存在，直接覆蓋；反之，插入；
• 第二步是將元素插入到 hash 表中，如果不同的元素都在一個(gè) hash 數(shù)組下標(biāo)下，就以鏈表的形式，采用頭插法存儲在 hash 節(jié)點(diǎn)下；
• 最后就是判斷當(dāng)前數(shù)組容量是否大于擴(kuò)容閥值，如果大于，就進(jìn)行擴(kuò)容處理，然后將舊元素復(fù)制到新的數(shù)組中；

好了，這個(gè)過程基本上沒啥問題。

我們再來演示一下擴(kuò)容中重新計(jì)算元素 hash 的過程！

2.單線程下擴(kuò)容元素 hash 過程

假設(shè)在單線程環(huán)境下，我們初始化的時(shí)候，給定的數(shù)組容量是2，分別添加3個(gè)元素，內(nèi)容如下：

• key=3，value=A;
• key=4，value=B;
• key=5，value=C;

源碼如下：

添加完成之后，數(shù)組就會進(jìn)行擴(kuò)容處理，擴(kuò)容后 hash 的容量為原來的2倍，擴(kuò)容操作流程如下：

在單線程環(huán)境下，一切看起來都很正常，擴(kuò)容過程也相當(dāng)順利。接下來我們看下并發(fā)情況下的擴(kuò)容。

3.多線程擴(kuò)容元素 hash 過程

假設(shè)我們有兩個(gè)線程，來分別添加3個(gè)元素。

線程二執(zhí)行完添加任務(wù)之后，在準(zhǔn)備將舊元素遷移到新元素的時(shí)候，也就是準(zhǔn)備 rehash 時(shí)，突然被 CPU 掛起，此時(shí)阻塞在如下圖中的第57行，不再往下執(zhí)行！而線程一繼續(xù)執(zhí)行直到擴(kuò)容完成。

2個(gè)線程此時(shí)的執(zhí)行結(jié)果，內(nèi)容如下：

接著線程二被喚醒，繼續(xù)回到第57行執(zhí)行。

此時(shí)注意了，我們來詳細(xì)的分析一下這個(gè)過程！

第一次循環(huán)過程如下：

• 第1步：此時(shí) e 等于{key:3,value:A}，next=e.next={key:5,value:C}；
• 第2步：通過 key 重新 hash 計(jì)算得到下標(biāo) i = 3；
• 第3步：newTable為局部變量，內(nèi)容都為null，所以 e.next = newTable[i]=null;
• 第4步：newTable[i]=e={key:3,value:A};
• 第5步：e=next={key:5,value:C};

循環(huán)結(jié)果如下，e={key:5,value:C}，滿足while()循環(huán)條件，接著繼續(xù)！

第二次循環(huán)過程如下：

• 第1步：此時(shí) e 等于{key:5,value:C}，取最新的鏈表結(jié)構(gòu)，next=e.next={key:3,value:A}；
• 第2步：通過 key 重新 hash 計(jì)算得到下標(biāo) i = 3；
• 第3步：在第一次循環(huán)中，newTable[i]已經(jīng)插入值，所以 e.next = newTable[i]={key:3,value:A};
• 第4步：newTable[i]=e={key:5,value:C};
• 第5步：e=next={key:3,value:A};

循環(huán)結(jié)果如下，e={key:3,value:A}，滿足while()循環(huán)條件，接著繼續(xù)！

第三次循環(huán)過程如下：

• 第1步：此時(shí) e 等于{key:3,value:A}，取最新的鏈表結(jié)構(gòu)，next=e.next=null；
• 第2步：通過 key 重新 hash 計(jì)算得到下標(biāo) i = 3；
• 第3步：在第二次循環(huán)中，newTable[i]已經(jīng)插入值，所以 e.next = newTable[i]={key:5,value:C};
• 第4步：newTable[i]=e={key:3,value:A};
• 第5步：e=next=null;

循環(huán)結(jié)果如下，e=null，while()程序不在循環(huán)！

綜合線程1、線程2執(zhí)行結(jié)果，最終 hashMap 的存儲結(jié)果，如下圖：

可以很清晰的看到，鏈表發(fā)生死循環(huán)了！

于是，當(dāng)我們在遍歷 hashMap 鏈表內(nèi)容的時(shí)候，就會出現(xiàn)上文中問題復(fù)現(xiàn)的場景，死循環(huán)式的輸出相同的內(nèi)容，CPU 直接飆到200%了！

對于這種問題，當(dāng)初有人上報(bào)到 SUN 公司，但是 SUN 不認(rèn)為這是一個(gè)問題，因?yàn)?HashMap 本來就不支持并發(fā)操作！

所以，不建議在多線程環(huán)境下使用 HashMap，那如果要在多線程環(huán)境下使用 map 操作類，該怎么辦呢？

四、解決辦法

辦法肯定是有的，如果大家想在多線程場景下使用 HashMap，有兩種解決辦法：

• 第一種，推薦使用并發(fā)包中的 ConcurrentHashMap 類，一種使用分段鎖的 hashMap 類，在之后的文章中，咱們也會介紹到它。
• 另一種，是使用Collections.synchronizedMap(Mao<K,V> map)工具方法，將 HashMap 變成一個(gè)線程安全的 map，其實(shí)就是對 map 中的方法進(jìn)行加鎖處理，保證多線程下操作安全！