Главная › Блог › ConcurrentHashMap: как устроена потокобезопасная мапа

ConcurrentHashMap: как устроена потокобезопасная мапа

Почему не хватает synchronizedMap

Самый простой способ сделать мапу потокобезопасной — обернуть HashMap в Collections.synchronizedMap или взять древний Hashtable. Оба варианта лочат всю мапу целиком на каждую операцию, даже на чтение. При высокой конкуренции это превращается в бутылочное горлышко: десять потоков читают из разных бакетов, но все стоят в одной очереди на монитор.

ConcurrentHashMap (CHM) решает это через мелкогранулярную блокировку и активное использование CAS-операций, чтобы читатели вообще не блокировались, а писатели мешали друг другу только если попадают в один и тот же бакет.

Hashtable — это касса в магазине с одним окном: даже если тебе нужно просто спросить цену, ты стоишь в общей очереди. ConcurrentHashMap — это торговый зал с отдельным продавцом на каждый стеллаж: покупатели у разных стеллажей не мешают друг другу, толкучка возможна только у одного и того же ряда.

Эволюция: Java 7 vs Java 8+

В Java 7 CHM был реализован через массив сегментов (Segment), каждый — по сути отдельный маленький Hashtable со своим ReentrantLock. Число сегментов задавалось при создании (concurrencyLevel) и не менялось. Это давало параллелизм записи, но фиксированное число сегментов плохо масштабировалось при большом количестве потоков.

Начиная с Java 8 сегменты убрали. Теперь блокировка происходит на уровне отдельного бакета (узла в table[i]), а не сегмента. Это увеличивает гранулярность блокировки почти до предела — конфликтуют только потоки, которые попадают в один и тот же индекс массива.

Как работает вставка put

Упрощённый алгоритм put в Java 8+:

1. Вычислить хеш ключа, найти индекс бакета i = hash & (n-1)
2. Если table[i] == null — вставить новый узел через CAS (casTabAt),
   без блокировок вообще
3. Если бакет занят — взять synchronized на первом узле бакета
   и добавить/обновить элемент внутри (список или дерево)
4. Если во время вставки идёт resize — помочь с переносом бакетов
5. Обновить счётчик размера через CounterCell (аналог LongAdder)

Ключевой момент: пустой бакет заполняется без единой блокировки — только атомарный CAS. Блокировка (synchronized) берётся только тогда, когда в бакете уже есть хотя бы один узел, и то — только на этот бакет, а не на всю таблицу.

Частая ошибка на собесе — сказать, что CHM использует ReentrantLock на каждый бакет, как было в Java 7. В современной реализации это обычный synchronized на объекте-узле, а не отдельный Lock-объект — экономия памяти на миллионах бакетов существенная.

Почему чтение без блокировок безопасно

Ссылки на узлы (Node.next, значения val) объявлены как volatile. Это значит, что запись в бакет становится видимой другим потокам сразу после публикации ссылки — то есть работает та же гарантия happens-before через volatile, что и в других частях JMM. Поэтому get() вообще не берёт блокировок: он просто читает volatile-поля и идёт по цепочке узлов.

Отсюда следует важное свойство: get() может увидеть промежуточное состояние во время резайза (переноса бакетов), но никогда не увидит «сломанную» структуру — только либо старое, либо уже перенесённое согласованное состояние.

Счётчик размера без единой точки конкуренции

Наивный volatile-counter, инкрементируемый CAS-ом на каждый put, стал бы точкой конкуренции при высокой параллельности записи. Поэтому size считается через механизм, похожий на LongAdder: массив CounterCell, куда потоки пишут в «свою» ячейку по хешу потока, а итоговый size() суммирует все ячейки. Это разносит конкуренцию по нескольким счётчикам вместо одного.

compute, merge и атомарность составных операций

Методы вроде computeIfAbsent, compute, merge выполняются атомарно относительно конкретного ключа — они берут ту же блокировку на бакет, что и put. Это удобно для паттерна «прочитать-изменить-записать» без внешней синхронизации, но есть подвох: лямбда внутри compute не должна сама лезть в ту же мапу — можно получить deadlock, так как блокировка уже держится на этом бакете.

Может ли ConcurrentHashMap потерять элементы при параллельной записи?

Нет, отдельные операции put/get/remove линейно согласованы для конкретного ключа за счёт CAS и synchronized на бакете. Но составные операции из нескольких вызовов (например, containsKey + put) не атомарны в совокупности — для этого нужны compute/merge или putIfAbsent.

Чем null в качестве значения опасен для ConcurrentHashMap?

CHM запрещает null-ключи и null-значения (в отличие от HashMap), потому что в многопоточной среде нельзя однозначно отличить «ключа нет» от «значение null» без дополнительной блокировки — это создавало бы гонку при проверках типа containsKey после get.