🔑 Розділ 10 · Питання #22

Як HashMap працює в багатопотоковому середовищі

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

🔑 HashMap equals hashCode 📄 Вихідний Markdown

🟢 Junior Level

Короткий опис для співбесіди (30 секунд)

Клас 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());
    }
}

[!NOTE] Аналогія: 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) Декоратор зі спільним м’ютексом на всю мапу Низька (потоки шикуються в чергу) Прості задачі з рідкісними зверненнями
Hashtable synchronized на кожному методі Низька (застаріла) Не рекомендується в новому коді

🔴 Senior Level

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

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

// Метод transfer у Java 7:
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+ більше ніколи не зависає на 100% CPU, є помилковим:

  • Якщо бакет містить $\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;
}

🎯 Шпаргалка для інтерв’ю

1. 30-секундний есенс (Elevator Pitch)

HashMap не є потокобезпечною: у ній немає блокувань, немає CAS-інструкцій, а поля не є volatile. Одночасний доступ призводить до втрати записів (Lost Updates), розсинхронізації лічильника size та появи фантомних null при читанні. У Java 7 паралельний ресайз викликав кільцеве зациклення списку (100% CPU); у Java 8+ це виправлено переходом на Tail Insertion, проте конкурентний запис у червоно-чорне дерево TreeNode усе одно може призвести до 100% навантаження CPU через пошкодження вказівників дерева. Для багатопотокового середовища слід використовувати ConcurrentHashMap.

2. 4 каверзні питання з глибокими відповідями

Питання 1: Чи правда, що в Java 8+ проблема 100% CPU (нескінченного циклу) в HashMap повністю вирішена?

Відповідь: Ні, це неправда.
У Java 8+ перехід на Tail Insertion ліквідував зациклення класичних зв’язних списків при ресайзі. Проте якщо через колізії бакет було перетворено на червоно-чорне дерево (TreeNode), одночасний запис без блокувань ламає вказівники parent, left і right. У дереві виникають циклічні зв’язки, через що наступні виклики get(), put() або обхід дерева зависають у нескінченному циклі, навантажуючи ядро процесора на 100%.

Питання 2: Чи захищає Collections.synchronizedMap(map) від ConcurrentModificationException під час обходу через цикл for-each?

Відповідь: Ні, не захищає.
Обгортка Collections.synchronizedMap блокує м’ютекс лише на час виконання поодиноких атомарних методів (get, put, remove). Ітератор створюється методом map.entrySet().iterator(), але сам цикл складається з безлічі послідовних викликів hasNext() та next(). Між цими викликами монітор звільняється. Якщо інший потік викличе put(), значення modCount зміниться, й ітератор викине ConcurrentModificationException. Для безпечної ітерації розробник зобов’язаний вручну заблокувати м’ютекс карти на весь час обходу:

synchronized (syncMap) {
    for (Map.Entry<K, V> entry : syncMap.entrySet()) {
        // Безпечний обхід
    }
}

Питання 3: Чи гарантує механізм fail-fast виявлення абсолютно всіх паралельних змін у HashMap?

Відповідь: Ні, не гарантує.
Специфікація JDK прямо вказує, що поведінка fail-fast не може бути абсолютно гарантованою за наявності несинхронізованих паралельних модифікацій. Поле 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.

3. Типові помилки та Red Flags

❌ «HashMap безпечна в багатопотоковості, якщо потоки додають ключі з різними гешами.»
Правильно: Конкурентний ресайз пошкодить структуру даних незалежно від значень ключів.

❌ «У Java 8+ проблема 100% CPU неможлива.»
Правильно: Пошкодження вказівників у дереві TreeNode викликає зациклення та 100% завантаження ядра CPU.

❌ «Collections.synchronizedMap повністю захищає від помилок в ітераторі.»
Правильно: Для ітератора потрібна явна зовнішня синхронізація synchronized(map).

4. Пов’язані питання