ConcurrentHashMap 陷入无限循环 - 为什么？
ConcurrentHashMap stuck in infinite loop - Why?
在对ConcurrentHashMap进行深入分析时，在互联网上发现一篇博客post，上面说即使ConcurrentHashMap也可能陷入死循环。
给出了这个例子。当我 运行 这段代码时 - 它卡住了：
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));
}
}
}
请解释为什么会出现这种死锁。
我不认为这与 ConcurrentHashMap 提供的线程安全有任何关系。它甚至根本不像死锁，而是一个无限循环。
这是因为在遍历键集时映射被修改，这是由同一个映射支持的！
以下是 map.keySet() 文档的摘录：
The set is backed by the map, so changes to the map are reflected in
the set, and vice-versa. If the map is modified while an iteration
over the set is in progress (except through the iterator's own remove
operation), the results of the iteration are undefined.
没有死锁。您只是 运行 陷入了无限循环。当我 运行 这段代码（并在循环中打印 key ）时，控制台重复显示：
0
4294967297
0
4294967297
0
...
如果您将 map 设为 HashMap 实例，您会看到代码引发 ConcurrentModificationException。所以你只是在修改映射的同时遍历它的键，ConcurrentHashMap 不会抛出并发修改异常，从而使你的循环无休止。
没有deadlock.A死锁是两个（或多个）线程各自阻塞other.obvious，你这里只有一个主线程
正如其他人已经说过的：这不是死锁，而是死循环。不管怎样，问题的核心（和标题）是：为什么会这样？
其他答案在这里没有详细介绍，但我也很想更好地理解这一点。例如，当您更改行
map.put((1L << 32) + 1, 0L);
到
map.put(1L, 0L);
那么它不会卡住。同样，问题是 为什么 .
答案是：很复杂。
ConcurrentHashMap是concurrent/collections框架中最复杂的类之一，代码高达6300行，只有230行注释解释实施的基本概念，以及为什么神奇且难以阅读的代码实际上有效。以下是相当简化的，但至少应该解释 basic 问题。
首先：Map::keySet返回的集合是内部状态的视图。 JavaDoc 说：
Returns a Set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress (except through the iterator's own remove operation), the results of the iteration are undefined. The set supports element removal, [...]
(本人强调)
然而，ConcurrentHashMap::keySet 的 JavaDoc 说：
Returns a Set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. The set supports element removal, [...]
（注意它没有提到未定义的行为！）
通常，在遍历 keySet 时修改地图会抛出 ConcurrentModificationException。但是 ConcurrentHashMap 能够应付这个。它保持一致并且仍然可以迭代，即使结果可能仍然出乎意料 - 就像您的情况一样。
得出您观察到的行为的原因：
A hash table (or hash map) 基本上是通过从键计算散列值，并将此键用作应添加条目的 "bucket" 的指示符来工作的。当多个键映射到同一个桶时，桶中的条目通常被管理为一个链表。 ConcurrentHashMap也是如此。
以下程序使用一些讨厌的反射技巧来打印 table 的内部状态 - 特别是 table 的 "buckets"，由节点组成 - 在迭代期间和修改：
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 和键 4294967297（这是您的 (1L << 32) + 1）的条目总是以存储桶 0 结尾，并且它们作为链接进行维护列表。所以 keySet 的迭代从这个 table:
开始
Bucket : Contents
0 : 0 --> 4294967297
1 : null
... : ...
15 : null
在第一次迭代中，它删除了键 0，基本上将 table 变成了这个：
Bucket : Contents
0 : 4294967297
1 : null
... : ...
15 : null
但是键 0 是在之后立即添加的，它在与 4294967297 相同的桶中结束 - 所以它被附加在列表的末尾：
Bucket : Contents
0 : 4294967297 -> 0
1 : null
... : ...
15 : null
（这由输出的 next 0=0 部分指示）。
在下一次迭代中，4294967297 被删除并 re-inserted，使 table 进入与最初相同的状态。
这就是无限循环的来源。
与此相反，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 最终出现在 不同的 桶中。因此，不存在可以追加删除（和添加）元素的链表，循环在遍历相关元素（即前两个桶）一次后终止。
无限循环的原因是
的组合
- 内部如何存储映射条目
- 密钥迭代器如何工作
1
地图条目存储为链表数组：
transient volatile Node<K,V>[] table
根据其散列 (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 个带有 same hash 的键（例如 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() 方法实现 returns 之前是 pre-computed 的值，并计算要在将来调用时返回的值。实例化迭代器时，它收集第一个元素，当第一次调用 next() 时，它收集第二个元素，returns 收集第一个元素。
这是 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 ] 第一个桶现在有两个条目
第 1 次迭代，迭代器 returns 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
在循环中添加的所有项目最终都在同一个桶中 - 第一个 - 我们的迭代器已经消耗的那个。
在对ConcurrentHashMap进行深入分析时，在互联网上发现一篇博客post，上面说即使ConcurrentHashMap也可能陷入死循环。
给出了这个例子。当我 运行 这段代码时 - 它卡住了：
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));
}
}
}
请解释为什么会出现这种死锁。
我不认为这与 ConcurrentHashMap 提供的线程安全有任何关系。它甚至根本不像死锁，而是一个无限循环。
这是因为在遍历键集时映射被修改，这是由同一个映射支持的！
以下是 map.keySet() 文档的摘录：
The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress (except through the iterator's own remove operation), the results of the iteration are undefined.
没有死锁。您只是 运行 陷入了无限循环。当我 运行 这段代码（并在循环中打印 key ）时，控制台重复显示：
0
4294967297
0
4294967297
0
...
如果您将 map 设为 HashMap 实例，您会看到代码引发 ConcurrentModificationException。所以你只是在修改映射的同时遍历它的键，ConcurrentHashMap 不会抛出并发修改异常，从而使你的循环无休止。
没有deadlock.A死锁是两个（或多个）线程各自阻塞other.obvious，你这里只有一个主线程
正如其他人已经说过的：这不是死锁，而是死循环。不管怎样，问题的核心（和标题）是：为什么会这样？
其他答案在这里没有详细介绍，但我也很想更好地理解这一点。例如，当您更改行
map.put((1L << 32) + 1, 0L);
到
map.put(1L, 0L);
那么它不会卡住。同样，问题是 为什么 .
答案是：很复杂。
ConcurrentHashMap是concurrent/collections框架中最复杂的类之一，代码高达6300行，只有230行注释解释实施的基本概念，以及为什么神奇且难以阅读的代码实际上有效。以下是相当简化的，但至少应该解释 basic 问题。
首先：Map::keySet返回的集合是内部状态的视图。 JavaDoc 说：
Returns a Set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress (except through the iterator's own remove operation), the results of the iteration are undefined. The set supports element removal, [...]
(本人强调)
然而，ConcurrentHashMap::keySet 的 JavaDoc 说：
Returns a Set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. The set supports element removal, [...]
（注意它没有提到未定义的行为！）
通常，在遍历 keySet 时修改地图会抛出 ConcurrentModificationException。但是 ConcurrentHashMap 能够应付这个。它保持一致并且仍然可以迭代，即使结果可能仍然出乎意料 - 就像您的情况一样。
得出您观察到的行为的原因：
A hash table (or hash map) 基本上是通过从键计算散列值，并将此键用作应添加条目的 "bucket" 的指示符来工作的。当多个键映射到同一个桶时，桶中的条目通常被管理为一个链表。 ConcurrentHashMap也是如此。
以下程序使用一些讨厌的反射技巧来打印 table 的内部状态 - 特别是 table 的 "buckets"，由节点组成 - 在迭代期间和修改：
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 和键 4294967297（这是您的 (1L << 32) + 1）的条目总是以存储桶 0 结尾，并且它们作为链接进行维护列表。所以 keySet 的迭代从这个 table:
Bucket : Contents
0 : 0 --> 4294967297
1 : null
... : ...
15 : null
在第一次迭代中，它删除了键 0，基本上将 table 变成了这个：
Bucket : Contents
0 : 4294967297
1 : null
... : ...
15 : null
但是键 0 是在之后立即添加的，它在与 4294967297 相同的桶中结束 - 所以它被附加在列表的末尾：
Bucket : Contents
0 : 4294967297 -> 0
1 : null
... : ...
15 : null
（这由输出的 next 0=0 部分指示）。
在下一次迭代中，4294967297 被删除并 re-inserted，使 table 进入与最初相同的状态。
这就是无限循环的来源。
与此相反，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 最终出现在 不同的 桶中。因此，不存在可以追加删除（和添加）元素的链表，循环在遍历相关元素（即前两个桶）一次后终止。
无限循环的原因是
的组合- 内部如何存储映射条目
- 密钥迭代器如何工作
1
地图条目存储为链表数组：
transient volatile Node<K,V>[] table
根据其散列 (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 个带有 same hash 的键（例如 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() 方法实现 returns 之前是 pre-computed 的值，并计算要在将来调用时返回的值。实例化迭代器时，它收集第一个元素，当第一次调用 next() 时，它收集第二个元素，returns 收集第一个元素。
这是 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 ] 第一个桶现在有两个条目
第 1 次迭代，迭代器 returns 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
在循环中添加的所有项目最终都在同一个桶中 - 第一个 - 我们的迭代器已经消耗的那个。