今天想知道HashMap為什么在多線程下不安全，找了許多資料，終于理解了。

首先先了解一下HashMap:

HashMap實現(xiàn)的原理是：數(shù)組+鏈表

?

HashMap的size大于等于(容量*加載因子)的時候,會觸發(fā)擴(kuò)容的操作,這個是個代價不小的操作。?

為什么要擴(kuò)容呢?

HashMap默認(rèn)的容量是16,隨著元素不斷添加到HashMap里,出現(xiàn)hash沖突的機(jī)率就更高,那每個桶對應(yīng)的鏈表就會更長,?

這樣會影響查詢的性能,因為每次都需要遍歷鏈表,比較對象是否相等,一直到找到元素為止。

為了提升查詢性能,只能擴(kuò)容,減少hash沖突,讓元素的key盡量均勻的分布。

在單線程中，HashMap是安全的，但是在高并發(fā)的環(huán)境下，會出現(xiàn)不安全，原因在于HashMap的擴(kuò)容。

我們先看下HashMap擴(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);//可能導(dǎo)致環(huán)鏈 table = newTable; threshold = (int)(newCapacity * loadFactor); }

　　

transfer方法就是進(jìn)行HashMap的擴(kuò)容的核心方法：

void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; 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; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } }

在并發(fā)情況下進(jìn)行擴(kuò)容，有一個線程執(zhí)行到

Entry<K,V> next = e.next;

而另外一個線程已經(jīng)執(zhí)行完擴(kuò)容，再等這個線程執(zhí)行完就會出現(xiàn)環(huán)路，并且也會丟失一些節(jié)點。

我查看一下陳皓大神的文章，里面寫的很詳細(xì)：

https://coolshell.cn/articles/9606.html

?

正常的ReHash的過程

畫了個圖做了個演示。

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

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

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

并發(fā)下的Rehash

1）假設(shè)我們有兩個線程。我用紅色和淺藍(lán)色標(biāo)注了一下。

我們再回頭看一下我們的 transfer代碼中的這個細(xì)節(jié)：

1 2 3 4 5 6 7

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

而我們的線程二執(zhí)行完成了。于是我們有下面的這個樣子。

注意，因為Thread1的 e 指向了key(3)，而next指向了key(7)，其在線程二rehash后，指向了線程二重組后的鏈表。我們可以看到鏈表的順序被反轉(zhuǎn)后。

2）線程一被調(diào)度回來執(zhí)行。

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

3）一切安好。

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

4）環(huán)形鏈接出現(xiàn)。

e.next = newTable[i] 導(dǎo)致? key(3).next 指向了 key(7)

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

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

轉(zhuǎn)載于:https://www.cnblogs.com/somelog/p/9299056.html

總結(jié)

以上是生活随笔為你收集整理的Java基础：详解HashMap在多线程下不安全的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。