探究HashMap線性不安全（二）——鏈表成環的詳細過程

內容

​　　網上很多資料都詳細地講解了HashMap底層的實現，但是講到HashMap的併發操作不是線性安全時，往往一筆帶過：在多個線程併發擴容時，會在執行transfer()方法轉移鍵值對時，造成鏈表成環，導致程式在執行get操作時形成死迴圈。

​　　對於沒有研究過該過程的童鞋，很難費解這句話的含義。下麵筆者分四個小節帶著大家共同研究一下JDK1.7和JDK1.8版本下HashMap的線性不安全是怎麼造成的，詳細探究鏈表成環的形成過程。如果對於HashMap底層的put、get操作不清楚，建議先學習參考1中的內容。

適合人群

​　　Java進階

說明

　　轉載請說明出處：探究HashMap線性不安全（二）——鏈表成環的詳細過程

 參考

​ 1、https://www.toutiao.com/i6544826418210013700/ HashMap底層數據結構原理

​ 2、https://www.toutiao.com/i6545790064104833539/ 為什麼HashMap非線程安全

​ 3、https://blog.csdn.net/qq_32182461/article/details/81152025 hashmap併發情況下的成環原因（筆者認為該文是一種誤解）

正文

​　　本節將詳細探究HashMap擴容的鍵值對遷移過程，多線程併發執行transfer()方法是如何產生環形鏈表的。transfer()方法的代碼為：

 1 void transfer(Entry[] newTable, boolean rehash) {
 2     int newCapacity = newTable.length;
 3     //遍歷table數組中鍵值對鏈
 4     for (Entry<K,V> e : table) {
 5         //遍歷鍵值對e鏈上的所有鍵值對，當e指向null時結束
 6         while(null != e) {
 7             Entry<K,V> next = e.next;//斷點一
 8             //通常rehash為false，不會重新計算鍵值對key的hash值
 9             if (rehash) {
10                 e.hash = null == e.key ? 0 : hash(e.key);
11             }
12             //根據擴容後的table數組長度計算鍵值對的index
13             int i = indexFor(e.hash, newCapacity);
14             //頭插法，將後遍歷的鍵值對存到鏈條的頭部
15             e.next = newTable[i];
16             newTable[i] = e;
17             //鏈條中的下一個鍵值對繼續執行while迴圈。
18             e = next;
19         }
20     }
21 }

 情景：

​　　兩個線程A、B同時向HashMap中寫入鍵值對，某個時刻HashMap已經到了Resize的臨界點。由於多線程的執行沒有必然的先後順序，存線上程A未完成擴容，而線程B又進行擴容的情況，即兩個線程都可能會執行擴容方法transfer()。此時兩個線程都會遍歷table數組中的鍵值對鏈，對於每個鏈執行while迴圈，遷移所有鍵值對。

　　假定HashMap中table數組的初始長度為4

​　　假如線程A和線程B都遍歷到index為2的鍵值鏈（即Entry3->Entry2->null這條鏈）。由於CPU時間片分配的不確定性，線程B執行到代碼中斷點一的位置後暫停，此時線程B中的e指向Entry3，e.next指向Entry2。而線程A繼續執行，完成了擴容操作。HashMap的數據結構為下圖所示。

​　　重點！！：e和e.next為線程B中的引用變數，分別指向hashMap中的Entry3和Entry2。由於Entry3和Entry2是線程共用的，因此受線程A執行的影響，Entry3將指向null，Entry2指向Entry3。

​　　此時線程B中局部變數newTable的結構：

執行第一次迴圈：e為Entry3，e.next為Entry2（線程B暫停前e和e.next引用變數的指向）

 1 //遍歷e所在鏈上的所有鍵值對
 2 while(null != e) {
 3     //斷點1，此時線程B中的e為Entry3，e.next為Entry2
 4     Entry<K,V> next = e.next;
 5     //通常rehash為false，不會重新計算鍵值對key的hash值
 6     if (rehash) {
 7         e.hash = null == e.key ? 0 : hash(e.key);
 8     }
 9     //根據擴容後的table數組長度計算鍵值對的index
10     int i = indexFor(e.hash, newCapacity);
11     //頭插法
12     e.next = newTable[i];//將Entry3的next設置為null
13     newTable[i] = e;//將Entry3放置到線程B newTable下標為3的位置
14     //繼續處理Entry2
15     e = next;
16 }

 執行完第一次迴圈後線程B中局部變數newTable的結構：

執行完第一次迴圈後hashMap對象的結構：

執行第二次迴圈：e為Entry2，e.next為Entry3（受線程A影響，e和e.next引用變數的指向發生改變）

 1 //遍歷鍵值對e鏈上的所有鍵值對
 2 while(null != e) {
 3     //斷點1，e為Entry2，e.next為Entry3
 4     Entry<K,V> next = e.next;
 5     //通常rehash為false，不會重新計算鍵值對key的hash值
 6     if (rehash) {
 7         e.hash = null == e.key ? 0 : hash(e.key);
 8     }
 9     //由線程A的執行結果可知，Entry2的index也為3
10     int i = indexFor(e.hash, newCapacity);
11     //頭插法，
12     e.next = newTable[i];//將Entry2的next設置為Entry3
13     newTable[i] = e; //newTable[3]設置為Entry2
14     //另e等於Entry3，繼續執行while迴圈。
15     e = next;
16 }

執行完第二次迴圈後線程B中局部變數newTable的結構：

執行完第二次迴圈後hashMap對象的結構：

執行第三次迴圈：e變為Entry3，e.next為null

 1 //遍歷鍵值對e鏈上的所有鍵值對
 2 while(null != e) {
 3     //斷點1，此時線程B中的e變為Entry3，e.next為null
 4     Entry<K,V> next = e.next;
 5     //通常rehash為false，不會重新計算鍵值對key的hash值
 6     if (rehash) {
 7         e.hash = null == e.key ? 0 : hash(e.key);
 8     }
 9     //由線程A的執行結果可知，Entry3的index為3
10     int i = indexFor(e.hash, newCapacity);
11     //頭插法
12     e.next = newTable[i];//將Entry3的next設置為當前鏈條的首個鍵值對Entry2
13     newTable[i] = e;//newTable[3]設置為Entry3
14     //另e=next=null，結束while迴圈。
15     e = next;
16 }

執行完第三次迴圈後線程B中局部變數newTable的結構：

執行完第三次迴圈後hashMap對象的結構：

​　　至此，線程B因為改變了Entry3的next屬性，在hashMap對象中產生了環形鏈表。下一節，將探究環形鏈表是如何在hashMap查詢時產生死迴圈的。