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

Question

在深入分析的时候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));        }    }}请解释为什么会出现这种僵局。

Answer 1

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

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

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

到

map.put(1L, 0L);

那么它就不会卡住。再一次，问题是为什么。

---

答案是：很复杂。

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

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

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

^{（本人强调）}

但是，JavaDocConcurrentHashMap::keySet说：

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

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

通常，在遍历 时修改地图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位于不同的桶中。因此，不存在可以追加删除（和添加）元素的链表，循环在遍历相关元素（即前两个桶）一次后终止。

Answer 2

没有僵局。您只是陷入了无限循环。key当我运行这段代码（并在循环中打印）时，控制台反复显示：

0

4294967297

0

4294967297

0

...

如果你创建了map一个HashMap实例，你会看到代码引发了一个ConcurrentModificationException. 所以你只是在修改映射的同时遍历它的键，并且ConcurrentHashMap不会抛出并发修改异常，从而使你的循环无休止。

Answer 3

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

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

以下是文档的摘录map.keySet()：

该集合由地图支持，因此对地图的更改会反映在集合中，反之亦然。如果在对集合进行迭代时修改映射（通过迭代器自己的删除操作除外），则迭代的结果是不确定的。

Answer 4

无限循环的原因是以下因素的组合

1. 地图条目如何在内部存储

2. 密钥迭代器如何工作

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

在循环中添加的所有项目最终都在同一个桶中 - 第一个 - 我们的迭代器已经消耗的那个。

Answer 5

没有死锁。死锁是当两个（或更多）线程互相阻塞时。很明显，你这里只有一个主线程。