HashMap為什么會導(dǎo)致CPU100%

1.HashMap 的底層數(shù)據(jù)結(jié)構(gòu)

先來說 HashMap 的底層數(shù)據(jù)結(jié)構(gòu)，看過 HashMap 的源碼我們就會發(fā)現(xiàn)，JDK 1.7 和 JDK 1.8 HashMap 的組成是不同的，JDK 1.7 HashMap 的組成是數(shù)組 + 鏈表的形式，而 JDK 1.8 新增了紅黑樹的數(shù)據(jù)結(jié)構(gòu)，當(dāng) HashMap 中的鏈表長度大于 8 時，鏈表結(jié)構(gòu)就會轉(zhuǎn)換為紅黑樹，如下圖所示：

2.哈希碰撞及解決方案

所謂的哈希碰撞指的是不同的值，經(jīng)過哈希之后得到的值確是相同的，這種情況就叫做哈希碰撞或哈希沖突。解決哈希碰撞的常用方法是：開放定址法和鏈表地址法，而 HashMap 采用的就是鏈表地址法。它的實現(xiàn)原理就是將 HashMap 中相同的哈希值以鏈表的形式存儲起來。

3.擴展因子

擴展因子也叫加載因子或負載因子是 HashMap 中的一個屬性，如下圖所示：假如數(shù)組的默認長度為 10，擴展因子為 0.5，那么當(dāng)數(shù)組超過 10*0.5=5 個時，HashMap 就會擴容為之前容量的兩倍，所以說擴展因子就是用來判定 HashMap 是否滿足擴容條件的。

4.HashMap死循環(huán)分析

HashMap 導(dǎo)致 CPU 100% 的原因就是因為 HashMap 死循環(huán)導(dǎo)致的，那 HashMap 是如何造成死循環(huán)的？接下來我們一起來看。

以 JDK 1.7 為例，假設(shè) HashMap 的默認大小為 2，HashMap 本身中有一個鍵值 key(5)，我們再使用兩個線程：t1 添加 key(3)，t2 添加 key(7)，首先兩個線程先把 key(3) 和 key(7) 都添加到 HashMap 中，此時因為 HashMap 的長度不夠用了就會進行擴容操作，然后這時線程 t1 在執(zhí)行到 Entry<K,V> next = e.next; 時，交出了 CPU 的使用權(quán)，源代碼如下：

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; // 線程一執(zhí)行此處
            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;
        }
    }
}

那么此時線程 t1 中的 e 指向了 key(3)，而 next 指向了 key(7) ；之后線程 t2 重新 rehash 之后鏈表的順序被反轉(zhuǎn)，鏈表的位置變成了 key(5) -> key(7) -> key(3)，其中 “->” 用來表示下一個元素，當(dāng) t1 重新獲得執(zhí)行權(quán)之后，先執(zhí)行 newTalbe[i] = e 把 key(3) 的 next 設(shè)置為 key(7)，而下次循環(huán)時查詢到 key(7) 的 e.next 為 key(3)，于是就形 成了 key(3) 和 key(7) 的環(huán)形引用，就導(dǎo)致了死循環(huán)的產(chǎn)生，如下圖所示：

HashMap 發(fā)生死循環(huán)的一個重要原因是 JDK 1.7 時鏈表的插入是首部倒序插入的，而 JDK 1.8 時已經(jīng)變成了尾部插入，有人把這個死循環(huán)的問題反饋給了 Sun 公司，但它們認為這不是一個問題，因為 HashMap 本身就是非線程安全的，如果要在多線程使用建議使用 ConcurrentHashMap 替代 HashMap，但面試中這個問題被問的頻率比較高，所以在這里就特殊說明一下。

HashMap 是非線程安全的，以 JDK 1.7 為例，當(dāng)多線程并發(fā)擴容時就會出現(xiàn)環(huán)形引用的問題，從而導(dǎo)致死循環(huán)的出現(xiàn)，一直死循環(huán)就會導(dǎo)致 CPU 運行 100%。