📦 Розділ 4 · Питання #19

Як ConcurrentHashMap забезпечує thread-safety

Клас ConcurrentHashMap забезпечує безпеку в багатопотоковому середовищі без використання глобальних блокувань на весь об'єкт. Замість вишиковування всіх потоків в одну чергу (як...

📦 Колекції 📄 Вихідний Markdown

🟢 Junior Level

1. Фундаментальний принцип потокобезпеки

Клас ConcurrentHashMap забезпечує безпеку в багатопотоковому середовищі без використання глобальних блокувань на весь об’єкт. Замість вишиковування всіх потоків в одну чергу (як це роблять застарілий Hashtable або обгортка Collections.synchronizedMap), ConcurrentHashMap поєднує три ключові механізми:

  1. Lock-Free читання (get): операції читання виконуються взагалі без жодних блокувань і ніколи не конфліктують з операціями запису.
  2. CAS (Compare-And-Swap): атомарна процесорна інструкція для безконфліктного додавання елементів у порожні кошики (бакети).
  3. Дрібногранулярна синхронізація (Node-Level Lock): у разі виникнення колізій блокується тільки перший вузол конкретного бакета (synchronized (head)). Усі інші бакети хеш-таблиці залишаються доступними для паралельного запису іншими потоками.
Потік 1 ──► put("A", 1) ──► Бакет [2] (заблоковано монітор вузла 'A')
Потік 2 ──► put("B", 2) ──► Бакет [7] (вільний, запис паралельно!)
Потік 3 ──► get("C")    ──► Бакет [5] (без блокувань, паралельно!)

🟡 Middle Level

1. Архітектура полів і гарантії Java Memory Model (JMM)

Всередині ConcurrentHashMap масив бакетів і поля зв’язних вузлів оголошені з модифікатором volatile:

// Масив бакетів:
transient volatile Node<K,V>[] table;

// Внутрішній клас вузла:
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;          // volatile значення!
    volatile Node<K,V> next; // volatile посилання на наступний вузол!
}

Чому читання get() абсолютно вільне від блокувань:

  1. Доступ до комірок масиву table[i] здійснюється через атомарний метод tabAt() із семантикою volatile load (через VarHandle / Unsafe).
  2. Поля val та next оголошені як volatile.
  3. Згідно зі специфікацією JMM, запис у volatile-змінну формує відношення Happens-Before з подальшим читанням цієї ж змінної. Потік-читач гарантовано бачить найсвіжіші дані, записані будь-яким потоком-письменником, без необхідності захоплення м’ютекса.

2. Алгоритм вставки putVal(): крок за кроком

Коли потік викликає map.put(key, value):

                          ┌───────────────────────────┐
                          │   Виклик put(key, value)  │
                          └─────────────┬─────────────┘
                                        │
                         Хешування: spread(key.hashCode())
                                        │
                                        ▼
                                ┌───────────────┐
                     ┌──────────┤ table == null?├──────────┐
                     │          └───────────────┘          │
                  ТАК│                                     │ НІ
                     ▼                                     ▼
           initTable() через CAS                  Індекс i = (n-1) & hash
                     │                                     │
                     └──────────────────┐                  ▼
                                        │         ┌─────────────────┐
                                        └────────►│  table[i] пустий?│
                                                  └────────┬────────┘
                                                 ТАК│             │ НІ
                                                    │             │
                    ┌───────────────────────────────┘             ▼
                    ▼                                   ┌────────────────────┐
        CAS: casTabAt(table, i, null, node)             │ hash == MOVED (-1)?│
                    │                                   └─────────┬──────────┘
           ┌────────┴────────┐                                ТАК│         │ НІ
        УСПІХ              FAIL                                  │         │
           │                 │                                   │         ▼
        ГОТОВО             RETRY              helpTransfer() ◄───┘   synchronized (head) {
                                                                       Вставка у список/дерево
                                                                     }
  1. Перевірка на null: якщо ключ або значення дорівнюють null, негайно викидається NullPointerException. ConcurrentHashMap принципово забороняє null, щоб уникнути неоднозначності в конкурентному середовищі (чи значення відсутнє, чи воно дорівнює null).
  2. Обчислення індексу бакета: хеш-код нормалізується функцією spread(int h) = (h ^ (h >>> 16)) & HASH_BITS, після чого індекс визначається бітовою маскою (n - 1) & hash.
  3. Бакет порожній (tabAt == null): потік намагається вставити новий вузол атомарною операцією casTabAt (Compare-And-Swap):
    • Якщо комірка все ще null, вузол записується атомарно без жодних блокувань.
    • Якщо інший потік встиг вклинитися за цей такт процесора, CAS повертає false, і цикл for переходить на повторну ітерацію (spin/retry).
  4. Бакет у процесі ресайзу (node.hash == MOVED): потік не чекає пасивно, а підключається до паралельного переносу даних через helpTransfer().
  5. У бакеті виникла колізія (є елементи): захоплюється монітор першого вузла бакета: 
    synchronized (f) {
    if (tabAt(tab, i) == f) { // Double Check: перевірка, що голова не змінилася
        if (fh >= 0) {
            // Обхід однозв'язного списку: перезапис або додавання в хвіст
        } else if (f instanceof TreeBin) {
            // Додавання у збалансоване червоно-чорне дерево
        }
    }
}
  6. Деревізація: якщо довжина списку в бакеті сягає 8 (TREEIFY_THRESHOLD), викликається treeifyBin() для трансформації списку в червоно-чорне дерево (за умови, що місткість таблиці $\ge 64$).

🔴 Senior Level

1. Розподілений паралельний ресайз: ForwardingNode та helpTransfer()

У класичній HashMap розширення таблиці (resize()) вимагає повної монополії на колекцію або призводить до гонитви даних і нескінченних циклів. У ConcurrentHashMap процес ресайзу є кооперативним і розподіленим:

  1. Коли кількість елементів перевищує поріг (sizeCtl), перший потік ініціює створення масиву nextTable подвоєного розміру.
  2. Вихідна таблиця розбивається на діапазони бакетів (страйди, мінімум 16 кошиків на один потік).
  3. Потік бере свій страйд і переносить елементи в новий масив.
  4. Як тільки бакет повністю перенесено, у старій таблиці на його місце встановлюється спеціальний сторожовий вузол — ForwardingNode із системним хешем MOVED = -1, що тримає посилання на nextTable.
  5. Кооперація: будь-який інший потік, який намагається виконати put(), remove() або compute() і натрапляє на ForwardingNode, розпізнає процес міграції й викликає метод helpTransfer(). Замість простою він отримує наступний нерозподілений страйд і допомагає переносити дані.
  6. Читання під час ресайзу: виклики get() при зустрічі з ForwardingNode не блокуються, а безперешкодно делегуються в nextTable через виклик ForwardingNode.find().

2. Спеціальні службові вузли (Special Sentinel Nodes)

ConcurrentHashMap кодує внутрішній стан бакета за допомогою від’ємних значень хеш-коду кореневого вузла:

Тип вузла Хеш-код Призначення
Node<K,V> $\ge 0$ Звичайний вузол однозв’язного списку колізій
ForwardingNode -1 (MOVED) Маркер перенесеного бакета під час ресайзу; перенаправляє операції в nextTable
TreeBin -2 (TREEBIN) Заголовний вузол червоно-чорного дерева (інкапсулює корінь TreeNode та Reader-Writer блокування дерева)
ReservationNode -3 (RESERVED) Тимчасовий вузол-заглушка для атомарного методу computeIfAbsent()

Роль ReservationNode:

Коли викликається map.computeIfAbsent(key, mappingFunction) для ще не існуючого ключа в порожньому бакеті, мапа не знає наперед результат обчислення функції. Щоб уникнути стану гонитви (race condition) і не допустити дублювання роботи іншими потоками, потік атомарно через CAS розміщує в бакеті ReservationNode, захоплює його монітор (synchronized (r)), виконує функцію користувача, а потім підміняє заглушку реальним вузлом з обчисленим значенням.

3. Масштабований підрахунок розміру: CounterCell (LongAdder патерн)

Класична змінна volatile int size при високому навантаженні стає вузьким місцем (bottleneck) через постійний contention процесорних кеш-ліній (cache coherency traffic / MESI invalidation).

Для масштабування ConcurrentHashMap використовує підхід, ідентичний java.util.concurrent.atomic.LongAdder:

  • Базовий лічильник baseCount.
  • Масив додаткових лічильників CounterCell[] counterCells.
  • Кожен потік при оновленні розміру спочатку намагається оновити baseCount через CAS. Якщо виникає конкуренція (CAS падає), потік вибирає комірку в counterCells за хешем свого ідентифікатора потоку (ThreadLocalRandom.getProbe()) і оновлює її через CAS.
  • Комірки CounterCell мають анотацію @jdk.internal.vm.annotation.Contended для запобігання хибному розділенню кеш-ліній (False Sharing, 64-байтний padding).
  • Метод mappingCount() або size() просто сумує значення baseCount і всіх активних counterCells.

4. Еволюція: чому в Java 8 відмовилися від Segment (Java 7)?

В Java 7 колекція складалася з фіксованого масиву сегментів (Segment<K,V>[]), де кожен сегмент успадковував ReentrantLock.

  • Обмеження 1 (Concurrency Level): Кількість сегментів фіксувалася під час ініціалізації (за замовчуванням 16). Навіть якщо в таблиці було 500 000 елементів, паралельно виконувати запис могли максимум 16 потоків.
  • Обмеження 2 (Витрати пам’яті): Кожен сегмент був окремим важким об’єктом-блокуванням зі своєю структурою таблиці та чергою AQS, що створювало колосальний оверхед пам’яті.
  • Обмеження 3 (Метод size()): У Java 7 підрахунок розміру виконував кілька оптимістичних спроб без блокувань, але за наявності паралельних модифікацій доводилося блокувати абсолютно всі 16 сегментів одночасно.

В Java 8+ реалізовано Node-Level Locking:

  • Блокування перенесено на перший вузол бакета (synchronized (head)).
  • Ступінь конкурентності зріс з фіксованих 16 до кількості непустих бакетів (тисячі паралельних операцій запису).
  • Для порожніх бакетів блокування відсутні взагалі завдяки атомарному CAS.

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

30-секундна відповідь (Elevator Pitch)

«ConcurrentHashMap у Java 8+ гарантує потокобезпеку завдяки трьом рівням оптимізації:

  1. Lock-Free читання: операція get() не вимагає блокувань, покладаючись на семантику volatile для посилань масиву table, полів значення val та посилань next.
  2. CAS-вставка: вставка в порожній бакет виконується атомарною процесорною інструкцією Compare-And-Swap без взаємних блокувань.
  3. Синхронізація на рівні бакета: у разі колізії блокується лише монітор кореневого вузла бакета (synchronized (head)). Додатково ресайз відбувається розподілено й кооперативно: потоки зустрічають ForwardingNode і допомагають міграції через helpTransfer(), а розмір таблиці масштабується через страйповані лічильники CounterCell».

3 каверзних запитання з інтерв’ю та відповіді

1. Чому читання get() не потребує блокувань, навіть якщо в цей момент інший потік перебудовує список колізій або дерево?

Відповідь: Поля val та next вузлів Node оголошені як volatile. При додаванні нового елемента він прилінковується атомарно (запис у volatile next), що формує зв’язок Happens-Before між записом і подальшим читанням. При видаленні або реорганізації існуючі вузли не мутують небезпечно для ітератора читача. Якщо ж бакет перебуває в стані ресайзу, потік-читач натрапляє на ForwardingNode і безперешкодно продовжує пошук у новій таблиці nextTable через поліморфний метод find().

2. Навіщо в блоці synchronized (f) всередині putVal виконується перевірка if (tabAt(tab, i) == f)?

Відповідь: Це реалізація патерну Double-Checked Locking. Між моментом, коли потік прочитав посилання на перший вузол f з масиву table, і моментом, коли він успішно захопив монітор synchronized (f), інший потік міг змінити структуру бакета (наприклад, видалити голову, перетворити список на дерево TreeBin або перенести бакет при ресайзі). Повторна перевірка гарантує, що захоплений вузол f досі дійсно є актуальною головою цього бакета.

3. Чому розробники Java 8 обрали вбудований synchronized (node), а не ReentrantLock?

Відповідь:

  1. ReentrantLock — це повноцінний об’єкт у купі (Heap), який вимагає виділення пам’яті під сам лок і чергу очікування потоків (AQS). Тримати окремий екземпляр ReentrantLock на кожен бакет таблиці спричинило б величезний оверхед пам’яті.
  2. Вбудований synchronized у сучасній JVM оптимізований на рівні машинного коду: він використовує Mark Word у заголовку вже наявного об’єкта Node, підтримує адаптивний спінінг (Adaptive Spinning) та перетворюється на блокування операційної системи (важкий монітор) лише за реальної тривалої конкуренції.

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

  • ❌ Стверджувати, що ConcurrentHashMap використовує сегменти (Segment): Сегменти було повністю усунуто в Java 8 (ще у 2014 році).
  • ❌ Вважати, що get() блокує потоки запису або блокується ними: Усі операції читання в CHM є абсолютно lock-free.
  • ❌ Використання зовнішнього synchronized(map) навколо CHM: Це вбиває паралелізм і нівелює всі внутрішні оптимізації. Для складених атомарних операцій слід використовувати методи compute, merge, putIfAbsent.
  • ❌ Спроба записати null ключ або null значення: CHM негайно викидає NullPointerException.
  • ❌ Важкі обчислення або мережеві запити всередині лямбди computeIfAbsent: Поки виконується лямбда, відповідний бакет залишається заблокованим (на ReservationNode або голові списку), що може заморозити інші потоки або спричинити дедлок при рекурсивному зверненні до цієї ж мапи.

Пов’язані теми