Ответ 1

Как уже говорили другие: это не тупик, а бесконечный цикл. Независимо от этого, суть (и заголовок) вопроса: почему это происходит?

Другие ответы здесь не вдавались в подробности, но мне было любопытно лучше понять это. Например, когда вы меняете строку

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

в

map.put(1L, 0L);

тогда это не застревает. И снова вопрос в том, почему.

Ответ: это сложно.

^{ConcurrentHashMap - это один из самых сложных классов в среде параллельных вычислений/коллекций, с колоссальными 6300 строками кода, с 230 строками комментариев, объясняющими только базовую концепцию реализации и почему на самом деле работает магический и нечитаемый код.Следующее довольно упрощено, но должно хотя бы объяснить основную проблему.}

Прежде всего: набор, который возвращается Map::keySet является представлением о внутреннем состоянии. И JavaDoc говорит:

Возвращает представление Set ключей, содержащихся в этой карте. Набор опирается на карту, поэтому изменения в карте отражаются в наборе, и наоборот. Если карта изменяется во время выполнения итерации по набору (кроме как через собственную операцию удаления итератора), результаты итерации не определены. Набор поддерживает удаление элементов, [...]

^{(Акцент мной)}

Тем не менее, JavaDoc ConcurrentHashMap::keySet говорит:

Возвращает представление Set ключей, содержащихся в этой карте. Набор опирается на карту, поэтому изменения в карте отражаются в наборе, и наоборот. Набор поддерживает удаление элементов, [...]

^{(Обратите внимание, что здесь не упоминается неопределенное поведение!)}

Как правило, изменение карты при переборе по keySet к keySet ConcurrentModificationException. Но ConcurrentHashMap способен справиться с этим. Он остается непротиворечивым и все еще может повторяться, даже если результаты могут быть неожиданными - как в вашем случае.

В связи с причиной поведения, которое вы наблюдали:

Хеш-таблица (или хеш-карта) в основном работает путем вычисления значения хеш-функции из ключа и использования этого ключа в качестве индикатора для "корзины", к которой должна быть добавлена запись. Когда несколько ключей сопоставляются одному и тому же сегменту, записи в этом разделе обычно обрабатываются как связанный список. То же самое относится и к 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 оказываются в разных ведрах. Таким образом, нет связанного списка, к которому можно было бы добавить удаленные (и добавленные) элементы, и цикл завершается после итерации по соответствующим элементам (то есть первым двум сегментам) один раз.

Ответ 2

Я не думаю, что это как-то связано с безопасностью потоков, которую предлагает ConcurrentHashMap. Это даже не похоже на тупик, а на бесконечный цикл.

И это из-за того, что карта была изменена во время перебора набора ключей, который поддерживается той же картой!

Вот выдержка из документации map.keySet():

Набор опирается на карту, поэтому изменения в карте отражаются в наборе, и наоборот. Если карта изменяется во время выполнения итерации по набору (кроме как через собственную операцию удаления итератора), результаты итерации не определены.

Ответ 3

Там нет тупика. Вы просто впадаете в бесконечный цикл. Когда я запускаю этот код (и печатаю key в цикле), консоль показывает это неоднократно:

0
4294967297
0
4294967297
0
...

Если вы сделали map экземпляра HashMap, вы увидите, что код вызывает ConcurrentModificationException. Таким образом, вы просто изменяете карту, перебирая ее ключи, и ConcurrentHashMap не генерирует исключение одновременной модификации, что делает ваш цикл бесконечным.

Ответ 4

Причиной бесконечного цикла является сочетание

1. Как записи на карте хранятся внутри
2. Как работает ключевой итератор

1

Записи карты хранятся в виде массива связанных списков:
transient volatile Node<K,V>[] table
Каждая запись карты попадет в один из связанных списков в этом массиве на основе его хеша (hash % array.length):

//simplified pseudocode
public V put(K key, V value) {
    int hash = computeHash(key) % table.size
    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() возвращает значение, которое было предварительно вычислено ранее, и вычисляет значение, которое будет возвращено при следующем вызове. Когда создается итератор, он собирает 1-й элемент, а когда next() вызывается 1-й раз, он собирает 2-й элемент и возвращает 1-й.
Вот соответствующий код из метода 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-я итерация

map.remove(key)

[ 4294967297:0, null,..., null ]

map.put(key, the item we just removed)

[ 4294967297:0 → 0:0, null,..., null ]

2-я итерация

map.remove(key)

[ 0:0, null,..., null ]

map.put(key, the item we just removed)

[ 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));
}

Выход:
iteration:1 key:0 map size:5
iteration:2 key:1 map size:5

Все элементы, добавленные в цикл, оказываются в одном и том же сегменте - первом, который уже использовался нашим итератором.

Ответ 5

Не существует тупиков. Блокировка - это когда два (или более) потока блокируют друг друга. Очевидно ， У вас есть только один основной поток.