面試必考之HashMap在并發(fā)編程環(huán)境下死循環(huán)

HashMap在并發(fā)編程環(huán)境下有什么問題啊?

代碼回顧

1.7 的時候，HashMap 在多并發(fā)環(huán)境下，多線程擴容，有可能引起的死循環(huán)問題：

如1.7 的時候，HashMap的底層是由數(shù)組加鏈表來實現(xiàn)的，如下所示：


jdk7-HashMap 數(shù)據(jù)結(jié)構(gòu).png

當往HashMap中put一個鍵值對時：

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        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++;
        addEntry(hash, key, value, i);
        return null;
    }

方法addEntry(hash, key, value, i);

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

當達到擴容條件為 if ((size >= threshold) && (null != table[bucketIndex])) 成立時，會發(fā)生 resize(2 * table.length); 擴容。

比如 table的初始容量為8,加載因子為0.75,此時閾值為6，table已有三個元素，現(xiàn)在put一個元素 Entry8 , Entry8 被散列到table[5]處，而table[5] != null,此時滿足擴容條件.

jdk7 HashMap 數(shù)據(jù)結(jié)構(gòu)插入擴容.png

擴容時先生成一個是table大小2倍的newTable，然后把table中的元素遷移到newTable中

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

遷移的工作就由 transfer方法來完成，這個方法就是引起死循環(huá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;
                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;
            }
        }
    }

環(huán)的形成

現(xiàn)在我們來模擬一下環(huán)是如何形成的，設(shè)HashMap的初始容量為4，先往HashMap中依次put三個元素<5,”B”>、<9,”C”>、<1,”A”>，它們都被散列到table[1]處，形成了鏈


模擬擴容前.png

假設(shè)一個HashMap已經(jīng)到了Resize的臨界點。此時有兩個線程Thread1和Thread2，在同一時刻對HashMap進行Put操作：


模擬擴容前插入.png

此時達到Resize條件，兩個線程各自進行resize的第一步，也就是擴容：


模擬同時擴容.png

此時， 這時候，兩個線程都走到了rehash的步驟。假設(shè)線程1執(zhí)行完 transfer 方法中的 Entry<K,V> next = e.next 語句后時間片用完，掛起

線程1掛起.png

此時，線程1內(nèi)的 e 指向 <1,“A”>，next指向<9,”C”> ，如下圖所示：


線程1掛起狀態(tài).png

線程2 生成完newTable后用transfer方法進行遷移，執(zhí)行完\color{red}{Entry<K,V> next = e.next;}后與線程1一樣，e指向<1,”A”>,next指向<9,”C”>

線程2第一次循環(huán)狀態(tài).png

線程2 然后繼續(xù)執(zhí)行循環(huá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;
                // 繼續(xù)執(zhí)行
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                // 此時 e = <1,A>
                // 下面的語句會把運行時的變量的值填進去
                //注意: <1,A> 代表了指向 <1,A>的引用，就是此e的值
                e.next = newTable[i];
                // <1,A>.next = newTable[1];
                newTable[i] = e;
                // newTable[1] = <1,A>;
                e = next;
                // <1,A> = <9,C>;
                // 此時e的指針指向了<9,C>
            }
        }

線程2執(zhí)行完之后為下圖 ：


線程2執(zhí)行完第一次循環(huán)狀態(tài).png

然后線程2按照同樣的邏輯進行第二次循環(huán)（while循環(huán)），下圖是第二遍循環(huán)后的結(jié)果 ：

線程2執(zhí)行完第二次循環(huán)狀態(tài).png

然后線程2按照同樣的邏輯進行第三遍循環(huán)，執(zhí)行后的結(jié)果 ：


線程2執(zhí)行完第三次循環(huán)狀態(tài).png

此時，線程2時間片用完，線程1得到時間片，開始執(zhí)行 :


線程1繼續(xù)執(zhí)行.png

注意，此時線程1的e指向<1,A>,next指向<9,C>,在線程2操作鏈表的時候，線程1 中的e,next指向的元素沒變(一直是紅色的e和next)

線程2時間片用完.png

線程一和線程二整體圖為：


線程1重新開始整體圖.png

然后線程1開始執(zhí)行循環(huán)內(nèi)剩下的代碼 ：

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;
                // 繼續(xù)執(zhí)行
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                // 此時 e = <1,A>
                // 下面的語句會把運行時的變量的值填進去
                //注意: <1,A> 代表了指向 <1,A>的引用，就是此e的值
                e.next = newTable[i];
                // <1,A>.next = newTable[1];
                newTable[i] = e;
                // newTable[1] = <1,A>;
                e = next;
                // <1,A> = <9,C>;
                // 此時e的指針指向了<9,C>
            }
        }

線程1執(zhí)行完之后為下圖 ：


線程1執(zhí)行第一次循環(huán).png

線程1繼續(xù)執(zhí)行第二遍循環(huá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;
                // next = <1,A>
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                // 此時 e = <9,C>
                e.next = newTable[i];
                // <9,C>.next = newTable[1];
                newTable[i] = e;
                // newTable[1] = <9,C>;
                e = next;
                // <9,C> = <1,A>;
                // 此時e的指針指向了<1,A>
            }
        }

執(zhí)行完之后如下圖所示：


線程1執(zhí)行第二次循環(huán).png

線程1繼續(xù)第三遍循環(huán)（注意：此次循環(huán)會形成環(huán)）：
先執(zhí)行 \color{#FF0000}{Entry<K,V> next = <1,A>.next }

線程1執(zhí)行第3-1次循環(huán).png

然后執(zhí)行 \color{#FF0000}{<1,A>.next = newTable[1] }

線程1執(zhí)行第3-2次循環(huán).png

此時環(huán)已經(jīng)形成

然后執(zhí)行剩余的兩行代碼

newTable[i] = e;
// newTable[1] = <1,A>;
e = next;
// e = null;

執(zhí)行完，e 為 null,退出循環(huán)


線程1執(zhí)行第3-3次循環(huán).png

死循環(huán)的發(fā)生

當形成環(huán)后,當往HashMap中put元素的時候，這個元素恰巧落在了table[1]（不管有沒有更新table），而這個元素的Key不在table[1]這條鏈上，此時會發(fā)生死循環(huán)

put死循環(huán).png

或者在get元素的時候，該元素恰巧落在table[1]上，并且該元素的Key不在該鏈上，會發(fā)生死循環(huán) ：


get死循環(huán).png

死循環(huán)是這樣形成的， 核心就是線程2修改了原來的鏈表結(jié)構(gòu)，而線程1卻以原來的邏輯執(zhí)行遷移 。

jdk1.8 會產(chǎn)生死循環(huán)么？

JDK 8 用 head 和 tail 來保證鏈表的順序和之前一樣； 并且采用尾插法，避免了這種死循環(huán)的產(chǎn)生， 但是還會有數(shù)據(jù)丟失等弊端（并發(fā)本身的問題）。

那并發(fā)下我還想使用散列表這種數(shù)據(jù)結(jié)構(gòu)怎么辦呢 ？

多線程情況下還是建議使用 ConcurrentHashMap，鎖的粒度較小，較HashTable或者 Collections.synchronizedMap() 性能要好一些 。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容