多線程下HashMap是怎么死循環(huán)的？

作者：看山灬 2025-01-21 00:00:00

競(jìng)態(tài)條件可能會(huì)導(dǎo)致程序崩潰、數(shù)據(jù)損壞、死鎖等問(wèn)題。為了避免競(jìng)爭(zhēng)條件，可以使用同步機(jī)制（如鎖、信號(hào)量等）來(lái)保證只有一個(gè)進(jìn)程或線程可以訪問(wèn)共享資源。

這是一個(gè)老問(wèn)題了，現(xiàn)在都Java21了，又翻出來(lái)Java7的問(wèn)題，算是對(duì)歷史的總結(jié)把。

背過(guò)面試八股文的都知道，HashMap是非線程安全的，多線程下要用ConcurrentHashMap之類(lèi)的。但是實(shí)際工作中，還是會(huì)碰到在多線程中使用HashMap。可能是寫(xiě)的時(shí)候迷糊了，也可能是代碼升級(jí)時(shí)沒(méi)有注意，比如原本是單線程的，后來(lái)性能不行改成多線程了。多線程下使用HashMap，偶爾會(huì)出現(xiàn)服務(wù)hang死的情況，重啟就好，測(cè)試環(huán)境還復(fù)現(xiàn)不了，純偶發(fā)，即Race Condition（競(jìng)態(tài)條件）。

競(jìng)態(tài)條件（Race Condition）是指在多線程或者多進(jìn)程的程序中，由于多個(gè)線程或進(jìn)程之間執(zhí)行順序的不確定性，導(dǎo)致程序出現(xiàn)意料之外的結(jié)果或者行為。這種情況通常發(fā)生在多個(gè)線程或進(jìn)程同時(shí)訪問(wèn)共享資源時(shí)，其中一個(gè)線程或進(jìn)程修改了共享資源的狀態(tài)，但其他線程或進(jìn)程并沒(méi)有意識(shí)到這個(gè)修改，導(dǎo)致它們基于過(guò)期的狀態(tài)做出了錯(cuò)誤的決策。競(jìng)爭(zhēng)條件是一種常見(jiàn)的并發(fā)編程錯(cuò)誤，需要在程序設(shè)計(jì)和實(shí)現(xiàn)時(shí)特別注意。

那我們來(lái)分析下，HashMap是怎么形成競(jìng)態(tài)條件的。

先梳理一下源碼

put方法是入口：

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    // 計(jì)算hash值
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    // 如果該key已被插入，則替換舊的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不存在，增加一個(gè)節(jié)點(diǎn)
    addEntry(hash, key, value, i);
    return null;
}

檢查容量是否超過(guò)閾值，超過(guò)了就擴(kuò)容：

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 判斷當(dāng)前的size是否超過(guò)閾值，如果超過(guò)了，重新resize，也就是擴(kuò)容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    // size未超過(guò)閾值或者擴(kuò)容完成后，增加節(jié)點(diǎn)
    createEntry(hash, key, value, bucketIndex);
}

將新增元素插入鏈表中：

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

擴(kuò)容重建新的hash表，并將老表中的數(shù)據(jù)遷移到新表中：

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    // 創(chuàng)建新的hash表
    Entry[] newTable = new Entry[newCapacity];
    boolean oldAltHashing = useAltHashing;
    useAltHashing |= sun.misc.VM.isBooted() &&
            (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean rehash = oldAltHashing ^ useAltHashing;
    // 將老表中的數(shù)據(jù)遷移到新表中
    transfer(newTable, rehash);
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

老表數(shù)據(jù)遷移到新表，就是循環(huán)遍歷舊數(shù)據(jù)，然后插入的新表中：

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;
        }
    }
}

上面的這個(gè)代碼沒(méi)有什么問(wèn)題，有問(wèn)題也不會(huì)堅(jiān)持這么多版本了。

那問(wèn)題出在哪呢？出在了多線程上，接下來(lái)我們畫(huà)圖看看。

看圖說(shuō)話

本節(jié)中的例子和圖片思路來(lái)源于酷殼。

假設(shè)我們的hash算法就是key mode表格大小，hash表size是2，當(dāng)前元素key是3、5、7，mod 2時(shí)hash值都是1。執(zhí)行resize成4時(shí)，所有元素遷移到新表數(shù)據(jù)，過(guò)程如下（下圖來(lái)源于酷殼）：

示例

上面的過(guò)程是正常運(yùn)行的結(jié)果，如果在遷移時(shí)有兩個(gè)現(xiàn)成同時(shí)操作（能過(guò)到同時(shí)遷移，說(shuō)明前置的都是同時(shí)執(zhí)行的），就會(huì)出現(xiàn)問(wèn)題，還是通過(guò)示意圖的方式：

怎么解決呢？

想要成功的解決競(jìng)態(tài)條件問(wèn)題，保證程序可以正確的按邏輯順序運(yùn)行，從理論上應(yīng)該滿足以下四個(gè)條件：

不會(huì)有兩個(gè)及以上進(jìn)程同時(shí)出現(xiàn)在他們的critical section；
不要做任何關(guān)于CPU速度和數(shù)量的假設(shè)；
任何進(jìn)程在運(yùn)行到critical section之外時(shí)都不能阻塞其他進(jìn)程；
不會(huì)有進(jìn)程永遠(yuǎn)等在critical section之前。

"Critical section" 是計(jì)算機(jī)科學(xué)中的一個(gè)概念，用于描述多個(gè)進(jìn)程或線程訪問(wèn)共享資源時(shí)的同步問(wèn)題。在一個(gè)程序中，當(dāng)多個(gè)進(jìn)程或線程需要同時(shí)訪問(wèn)共享資源（如共享內(nèi)存或文件），為了避免數(shù)據(jù)競(jìng)爭(zhēng)和其他同步問(wèn)題，需要將訪問(wèn)共享資源的代碼段限制在一個(gè)受保護(hù)的區(qū)域內(nèi)，這個(gè)區(qū)域就稱(chēng)為 "critical section"。在這個(gè)區(qū)域內(nèi)，只有一個(gè)進(jìn)程或線程可以訪問(wèn)共享資源，其他進(jìn)程或線程必須等待，直到進(jìn)程或線程退出該區(qū)域。這樣可以確保共享資源的一致性和正確性。

為了避免這種情況的發(fā)生，我們可以采用以下幾種方法：

使用ConcurrentHashMap：ConcurrentHashMap是Java提供的一種線程安全的哈希表實(shí)現(xiàn)。它采用了分段鎖的機(jī)制，在多線程環(huán)境下能夠保證高效并發(fā)訪問(wèn)。如果我們需要在多線程環(huán)境下使用哈希表，建議使用ConcurrentHashMap來(lái)代替HashMap。
使用Collections.synchronizedMap：Collections.synchronizedMap是Java提供的一種線程安全的Map實(shí)現(xiàn)。它通過(guò)對(duì)Map的所有方法進(jìn)行同步，來(lái)保證線程安全。但是，由于它采用了同步的機(jī)制，因此在高并發(fā)環(huán)境下可能會(huì)出現(xiàn)性能瓶頸。
使用Lock：我們也可以使用Lock來(lái)手動(dòng)控制對(duì)HashMap的訪問(wèn)。具體來(lái)說(shuō)，我們可以在對(duì)HashMap進(jìn)行操作時(shí)，先獲取一個(gè)鎖，然后再進(jìn)行操作。這種方式需要我們手動(dòng)控制鎖的釋放，因此比較容易出現(xiàn)死鎖的情況。