Как можно с помощью HashMap создать бесконечный цикл?

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

При рехешировании элементы из старого массива бакетов переносятся в новый. В однопоточном режиме порядок элементов в связном списке бакета сохраняется. В многопоточном режиме, если поток A начинает рехеширование, а поток B модифицирует (добавляет/удаляет) элементы или тоже начинает рехеширование, то могут возникнуть проблемы.

Рассмотрим сценарий с двумя потоками, добавляющими элементы в HashMap при приближении к пороговому значению для рехеширования. Поток A может увидеть старый массив и начать переносить элементы, а поток B может увидеть новый массив и тоже начать переносить или модифицировать. При переносе элементов в новый массив HashMap использует связные списки. В многопоточном режиме, без синхронизации, атомарность операций нарушается.

Пример цикла может выглядеть так:

1. HashMap почти полный, требуется рехеширование.
2. Поток A начинает рехеширование. Он перебирает элементы в старом бакете и создает новые узлы для нового массива.
3. До того, как Поток A завершит перенос элемента X, планировщик переключается на Поток B.
4. Поток B также начинает рехеширование или модифицирует этот же бакет.
5. В результате некорректной конкурентной модификации, узел Y, который должен указывать на null (конец списка), может начать указывать на узел X, который уже был обработан Потоком A, или на себя.

Это приводит к зацикливанию при последующих операциях get() или put() в данном бакете, так как обход связного списка становится бесконечным.

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

// Пример (НЕ рекомендуется для использования в многопоточных приложениях без синхронизации)
// Демонстрация возможного сценария возникновения цикла.
// В реальных условиях это трудно воспроизвести без специфических условий и инструментов.
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class HashMapLoopExample {
    private static final ManInBlack hatGuy = new ManInBlack(1);
    private static final ManInBlack jacketGuy = new ManInBlack(2);

    // Класс для ключей с одинаковым хэш-кодом
    static class ManInBlack {
        private final int id;

        ManInBlack(int id) {
            this.id = id;
        }

        // Переопределяем equals, чтобы они были неравны
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            ManInBlack that = (ManInBlack) o;
            return id == that.id;
        }

        // Возвращаем одинаковый хэш-код для демонстрации
        @Override
        public int hashCode() {
            return 1; // Всегда возвращаем 1
        }

        @Override
        public String toString() {
            return "ManInBlack{" + "id=" + id + '}';
        }
    }

    public static void main(String[] args) throws InterruptedException {
        final Map<ManInBlack, String> map = new HashMap<>(2); // Маленький начальный размер

        ExecutorService executor = Executors.newFixedThreadPool(2); // Два потока

        executor.submit(() -> {
            while (true) {
                // Попытка добавить элементы, которые могут вызвать рехеширование
                map.put(hatGuy, "Hat");
                map.put(jacketGuy, "Jacket");
                // Если зацикливание произошло, следующая операция может зависнуть
                // или выдать ошибку после долгого выполнения.
                // System.out.println("Thread 1: Put operation completed.");
            }
        });

        executor.submit(() -> {
             while (true) {
                 // Другой поток также взаимодействует с картой,
                 // что увеличивает шанс конкурентной модификации.
                 // Операция get может зависнуть при зацикливании.
                 map.get(hatGuy);
                 map.get(jacketGuy);
                 // System.out.println("Thread 2: Get operation completed.");
             }
        });

        // В реальном сценарии отлавливать зацикливание сложно.
        // Можно поставить таймер и проверить, не зависло ли выполнение fori

        // Для демонстрации оставим потоки работать некоторое время
        Thread.sleep(5000); // Даем потокам поработать 5 секунд

        executor.shutdownNow(); // Принудительно завершаем потоки
        System.out.println("Скрипт завершен.");
    }
}