Java集合：HashMap线程不安全？有哪些表现？
HashMap是線程不安全的！主要表現在多線程情況下：
1）hash沖突時，put方法不是同步的，先存的值會被后存的值覆蓋。（1.7和1.8都有的表現）
2）在resize的時候，可能會導致死循環（環形鏈表）（僅1.7會有的表現，因為其頭插法導致）
讓我們先來了解一下HashMap的底層存儲結構，HashMap底層是一個Entry數組，一旦發生Hash沖突的的時候，HashMap采用拉鏈法解決碰撞沖突，Entry內部的變量：
[java]?view plain?copy
?
? ? ? ? 通過Entry內部的next變量可以知道使用的是鏈表，這時候我們可以知道，如果多個線程，在某一時刻同時操作HashMap并執行put操作，而有大于兩個key的hash值相同，如圖中a1、a2，這個時候需要解決碰撞沖突，而解決沖突的辦法上面已經說過，對于鏈表的結構在這里不再贅述，暫且不討論是從鏈表頭部插入還是從尾部初入，這個時候兩個線程如果恰好都取到了對應位置的頭結點e1，而最終的結果可想而知，a1、a2兩個數據中勢必會有一個會丟失，如圖所示：
?
再來看下put方法
?
[java]?view plain?copy
?
put方法不是同步的，同時調用了addEntry方法：
?
[java]?view plain?copy
?
addEntry方法依然不是同步的，所以導致了線程不安全出現傷處問題，其他類似操作不再說明，源碼一看便知，
?resize死循環（JDK1.7）
重新調整 HashMap 大小的時候，存在條件競爭。
因為如果兩個線程都發現 HashMap 需要重新調整大小了，它們會同時試著調整大小。在調整大小的過程中，存儲在鏈表中的元素的次序會反過來。因為移動到新的 bucket 位置的時候，HashMap 并不會將元素放在鏈表的尾部，而是放在頭部。這是為了避免尾部遍歷（tail traversing）。如果條件競爭發生了，那么就死循環了。多線程的環境下不使用 HashMap。
HashMap 的容量是有限的。當經過多次元素插入，使得 HashMap 達到一定飽和度時，Key 映射位置發生沖突的幾率會逐漸提高。這時候， HashMap 需要擴展它的長度，也就是進行Resize。
擴容：創建一個新的 Entry 空數組，長度是原數組的2倍
rehash：遍歷原 Entry 數組，把所有的 Entry 重新 Hash 到新數組
為什么多線程會導致死循環，它是怎么發生的？
我們都知道HashMap初始容量大小為16,一般來說，當有數據要插入時，都會檢查容量有沒有超過設定的thredhold，如果超過，需要增大Hash表的尺寸，但是這樣一來，整個Hash表里的元素都需要被重算一遍。這叫rehash，這個成本相當的大。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 | 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); } |
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | 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); ????????????????} ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //頭插法（JDK1.7） ????????????????int i = indexFor(e.hash, newCapacity); ????????????????e.next = newTable[i]; ????????????????newTable[i] = e; ????????????????e = next; ????????????} ????????} } |
| ? | ? |
大概看下transfer：
經過這幾步，我們會發現轉移的時候是逆序的。假如轉移前鏈表順序是1->2->3，那么轉移后就會變成3->2->1。這時候就有點頭緒了，死鎖問題不就是因為1->2的同時2->1造成的嗎？所以，HashMap 的死鎖問題就出在這個transfer()函數上。
1.1?單線程 rehash 詳細演示
單線程情況下，rehash 不會出現任何問題：
- 假設hash算法就是最簡單的 key mod table.length（也就是數組的長度）。
- 最上面的是old hash 表，其中的Hash表的 size = 2, 所以 key = 3, 7, 5，在 mod 2以后碰撞發生在 table[1]
- 接下來的三個步驟是 Hash表 resize 到4，并將所有的?<key,value>?重新rehash到新 Hash 表的過程
如圖所示：頭插法
?
1.2?多線程 rehash 詳細演示
為了思路更清晰，我們只將關鍵代碼展示出來
| 1 2 3 4 5 6 | while(null != e) { ????Entry<K,V> next = e.next; ????e.next = newTable[i]; ????newTable[i] = e; ????e = next; } |
假設這里有兩個線程同時執行了put()操作，并進入了transfer()環節
| 1 2 3 4 5 6 | while(null != e) { ????Entry<K,V> next = e.next; //線程1執行到這里被調度掛起了 ????e.next = newTable[i]; ????newTable[i] = e; ????e = next; } |
那么現在的狀態為：
?
從上面的圖我們可以看到，因為線程1的 e 指向了 key(3)，而 next 指向了 key(7)，在線程2 rehash 后，就指向了線程2 rehash 后的鏈表。
然后線程1被喚醒了：
然后該執行 key(3)的 next 節點 key(7)了:
這時候的狀態圖為：
?
然后又該執行 key(7)的 next 節點 key(3)了：
這時候的狀態如圖所示：
?
很明顯，環形鏈表出現了！！當然，現在還沒有事情，因為下一個節點是 null，所以transfer()就完成了，等put()的其余過程搞定后，HashMap 的底層實現就是線程1的新 Hash 表了。
JDK 1.7 HashMap擴容導致死循環的主要原因
HashMap擴容導致死循環的主要原因在于擴容后鏈表中的節點在新的hash桶使用頭插法插入。
新的hash桶會倒置原hash桶中的單鏈表，那么在多個線程同時擴容的情況下就可能導致產生一個存在閉環的單鏈表，從而導致死循環。
JDK 1.8 HashMap擴容不會造成死循環的原因
在JDK 1.8中執行上面的擴容死循環代碼示例就不會發生死循環。由于使用的是尾插法，不會導致單鏈表的倒置，所以擴容的時候不會導致死循環。
通過上面的分析，不難發現循環的產生是因為新鏈表的順序跟舊的鏈表是完全相反的，所以只要保證建新鏈時還是按照原來的順序的話就不會產生循環。
?
這里雖然JDK 1.8 中HashMap擴容的時候不會造成死循環，但是如果多個線程同時執行put操作，可能會導致同時向一個單鏈表中插入數據，從而導致數據丟失的。
所以不論是JDK 1.7 還是 1.8，HashMap線程都是不安全的，要使用線程安全的Map可以考慮ConcurrentHashMap。
?
總結
以上是生活随笔為你收集整理的Java集合：HashMap线程不安全？有哪些表现？的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Java集合:JDK7与JDK8中Has
- 下一篇： Java集合：ConcurrentHas