Java集合——HashMap擴容的死鎖問題
摘要：本文主要了解了HashMap在多執行緒并發情況下擴容產生的死鎖問題，
死鎖問題
在JDK的1.7版本進行擴容時，因為是頭插法插入節點，并且在一個執行緒擴容后會替換掉之前的陣列，所以在多執行緒環境下可能會產生死鎖，1 // 擴容， 2 void resize(int newCapacity) { 3 // 判斷是否需要擴容， 4 Entry[] oldTable = table; 5 int oldCapacity = oldTable.length; 6 if (oldCapacity == MAXIMUM_CAPACITY) { 7 threshold = Integer.MAX_VALUE; 8 return; 9 } 10 // 創建擴容后的新陣列，并且在擴容后替換老陣列， 11 Entry[] newTable = new Entry[newCapacity]; 12 transfer(newTable, initHashSeedAsNeeded(newCapacity)); 13 table = newTable; 14 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); 15 } 16 17 // 擴容， 18 void transfer(Entry[] newTable, boolean rehash) { 19 int newCapacity = newTable.length; 20 for (Entry<K,V> e : table) { 21 while(null != e) { 22 Entry<K,V> next = e.next; 23 if (rehash) { 24 e.hash = null == e.key ? 0 : hash(e.key); 25 } 26 int i = indexFor(e.hash, newCapacity); 27 e.next = newTable[i]; 28 newTable[i] = e; 29 e = next; 30 } 31 } 32 }以上是擴容相關的代碼，可以發現，多執行緒情況下，每個執行緒都有自己的新陣列，并且在擴容后會替換以前的陣列， 這就有可能導致A執行緒和B執行緒同時對一個陣列擴容，A執行緒擴容后替換掉老陣列，這時B執行緒使用的陣列實際上是A執行緒擴容后的陣列，就會產生執行緒安全問題，
死鎖原因
比如，當前集合陣列長度為2，已經有兩個元素被放在了下標為0的節點里形成了鏈表結構，此時，有兩個執行緒都同時向集合添加新元素，所以每個執行緒在添加時都會對原集合陣列進行擴容， 插入前的陣列如圖：
1）執行緒一先執行，當它執行完上面代碼“Entry<K,V> next = e.next;”以后，e指向A，next指向B，時間片用完，執行緒一掛起，此時，如圖：
2）執行緒二后執行，并且完成了整個擴容操作，而且擴容后的新陣列替換了原陣列，此時，如圖：
3）執行緒一繼續執行，e指向A，next指向B，此時，原陣列已經被執行緒二擴充了，
在執行了“e.next = newTable[i];”之后，e的下一節點指向了新陣列下標為0的節點，此時，如圖：
在執行了“newTable[i] = e;”之后，將e作為新陣列下標為0的節點，e指向了A，A的下一節點指向null，此時，如圖：
在執行了“e = next;”之后，e指向了B，此時，如圖：
4）執行緒一繼續執行，開始第二輪回圈，
在執行了“Entry<K,V> next = e.next;”之后，e指向B，next指向A，此時，如圖：
在執行了“e.next = newTable[i];”之后，e的下一節點指向了新陣列下標為0的節點，此時，如圖：
在執行了“newTable[i] = e;”之后，將e作為新陣列下標為0的節點，e指向了B，B的下一節點指向null，此時，如圖：
在執行了“e = next;”之后，e指向了A，此時，如圖：
5）執行緒一繼續執行，開始第三輪回圈，
在執行了“Entry<K,V> next = e.next;”之后，e指向A，next指向null，此時，如圖：
在執行了“e.next = newTable[i];”之后，e的下一節點指向了新陣列下標為0的節點，此時，如圖：
在執行了“newTable[i] = e;”之后，將e作為新陣列下標為0的節點，e指向了A，A的下一節點指向null，此時，如圖：
在執行了“e = next;”之后，e指向了null，此時，如圖：
6）執行緒一將新陣列賦值給原陣列，如圖：
如果再有執行緒嘗試在下標為1的陣列進行插入操作，就會引發死回圈，
2.11 擴容的死鎖問題
在JDK的1.7版本進行擴容時，因為是頭插法插入節點，并且在一個執行緒擴容后會替換掉之前的陣列，所以在多執行緒環境下可能會產生死鎖，
|
// 擴容， void resize(int newCapacity) { // 判斷是否需要擴容， Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } // 創建擴容后的新陣列，并且在擴容后替換老陣列， Entry[] newTable = new Entry[newCapacity]; transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }
// 擴容， 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; } } } |
以上是擴容相關的代碼，可以發現，多執行緒情況下，每個執行緒都有自己的新陣列，并且在擴容后會替換以前的陣列，
這就有可能導致A執行緒和B執行緒同時對一個陣列擴容，A執行緒擴容后替換掉老陣列，這時B執行緒使用的陣列實際上是A執行緒擴容后的陣列，就會產生執行緒安全問題，
比如，當前集合陣列長度為2，已經有兩個元素被放在了下標為0的節點里形成了鏈表結構，此時，有兩個執行緒都同時向集合添加新元素，所以每個執行緒在添加時都會對原集合陣列進行擴容，
插入前的陣列如圖：
1）執行緒一先執行，當它執行完上面代碼“Entry<K,V> next = e.next;”以后，e指向A，next指向B，時間片用完，執行緒一掛起，此時，如圖：
2）執行緒二后執行，并且完成了整個擴容操作，而且擴容后的新陣列替換了原陣列，此時，如圖：
3）執行緒一繼續執行，e指向A，next指向B，此時，原陣列已經被執行緒二擴充了，
在執行了“e.next = newTable[i];”之后，e的下一節點指向了新陣列下標為0的節點，此時，如圖：
在執行了“newTable[i] = e;”之后，將e作為新陣列下標為0的節點，e指向了A，A的下一節點指向null，此時，如圖：
在執行了“e = next;”之后，e指向了B，此時，如圖：
4）執行緒一繼續執行，開始第二輪回圈，
在執行了“Entry<K,V> next = e.next;”之后，e指向B，next指向A，此時，如圖：
在執行了“e.next = newTable[i];”之后，e的下一節點指向了新陣列下標為0的節點，此時，如圖：
在執行了“newTable[i] = e;”之后，將e作為新陣列下標為0的節點，e指向了B，B的下一節點指向null，此時，如圖：
在執行了“e = next;”之后，e指向了A，此時，如圖：
5）執行緒一繼續執行，開始第三輪回圈，
在執行了“Entry<K,V> next = e.next;”之后，e指向A，next指向null，此時，如圖：
在執行了“e.next = newTable[i];”之后，e的下一節點指向了新陣列下標為0的節點，此時，如圖：
在執行了“newTable[i] = e;”之后，將e作為新陣列下標為0的節點，e指向了A，A的下一節點指向null，此時，如圖：
在執行了“e = next;”之后，e指向了null，此時，如圖：
6）執行緒一將新陣列賦值給原陣列，如圖：
如果再有執行緒嘗試在下標為1的陣列進行插入操作，就會引發死回圈，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/124089.html
標籤：Java
上一篇：同事牛逼啊，寫了個隱藏 bug，我排查了 3 天才解決問題！
下一篇：JVM 學習筆記記錄