多線程環(huán)境下，HashMap為什么會出現(xiàn)死循環(huán)？

轉(zhuǎn)自：powerfuler

鏈接：blog.csdn.net/dingjianmin/article/details/79780350

Java 中的 HashMap 是非線程安全的，多線程下應(yīng)該用 ConcurrentHashMap。

多線程下 HashMap 的問題（這里主要說死循環(huán)問題）：

• 多線程 put 操作后，get 操作導(dǎo)致死循環(huán)；
• 多線程 put 非 null 元素后，get 操作得到 null 值；
• 多線程 put 操作，導(dǎo)致元素丟失。

1. 為何出現(xiàn)死循環(huán)

在多線程下使用非線程安全的 HashMap，單線程根本不會出現(xiàn)。

• HashMap 是采用鏈表解決 Hash 沖突。因?yàn)槭擎湵斫Y(jié)構(gòu)，那么就很容易形成閉合的鏈路。這樣在循環(huán)的時(shí)候，只要有線程對這個(gè) HashMap 進(jìn)行 get 操作就會產(chǎn)生死循環(huán)；
• 在單線程情況下，只有一個(gè)線程對 HashMap 的數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作，是不可能產(chǎn)生閉合的回路的；
• 只有在多線程并發(fā)的情況下才會出現(xiàn)這種情況，那就是在 put 操作的時(shí)候。如果 size > initialCapacity*loadFactor，那么這時(shí)候 HashMap 就會進(jìn)行 rehash 操作，隨之 HashMap 的結(jié)構(gòu)就會發(fā)生翻天覆地的變化。很有可能就是在兩個(gè)線程在這個(gè)時(shí)候同時(shí)觸發(fā)了 rehash 操作，產(chǎn)生了閉合的回路。

2. 死循環(huán)是如何產(chǎn)生的

存儲數(shù)據(jù) put()：

public V put(K key, V value) {    //......    //算Hash值    int hash = hash(key.hashCode());    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;}

當(dāng)我們往 HashMap 中 put 元素的時(shí)候，先根據(jù) key 的 hash 值得到這個(gè)元素在數(shù)組中的位置（即下標(biāo)），然后就可以把這個(gè)元素放到對應(yīng)的位置中了。

如果這個(gè)元素所在的位置上已經(jīng)存放有其他元素了，那么在同一個(gè)位置上的元素將以鏈表的形式存放。新加入的元素放在鏈頭，而先前加入的放在鏈尾。

檢查容量是否超標(biāo) addEntry：

void addEntry(int hash, K key, V value, int bucketIndex) {    Entry<K,V> e = table[bucketIndex];    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);    //查看當(dāng)前的size是否超過了我們設(shè)定的閾值threshold，如果超過，需要resize    if (size++ >= threshold) {       resize(2 * table.length);    }}

如果現(xiàn)在 size 已經(jīng)超過了 threshold，那么就要進(jìn)行 resize 操作。新建一個(gè)更大尺寸的 hash 表，然后把數(shù)據(jù)從老的 Hash 表中遷移到新的 Hash 表中。

調(diào)整 Hash 表大小 resize：

void resize(int newCapacity) {    Entry[] oldTable = table;    int oldCapacity = oldTable.length;    // ......    //創(chuàng)建一個(gè)新的Hash Table    Entry[] newTable = new Entry[newCapacity];    //將Old Hash Table上的數(shù)據(jù)遷移到New Hash Table上    transfer(newTable);    table = newTable;    threshold = (int)(newCapacity * loadFactor);}

當(dāng) table[] 數(shù)組容量較小，容易產(chǎn)生哈希碰撞。所以，Hash 表的尺寸和容量非常的重要。

一般來說，Hash 表這個(gè)容器當(dāng)有數(shù)據(jù)要插入時(shí)，都會檢查容量有沒有超過設(shè)定的 thredhold。如果超過，需要增大 Hash 表的尺寸，這個(gè)過程稱為 resize。

多個(gè)線程同時(shí)往 HashMap 添加新元素時(shí)，多次 resize 會有一定概率出現(xiàn)死循環(huán)。因?yàn)槊看?resize 需要把舊的數(shù)據(jù)映射到新的哈希表，這一部分代碼在 HashMap#transfer()  方法中：

void transfer(Entry[] newTable) {    Entry[] src = table;    int newCapacity = newTable.length;    //下面這段代碼的意思是：    //從OldTable里摘一個(gè)元素出來，然后放到NewTable中    for (int j = 0; j < src.length; j++) {       Entry<K,V> e = src[j];       if (e != null) {          src[j] = null;          do {             Entry<K,V> next = e.next; //取出第一個(gè)元素             int i = indexFor(e.hash, newCapacity);             e.next = newTable[i];             newTable[i] = e;             e = next;          } while (e != null);       }    }}

標(biāo)紅代碼是導(dǎo)致多線程使用 hashmap 出現(xiàn) CPU 使用率驟增，出現(xiàn)死循環(huán)，從而多個(gè)線程阻塞的罪魁禍?zhǔn)住?/span>

3、圖解 HashMap 死循環(huán)

3.1 正常的 reHash 的過程（單線程）

假設(shè)了我們的 hash 算法就是簡單的用 key mod 一下表的大小（也就是數(shù)組的長度）。

最上面的是 old hash 表，其中的 Hash 表的 size=2,。所以 key = 3, 7, 5，在 mod 2 以后都沖突在 table[1] 這里了。

接下來的三個(gè)步驟是 Hash 表 resize 成 4，然后所有的 <key,value> 重新 rehash 的過程。

3.2 并發(fā)下的Rehash（多線程）

假設(shè)我們有兩個(gè)線程。

 do {    Entry<K,V> next = e.next; // <--假設(shè)線程一執(zhí)行到這里就被調(diào)度掛起了，執(zhí)行其他操作    int i = indexFor(e.hash, newCapacity);    e.next = newTable[i];    newTable[i] = e;    e = next; } while (e != null);

而我們的線程二執(zhí)行完成了。于是我們有下面這張圖：

注意：因?yàn)?Thread1 的 e 指向了 key(3)，而 next 指向了 key(7)，其在線程二 rehash 后，指向了線程二重組后的鏈表。我們可以看到，鏈表的順序被反轉(zhuǎn)后，在這里線程一變成了操作經(jīng)過線程二操作后的 HashMap。

線程一調(diào)度執(zhí)行。

• 先是執(zhí)行 newTalbe[i] = e；
• 然后是 e = next，導(dǎo)致了 e 指向了 key(7)；
• 而下一次循環(huán)的 next = e.next 導(dǎo)致了 next 指向了 key(3)。

一切安好。

線程一接著工作。把 key(7) 摘下來，放到 newTable[i] 的第一個(gè)。然后把 e 和 next 往下移。

這個(gè)元素所在的位置上已經(jīng)存放有其他元素了，那么在同一個(gè)位置上的元素將以鏈表的形式存放。新加入的放在鏈頭，而先前加入的放在鏈尾。

環(huán)形鏈接出現(xiàn)：e.next = newTable[i] 導(dǎo)致  key(3).next 指向了 key(7)。

注意：此時(shí)的 key(7).next 已經(jīng)指向了 key(3)， 環(huán)形鏈表就這樣出現(xiàn)了。

于是，當(dāng)我們的線程一調(diào)用到 HashTable.get(11) 時(shí)，悲劇就出現(xiàn)了——Infinite Loop。

這里介紹了在多線程下為什么 HashMap 會出現(xiàn)死循環(huán)。不過在真實(shí)的生產(chǎn)環(huán)境下，不會使用線程不安全的 HashMap。

往
期
推
薦
1、靈魂一問：你的登錄接口真的安全嗎？
2、HashMap 中這些設(shè)計(jì)，絕了~
3、在 IntelliJ IDEA 中這樣使用 Git，賊方便了！
4、計(jì)算機(jī)時(shí)間到底是怎么來的？程序員必看的時(shí)間知識！
5、這些IDEA的優(yōu)化設(shè)置趕緊安排起來，效率提升杠杠的！
6、21 款 yyds 的 IDEA插件
7、真香！用 IDEA 神器看源碼，效率真高！
點(diǎn)分享
點(diǎn)收藏
點(diǎn)點(diǎn)贊
點(diǎn)在看