文檔處理控制欄： * [x] 選題收集：2017/12/28 * [ ] 初稿整理： * [ ] 補充校對： * [ ] 入庫存檔： --- # 圖解HashMap(二) ### 概述 上篇分析了HashMap的設計思想以及Java7和Java8源碼上的實現，當然還有一些"坑"還沒填完，比如大家都知道HashMap是線程不安全的數據結構，多線程情況下HashMap會引起死循環引用，它是怎么產生的？Java8引入了紅黑樹，那是怎么提高效率的？本篇先填第一個坑，還是以圖解的形式加深理解。 ### Java7分析 通過上一篇的整體學習，可以知道當存入的鍵值對超過HashMap的閥值時，HashMap會擴容，即創建一個新的數組，并將原數組里的鍵值對"轉移"到新的數組中。在“轉移”的時候，會根據新的數組長度和要轉移的鍵值對key值重新計算在新數組中的位置。重溫下Java7中負責"轉移"功能的代碼 ~~~ void transfer(Entry[] newTable, boolean rehash) { //獲取新數組的長度 int newCapacity = newTable.length; //遍歷舊數組中的鍵值對 for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } //計算在新表中的索引，并到新數組中 int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } } ~~~ 為了加深理解，畫個圖如下  這里假設擴容前后5號坑石頭、蓋倫、蒙多的hash值與新舊數組長度取模運算后還是5。上篇文章也總結了，Java7擴容轉移前后鏈表順序會倒置。當只有單線程操作hashMap時，一切都是那么美好，但是如果多線程同時操作一個hashMap，問題就來了，下面看下多線程操作一個hashMap在Java7源碼下是怎樣引起死循環引用。 前戲是這樣的：有兩個線程分別叫Thread1和Thread2，它們都有操作同一個hashMap的權利，假設hashMap中的鍵值對是12個，石頭和蓋倫擴容前后的hash值與新舊數組長度取模運算后還是5。擴容前的模擬堆內存情況如圖  Thread1得到執行權(Thread2被掛起)，Thread1往hashMap里put第13個鍵值對的時候判斷超過閥值，執行擴容操作，Thread1創建了一個新數組，還沒來得及轉移舊鍵值對的時候，系統時間片反手切到Thread2(Thread1被掛起)，整個過程用圖表示  可以看到Thread1只是創建了個新數組，還沒來得及轉移就被掛起了，新數組沒有內容，此時在Thread1的視角認的是e是石頭，next是蓋倫；此時的模擬內存圖情況  再看下Thread2的操作，同樣Thread2往hashMap里put第13個鍵值對的時候判斷超過閥值，執行擴容操作，Thread2先創建一個新數組，不同的是，Thread2運氣好，在時間片輪換前轉移工作也走完了。第一次遍歷  第二次遍歷  此時模擬的內存情況  可以看到此時對于蓋倫來說，他的next是石頭；對于石頭來說，它的next為null，隱患就此埋下。接下來時間片又切到Thread1(停了半天終于輪到我出場了)，先看下Thread1的處境  結合代碼分析如下 第一步：  第二步：  第三步：  第四步：  第五步：  第六步：  第七步：  第八步：  第九步：  第10步：  到這終于看到蓋倫和石頭"互指"，水乳交融。  那這會帶來什么后果呢？后續操作新數組的5號坑會進入死循環(注意，操作其他坑并不會有問題)，例如Java7 put操作  Java7 get操作會執行getEntry，同樣會引起死循環。  到此，Java7多線程操作HashMap可能形成死循環的原因剖析完成。 ### Java8分析 通過上一篇的學習可知，Java7轉移前后位置顛倒，而Java8轉移鍵值對前后位置不變。同樣的前戲，看下代碼  此時模擬堆內存情況  Thread1的情況  這時候Thread2獲得執行權，擴容并完成轉移工作，通過上篇的學習可知，Java8在轉移前會創建兩條鏈表，即擴容后位置不加原數組長度的lo鏈和要加原數組長度的hi鏈，這里假設石頭和蓋倫擴容前后都在5號坑，即這是一條lo鏈(其實就算不在同一個坑也不影響，原因就是Java8擴容前后鏈順序不變)。Thread2遍歷第一次 第二次  可以看到Thread2全程是沒有去修改石頭和蓋倫的引用關系，石頭.next是蓋倫，蓋倫.next是null。那么Thread1得到執行權后其實只是重復了Thread2的工作。 ### 總結 通過源碼分析，Java7在多線程操作hashmap時可能引起死循環，原因是擴容轉移后前后鏈表順序倒置，在轉移過程中修改了原來鏈表中節點的引用關系；Java8在同樣的前提下并不會引起死循環，原因是擴容轉移后前后鏈表順序不變，保持之前節點的引用關系。那是不是意味著Java8就可以把HashMap用在多線程中呢？個人感覺即使不會出現死循環，但是通過源碼看到put/get方法都沒有加同步鎖，多線程情況最容易出現的就是：無法保證上一秒put的值，下一秒get的時候還是原值，建議使用ConcurrentHashMap。 ### 感謝 [講HashMap多線程死循環最詳細的外國小哥](https://link.juejin.im/?target=http%3A%2F%2Fjavabypatel.blogspot.ca%2F2016%2F01%2Finfinite-loop-in-hashmap.html)