Що таке ConcurrentHashMap?

🟢 Junior Level

ConcurrentHashMap — потокобезпечна Map для багатопотокових додатків.

На відміну від Collections.synchronizedMap(new HashMap<>()) (одне блокування на всю мапу), CHM дозволяє багатьом потокам працювати паралельно, блокуючи тільки окремі корзини.

Головна відмінність від HashMap:

HashMap: не безпечна для потоків
ConcurrentHashMap: безпечна, без блокувань для читання

Map<String, Integer> map = new ConcurrentHashMap<>();

// Безпечно з різних потоків
map.put("A", 1);
map.get("A");  // → 1

// null не можна!
map.put("A", null);  // → NullPointerException!

Правило:

Один потік або thread-local → HashMap
Кілька потоків читають і пишуть → ConcurrentHashMap
Кілька потоків тільки читають → підійде і HashMap (після safe publication)

🟡 Middle Level

Еволюція

Java 7: Segment Locking

Java 7 — історична довідка, не використовується в сучасному коді.

Мапа розділена на 16 сегментів
  → Потоки на різних сегментах не блокуються
  → size() = блокування ВСІХ сегментів!

Java 8+: Node-level Locking

CAS для пустих корзин (без блокувань!)
Synchronized тільки для колізій (на корзину!)
  → Максимальний паралелізм

Атомарні операції

map.putIfAbsent(key, value);  // Вставити якщо немає

map.computeIfAbsent(key, k -> new ArrayList<>())
   .add(value);  // Обчислити і вставити

map.merge(key, 1, Integer::sum);  // Атомарне оновлення

Особливості

// ❌ null заборонений!
map.put(key, null);  // → NullPointerException

// ⚠️ size() приблизний!
int size = map.size();  // Може змінитися одразу!

// ✅ mappingCount() для великих колекцій
long count = map.mappingCount();  // > 2^31

// ✅ Ітератори НЕ кидають Exception
// → Weakly consistent
// → Weakly consistent = ітератор бачить дані на момент створення і може (але не зобов'язаний) побачити подальші зміни. Ніколи не кидає ConcurrentModificationException.
for (var entry : map) { ... }  // Безпечно

🔴 Senior Level

Lock-free Reads

// get() БЕЗ блокувань!
// Через volatile поля:
//   table array → volatile
//   Node.val → volatile
//   Node.next → volatile

// Happens-Before гарантія:
// → Читач бачить останній запис

CAS + Synchronized

CAS (Compare-And-Swap) — атомарна процесорна інструкція: «запиши нове значення, тільки якщо поточне дорівнює очікуваному». Працює без блокувань — якщо два потоки одночасно пишуть, один succeeds, інший retry.

put(key, value):
  1. Корзина пуста → CAS (без блокувань!)
  2. Корзина зайнята → synchronized на HEAD
     → Тільки ця корзина заблокована
     → Решта працюють паралельно

Parallel Resizing

При ресайзі:
  → ForwardingNode в старих корзинах
  → Потоки-писарі БАЧАТЬ ForwardingNode
  → Викликають helpTransfer() → ДОПОМАГАЮТЬ ресайзити!

→ Розподілений ресайз, без повного блокування

CounterCells

Замість одного volatile size:
  → Масив CounterCell (як LongAdder)
  → Кожен потік інкрементує СВІЮ комірку
  → size() = сума всіх комірок

→ Мінімальний contention!

Compute пастка

// ❌ Довга операція в compute
map.computeIfAbsent(key, k -> {
    Thread.sleep(10000);  // Блокує корзину на 10 сек!
    return value;
});

// ❌ Рекурсивний доступ → Deadlock!
map.computeIfAbsent(key1, k -> {
    return map.get(key2);  // Може чекати ту саму корзину!
});

Java 21: Virtual Threads

synchronized в CHM може «пінити» віртуальні потоки
  → Але критичні секції ДУЖЕ короткі
  → Рідко проблема на практиці

Якщо проблема:
  → async-profiler покаже blocked час

Production Experience

Реальний сценарій: Bad hashCode

// Усі ключі → одна корзина
// → Synchronized на одну корзину
// → 100 потоків чекають → 0 паралелізму!

// Рішення: переписати hashCode()
// Результат: +500% throughput

Best Practices

За замовчуванням для багатопотоковості
null заборонений — захист від неоднозначності
computeIfAbsent — атомарна ініціалізація
Не довгі операції в compute
mappingCount() > size() для > 2^31
Bad hashCode → головний ворог паралелізму
Weakly consistent ітератори

Резюме для Senior

CAS для пустих корзин, synchronized для колізій
Lock-free читання через volatile
Parallel resizing з helpTransfer()
CounterCells = масштабований лічильник
compute → не довгі операції, немає рекурсії
null заборонений — філософське рішення
Bad hashCode → contention на одну корзину

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

Обов’язково знати:

ConcurrentHashMap — thread-safe Map, на відміну від HashMap дозволяє паралельну роботу без повного блокування
Java 8+: CAS для пустих корзин (lock-free) + synchronized тільки на корзину при колізіях (замість Segment locking з Java 7)
Lock-free читання через volatile: table, Node.val, Node.next — get() без блокувань
null заборонені (ключі і значення) — захист від неоднозначності (null = ключ відсутній vs null = значення)
Ітератори weakly consistent — не кидають ConcurrentModificationException, можуть не бачити останні зміни
Parallel resizing: ForwardingNode + helpTransfer() — потоки-писарі допомагають ресайзити
CounterCells (як LongAdder) — кожен потік інкрементує свою комірку, size() = сума
size() приблизний, mappingCount() > 2^31 елементів

Часті уточнюючі запитання:

Чим CHM відрізняється від Collections.synchronizedMap? — synchronizedMap блокує ВСЮ мапу на кожну операцію. CHM блокує тільки одну корзину (synchronized) або не блокує зовсім (CAS).
Чому null заборонені в CHM? — Щоб відрізнити «ключа немає» (get = null) від «значення = null». У HashMap це неможливо, що створює неоднозначність.
Що буде при довгій операції в computeIfAbsent? — Блокування корзини на весь час обчислення. Інші потоки, що пишуть у ту саму корзину, чекатимуть. Рекурсивний доступ → deadlock.
Як CHM ресайзиться без повного блокування? — Виставляє ForwardingNode в старих корзинах. Потоки-писарі, побачивши його, викликають helpTransfer() і допомагають переносити дані.

Червоні прапорці (НЕ говорити):

❌ «CHM використовує Segment locking» — це Java 7, в Java 8+ node-level locking
❌ «CHM повністю блокує мапу при запису» — блокує тільки одну корзину, решта працюють
❌ «CHM підтримує null значення» — ні, NullPointerException для null ключів і значень
❌ «size() в CHM точний» — приблизний, може змінитися одразу після виклику

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

[[19. Як ConcurrentHashMap забезпечує thread-safety]]
[[14. Що таке Map і які реалізації існують]]
[[20. Що таке CopyOnWriteArrayList]]
[[15. В чому різниця між HashMap, LinkedHashMap та TreeMap]]