HashMap在高并發下會出現什么問題

本篇內容介紹了“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 還是非線程安全類，仍然會產生數據丟失等問題。

“HashMap在高并發下會出現什么問題”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！