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