在深入分析的時候ConcurrentHashMap，發現網上有一篇博文說evenConcurrentHashMap可能會陷入死循環。它給出了這個例子。當我運行這段代碼時——它卡住了：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)); } }}請解釋為什么會出現這種僵局。
5 回答
UYOU
TA貢獻1878條經驗 獲得超4個贊
正如其他人已經說過的：這不是死鎖，而是無限循環。不管怎樣，問題的核心（和標題）是：為什么會這樣？
其他答案在這里沒有詳細介紹，但我也很想更好地理解這一點。例如，當您更改行
map.put((1L << 32) + 1, 0L);
到
map.put(1L, 0L);
那么它就不會卡住。再一次，問題是為什么。
答案是：很復雜。
它是并發/集合框架中最復雜的類之一，代碼高達 6300 行，其中 230 行注釋僅解釋了實現的ConcurrentHashMap基本概念，以及為什么神奇且難以閱讀的代碼實際有效。以下是相當簡化的，但至少應該解釋基本問題。
首先：返回的集合Map::keySet是內部狀態的視圖。JavaDoc 說：
返回此映射中包含的鍵的 Set 視圖。該集合由地圖支持，因此對地圖的更改會反映在集合中，反之亦然。如果在對集合進行迭代時修改映射（除了通過迭代器自己的刪除操作），迭代的結果是不確定的。 該集支持刪除元素，[...]
（本人強調）
但是，JavaDocConcurrentHashMap::keySet說：
返回此映射中包含的鍵的 Set 視圖。該集合由地圖支持，因此對地圖的更改會反映在集合中，反之亦然。該集支持刪除元素，[...]
（注意它沒有提到未定義的行為?。?/sup>
通常，在遍歷 時修改地圖keySet會拋出一個ConcurrentModificationException. 但是ConcurrentHashMap能夠應付這個。它保持一致并且仍然可以迭代，即使結果可能仍然出乎意料 - 就像你的情況一樣。
得出您觀察到的行為的原因：
哈希表（或哈希映射）的工作原理基本上是根據鍵計算哈希值，并將該鍵用作應將條目添加到的“桶”的指示符。當多個key映射到同一個bucket時，bucket中的entries通常以鏈表的形式進行管理。的情況也是如此ConcurrentHashMap。
以下程序在迭代和修改期間使用一些討厭的反射黑客來打印表的內部狀態 - 特別是表的“桶”，由節點組成：
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 結尾，并且它們被維護為一個鏈表。所以迭代從keySet這張表開始：
Bucket : Contents
0 : 0 --> 4294967297
1 : null
... : ...
15 : null
在第一次迭代中，它刪除了 key 0，基本上將表變成了這個：
Bucket : Contents
0 : 4294967297
1 : null
... : ...
15 : null
但是之后會立即添加密鑰0，并且它在與 - 相同的存儲桶中結束，4294967297因此它被附加在列表的末尾：
Bucket : Contents
0 : 4294967297 -> 0
1 : null
... : ...
15 : null
（這由next 0=0輸出的一部分指示）。
在下一次迭代中，4294967297刪除并重新插入，使表恢復到最初的狀態。
這就是你的無限循環的來源。
與此相反，案例的輸出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位于不同的桶中。因此，不存在可以追加刪除（和添加）元素的鏈表，循環在遍歷相關元素（即前兩個桶）一次后終止。
慕勒3428872
TA貢獻1848條經驗 獲得超6個贊
沒有僵局。您只是陷入了無限循環。key當我運行這段代碼（并在循環中打印）時，控制臺反復顯示：
0
4294967297
0
4294967297
0
...
如果你創建了map一個HashMap實例，你會看到代碼引發了一個ConcurrentModificationException. 所以你只是在修改映射的同時遍歷它的鍵，并且ConcurrentHashMap不會拋出并發修改異常，從而使你的循環無休止。
慕萊塢森
TA貢獻1810條經驗 獲得超4個贊
我不認為這與提供的線程安全有任何關系ConcurrentHashMap。它甚至看起來根本不像死鎖，而是一個無限循環。
這是由于映射在迭代鍵集時被修改，鍵集由同一個映射支持！
以下是文檔的摘錄map.keySet()：
該集合由地圖支持，因此對地圖的更改會反映在集合中，反之亦然。如果在對集合進行迭代時修改映射（通過迭代器自己的刪除操作除外），則迭代的結果是不確定的。
浮云間
TA貢獻1829條經驗 獲得超4個贊
無限循環的原因是以下因素的組合
地圖條目如何在內部存儲
密鑰迭代器如何工作
1個
映射條目存儲為一個鏈表數組：transient volatile Node<K,V>[] table
每個映射條目都將基于其 hash() 結束于該數組中的一個鏈表中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）將出現在同一個列表中
2個
迭代器的工作非常簡單：一個接一個地迭代條目。
鑒于內部存儲基本上是集合的集合，它遍歷table[0]列表中的所有條目，等等table[1]。但是有一個實現細節使我們的示例僅針對具有哈希沖突的映射永遠運行：
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 ()方法實現返回一個之前預先計算的值，并計算要在將來調用時返回的值。當迭代器被實例化時，它收集第一個元素，當next()第一次被調用時，它收集第二個元素并返回第一個。
這是該方法的相關代碼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
. . .
}
}
以下是我們地圖的內部狀態是如何演變的：
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 ]第一個桶現在有兩個條目
第一次迭代，迭代器返回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 次迭代之后我們回到了開始的位置，因為我們的操作歸結為從鏈表的頭部刪除一個項目并將其添加到它的尾部，因此我們無法完成消費。
對于沒有散列沖突的映射，它不會陷入無限循環，因為我們添加的鏈表已經被迭代器留下了。
這是一個證明它的例子：
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
在循環中添加的所有項目最終都在同一個桶中 - 第一個 - 我們的迭代器已經消耗的那個。
添加回答
舉報
0/150
提交
取消