淺談HashMap在高並發下的問題
前言
總所周知,HashMap不是線程安全的,在高並發情況下會出現問題。特別是,在java1.7中,多線程的HashMap會出現CPU 100%的嚴重問題。這個問題是怎樣產生的,後續版本還會有這個問題嗎(指java8及後續版本)?下面就來用通俗的語言講解下。
解析
關於這個問題,是由於java7多線程擴容機制下鏈表變為循環鏈表,再獲取該鏈表導致的。
看下java7中擴容的代碼。java7中HashMap的實現為數組+鏈表的形式,沒有紅黑樹。
java7擴容的原則很簡單,新數組長度為原數組2倍。遍歷原數組,將數組每個位置(有可能為空,有可能隻有一個數組,有可能是一個鏈表)重新哈希,放到對應的新數組上。全部遍歷完後更改數組指針,指向新數組。需要註意的是,這裡重哈希將鏈表元素放到新數組,使用的是頭插法。
// 擴容核心方法,基本思想就是遍歷數據,使用頭插法將舊數組元素移到新數組。 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]; // 頭插法,新節點next指向該位置首節點 newTable[i] = e; // 新元素歸位 e = next; // 指向下一個節點,繼續遍歷 } } } 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); }
這裡處理的話,如果單線程情況下不會有問題。如果在多線程情況下,會導致鏈表在擴容過程中形成循環鏈表。
形成循環鏈表的原因在於多線程和頭插法。試想,兩個線程在添加元素時,同時發現該擴容瞭,然後同時發起擴容過程。由上述代碼可知,擴容完成之前是在自己的線程裡創建一個新數組。等擴容完成後(也就是將原數組元素遷移到新數組後)再更改指針指向新擴容數組。
舉例初始HashMap是這樣的
假設兩個線程同時擴容,一個線程擴容到一半後被掛起。(標識瞭某鏈表的e和next),另一個線程執行擴容,且完成瞭擴容。
紅色的數組和元素表示線程1,也就是擴容一半掛起的線程,而線程二已完成擴容。觀察完成擴容的線程二,在3的位置,該鏈表的位置順序已經改變(原數組順訊為3->7,現在反過來瞭,這是使用頭插法的效果,你也可以對著代碼試試)。從圖中也可以看出,線程1,2分別創建瞭自己的新數組,並在自己的新數組中完成擴容。
這時線程1開始執行。熟悉下它即將執行的代碼。
// transfer 方法循環部分 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]; // 頭插法,新節點next指向該位置首節點 newTable[i] = e; // 新元素歸位 e = next; // 指向下一個節點,繼續遍歷 }
下面線程1將使用頭插法將元素插入線程1新建的數組中去。註意此時e指向的是Key3,next指向的是Key7。不用想也知道後面操作會有問題。因為現在的next指針指的不是e的下一個元素,而是它的前一個元素!
如果繼續走代碼的話,把Key3(當前e指向元素)放入新數組後,再把Key7放入新數組,後面會放哪個元素?當然又是Key3瞭,因為Key7next是Key3,這樣就形成瞭死循環。
java8的改進
- 添加瞭紅黑樹,當鏈表長度大於8時,會將鏈表轉為紅黑樹。
- 擴容後,新數組中的鏈表順序依然與舊數組中的鏈表順序保持一致。具體JDK8是用 head 和 tail 來保證鏈表的順序和之前一樣,這樣就不會產生循環引用。也就沒有死循環瞭。
- 雖然修復瞭死循環的BUG,但是HashMap 還是非線程安全類,仍然會產生數據丟失等問題。
以上為個人經驗,希望能給大傢一個參考,也希望大傢多多支持WalkonNet。
推薦閱讀:
- hashMap擴容時應該註意這些死循環問題
- Java京東面試題之為什麼HashMap線程不安全
- Java1.7全網最深入HashMap源碼解析
- HashMap在JDK7與JDK8中的實現過程解析
- HashMap底層實現原理詳解