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

Question

在深入分析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));
        }
    }
}

请解释为什么会出现这种死锁。

Answer 1

正如其他人已经说过的:这不是死锁，而是死循环。不管怎样，问题的核心(和标题)是:为什么会这样？

其他答案在这里没有详细介绍，但我也很想更好地理解这一点。例如，当您更改行时

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

到

map.put(1L, 0L);

然后它不会卡住。同样，问题是为什么。

---

答案是:这很复杂。

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

首先: Map::keySet 返回的集合是内部状态的 View 。 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 时修改 map 会抛出 ConcurrentModificationException .但是 ConcurrentHashMap能够应付这个。它保持一致并且仍然可以迭代，即使结果可能仍然出乎意料 - 就像您的情况一样。

---

得出您观察到的行为的原因:

A hash table (or hash map)基本上是通过计算键的哈希值，并将此键用作应将条目添加到的“桶”的指示器来工作的。当多个键映射到同一个桶时，桶中的条目通常被管理为一个链表。 ConcurrentHashMap也是如此.

以下程序在迭代和修改期间使用一些讨厌的反射 hack 来打印表的内部状态 - 特别是表的“桶”，由节点组成:

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 4294967297 (这是你的 (1L << 32) + 1 )总是以桶 0 结尾，并且它们作为链表进行维护。所以对 keySet 的迭代从这张表开始:

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被删除并重新插入，使表进入与最初相同的状态。

这就是无限循环的由来。

---

与此相反，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最终进入不同的桶。因此，不存在可以追加删除(和添加)元素的链表，循环在遍历相关元素(即前两个桶)一次后终止。