Явный контур Java HashMap.get(Object)

Несколько ответов на SO упоминают, что метод get в HashMap может попасть в бесконечный цикл (например, этот или этот), если не синхронизирован должным образом (и, как правило, в нижней строке "не используйте HashMap в многопоточной среде, используйте ConcurrentHashMap" ).

Хотя я могу легко понять, почему одновременные вызовы метода HashMap.put(Object) могут вызвать бесконечный цикл, я не могу понять, почему метод get (Object) может застрять, когда он пытается прочитать HashMap, что в этот момент изменяется. Я рассмотрел реализацию в openjdk и содержит цикл, но условие выхода e != null должно быть выполнено рано или поздно. Как он может зависеть навсегда? Кусок кода, который явно упоминается, чтобы быть уязвимым для этой проблемы:

public class MyCache {
    private Map<String,Object> map = new HashMap<String,Object>();

    public synchronized void put(String key, Object value){
        map.put(key,value);
    }

    public Object get(String key){
        // can cause in an infinite loop in some JDKs!!
        return map.get(key);
    }
}

Может кто-нибудь объяснить, как поток, помещающий объект в HashMap, и другое чтение из него может чередоваться таким образом, что генерируется бесконечный цикл? Это связано с некоторой проблемой когерентности кеша или переупорядочением команд процессора (поэтому проблема может возникнуть только на многопроцессорной машине)?

Ответы

Ответ 1

Вы ссылаетесь на HashMap в Java 6. Он был переписан на Java 8. До этого переписать бесконечный цикл на get(Object) был возможен, если бы было два потока записи. Я не знаю, как может произойти бесконечный цикл на get с одним автором.

В частности, бесконечный цикл возникает, когда есть два одновременных вызова на resize(int), который вызывает transfer:

 void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
         while(null != e) {
             Entry<K,V> next = e.next;
             if (rehash) {
                 e.hash = null == e.key ? 0 : hash(e.key);
             }
             int i = indexFor(e.hash, newCapacity);
             e.next = newTable[i];
             newTable[i] = e;
             e = next;
         }
     }
 }

Эта логика меняет порядок упорядочения узлов в хэш-ведре. Два одновременных обращения могут сделать цикл.

Посмотрите:

             e.next = newTable[i];
             newTable[i] = e;

Если два потока обрабатывают один и тот же node e, тогда первый поток выполняется нормально, а второй поток устанавливает e.next = e, потому что newTable[i] уже был установлен на e первым потоком. node e теперь указывает на себя, и когда get(Object) называется, он вводит бесконечный цикл.

В Java 8 размер изменяет порядок node, поэтому цикл не может произойти таким образом. Однако вы можете потерять данные.

Итераторы для класса LinkedHashMap могут застревать в бесконечном цикле, когда есть несколько читателей и нет писателей, когда поддерживается упорядочение доступа. С несколькими считывателями и порядком доступа каждое чтение удаляет, а затем вставляет доступный node из двойного связанного списка узлов. Несколько считывателей могут привести к тому, что один и тот же node будет повторно вставлен в список более одного раза, вызывая цикл. Снова класс был переписан для Java 8, и я не знаю, существует ли эта проблема или нет.

Ответ 2

Ситуация:

По умолчанию емкость HashMap равна 16, а коэффициент загрузки - 0,75, что означает, что HashMap удвоит свою емкость, когда 12-я пара ключей-значений входит в карту (16 * 0,75 = 12).

Когда 2 потока пытается получить доступ к HashMap одновременно, вы можете столкнуться с бесконечным циклом. Thread 1 и Thread 2 пытается поставить 12-ю пару ключей.

Thread 1 получил шанс выполнения:

  • В потоке 1 ставится 12-я пара ключ-значение,
  • В Thread 1 установлено, что предел порога достигнут, и он создает новые ковши повышенной емкости. Таким образом, емкость карты увеличивается с 16 до 32.
  • Теперь поток 1 переносит все существующие пары ключ-значение в новые ковши.
  • Тема 1 указывает на первую пару ключа и пару (пару) ключ-значение для начала процесса передачи.

Тема 1 после указания пар ключ-значение и перед запуском процесса передачи потеряет контроль, а Thread 2 получил шанс на выполнение.

Тема 2 получила шанс выполнения:

  • В Thread 2 делается попытка поставить 12-ю пару ключ-значение,
  • В Thread 2 установлено, что предельный порог достигнут, и он создает новые ковши повышенной емкости. Таким образом, емкость карты увеличивается с 16 до 32.
  • В потоке 2 теперь передаются все существующие пары ключ-значение в новые ковши.
  • Поток 2 указывает на первую пару ключевых значений и следующую (вторую) пару ключ-значение для начала процесса передачи.
  • При передаче пар ключ-значение из старых ковшей в новые ведра пары ключ-значение будут отменены в новых ковшиках, потому что hashmap добавит пары ключ-значение в начале, а не в конец. Hashmap добавляет новые пары ключ-значение в начале, чтобы избежать перетаскивания связанного списка каждый раз и поддерживать постоянную производительность.
  • В потоке 2 будут переданы все пары ключ-значение из старых ковшей в новые ведра, а Thread 1 получит шанс на выполнение.

Thread 1 получил шанс выполнения:

  • Тема 1 перед тем, как оставить управление, указывала на первый элемент и следующий элемент старого ведра.
  • Теперь, когда Thread 1 начал класть пары ключ-значение из старого ведра в новое ведро. Он успешно помещает (90, val) и (1, val) в новый Bucket.
  • Когда он пытается добавить следующий элемент (1, val), который равен (90, val) в новый Bucket, он закончится бесконечным циклом.

Решение:

Чтобы решить эту проблему, используйте либо Collections.synchronizedMap, либо ConcurrentHashMap.

ConcurrentHashMap является потокобезопасным, к коду может обращаться один поток за раз.

HashMap можно синхронизировать с помощью метода Collections.synchronizedMap(hashMap). Используя этот метод, мы получаем объект HashMap, который эквивалентен объекту HashTable. Поэтому каждая модификация выполняется на карте заблокирована на объекте Map.

Ответ 3

Учитывая, что единственная возможность, которую я вижу для бесконечного цикла, будет e.next = e в методе get:

for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next)

И это может произойти только в методе transfer во время изменения размера:

 do {
     Entry<K,V> next = e.next;
     int i = indexFor(e.hash, newCapacity);
     e.next = newTable[i]; //here e.next could point on e if the table is modified by another thread
     newTable[i] = e;
     e = next;
 } while (e != null);

Если только один поток изменяет карту, я считаю, что совершенно невозможно иметь бесконечный цикл только с одним потоком. Это было более очевидно при старой реализации get перед jdk 6 (или 5):

public Object get(Object key) {
        Object k = maskNull(key);
        int hash = hash(k);
        int i = indexFor(hash, table.length);
        Entry e = table[i]; 
        while (true) {
            if (e == null)
                return e;
            if (e.hash == hash && eq(k, e.key)) 
                return e.value;
            e = e.next;
        }
    }

Даже тогда случай все еще кажется невероятным, за исключением случаев, когда есть много столкновений.

P.S: Мне бы хотелось, чтобы это было неправильно, хотя!

Ответ 4

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

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

В Java ключевое слово synchronized гарантирует, что указанный метод синхронизируется по всем потокам, поэтому ни один из двух потоков не пытается получить доступ к одной и той же информации сразу.

Вернуться к ресурсу... Если я правильно помню... В Java весь хэш файл считается ресурсом, поэтому один метод "проверяет его", как только он начнется. Однако, если два метода пытаются получить хэш-карту в одно и то же время: тупик.

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

Дальнейшее чтение: Существует очень вдохновляющий человек по имени Эдсгар У. Дейкстра из Нидерландов, который, я считаю, очень интенсивно работал над предотвращением тупиковой ситуации и многопоточными системами. Одной из его самых известных визуализаций и головоломок о тупиках была проблема столовых философов. Действительно фантастический человек.