ConcurrentHashMap陷入无限循环 - 为什么？

正如其他人已经说过的那样：这不是一个死锁，而是一个无限循环。无论如何，问题的核心（和标题）是：为什么会发生这种情况？

其他答案在这里没有太多细节，但我也很好奇地更好地理解这一点。例如，当您更改线条时

map.put((1L << 32) + 1, 0L);

自

map.put(1L, 0L);

然后它不会卡住。再说一遍，问题是为什么。

答案是：这很复杂。

^{ConcurrentHashMap是并发/集合框架中最复杂的类之一，有高达6300行代码，230行注释只解释了实现的基本概念，以及为什么神奇和不可读的代码实际上有效。以下内容相当简化，但至少应该解释基本问题。}

首先：Map：：keySet 返回的集合是内部状态的视图。JavaDoc说：

返回此映射中包含的键的 Set 视图。集合由地图支持，因此对地图的更改将反映在集合中，反之亦然。如果在对集合进行迭代时修改映射（除非通过迭代器自己的移除操作），则迭代的结果未定义。该集合支持元素删除，[...]

^{（强调我）}

但是，ConcurrentHashMap：：keySet 的 JavaDoc 说：

返回此映射中包含的键的 Set 视图。集合由地图支持，因此对地图的更改将反映在集合中，反之亦然。该集合支持元素删除，[...]

^{（请注意，它没有提到未定义的行为！}

通常，在迭代 时修改映射会抛出一个 .但是能够应付这个。它保持一致，仍然可以迭代，即使结果可能仍然是出乎意料的 - 就像您的情况一样。keySetConcurrentModificationExceptionConcurrentHashMap

关于您观察到的行为的原因：

哈希表（或哈希映射）的工作原理基本上是从密钥计算哈希值，并将此密钥用作应将条目添加到的“存储桶”的指示器。当多个键映射到同一存储桶时，存储桶中的条目通常作为链接列表进行管理。的情况也是如此。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 结尾，并且它们作为链表进行维护。因此，迭代从此表开始：04294967297(1L << 32) + 1keySet

Bucket   :   Contents
   0     :   0 --> 4294967297
   1     :   null
  ...    :   ...
  15     :   null

在第一次迭代中，它删除了键，基本上将表转换为此表：0

Bucket   :   Contents
   0     :   4294967297
   1     :   null
  ...    :   ...
  15     :   null

但是该键在之后会立即添加，并且它结束于与 - 相同的存储桶中，因此它被附加到列表的末尾：04294967297

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

人们可以看到，键和最终在不同的桶中。因此，没有可以将已删除（和添加）的元素追加到的链接列表，并且循环在循环访问相关元素（即前两个存储桶）一次后终止。01

我不认为这与提供的线程安全性有任何关系。它甚至看起来根本不像一个死锁，而是一个无限循环。ConcurrentHashMap

这是由于在迭代键集时修改了映射，该键集由同一映射支持！

以下是 map.keySet（） 文档的摘录：

集合由地图支持，因此对地图的更改将反映在集合中，反之亦然。如果在对集合进行迭代时修改映射（除非通过迭代器自己的移除操作），则迭代的结果未定义。