在对ConcurrentHashMap进行深入分析时，发现互联网上有一篇博客文章称，即使是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));
}
}
}
正如其他人已经说过的：这不是死锁，而是一个无限循环。尽管如此，该问题的核心（和标题）是：为什么会发生这种情况？
其他答案在这里没有详细说明，但我也很想更好地理解这一点。例如，当您更改以下行时：
map.put((1L << 32) + 1, 0L);
to
map.put(1L, 0L);
那么它就不会卡住。问题再次是为什么。
关于你观察到的行为原因：
哈希表（或散列表）的工作原理基本上是通过从键计算哈希值，并使用该键作为指示符将条目添加到“桶”中。当多个键映射到同一个桶时，通常将桶中的条目管理为链表。对于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和4294967297（即(1L << 32) + 1）的条目始终以桶0结束，并作为链接列表维护。因此，对keySet的迭代从该表开始：Bucket : Contents
0 : 0 --> 4294967297
1 : null
... : ...
15 : null
在第一次迭代中，它移除了键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最终落入了不同的桶中。因此，没有链表可以将已删除（和添加）的元素附加到其中，循环在迭代相关元素（即前两个桶）一次后终止。没有死锁。你只是陷入了一个无限循环。当我运行这段代码时（并在循环中打印key），控制台会不断地显示：
没有死锁。你只是进入了一个无限循环。当我运行这段代码时（并在循环中打印key），控制台会一遍又一遍地显示：
0
4294967297
0
4294967297
0
...
如果你将map设为HashMap实例，你会发现代码会触发一个ConcurrentModificationException异常。所以你只是在遍历它的键时修改了这个映射表，而ConcurrentHashMap不会抛出并发修改异常，从而使你的循环无限进行。
transient volatile Node<K,V>[] tablehash % 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))
}
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);
map.remove(0)
[ 4294967297:0, null, ... , null ]
map.put(0, 0) // the entry our iterator holds has its next pointer modified
map.remove(4294967297)
[ 0:0，null，...，null ]
map.put(4294967297, 0)
[ 0:0 -> 4294967297:0, null, ... , null ]
经过两次迭代，我们回到了起点，因为我们的操作归结为从链表头部删除项目并将其添加到尾部，因此我们无法完成消耗。
如果没有哈希冲突的映射，它不会陷入无限循环，因为我们添加到的链表已经被迭代器留下。
以下是一个证明它的示例：
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));
}
迭代次数：1 键值：0 映射大小：5迭代次数：2 键值：1 映射大小：5
循环中添加的所有项都会进入同一个桶中——第一个桶——这是我们的迭代器已经消耗的那个桶。
没有死锁。死锁是指两个（或多个）线程互相阻塞。显然，在这里你只有一个主线程。