快捷導(dǎo)航

hashMap擴(kuò)容時(shí)應(yīng)該注意這些死循環(huán)問(wèn)題

更新時(shí)間：2021年06月10日 11:39:36 作者：攻城獅numberOne

今天給大家?guī)?lái)的是關(guān)于Java的相關(guān)知識(shí),文章圍繞著hashMap擴(kuò)容時(shí)的死循環(huán)問(wèn)題展開(kāi),文中有非常詳細(xì)的介紹及代碼示例,需要的朋友可以參考下

hashMap死循環(huán)

1.原因： jdk1.7時(shí)使用頭插入法 ,1.8之后改成了尾插入法解決了這個(gè)問(wèn)題

HashMap死循環(huán)問(wèn)題圖解

在HashMap的數(shù)組真實(shí)長(zhǎng)度達(dá)到閾值后，會(huì)調(diào)用擴(kuò)容方法：

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

這里可以看到如果有兩個(gè)線程A和B，那么在調(diào)用transfer方法之前會(huì)在各自的線程中創(chuàng)建新的數(shù)組，然后進(jìn)入到transfer方法中將節(jié)點(diǎn)轉(zhuǎn)移，再看transfer方法：

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;   ------（1）
                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;
            }
        }
    }

我在上面的程序中標(biāo)記了一個(gè)（1），待會(huì)會(huì)用到，首先假設(shè)HashMap中的結(jié)構(gòu)是這樣的：

那么線程A如果執(zhí)行到（1）的位置，那么e為節(jié)點(diǎn)5，next為節(jié)點(diǎn)6，這個(gè)時(shí)候線程B開(kāi)始運(yùn)行，在自己的擴(kuò)容數(shù)組里面運(yùn)行：

e.next = newTable[i];
newTable[i] = e;

這個(gè)時(shí)候結(jié)構(gòu)圖：

然后e=next；
在進(jìn)入循環(huán)執(zhí)行：

e.next = newTable[i];
newTable[i] = e;

這個(gè)時(shí)候結(jié)構(gòu)為：

然后線程B執(zhí)行完畢。線程A開(kāi)始從（1）后面繼續(xù)執(zhí)行，這個(gè)時(shí)候也是先執(zhí)行

e.next = newTable[i];
newTable[i] = e;

然后e=next；這個(gè)時(shí)候e是節(jié)點(diǎn)6，然后再進(jìn)入循環(huán)，執(zhí)行上面兩行程序后的結(jié)構(gòu)如下：

但是這個(gè)時(shí)候由于6的next是有值的，是節(jié)點(diǎn)5，所以再執(zhí)行e=next；的時(shí)候，e不為空，還會(huì)進(jìn)入一次循環(huán)，在執(zhí)行將節(jié)點(diǎn)插入頭部的操作，所以這個(gè)時(shí)候的結(jié)構(gòu)圖：

可以，看到已經(jīng)成為了環(huán)狀鏈表，當(dāng)執(zhí)行g(shù)et操作的時(shí)候就會(huì)產(chǎn)生死循環(huán)。

到此這篇關(guān)于hashMap擴(kuò)容時(shí)應(yīng)該注意這些死循環(huán)問(wèn)題的文章就介紹到這了,更多相關(guān)hashMap擴(kuò)容內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: