在深入分析的時候ConcurrentHashMap，發(fā)現(xiàn)網(wǎng)上有一篇博文說evenConcurrentHashMap可能會陷入死循環(huán)。它給出了這個例子。當(dāng)我運行這段代碼時——它卡住了：public class Test { public static void main(String[] args) throws Exception { Map<Long, Long> map = new ConcurrentHashMap<>(); map.put(0L, 0L); map.put((1L << 32) + 1, 0L); for (long key : map.keySet()) { map.put(key, map.remove(key)); } }}請解釋為什么會出現(xiàn)這種僵局。
5 回答
UYOU
TA貢獻(xiàn)1878條經(jīng)驗 獲得超4個贊
正如其他人已經(jīng)說過的：這不是死鎖，而是無限循環(huán)。不管怎樣，問題的核心（和標(biāo)題）是：為什么會這樣？
其他答案在這里沒有詳細(xì)介紹，但我也很想更好地理解這一點。例如，當(dāng)您更改行
map.put((1L << 32) + 1, 0L);
到
map.put(1L, 0L);
那么它就不會卡住。再一次，問題是為什么。
答案是：很復(fù)雜。
它是并發(fā)/集合框架中最復(fù)雜的類之一，代碼高達(dá) 6300 行，其中 230 行注釋僅解釋了實現(xiàn)的ConcurrentHashMap基本概念，以及為什么神奇且難以閱讀的代碼實際有效。以下是相當(dāng)簡化的，但至少應(yīng)該解釋基本問題。
首先：返回的集合Map::keySet是內(nèi)部狀態(tài)的視圖。JavaDoc 說：
返回此映射中包含的鍵的 Set 視圖。該集合由地圖支持，因此對地圖的更改會反映在集合中，反之亦然。如果在對集合進行迭代時修改映射（除了通過迭代器自己的刪除操作），迭代的結(jié)果是不確定的。 該集支持刪除元素，[...]
（本人強調(diào)）
但是，JavaDocConcurrentHashMap::keySet說：
返回此映射中包含的鍵的 Set 視圖。該集合由地圖支持，因此對地圖的更改會反映在集合中，反之亦然。該集支持刪除元素，[...]
（注意它沒有提到未定義的行為！）
通常，在遍歷 時修改地圖keySet會拋出一個ConcurrentModificationException. 但是ConcurrentHashMap能夠應(yīng)付這個。它保持一致并且仍然可以迭代，即使結(jié)果可能仍然出乎意料 - 就像你的情況一樣。
得出您觀察到的行為的原因：
哈希表（或哈希映射）的工作原理基本上是根據(jù)鍵計算哈希值，并將該鍵用作應(yīng)將條目添加到的“桶”的指示符。當(dāng)多個key映射到同一個bucket時，bucket中的entries通常以鏈表的形式進行管理。的情況也是如此ConcurrentHashMap。
以下程序在迭代和修改期間使用一些討厭的反射黑客來打印表的內(nèi)部狀態(tài) - 特別是表的“桶”，由節(jié)點組成：
import java.lang.reflect.Array;
import java.lang.reflect.Field;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
public class MapLoop
{
public static void main(String[] args) throws Exception
{
runTestInfinite();
runTestFinite();
}
private static void runTestInfinite() throws Exception
{
System.out.println("Running test with inifinite loop");
Map<Long, Long> map = new ConcurrentHashMap<>();
map.put(0L, 0L);
map.put((1L << 32) + 1, 0L);
int counter = 0;
for (long key : map.keySet())
{
map.put(key, map.remove(key));
System.out.println("Infinite, counter is "+counter);
printTable(map);
counter++;
if (counter == 10)
{
System.out.println("Bailing out...");
break;
}
}
System.out.println("Running test with inifinite loop DONE");
}
private static void runTestFinite() throws Exception
{
System.out.println("Running test with finite loop");
Map<Long, Long> map = new ConcurrentHashMap<>();
map.put(0L, 0L);
map.put(1L, 0L);
int counter = 0;
for (long key : map.keySet())
{
map.put(key, map.remove(key));
System.out.println("Finite, counter is "+counter);
printTable(map);
counter++;
}
System.out.println("Running test with finite loop DONE");
}
private static void printTable(Map<Long, Long> map) throws Exception
{
// Hack, to illustrate the issue here:
System.out.println("Table now: ");
Field fTable = ConcurrentHashMap.class.getDeclaredField("table");
fTable.setAccessible(true);
Object t = fTable.get(map);
int n = Array.getLength(t);
for (int i = 0; i < n; i++)
{
Object node = Array.get(t, i);
printNode(i, node);
}
}
private static void printNode(int index, Object node) throws Exception
{
if (node == null)
{
System.out.println("at " + index + ": null");
return;
}
// Hack, to illustrate the issue here:
Class<?> c =
Class.forName("java.util.concurrent.ConcurrentHashMap$Node");
Field fHash = c.getDeclaredField("hash");
fHash.setAccessible(true);
Field fKey = c.getDeclaredField("key");
fKey.setAccessible(true);
Field fVal = c.getDeclaredField("val");
fVal.setAccessible(true);
Field fNext = c.getDeclaredField("next");
fNext.setAccessible(true);
System.out.println(" at " + index + ":");
System.out.println(" hash " + fHash.getInt(node));
System.out.println(" key " + fKey.get(node));
System.out.println(" val " + fVal.get(node));
System.out.println(" next " + fNext.get(node));
}
}
該runTestInfinite案例的輸出如下（省略多余部分）：
Running test with infinite loop
Infinite, counter is 0
Table now:
at 0:
hash 0
key 4294967297
val 0
next 0=0
at 1: null
at 2: null
...
at 14: null
at 15: null
Infinite, counter is 1
Table now:
at 0:
hash 0
key 0
val 0
next 4294967297=0
at 1: null
at 2: null
...
at 14: null
at 15: null
Infinite, counter is 2
Table now:
at 0:
hash 0
key 4294967297
val 0
next 0=0
at 1: null
at 2: null
...
at 14: null
at 15: null
Infinite, counter is 3
...
Infinite, counter is 9
...
Bailing out...
Running test with infinite loop DONE
0可以看到 key和 key 4294967297（你的）的條目(1L << 32) + 1總是以 bucket 0 結(jié)尾，并且它們被維護為一個鏈表。所以迭代從keySet這張表開始：
Bucket : Contents
0 : 0 --> 4294967297
1 : null
... : ...
15 : null
在第一次迭代中，它刪除了 key 0，基本上將表變成了這個：
Bucket : Contents
0 : 4294967297
1 : null
... : ...
15 : null
但是之后會立即添加密鑰0，并且它在與 - 相同的存儲桶中結(jié)束，4294967297因此它被附加在列表的末尾：
Bucket : Contents
0 : 4294967297 -> 0
1 : null
... : ...
15 : null
（這由next 0=0輸出的一部分指示）。
在下一次迭代中，4294967297刪除并重新插入，使表恢復(fù)到最初的狀態(tài)。
這就是你的無限循環(huán)的來源。
與此相反，案例的輸出runTestFinite是這樣的：
Running test with finite loop
Finite, counter is 0
Table now:
at 0:
hash 0
key 0
val 0
next null
at 1:
hash 1
key 1
val 0
next null
at 2: null
...
at 14: null
at 15: null
Finite, counter is 1
Table now:
at 0:
hash 0
key 0
val 0
next null
at 1:
hash 1
key 1
val 0
next null
at 2: null
...
at 14: null
at 15: null
Running test with finite loop DONE
可以看到密鑰0最終1位于不同的桶中。因此，不存在可以追加刪除（和添加）元素的鏈表，循環(huán)在遍歷相關(guān)元素（即前兩個桶）一次后終止。
慕勒3428872
TA貢獻(xiàn)1848條經(jīng)驗 獲得超6個贊
沒有僵局。您只是陷入了無限循環(huán)。key當(dāng)我運行這段代碼（并在循環(huán)中打?。r，控制臺反復(fù)顯示：
0
4294967297
0
4294967297
0
...
如果你創(chuàng)建了map一個HashMap實例，你會看到代碼引發(fā)了一個ConcurrentModificationException. 所以你只是在修改映射的同時遍歷它的鍵，并且ConcurrentHashMap不會拋出并發(fā)修改異常，從而使你的循環(huán)無休止。
慕萊塢森
TA貢獻(xiàn)1810條經(jīng)驗 獲得超4個贊
我不認(rèn)為這與提供的線程安全有任何關(guān)系ConcurrentHashMap。它甚至看起來根本不像死鎖，而是一個無限循環(huán)。
這是由于映射在迭代鍵集時被修改，鍵集由同一個映射支持！
以下是文檔的摘錄map.keySet()：
該集合由地圖支持，因此對地圖的更改會反映在集合中，反之亦然。如果在對集合進行迭代時修改映射（通過迭代器自己的刪除操作除外），則迭代的結(jié)果是不確定的。
浮云間
TA貢獻(xiàn)1829條經(jīng)驗 獲得超4個贊
無限循環(huán)的原因是以下因素的組合
地圖條目如何在內(nèi)部存儲
密鑰迭代器如何工作
1個
映射條目存儲為一個鏈表數(shù)組：transient volatile Node<K,V>[] table
每個映射條目都將基于其 hash() 結(jié)束于該數(shù)組中的一個鏈表中hash % table.length：
//simplified pseudocode
public V put(K key, V value) {
int hash = computeHash(key) % table.length
Node<K,V> linkedList = table[hash]
linkedList.add(new Node(key, value))
}
具有相同散列值的 2 個鍵（如 0 和 4294967297）將出現(xiàn)在同一個列表中
2個
迭代器的工作非常簡單：一個接一個地迭代條目。
鑒于內(nèi)部存儲基本上是集合的集合，它遍歷table[0]列表中的所有條目，等等table[1]。但是有一個實現(xiàn)細(xì)節(jié)使我們的示例僅針對具有哈希沖突的映射永遠(yuǎn)運行：
public final K next() {
Node<K,V> p;
if ((p = next) == null)
throw new NoSuchElementException();
K k = p.key;
lastReturned = p;
advance();
return k;
}
next ()方法實現(xiàn)返回一個之前預(yù)先計算的值，并計算要在將來調(diào)用時返回的值。當(dāng)?shù)鞅粚嵗瘯r，它收集第一個元素，當(dāng)next()第一次被調(diào)用時，它收集第二個元素并返回第一個。
這是該方法的相關(guān)代碼advance()：
Node<K,V>[] tab; // current table; updated if resized
Node<K,V> next; // the next entry to use
. . .
final Node<K,V> advance() {
Node<K,V> e;
if ((e = next) != null)
e = e.next;
for (;;) {
Node<K,V>[] t; int i, n;
if (e != null)
return next = e; // our example will always return here
. . .
}
}
以下是我們地圖的內(nèi)部狀態(tài)是如何演變的：
Map<Long, Long> map = new ConcurrentHashMap<>();
[ null, null, ... , null ]所有桶（鏈表）都是空的
map.put(0L, 0L);
[ 0:0, null, ... , null ]第一個桶有一個條目
map.put((1L << 32) + 1, 0L);
[ 0:0 -> 4294967297:0, null, ... , null ]第一個桶現(xiàn)在有兩個條目
第一次迭代，迭代器返回0并將4294967297:0條目保存為next
map.remove(0)
[ 4294967297:0, null, ... , null ]
map.put(0, 0) // the entry our iterator holds has its next pointer modified
[ 4294967297:0 -> 0:0, null, ... , null ]
第二次迭代
map.remove(4294967297)
[ 0:0, null, ... , null ]
map.put(4294967297, 0)
[ 0:0 -> 4294967297:0, null, ... , null ]
所以在 2 次迭代之后我們回到了開始的位置，因為我們的操作歸結(jié)為從鏈表的頭部刪除一個項目并將其添加到它的尾部，因此我們無法完成消費。
對于沒有散列沖突的映射，它不會陷入無限循環(huán)，因為我們添加的鏈表已經(jīng)被迭代器留下了。
這是一個證明它的例子：
Map<Long, Long> map = new ConcurrentHashMap<>();
map.put(0L, 0L);
map.put(1L, 0L);
int iteration = 0;
for (long key : map.keySet()) {
map.put((1L << 32) + 1, 0L);
map.put((1L << 33) + 2, 0L);
map.put((1L << 34) + 4, 0L);
System.out.printf("iteration:%d key:%d map size:%d %n", ++iteration, key, map.size());
map.put(key, map.remove(key));
}
輸出是：
iteration:1 key:0 map size:5
iteration:2 key:1 map size:5
在循環(huán)中添加的所有項目最終都在同一個桶中 - 第一個 - 我們的迭代器已經(jīng)消耗的那個。
添加回答
舉報
0/150
提交
取消