🟢 Junior Level

ConcurrentHashMap — це потокобезпечна версія HashMap. Кілька потоків можуть одночасно читати і записувати дані без проблем.

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

HashMap	ConcurrentHashMap
Не потокобезпечна	Потокобезпечна
Швидша в одному потоці	Трохи повільніша, але безпечна
Дозволяє null ключі/значення	Забороняє null
Fail-fast ітератор	Weakly Consistent ітератор (не кидає CME)

Приклад:

// HashMap — впаде в багатопотоковому середовищі
Map<String, Integer> unsafe = new HashMap<>();

// ConcurrentHashMap — безпечно
ConcurrentMap<String, Integer> safe = new ConcurrentHashMap<>();
safe.put("key1", 100);
safe.putIfAbsent("key2", 200); // Атомарна операція

Коли використовувати: Коли до мапи звертаються кілька потоків одночасно.

🟡 Middle Level

Архітектура ConcurrentHashMap (Java 8+)

Характеристика	HashMap	ConcurrentHashMap
Потокобезпечність	Ні	Так
Блокування	Ні	Побакетні (synchronized на голові бакета)
Null-ключі/значення	Дозволені	Заборонені (NPE)
Ітератор	Fail-fast	Weakly Consistent (snapshot на момент створення)
Атомарні операції	Ні	putIfAbsent, computeIfAbsent, merge

Як працює потокобезпечність

1. CAS (Compare-And-Swap) — для порожнього бакета блокування не потрібне
2. synchronized на голові бакета — лише при колізіях
3. volatile поля — гарантії видимості між потоками

// CAS для порожнього бакета:
if (casTabAt(tab, i, null, newNode))
    break; // Успішно, без блокування!

// synchronized при колізії:
synchronized (f) {
    // Додавання в список/дерево
}

Чому заборонений null?

В багатопотоковому середовищі get(key) = null неоднозначно:

• Ключа немає? Або значення = null?
• Не можна атомарно перевірити containsKey() після get() — стан може змінитися

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

map.putIfAbsent("key", 100);     // Перевірка + вставка = атомарно
map.computeIfAbsent("key", k -> computeExpensive(k)); // Ліниве обчислення
map.merge("key", 1, Integer::sum); // Атомарне оновлення

Ітерація: Weakly Consistent

for (Map.Entry<String, Integer> e : map.entrySet()) {
    // Не кине ConcurrentModificationException
    // Може не побачити зміни, зроблені після створення ітератора
}

🔴 Senior Level

Internal Implementation (Java 8+)

transient volatile Node<K,V>[] table;

Ключові відмінності від HashMap:

• volatile масив — гарантії видимості
• volatile поля Node (val, next) — happens-before
• ForwardingNode при resize — сигналізує про прогрес

Multi-threaded Resize

// При resize кілька потоків можуть допомагати:
private transient volatile int transferIndex;

Потоки координуються через transferIndex, кожен обробляє свій діапазон бакетів. Це прискорює resize у високонавантажених системах.

Lock Striping vs Node-level Locking

Підход	Java 7 (Segment)	Java 8+ (Node)
Гранулярність	16 сегментів	Кожен бакет
Конкуренція	До 16 потоків	До capacity потоків
Overhead	Менше	Мінімальний

Memory Ordering

ConcurrentHashMap використовує full memory barrier через volatile:

• Запис у val видний всім потокам
• Happens-before між put і get з різних потоків
• Жодних stale reads

Why No Null?

Liveness Problem в багатопотоковості:

// Потенційний сценарій без заборони null:
if (map.get(key) == null) {      // null чи немає ключа?
    if (!map.containsKey(key)) { // Ключа немає... або він видалений між викликами?
        map.put(key, value);     // TOCTOU race!
    }
}

Benchmark

Метрика	HashMap	ConcurrentHashMap
get (1 thread)	5 ns	8 ns
get (8 threads)	N/A (race)	60 ns
put (1 thread)	8 ns	15 ns
put (8 threads)	N/A (race)	120 ns

Overhead ~60% на single-thread, але на 8 threads — єдиний коректний варіант.

Production Best Practices

1. Default choice для багатопотоковості — ConcurrentHashMap
2. Атомарні операції — compute, merge замість check-then-act
3. size() в Java 8+ використовує систему CounterCell і працює за O(1) у звичайному випадку. Результат точний, але може застаріти до моменту використання — не використовуйте в hot path.
4. Bulk operations — forEach, search, reduce (Java 8+) з parallelism threshold

---

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

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

• ConcurrentHashMap — потокобезпечна через CAS + synchronized на голові бакета
• Забороняє null-ключі/значення — усуває ambiguity в check-then-act
• Weakly Consistent ітератор — snapshot на момент створення, не кидає CME
• Атомарні операції: putIfAbsent, computeIfAbsent, merge — замінюють check-then-act
• Java 8+: node-level locking (раніше Java 7: segment-level, 16 сегментів)
• size() через CounterCell: O(1), точний але може застаріти
• Multi-threaded resize: потоки допомагають через transferIndex

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

• Чому заборонений null? — get=null неоднозначно (немає ключа чи значення=null?), ламає putIfAbsent
• Чим Weakly Consistent відрізняється від Fail-safe? — Weakly Consistent: бачить зміни після створення, але не гарантує повноту
• Чому не synchronizedMap? — один м’ютекс на все; CHM = конкурентний доступ до різних бакетів
• Overhead vs HashMap? — ~60% на single-thread, але єдиний коректний варіант для multi-thread

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

• «ConcurrentHashMap використовує volatile поля Node» — ні, CAS + memory barriers
• «Fail-safe ітератор» — правильно: Weakly Consistent
• «size() = O(n)» — ні, в Java 8+ через CounterCell = O(1)

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

• [[22. Як HashMap працює в багатопотоковому середовищі]]
• [[25. Чи можна зберігати null значення в HashMap]]
• [[26. В чому різниця між HashMap та Hashtable]]