前言

總所周知，HashMap不是線程安全的，在高并發(fā)情況下會(huì)出現(xiàn)問題。特別是，在java1.7中，多線程的HashMap會(huì)出現(xiàn)CPU 100%的嚴(yán)重問題。這個(gè)問題是怎樣產(chǎn)生的，后續(xù)版本還會(huì)有這個(gè)問題嗎（指java8及后續(xù)版本）？下面就來用通俗的語言講解下。

解析

關(guān)于這個(gè)問題，是由于java7多線程擴(kuò)容機(jī)制下鏈表變?yōu)檠h(huán)鏈表，再獲取該鏈表導(dǎo)致的。

看下java7中擴(kuò)容的代碼。java7中HashMap的實(shí)現(xiàn)為數(shù)組+鏈表的形式，沒有紅黑樹。

java7擴(kuò)容的原則很簡單，新數(shù)組長度為原數(shù)組2倍。遍歷原數(shù)組，將數(shù)組每個(gè)位置（有可能為空，有可能只有一個(gè)數(shù)組，有可能是一個(gè)鏈表）重新哈希，放到對(duì)應(yīng)的新數(shù)組上。全部遍歷完后更改數(shù)組指針，指向新數(shù)組。需要注意的是，這里重哈希將鏈表元素放到新數(shù)組，使用的是頭插法。

 // 擴(kuò)容核心方法，基本思想就是遍歷數(shù)據(jù)，使用頭插法將舊數(shù)組元素移到新數(shù)組。
 void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        // 遍歷舊數(shù)組
        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]; // 頭插法,新節(jié)點(diǎn)next指向該位置首節(jié)點(diǎn)
                newTable[i] = e; // 新元素歸位
                e = next; // 指向下一個(gè)節(jié)點(diǎn)，繼續(xù)遍歷
            }
        }
    }
   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]; // 創(chuàng)建新數(shù)組
        transfer(newTable, initHashSeedAsNeeded(newCapacity)); // 擴(kuò)容
        table = newTable;  // 更改指針
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

這里處理的話，如果單線程情況下不會(huì)有問題。如果在多線程情況下，會(huì)導(dǎo)致鏈表在擴(kuò)容過程中形成循環(huán)鏈表。

形成循環(huán)鏈表的原因在于多線程和頭插法。試想，兩個(gè)線程在添加元素時(shí)，同時(shí)發(fā)現(xiàn)該擴(kuò)容了，然后同時(shí)發(fā)起擴(kuò)容過程。由上述代碼可知，擴(kuò)容完成之前是在自己的線程里創(chuàng)建一個(gè)新數(shù)組。等擴(kuò)容完成后（也就是將原數(shù)組元素遷移到新數(shù)組后）再更改指針指向新擴(kuò)容數(shù)組。

舉例初始HashMap是這樣的

假設(shè)兩個(gè)線程同時(shí)擴(kuò)容，一個(gè)線程擴(kuò)容到一半后被掛起。（標(biāo)識(shí)了某鏈表的e和next）,另一個(gè)線程執(zhí)行擴(kuò)容，且完成了擴(kuò)容。

紅色的數(shù)組和元素表示線程1，也就是擴(kuò)容一半掛起的線程，而線程二已完成擴(kuò)容。觀察完成擴(kuò)容的線程二，在3的位置，該鏈表的位置順序已經(jīng)改變（原數(shù)組順訊為3->7,現(xiàn)在反過來了，這是使用頭插法的效果，你也可以對(duì)著代碼試試）。從圖中也可以看出，線程1，2分別創(chuàng)建了自己的新數(shù)組，并在自己的新數(shù)組中完成擴(kuò)容。

這時(shí)線程1開始執(zhí)行。熟悉下它即將執(zhí)行的代碼。

       // transfer 方法循環(huán)部分
         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]; // 頭插法,新節(jié)點(diǎn)next指向該位置首節(jié)點(diǎn)
                newTable[i] = e; // 新元素歸位
                e = next; // 指向下一個(gè)節(jié)點(diǎn)，繼續(xù)遍歷
            }

下面線程1將使用頭插法將元素插入線程1新建的數(shù)組中去。注意此時(shí)e指向的是Key3,next指向的是Key7。不用想也知道后面操作會(huì)有問題。因?yàn)楝F(xiàn)在的next指針指的不是e的下一個(gè)元素，而是它的前一個(gè)元素！

如果繼續(xù)走代碼的話，把Key3(當(dāng)前e指向元素)放入新數(shù)組后，再把Key7放入新數(shù)組，后面會(huì)放哪個(gè)元素？當(dāng)然又是Key3了，因?yàn)镵ey7next是Key3,這樣就形成了死循環(huán)。

java8的改進(jìn)

• 添加了紅黑樹，當(dāng)鏈表長度大于8時(shí)，會(huì)將鏈表轉(zhuǎn)為紅黑樹。
• 擴(kuò)容后，新數(shù)組中的鏈表順序依然與舊數(shù)組中的鏈表順序保持一致。具體JDK8是用 head 和 tail 來保證鏈表的順序和之前一樣，這樣就不會(huì)產(chǎn)生循環(huán)引用。也就沒有死循環(huán)了。
• 雖然修復(fù)了死循環(huán)的BUG，但是HashMap 還是非線程安全類，仍然會(huì)產(chǎn)生數(shù)據(jù)丟失等問題。

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論