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

🟢 Junior Level

ConcurrentHashMap безпечний для потоків завдяки трьом механізмам:

CAS — для вставки в пусту корзину (без блокувань)
Volatile — щоб усі потоки бачили останні дані
Synchronized — тільки для колізій (блокує одну корзину)

Як вони працюють разом:

CAS = вставка нового елемента без блокувань
Volatile = видимість змін між потоками (кожен потік одразу бачить нові елементи)
Synchronized = захист при колізіях (коли два потоки одночасно пишуть в одну корзину)

// Безпечно з різних потоків:
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

// Потік 1:
map.put("A", 1);

// Потік 2 (одночасно):
map.put("B", 2);

// Обидва безпечно!

🟡 Middle Level

Три кити безпеки

1. CAS (Compare-And-Swap):

// Для пустої корзини:
if (CAS(table[i], null, newNode)) {
    // Успіх! Вставили без блокувань
} else {
    // Інший потік вставив → retry
}

2. Volatile:

// Усі поля volatile:
transient volatile Node[] table;
volatile V val;
volatile Node next;

// → Запис одного потоку видна всім
// → get() без блокувань!

3. Synchronized на корзину:

// Якщо колізія:
synchronized (firstNode) {  // Тільки ця корзина!
    // Вставка/видалення
}
// → Решта корзин працюють паралельно!

Атомарні методи

map.putIfAbsent(key, value);      // Атомарно
map.computeIfAbsent(key, func);   // Атомарно
map.merge(key, value, func);      // Атомарно

// Без цих методів:
// ❌ Race condition!
// Race condition покроково:
// Потік 1: containsKey = false (ключа немає)
// Потік 2: containsKey = false (ключа все ще немає)
// Потік 1: put(key, value1)  ← вставив
// Потік 2: put(key, value2)  ← ПЕРЕЗАПИСАВ! Втрата оновлення.
if (!map.containsKey(key)) {
    map.put(key, value);  // Інший потік може вклинитися!
}

🔴 Senior Level

Коли НЕ використовувати ConcurrentHashMap

Однопоточний доступ — оверхед CAS/volatile без причини
Read-only мапа після публікації — достатньо HashMap (після safe publication)
Потрібні null значення — CHM забороняє null ключі і значення

ForwardingNode і паралельний Resizing

// При ресайзі:
// Стара корзина → ForwardingNode

// Потік-писар бачить ForwardingNode:
if (node instanceof ForwardingNode) {
    // Допомагає ресайзити!
    table = helpTransfer(table, forwardingNode);
}

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

CounterCells (LongAdder патерн)

LongAdder — стратегія: замість однієї volatile-змінної (contention при конкурентному записі), масив лічильників. Кожен потік пише у свою комірку, результат = сума всіх комірок.

// Замість одного volatile size:
transient volatile CounterCell[] counterCells;

// Кожен потік:
counterCells[hash(threadId) & mask].value++;

// size() = sum(counterCells)

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

Treeification захист

> 8 елементів в корзині → червоно-чорне дерево
→ Навіть при Hash DoS атаці: O(log n)

// Node → TreeNode заміна
// Синхронізація все ще на HEAD

ReservationNode

ReservationNode = placeholder-вузол, що блокує корзину поки обчислюється значення в computeIfAbsent. Запобігає дублікатам від інших потоків.

// computeIfAbsent для пустої корзини:
// Вставляє ReservationNode → синхронізується на ньому
// → Запобігає дублікатам поки функція обчислюється

Contention діагностика

// Якщо CHM гальмує:
// 1. async-profiler → blocked стан
// 2. Багато потоків на CHM.put
// 3. → Всі в одну корзину!

// Причина: поганий hashCode()
// → Усі ключі хешуються в один bucket
// → Synchronized на одну корзину
// → 0 паралелізму!

// Рішення: переписати hashCode()

Java 7 vs Java 8+

Java 7: Segment[] segments (16 фіксовано)
  → Блокування на сегмент
  → size() = блокування ВСІХ сегментів

Java 8+: Node-level locking
  → Блокування на корзину
  → CAS для пустих корзин
  → size() = сума CounterCells
  → Parallel resizing

Best Practices

CAS = lock-free для нових ключів
Volatile = видимість без блокувань
Synchronized = тільки на корзину
helpTransfer = паралельний ресайз
CounterCells = масштабований size()
Bad hashCode = головний ворог
compute = не блокуйте надовго

Резюме для Senior

CAS для пустих корзин, Synchronized для колізій
Volatile = lock-free читання
ForwardingNode = паралельний ресайз
CounterCells = LongAdder патерн для size
Treeification = захист від DoS
Bad hashCode = contention = 0 паралелізму
helpTransfer = потоки допомагають ресайзити

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

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

Три механізми thread-safety: CAS (lock-free вставка в пусту корзину), volatile (видимість між потоками), synchronized (захист при колізіях на рівні корзини)
CAS = атомарна процесорна інструкція: «запиши нове, тільки якщо поточне дорівнює очікуваному». Два потоки пишуть одночасно — один succeeds, інший retry.
Volatile поля: table, Node.val, Node.next — get() без блокувань, happens-before гарантія
Synchronized тільки на HEAD корзини — решта корзин працюють паралельно
Атомарні методи: putIfAbsent, computeIfAbsent, merge — замінюють check-then-act (race condition)
ForwardingNode при ресайзі — потоки-писарі бачать його і викликають helpTransfer() (паралельний ресайз)
CounterCells = LongAdder патерн: масив лічильників, кожен потік пише у свою комірку, size() = сума
Treeification при > 8 елементів в корзині — захист від Hash DoS, O(log n) навіть при атаці
ReservationNode в computeIfAbsent — placeholder запобігає дублікатам від інших потоків

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

Чому не можна замінити CHM на HashMap у багатопотоковому коді? — Race condition: два потоки одночасно роблять containsKey = false, обидва роблять put — один перезаписує іншого. Втрата оновлень.
Що таке race condition в контексті Map? — Потік 1 перевірив «ключа немає», Потік 2 перевірив «ключа немає», обидва вставили — другий перезаписав перший. Вирішується computeIfAbsent (атомарно).
Як діагностувати contention в CHM? — async-profiler показує blocked час. Причина: поганий hashCode() → усі ключі в одну корзину → synchronized на одну корзину → 0 паралелізму.
Чим Java 8+ CHM відрізняється від Java 7? — Java 7: Segment[] (16 фіксованих, блокування на сегмент). Java 8+: node-level locking + CAS, паралельний ресайз, CounterCells.

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

❌ «CHM блокує всю мапу при запису» — тільки одну корзину (synchronized на HEAD)
❌ «get() в CHM використовує synchronized» — ні, lock-free читання через volatile
❌ «CHM використовує Segment locking в Java 8+» — це застаріло, тепер node-level locking
❌ «computeIfAbsent можна замінити на containsKey + put» — ні, це не атомарно, race condition

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

[[18. Що таке ConcurrentHashMap]]
[[12. Як працює HashSet всередині]]
[[14. Що таке Map і які реалізації існують]]
[[20. Що таке CopyOnWriteArrayList]]