占小狼 轉(zhuǎn)載請(qǐng)注明原創(chuàng)出處，謝謝！

問(wèn)題

最近的幾次面試中，我都問(wèn)了是否了解HashMap在并發(fā)使用時(shí)可能發(fā)生死循環(huán)，導(dǎo)致cpu100%，結(jié)果讓我很意外，都表示不知道有這樣的問(wèn)題，讓我意外的是面試者的工作年限都不短。

由于HashMap并非是線程安全的，所以在高并發(fā)的情況下必然會(huì)出現(xiàn)問(wèn)題，這是一個(gè)普遍的問(wèn)題，雖然網(wǎng)上分析的文章很多，還是覺(jué)得有必須寫一篇文章，讓關(guān)注我公眾號(hào)的同學(xué)能夠意識(shí)到這個(gè)問(wèn)題，并了解這個(gè)死循環(huán)是如何產(chǎn)生的。

如果是在單線程下使用HashMap，自然是沒(méi)有問(wèn)題的，如果后期由于代碼優(yōu)化，這段邏輯引入了多線程并發(fā)執(zhí)行，在一個(gè)未知的時(shí)間點(diǎn)，會(huì)發(fā)現(xiàn)CPU占用100%，居高不下，通過(guò)查看堆棧，你會(huì)驚訝的發(fā)現(xiàn)，線程都Hang在hashMap的get()方法上，服務(wù)重啟之后，問(wèn)題消失，過(guò)段時(shí)間可能又復(fù)現(xiàn)了。

這是為什么？

原因分析

在了解來(lái)龍去脈之前，我們先看看HashMap的數(shù)據(jù)結(jié)構(gòu)。

在內(nèi)部，HashMap使用一個(gè)Entry數(shù)組保存key、value數(shù)據(jù)，當(dāng)一對(duì)key、value被加入時(shí)，會(huì)通過(guò)一個(gè)hash算法得到數(shù)組的下標(biāo)index，算法很簡(jiǎn)單，根據(jù)key的hash值，對(duì)數(shù)組的大小取模 hash & (length-1)，并把結(jié)果插入數(shù)組該位置，如果該位置上已經(jīng)有元素了，就說(shuō)明存在hash沖突，這樣會(huì)在index位置生成鏈表。

如果存在hash沖突，最慘的情況，就是所有元素都定位到同一個(gè)位置，形成一個(gè)長(zhǎng)長(zhǎng)的鏈表，這樣get一個(gè)值時(shí)，最壞情況需要遍歷所有節(jié)點(diǎn)，性能變成了O(n)，所以元素的hash值算法和HashMap的初始化大小很重要。

當(dāng)插入一個(gè)新的節(jié)點(diǎn)時(shí)，如果不存在相同的key，則會(huì)判斷當(dāng)前內(nèi)部元素是否已經(jīng)達(dá)到閾值（默認(rèn)是數(shù)組大小的0.75），如果已經(jīng)達(dá)到閾值，會(huì)對(duì)數(shù)組進(jìn)行擴(kuò)容，也會(huì)對(duì)鏈表中的元素進(jìn)行rehash。

實(shí)現(xiàn)

HashMap的put方法實(shí)現(xiàn)：

1、判斷key是否已經(jīng)存在

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    // 如果key已經(jīng)存在，則替換value，并返回舊值
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    // key不存在，則插入新的元素
    addEntry(hash, key, value, i);
    return null;
}

2、檢查容量是否達(dá)到閾值threshold

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

如果元素個(gè)數(shù)已經(jīng)達(dá)到閾值，則擴(kuò)容，并把原來(lái)的元素移動(dòng)過(guò)去。

3、擴(kuò)容實(shí)現(xiàn)

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    ...

    Entry[] newTable = new Entry[newCapacity];
    ...
    transfer(newTable, rehash);
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

這里會(huì)新建一個(gè)更大的數(shù)組，并通過(guò)transfer方法，移動(dòng)元素。

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];
            newTable[i] = e;
            e = next;
        }
    }
}

移動(dòng)的邏輯也很清晰，遍歷原來(lái)table中每個(gè)位置的鏈表，并對(duì)每個(gè)元素進(jìn)行重新hash，在新的newTable找到歸宿，并插入。

案例分析

假設(shè)HashMap初始化大小為4，插入個(gè)3節(jié)點(diǎn)，不巧的是，這3個(gè)節(jié)點(diǎn)都hash到同一個(gè)位置，如果按照默認(rèn)的負(fù)載因子的話，插入第3個(gè)節(jié)點(diǎn)就會(huì)擴(kuò)容，為了驗(yàn)證效果，假設(shè)負(fù)載因子是1.

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];
            newTable[i] = e;
            e = next;
        }
    }
}

以上是節(jié)點(diǎn)移動(dòng)的相關(guān)邏輯。

插入第4個(gè)節(jié)點(diǎn)時(shí)，發(fā)生rehash，假設(shè)現(xiàn)在有兩個(gè)線程同時(shí)進(jìn)行，線程1和線程2，兩個(gè)線程都會(huì)新建新的數(shù)組。

假設(shè) 線程2 在執(zhí)行到Entry<K,V> next = e.next;之后，cpu時(shí)間片用完了，這時(shí)變量e指向節(jié)點(diǎn)a，變量next指向節(jié)點(diǎn)b。

線程1繼續(xù)執(zhí)行，很不巧，a、b、c節(jié)點(diǎn)rehash之后又是在同一個(gè)位置7，開(kāi)始移動(dòng)節(jié)點(diǎn)

第一步，移動(dòng)節(jié)點(diǎn)a

第二步，移動(dòng)節(jié)點(diǎn)b

注意，這里的順序是反過(guò)來(lái)的，繼續(xù)移動(dòng)節(jié)點(diǎn)c

這個(gè)時(shí)候 線程1 的時(shí)間片用完，內(nèi)部的table還沒(méi)有設(shè)置成新的newTable， 線程2 開(kāi)始執(zhí)行，這時(shí)內(nèi)部的引用關(guān)系如下：

這時(shí)，在 線程2 中，變量e指向節(jié)點(diǎn)a，變量next指向節(jié)點(diǎn)b，開(kāi)始執(zhí)行循環(huán)體的剩余邏輯。

Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;

執(zhí)行之后的引用關(guān)系如下圖

執(zhí)行后，變量e指向節(jié)點(diǎn)b，因?yàn)閑不是null，則繼續(xù)執(zhí)行循環(huán)體，執(zhí)行后的引用關(guān)系

變量e又重新指回節(jié)點(diǎn)a，只能繼續(xù)執(zhí)行循環(huán)體，這里仔細(xì)分析下：
1、執(zhí)行完Entry<K,V> next = e.next;，目前節(jié)點(diǎn)a沒(méi)有next，所以變量next指向null；
2、e.next = newTable[i]; 其中 newTable[i] 指向節(jié)點(diǎn)b，那就是把a(bǔ)的next指向了節(jié)點(diǎn)b，這樣a和b就相互引用了，形成了一個(gè)環(huán)；
3、newTable[i] = e 把節(jié)點(diǎn)a放到了數(shù)組i位置；
4、e = next; 把變量e賦值為null，因?yàn)榈谝徊街凶兞縩ext就是指向null；

所以最終的引用關(guān)系是這樣的：

節(jié)點(diǎn)a和b互相引用，形成了一個(gè)環(huán)，當(dāng)在數(shù)組該位置get尋找對(duì)應(yīng)的key時(shí)，就發(fā)生了死循環(huán)。

另外，如果線程2把newTable設(shè)置成到內(nèi)部的table，節(jié)點(diǎn)c的數(shù)據(jù)就丟了，看來(lái)還有數(shù)據(jù)遺失的問(wèn)題。

總結(jié)

所以在并發(fā)的情況，發(fā)生擴(kuò)容時(shí)，可能會(huì)產(chǎn)生循環(huán)鏈表，在執(zhí)行g(shù)et的時(shí)候，會(huì)觸發(fā)死循環(huán)，引起CPU的100%問(wèn)題，所以一定要避免在并發(fā)環(huán)境下使用HashMap。

曾經(jīng)有人把這個(gè)問(wèn)題報(bào)給了Sun，不過(guò)Sun不認(rèn)為這是一個(gè)bug，因?yàn)樵贖ashMap本來(lái)就不支持多線程使用，要并發(fā)就用ConcurrentHashmap。

END。
我是占小狼。 如果讀完覺(jué)得有收獲的話，記得關(guān)注和點(diǎn)贊