🔑 Раздел 10 · Вопрос #22

Как работает HashMap в многопоточной среде

Класс HashMap не является потокобезопасным (Not Thread-Safe). Он проектировался для максимальной скорости работы в однопоточных сценариях, поэтому в его коде полностью отсутству...

🔑 HashMap equals hashCode 📄 Исходный Markdown

🟢 Junior Level

Класс HashMap не является потокобезопасным (Not Thread-Safe). Он проектировался для максимальной скорости работы в однопоточных сценариях, поэтому в его коде полностью отсутствуют блокировки (synchronized), атомарные операции (CAS) и барьеры памяти (volatile).

Если несколько потоков одновременно читают и модифицируют HashMap, поведение программы становится непредсказуемым (Undefined Behavior):

  1. Потеря данных (Lost Updates): Два потока могут одновременно попытаться записать элемент в одну и ту же ячейку, в результате чего запись одного потока молча затрет запись другого.
  2. Некорректный размер (size): Счетчик элементов инкрементируется неатомарно (++size), поэтому реальное число записей в таблице перестает совпадать со значением map.size().
  3. Фантомные null при чтении: Метод map.get(key) может вернуть null для гарантированно существующего ключа из-за несогласованности кэшей процессора или происходящего в фоне ресайза.
  4. Выброс ConcurrentModificationException: Итераторы HashMap работают по принципу fail-fast и аварийно завершают обход при обнаружении изменений.
import java.util.HashMap;
import java.util.Map;

public class ConcurrencyBugDemo {
    public static void main(String[] args) throws InterruptedException {
        Map<Integer, Integer> map = new HashMap<>();

        // Запуск двух параллельных потоков на запись
        Thread t1 = new Thread(() -> {
            for (int i = 0; i < 10_000; i++) map.put(i, i);
        });
        Thread t2 = new Thread(() -> {
            for (int i = 10_000; i < 20_000; i++) map.put(i, i);
        });

        t1.start();
        t2.start();
        t1.join();
        t2.join();

        // Ожидали 20 000 элементов, но размер будет непредсказуемым (например, 18 432)!
        System.out.println("Фактический size: " + map.size());
    }
}

Аналогия: HashMap — это общая школьная доска без дежурного. Если два человека одновременно начнут писать мелом в одном и том же месте доски, они перечеркают буквы друг друга, и итоговый текст станет нечитаемой кашей.

🟡 Middle Level

Анатомия гонок данных (Race Conditions)

1. Гонка при вставке в пустой бакет

В методе putVal проверка наличия бакета и запись нового узла разделены:

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

Если Поток 1 и Поток 2 одновременно обращаются к пустому бакету tab[i]:

  1. Оба потока видят tab[i] == null.
  2. Поток 1 создает узел и записывает в tab[i].
  3. Поток 2 тут же перезаписывает tab[i] своим узлом.
  4. Итог: Узел Потока 1 безвозвратно утерян и будет уничтожен GC.

2. Разрушение структуры при конкурентном resize()

Когда два потока одновременно превышают threshold, оба запускают процедуру resize():

  • Потоки параллельно аллоцируют два независимых массива newTab.
  • Начинается конкурентное перераспределение ссылок next существующих узлов.
  • В результате часть элементов попадает в один массив, часть в другой, а ссылка this.table указывает лишь на один из них. Половина коллекции теряется.

Безопасные альтернативы для многопоточности

Коллекция Механизм синхронизации Производительность Применение
ConcurrentHashMap Lock-Free чтение, CAS для новых бакетов, synchronized на голове бакета Очень высокая Основной промышленный стандарт
Collections.synchronizedMap(map) Декоратор с общим объектом блокировки (mutex) на всю Map Низкая (потоки встают в очередь) Простые сценарии с редкими обращениями
Hashtable synchronized на каждом методе Низкая (устарела) Не рекомендуется в современном коде

🔴 Senior Level

Проблема Java 7: бесконечный цикл (Infinite Loop & 100% CPU)

В Java 7 метод transfer() при ресайзе использовал добавление в голову (Head Insertion), что разворачивало порядок элементов в бакете на противоположный:

// Java 7 transfer method:
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; // Поток 1 прерывается здесь!
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

Сценарий зависания:

  1. В бакете лежат узлы [A] -> [B] -> null.
  2. Поток 1 успевает запомнить e = A, next = B, после чего планировщик ОС переключает контекст на Поток 2.
  3. Поток 2 полностью завершает ресайз: порядок узлов обращается: [B] -> [A] -> null.
  4. Поток 1 просыпается: для него e = A, next = B. Он связывает A.next = newTable[i]. На следующей итерации для B он связывает B.next = A.
  5. Результат: Образуется циклическая ссылка: [A] <-> [B].
  6. При любом последующем вызове get() по этому бакету цикл while (e != null) e = e.next начинает бесконечно крутиться, загружая ядро процессора на 100%.

Устранена ли проблема 100% CPU в Java 8+?

В Java 8+ в связных списках перешли на Tail Insertion (Lo/Hi списки), что сохранило относительный порядок элементов и ликвидировало циклы в линейных списках.

Однако миф о том, что HashMap в Java 8+ больше никогда не зависает, ошибочен:

  • Если бакет содержит $\ge 8$ элементов и превращается в красно-чёрное дерево (TreeNode).
  • При конкурентных вставках несколько потоков начинают одновременно модифицировать ссылки дерева (parent, left, right) и запускать ребалансировку (balanceInsertion).
  • Из-за отсутствия барьеров памяти и атомарности ссылки в дереве зацикливаются (node.parent.left == node).
  • Последующий вызов root(), find() или get() зацикливается при обходе древовидной структуры, по-прежнему приводя к 100% загрузке CPU!

Модель памяти Java (JMM) и Safe Publication

Поля table, size, modCount и поля внутри Node в HashMap не объявлены как volatile:

transient Node<K,V>[] table;
transient int size;
transient int modCount;

Согласно Java Memory Model (JMM):

  • Запись данных в HashMap одним потоком без синхронизации не устанавливает отношение Happens-Before с операциями чтения в других потоках.
  • Процессор и JIT-компилятор имеют право переупорядочивать инструкции (Instruction Reordering).
  • Другие потоки могут бесконечно долго читать устаревшие данные из локальных кэшей ядер L1/L2 или увидеть ссылку на HashMap, чьи внутренние поля еще не инициализированы (Data Race / Partially Constructed Object).

Паттерн безопасной публикации (Safe Publication) для Read-Only Map:

Если HashMap наполняется данными один раз при старте приложения, а затем используется строго на чтение несколькими потоками, она может безопасно работать без ConcurrentHashMap, если соблюдены правила безопасной публикации:

public class ConfigHolder {
    // 1. Через final-поле класса (гарантия JMM на freeze полей)
    private final Map<String, String> configMap;

    public ConfigHolder() {
        Map<String, String> temp = new HashMap<>();
        temp.put("timeout", "5000");
        this.configMap = Collections.unmodifiableMap(temp); // Защита от мутаций
    }

    // 2. Либо публикация ссылки через volatile-переменную
    // private volatile Map<String, String> dynamicConfig;
}

4 Tricky Questions

1. Правда ли, что в Java 8+ проблема 100% CPU (бесконечный цикл) в HashMap полностью устранена?

Ответ: Нет, это неправда. В Java 8+ переход на Tail Insertion устранил зацикливание классических связных списков в бакетах при ресайзе. Однако если при коллизиях бакет был трифицирован в красно-чёрное дерево (TreeNode), одновременная запись без блокировок ломает указатели parent, left и right. В дереве возникают циклические связи, из-за чего последующие вызовы get(), put() или итерация зависают в бесконечном цикле, утилизируя 100% ядра CPU.

2. Защищает ли Collections.synchronizedMap(map) от ConcurrentModificationException при обходе через for-each?

Ответ: Нет, не защищает. Обертка Collections.synchronizedMap блокирует мьютекс только на время выполнения атомарных методов (get, put, remove). Итератор создается методом map.entrySet().iterator(), но сам цикл for (Map.Entry<K, V> e : syncMap.entrySet()) состоит из множества последовательных вызовов hasNext() и next(). Между этими вызовами монитор освобождается. Если другой поток вызовет put(), значение modCount изменится, и итератор выбросит ConcurrentModificationException.

Чтобы безопасно итерироваться по synchronizedMap, разработчик обязан вручную заблокировать мьютекс карты на всё время обхода:

synchronized (syncMap) {
    for (Map.Entry<K, V> entry : syncMap.entrySet()) {
        // Безопасно
    }
}

3. Гарантирует ли механизм fail-fast обнаружение абсолютно всех параллельных изменений в HashMap?

Ответ: Нет, не гарантирует. Спецификация JDK прямо указывает: «The fail-fast behavior of iterators cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification». Поле modCount не является volatile. Если поток A выполняет put(), инкремент modCount может задержаться в кэше L1 его ядра процессора и не дойти до потока B, выполняющего итерацию. В этом случае поток B не выбросит исключение вовремя и прочитает поврежденные данные. Fail-fast служит исключительно средством отладки («best-effort basis»), а не механизмом синхронизации.

4. Почему в Spring-приложениях поле private Map<String, Object> cache = new HashMap<>() внутри @Service или @Component является критической ошибкой?

Ответ: По умолчанию все бины в Spring Framework создаются со скоупом Singleton (один экземпляр класса на весь контекст приложения). Веб-сервер (Tomcat, Jetty) обрабатывает входящие HTTP-запросы в общем пуле потоков (worker-threads). В результате сотни потоков начинают параллельно выполнять методы сервиса, обращаясь к одному и тому же экземпляру HashMap. Это неизбежно приводит к потере данных, разрушению структуры карты, утечкам памяти и зависанию потоков на проде. Для кэширования внутри Singleton-бинов обязателен ConcurrentHashMap или специализированные решения (Caffeine, Redis).

🎯 Шпаргалка для интервью

  • Почему HashMap не thread-safe: Нет блокировок, нет CAS, поля не volatile.
  • Последствия гонок: Lost updates (потерянные записи), рассинхронизация size, повреждение бакетов при ресайзе.
  • Java 7 vs Java 8+:
    • В Java 7: Head Insertion приводил к циклу A <-> B в связном списке $\to$ 100% CPU.
    • В Java 8+: Tail Insertion исправил списки, но конкурентная модификация TreeNode по-прежнему может вызвать 100% CPU из-за зацикливания дерева!
  • Fail-Fast: Итератор по modCount работает на best-effort основе; не гарантирует безопасность и не заменяет синхронизацию.
  • Safe Publication: Чтение обычной HashMap несколькими потоками допустимо, только если карта неизменяема (unmodifiableMap) и корректно опубликована через final или volatile.
  • Выбор альтернативы: В 99% многопоточных задач используйте ConcurrentHashMap.

Связанные темы