Що таке ConcurrentHashMap і чим він відрізняється від HashMap

ConcurrentHashMap — це високопродуктивна потокобезпечна реалізація інтерфейсу ConcurrentMap (та Map), розроблена для одночасної взаємодії множини паралельних потоків без блокува...

🟢 Junior Level

ConcurrentHashMap — це високопродуктивна потокобезпечна реалізація інтерфейсу ConcurrentMap (та Map), розроблена для одночасної взаємодії множини паралельних потоків без блокування всієї таблиці цілком.

Головні відмінності від `HashMap`

Характеристика	`HashMap`	`ConcurrentHashMap`
Потокобезпечність	❌ Не потокобезпечна	✅ Потокобезпечна
Підтримка `null`	✅ Дозволяє `null`-ключ і `null`-значення	❌ Викидає `NullPointerException`
Поведінка ітератора	Fail-fast (викидає `ConcurrentModificationException`)	Weakly Consistent (ніколи не викидає CME)
Продуктивність в 1 потік	Максимальна (без оверхеду синхронізації)	Незначно нижча (на частки наносекунд)
Багатопотоковий запис	Спричиняє стан гонитви, втрату даних і зациклення	Безпечний паралельний запис

Приклад базового використання

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;

public class ConcurrentMapDemo {
    public static void main(String[] args) {
        ConcurrentMap<String, Integer> stock = new ConcurrentHashMap<>();

        stock.put("MacBook", 10);

        // Атомарне оновлення без стану гонитви:
        stock.merge("MacBook", 1, Integer::sum); // Стало 11

        // Спроба передати null призведе до NullPointerException:
        // stock.put(null, 5); // Runtime-помилка!
    }
}

Аналогія: HashMap — це примірочна в магазині на одну особу: якщо всередину увірвуться двоє, виникне конфлікт. ConcurrentHashMap — це великий гардероб із десятками незалежних секцій: кожен клієнт обслуговується біля своєї стійки, вони не заважають один одному й не шикуються в одну спільну чергу.

🟡 Middle Level

Архітектура багатопотоковості в Java 8+

У Java 7 ConcurrentHashMap базувався на концепції сегментів (Segment[], типово 16 сегментів), де кожен сегмент був окремою блокувальною таблицею (ReentrantLock).

Починаючи з Java 8, архітектуру було докорінно перероблено на Node-level locking (блокування на рівні окремого бакета):

[Bucket 0] -> Node (CAS вставка)
[Bucket 1] -> synchronized (firstNode) { [Node] -> [Node] -> [Node] }
[Bucket 2] -> ForwardingNode (перенесення даних під час resize)
[Bucket 3] -> TreeBin (блокування читання/запису для червоно-чорного дерева)

Читання (get): Працює повністю без блокувань (Lock-Free). Поля val та next у вузлі Node оголошені як volatile, що гарантує негайну видимість змін між ядрами CPU згідно з моделлю пам’яті Java (JMM).
Вставка в порожній бакет: Виконується за допомогою неблокувальної атомарної інструкції процесора CAS (Compare-And-Swap) через VarHandle / Unsafe:
```
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
    break; // Успішно вставили без жодних моніторів!
```
Вставка в разі колізії: Блокується лише перший вузол (голова) бакета через легковагий монітор synchronized (f). Інші потоки можуть вільно й паралельно модифікувати будь-які інші бакети таблиці.

Чому в `ConcurrentHashMap` категорично заборонено `null`?

Автор класу Даґ Лі (Doug Lea) виключив null через проблему усунення неоднозначності (Ambiguity) в багатопотоковому середовищі.

Якщо у звичайній HashMap метод map.get("key") повернув null, в одному потоці можна однозначно визначити причину:

if (map.get(key) == null) {
    if (map.containsKey(key)) {
        // Значення дійсно null
    } else {
        // Ключа в мапі немає
    }
}

У конкурентному середовищі між викликом map.get(key) та map.containsKey(key) інший потік може встигнути додати, видалити або оновити ключ. Стан між перевірками стає неузгодженим (TOCTOU — Time-of-Check to Time-of-Use). Заборона null гарантує: якщо get(k) == null, ключа в таблиці немає на 100%.

Атомарні складені операції

У багатопотокових програмах не можна застосовувати класичний шаблон if (!map.containsKey(k)) map.put(k, v); — між перевіркою та вставкою виникає стан гонитви. ConcurrentHashMap надає атомарні методи:

putIfAbsent(key, value): Вставляє значення тільки якщо ключ був відсутній.
computeIfAbsent(key, mappingFunction): Атомарно обчислює та записує значення, тільки якщо ключ відсутній (ідеально для потокобезпечних кешів).
merge(key, value, remappingFunction): Атомарно об’єднує старе значення з новим (підходить для лічильників).

🔴 Senior Level

Механізм спільного розширення (Cooperative Parallel Resize)

На відміну від HashMap, де один потік бере на себе весь тягар зміни розміру ($O(N)$), у ConcurrentHashMap ресайз є розподіленим і багатопотоковим:

ForwardingNode: Коли бакет успішно перенесено в новий масив, у старий бакет на його місце встановлюється спеціальний маркувальний вузол ForwardingNode (з від’ємним хешем -1).
Допомога інших потоків (helpTransfer): Якщо потік-письменник звертається до бакета, в якому бачить ForwardingNode, він не блокується в очікуванні. Натомість він долучається до перенесення решти бакетів!
Координатор transferIndex: Глобальний лічильник атомарно виділяє кожному потоку пачку бакетів для обробки (крок stride, зазвичай від 16 до 64 бакетів).
Безпечне читання: Потоки, які викликають get(), натрапивши на ForwardingNode, перенаправляються одразу в нову таблицю nextTable без затримок.

Архітектура підрахунку розміру: `CounterCell` (LongAdder Pattern)

У HashMap розмір зберігається в полі int size. У конкурентному середовищі атомарний інкремент одного спільного AtomicInteger спричинив би катастрофічну деградацію швидкодії через Cache Line Bouncing (постійна інвалідація кеш-ліній L1/L2 процесора між ядрами).

У ConcurrentHashMap підрахунок розміру реалізовано за принципом java.util.concurrent.atomic.LongAdder:

private transient volatile long baseCount;
private transient volatile CounterCell[] counterCells;

Потік спочатку намагається атомарно оновити baseCount через CAS.
За високої конкуренції потік обирає комірку в масиві counterCells за своїм потоковим хешем (ThreadLocalRandom.getProbe()) та інкрементує значення всередині неї.
Метод size() / mappingCount() підсумовує baseCount і значення всіх комірок counterCells. Це дає складність $O(1)$ і повну відсутність блокувань під час запису.

Ітератори: семантика Weakly Consistent

Ітератори ConcurrentHashMap (iterator(), spliterator()) мають такі властивості:

Не викидають ConcurrentModificationException.
Можуть безпечно обходити таблицю паралельно з виконанням операцій запису.
Гарантовано обходять елементи, що існували на момент створення ітератора, і можуть (але не зобов’язані) відобразити наступні модифікації.
Створюються без копіювання масиву (snapshot), споживаючи $O(1)$ пам’яті.

4 Tricky Questions

1. Чому метод `get()` у `ConcurrentHashMap` працює без блокувань, але гарантує видимість найсвіжіших даних?

Відповідь: Метод get() не використовує ані synchronized, ані явних блокувань (locks), забезпечуючи мінімальну затримку (latency) завдяки трьом факторам моделі пам’яті Java (JMM):

volatile посилання масиву: Масив вузлів table оголошено як transient volatile Node<K,V>[] table;, а доступ до елементів масиву виконується через volatile-читання (Unsafe.getObjectVolatile / VarHandle).
volatile поля вузла: Усередині класу Node<K,V> поля значення та посилання на наступний елемент оголошені як volatile:
```
volatile V val;
volatile Node<K,V> next;
```
Згідно з JMM, запис у volatile-змінну формує відношення Happens-Before з подальшим читанням цієї змінної в іншому потоці, гарантуючи, що потік-читач побачить найостанніше значення з оперативної пам’яті без застарівання в кешах процесора.
Незмінність (immutability) ключа та хешу: Поля final int hash; і final K key; не можуть змінитися після ініціалізації вузла.

2. Чому код `if (!map.containsKey(k)) map.put(k, v);` не є потокобезпечним навіть із `ConcurrentHashMap`?

Відповідь: Хоча методи containsKey() та put() окремо є потокобезпечними й атомарними, їхня композиція (послідовність викликів) не є атомарною. Між виконанням containsKey() (який поверне false) та наступним викликом put() потік може бути призупинений планувальником ОС. У цей часовий мікроінтервал інший потік встигне записати своє значення за ключем k. Перший потік прокинеться і затре дані другого потоку. Це класичний стан гонитви Check-Then-Act (TOCTOU). Рішення — використання єдиного атомарного методу map.putIfAbsent(k, v) або map.computeIfAbsent(k, ...).

3. Що відбувається під час виклику `size()` у `ConcurrentHashMap`, якщо паралельно тривають тисячі записів? Чи повертає він абсолютно точне значення?

Відповідь: Метод size() (або mappingCount()) повертає знімок розміру таблиці на момент виклику, підсумовуючи baseCount і значення розподіленого масиву CounterCell[]. Специфікація JDK прямо вказує, що в умовах інтенсивного багатопотокового запису значення, яке повертається, є наближеною оцінкою (estimate). До того моменту, як метод закінчить підсумовування всіх комірок, паралельні потоки вже додадуть або видалять нові елементи. Тому покладатися на map.size() == 0 для логіки керування потоками не можна (для цього призначено метод map.isEmpty()).

4. Чи може виникнути Deadlock під час використання методу `computeIfAbsent()` у `ConcurrentHashMap`?

Відповідь: Так, може. Усередині computeIfAbsent потік захоплює монітор бакета synchronized (node). Якщо всередині переданої лямбда-функції спробувати звернутися до цієї ж ConcurrentHashMap для оновлення ключа з того ж або залежного бакета, виникне взаємне блокування або виняток IllegalStateException:

map.computeIfAbsent("key1", k -> {
    // Фатальна помилка: виклик мутувальних методів цієї ж мапи всередині лямбди!
    map.put("key2", 42);
    return 100;
});

Javadoc ConcurrentHashMap суворо забороняє будь-які спроби модифікації мапи всередині функцій зворотного виклику (mappingFunction).

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

Сутність ConcurrentHashMap: Потокобезпечна хеш-таблиця з високою конкурентністю (Java 8+: CAS для порожніх бакетів, synchronized на першому вузлі бакета).
get() Lock-Free: Читання виконується без локів завдяки volatile полям val та next у Node.
Заборона null: null заборонено для ключів і значень, щоб уникнути неоднозначності (ambiguity) в багатопотоковому середовищі.
Ітератори: Слабоузгоджені (Weakly Consistent), не створюють повних копій, не викидають ConcurrentModificationException.
Паралельний Resize: Потоки допомагають один одному переносити бакети через маркер ForwardingNode та transferIndex.
Підрахунок розміру: Виконується через патерн LongAdder (CounterCell[] + baseCount), запобігаючи Cache Line Bouncing.
Правило роботи: Уникайте композицій containsKey + put; використовуйте атомарні методи putIfAbsent, computeIfAbsent, merge.

Червоні прапорці (чого уникати)

Твердження, що ConcurrentHashMap у Java 8+ досі використовує масив Segment[] (сегменти були в Java 7).
Твердження, що ітератор є Fail-safe і копіює весь масив (він Weakly Consistent і працює без знімків у пам’яті).
Використання конструкцій if (!map.containsKey(k)) map.put(k, v) замість атомарних методів.
Твердження, що get() блокує бакет під час читання.

🟢 Junior Level

Головні відмінності від HashMap