Объясните время, заставляющее HashMap.put() выполнять бесконечный цикл

Question

Как ряд людей отметили и столкнулись HashMap.put может использоваться в бесконечном цикле выполнения при одновременном использовании (см. GRIZZLY-1207, JGRP-525, возможно, HHH-6414 и этот ответ SO).

HashMap четко документировано как не защищенное от потоков. Очевидно, что правильным решением является использование многопоточной реализации Map, ConncurrentHashMap особенно. Меня больше интересует параллельное время, которое вызывает бесконечный цикл. Я недавно столкнулся с этим циклом с Java 7 JRE и хотел бы понять точные причины. Например, это вызвано несколькими путами одновременно?

Взгляд в HashMap.put показывает, что HashMap.Entry содержит ссылку на следующий узел (в корзине?). Я предполагаю, что эти ссылки портятся, чтобы содержать круговые ссылки, что вызывает бесконечный цикл. Однако я до сих пор не понимаю, как именно происходит эта коррупция.

Answer 1

Напротив того, что думают многие, главная проблема с multi-threading а также HashMaps это не просто повторяющаяся запись или исчезающая... Как вы сказали, бесконечный цикл может произойти, когда два или несколько Threads одновременно решили изменить размер HashMap,

Если размер HashMap превышает заданное пороговое значение, несколько потоков могут попытаться изменить его размер одновременно, и если нам повезет (вы уже развернули код в рабочей среде), они будут работать вечно...

Проблема вызвана тем, как void resize(int newCapacity); а также void transfer(Entry[] newTable); реализованы, вы можете взглянуть на исходный код openjdk самостоятельно. Смесь невезения, удачного времени, записей, которые меняются местами (упорядочение не требуется в этой структуре данных) и которые в результате ошибочно ссылаются друг на друга, пока поток продолжает работать while(e != null)...

Хотя я мог бы попытаться дать вам объяснение самостоятельно, я хочу отдать должное посту Пола Тимы(я не могу добиться большего успеха, чем у него в любом случае), где я узнал, как это работает, в первый раз, когда я решил выяснить, почему я не был нанят на работу несколько месяцев назад...

http://mailinator.blogspot.com/2009/06/beautiful-race-condition.html

Как говорит Павел, лучшим словом для описания этой расы является условие: beautiful