Как 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]]