代碼回顧
師傅，我常常聽別人說，不要在併發情況下使用HashMap，可能會出現死循環，這個死循環是怎麼形成的呢？
一塵
慧能
這個聽為師慢慢道來
我們都知道，HashMap的底層是由數組加鏈表來實現的
當往HashMap中put一個鍵值對時，如果HashMap中的鍵值對數量 size 大於或等於閾值(threshold) 並且null != table[bucketIndex] 時會進行擴容
bucketIndex為該鍵值對最後被散列到hash表table的位置
比如 table的初始容量為4,加載因子為0.75,此時閾值為3，table已有三個元素，現在put一個元素<1,”A”>,<1,”A”>被散列到table[1]處，而table[1] != null,此時滿足擴容條件
閾值 = 容量 * 加載因子
threshold = capacity * loadFactor
擴容時先生成一個是table大小2倍的newTable，然後把table中的元素遷移到newTable中，遷移的工作就由 transfer方法來完成，這個方法就是引起死循環的原因所在
環的形成
現在我們來模擬一下環是如何形成的，設HashMap的初始容量為4，先往HashMap中依次put三個元素<5,”B”>、<9,”C”>、<1,”A”>，它們都被散列到table[1]處，形成了鏈
假設此時有兩個線程併發對該HashMap進行put，線程1 put <13,”D”>時，這個鍵值對被散列到table[1]處，滿足擴容條件，進行擴容（生成newTable並進行遷移）
此時，線程1用 transfer 方法將 table中的元素遷移到 newTable 中，假設線程1執行完 transfer 方法中的 Entry
此時，線程1內的 e 指向 <1,“A”>，next指向<9,”C”>
然後線程2 put <16,”E”>,同樣這個鍵值對被散列到table[1]處，滿足擴容條件，進行擴容
生成完newTable後用transfer方法進行遷移，執行完Entry
線程2 然後執行循環體下面的語句
線程2執行完之後為下圖
然後線程2按照同樣的邏輯進行第二次循環（while循環），下面是第二遍循環後的結果
下面是第三遍循環後的結果
此時，線程2時間片用完，線程1得到時間片，開始執行
注意，此時線程1的e指向<1,A>,next指向<9,C>,在線程2操作鏈表的時候，線程1 中的e,next指向的元素沒變(一直是紅色的e和next)
線程一和線程二整體圖為：
然後線程1開始執行循環內剩下的代碼
執行完後為下圖
線程1繼續執行第二遍循環
執行完為下圖
線程1繼續第三遍循環（注意：此次循環會形成環）
先執行 Entry
然後執行 <1,A>.next = newTable[1]
此時環已經形成
然後執行剩餘的兩行代碼
執行完，e 為 null,退出循環
死循環的發生
當形成環後,當給HashMap中put元素的時候，這個元素恰巧落在了table[1]（不管有沒有更新table），而這個元素的Key不在table[1]這條鏈上，此時會發生死循環
或者在get元素的時候，該元素恰巧落在table[1]上，並且該元素的Key不在該鏈上，會發生死循環
原來死循環是這樣形成的
一塵
慧能
對，核心就是線程2修改了原來的鏈表結構，而線程1卻以原來的邏輯執行遷移
那併發下我還想使用散列表這種數據結構怎麼辦呢
一塵
慧能
用ConcurrentHashMap
閱讀更多 Java識堂 的文章
