📦 Раздел 4 · Вопрос #19

Как ConcurrentHashMap обеспечивает thread-safety

Класс ConcurrentHashMap обеспечивает безопасность в многопоточной среде без использования глобальных блокировок на весь объект. Вместо того чтобы выстраивать все потоки в одну о...

📦 Коллекции 📄 Исходный Markdown

🟢 Junior Level

1. Фундаментальный принцип потокобезопасности

Класс ConcurrentHashMap обеспечивает безопасность в многопоточной среде без использования глобальных блокировок на весь объект. Вместо того чтобы выстраивать все потоки в одну очередь (как это делают Hashtable или Collections.synchronizedMap), ConcurrentHashMap использует комбинацию трёх механизмов:

  1. Lock-Free чтение (get): операции чтения выполняются вообще без каких-либо блокировок и не конфликтуют с операциями записи.
  2. CAS (Compare-And-Swap): атомарная инструкция процессора для бесконфликтной вставки элементов в пустые корзины (бакеты).
  3. Мелкогранулярная синхронизация (Node-Level Lock): при возникновении коллизий блокируется только первый узел конкретного бакета (synchronized (head)). Все остальные бакеты хэш-таблицы остаются открытыми для параллельной записи другими потоками.
Поток 1 ──► put("A", 1) ──► Бакет [2] (заблокирован монитор ноды 'A')
Поток 2 ──► put("B", 2) ──► Бакет [7] (свободен, выполняется параллельно!)
Поток 3 ──► get("C")    ──► Бакет [5] (без блокировок, параллельно!)

🟡 Middle Level

1. Архитектура полей и гарантии Java Memory Model (JMM)

Внутри ConcurrentHashMap массив бакетов и поля связных узлов объявлены со спецификатором volatile:

// Массив бакетов:
transient volatile Node<K,V>[] table;

// Внутренний класс узла:
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;       // volatile значение!
    volatile Node<K,V> next; // volatile ссылка на следующий узел!
}

Почему чтение get() абсолютно свободно от блокировок:

  1. Доступ к ячейкам массива table[i] осуществляется через атомарный метод tabAt() с семантикой volatile load (через Unsafe / VarHandle).
  2. Поля val и next объявлены как volatile.
  3. Согласно спецификации JMM, запись в volatile-переменную формирует отношение Happens-Before с последующим чтением из этой же переменной. Поток-читатель гарантированно видит самые свежие данные, записанные любым потоком-писателем, без необходимости захвата мьютекса.

2. Алгоритм вставки putVal(): шаг за шагом

Когда поток вызывает map.put(key, value):

                          ┌───────────────────────────┐
                          │   Вызов put(key, value)   │
                          └─────────────┬─────────────┘
                                        │
                         Хэширование: spread(key.hashCode())
                                        │
                                        ▼
                                ┌───────────────┐
                     ┌──────────┤ table == null?├──────────┐
                     │          └───────────────┘          │
                  ДА │                                     │ НЕТ
                     ▼                                     ▼
           initTable() через CAS                  Индекс i = (n-1) & hash
                     │                                     │
                     └──────────────────┐                  ▼
                                        │         ┌─────────────────┐
                                        └────────►│  table[i] пуст? │
                                                  └────────┬────────┘
                                                 ДА │             │ НЕТ
                                                    │             │
                    ┌───────────────────────────────┘             ▼
                    ▼                                   ┌────────────────────┐
        CAS: casTabAt(table, i, null, node)             │ hash == MOVED (-1)?│
                    │                                   └─────────┬──────────┘
           ┌────────┴────────┐                                 ДА │         │ НЕТ
        УСПЕХ              FAIL                                   │         │
           │                 │                                    │         ▼
        ГОТОВО            RETRY               helpTransfer() ◄────┘   synchronized (head) {
                                                                        Вставка в список/дерево
                                                                      }
  1. Проверка на null: если ключ или значение равны null, сразу выбрасывается NullPointerException.
  2. Вычисление индекса бакета: хэш-код подмешивается функцией spread(), после чего индекс находится как (n - 1) & hash.
  3. Бакет пуст (tabAt == null): поток пытается вставить новую ноду с помощью инструкции casTabAt (Compare-And-Swap):
    • Если ячейка все еще null, нода записывается атомарно без блокировок.
    • Если другой поток успел вклиниться за этот такт, CAS завершается неудачей (false), и цикл for уходит на повторную итерацию (Retry).
  4. Бакет находится в процессе ресайза (node.hash == MOVED): поток не ждет пассивно, а подключается к переносу данных через helpTransfer().
  5. В бакете коллизия (есть элементы): захватывается монитор первого узла бакета: 
    synchronized (f) {
    if (tabAt(tab, i) == f) { // Double Check: проверяем, что голова не изменилась
        if (fh >= 0) {
            // Обход связного списка: перезапись или добавление в хвост
        } else if (f instanceof TreeBin) {
            // Добавление в красно-черное дерево
        }
    }
}
  6. Деревизация: если длина списка в бакете достигает 8 (TREEIFY_THRESHOLD), вызывается treeifyBin() для превращения списка в красно-черное дерево (при емкости таблицы $\ge 64$).

🔴 Senior Level

1. Распределенный параллельный ресайз: ForwardingNode и helpTransfer()

В HashMap увеличение таблицы (resize()) блокирует либо инвалидирует всю структуру данных. В ConcurrentHashMap ресайз является кооперативным и многопоточным:

  1. Когда суммарное число элементов превышает порог, первый поток инициирует создание массива nextTable удвоенного размера.
  2. Исходная таблица делится на диапазоны бакетов (страйды, минимум 16 корзин на поток).
  3. Поток переносит свой диапазон корзин в новую таблицу.
  4. Как только бакет полностью перенесен, в старой таблице вместо него выставляется специальный сторожевой узел — ForwardingNode с системным хэшем MOVED = -1, хранящий ссылку на nextTable.
  5. Кооперация: любой другой поток, пришедший выполнить put() или remove() и попавший на ForwardingNode, распознает ресайз и вызывает метод helpTransfer(). Вместо ожидания он берет следующий нераспределенный страйд бакетов и помогает миграции!
  6. Чтение при ресайзе: вызовы get() при встрече с ForwardingNode не блокируются, а беспрепятственно перенаправляются в nextTable через вызов ForwardingNode.find().

2. Специальные служебные узлы (Special Sentinel Nodes)

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

Тип узла Хэш-код Назначение
Node<K,V> $\ge 0$ Обычный узел односвязного списка коллизий
ForwardingNode -1 (MOVED) Маркер перенесенного бакета при ресайзе; перенаправляет в nextTable
TreeBin -2 (TREEBIN) Заголовок сбалансированного красно-черного дерева (инкапсулирует TreeNode)
ReservationNode -3 (RESERVED) Временный узел-заглушка для атомарного метода computeIfAbsent()

Роль ReservationNode:

Когда вызывается map.computeIfAbsent(key, mappingFunction) для еще не существующего ключа в пустом бакете, мапа не может заранее знать результат вычисления функции. Чтобы не допустить гонки, поток атомарно через CAS ставит в бакет ReservationNode, блокирует его монитор (synchronized (r)), выполняет пользовательскую лямбду и затем подменяет заглушку реальным вычисленным значением.

3. Эволюция: почему в Java 8 отказались от Segment (Java 7)?

В Java 7 мапа состояла из массива сегментов (Segment<K,V>[]), где каждый сегмент наследовал ReentrantLock.

  • Проблема 1: Число сегментов фиксировалось при инициализации (по умолчанию 16). Даже если в таблице было 100 000 элементов, параллельно писать могли максимум 16 потоков.
  • Проблема 2: Каждый сегмент представлял собой отдельный тяжелый объект-блокировку, создавая громадный оверхед по памяти.
  • Проблема 3: Метод size() в Java 7 требовал блокировки всех сегментов подряд, если за два прохода без блокировок мапа менялась.

В Java 8+ произошел переход на Node-Level Locking:

  • Блокировка перенесена на саму ноду бакета (synchronized (firstNode)).
  • Уровень потенциального параллелизма возрос с фиксированных 16 до числа непустых бакетов таблицы (тысячи параллельных записей).
  • Для пустых бакетов блокировки отсутствуют вовсе благодаря CAS.

🎯 Шпаргалка для интервью

30-секундный ответ (Elevator Pitch)

«ConcurrentHashMap в Java 8+ обеспечивает потокобезопасность на трёх уровнях:

  1. Lock-Free чтение: метод get() не использует блокировок, полагаясь на семантику volatile для массива table, поля значений val и ссылок next.
  2. CAS-вставка: вставка в пустой бакет выполняется атомарной машинной инструкцией процессора Compare-And-Swap без блокировок.
  3. Блокировка бакета: при коллизиях блокируется только монитор первого узла конкретного бакета (synchronized(head)). Кроме того, ресайз выполняется распределенно: потоки встречают ForwardingNode и кооперируются через helpTransfer(), а подсчет размера масштабируется через страйпированные счетчики CounterCell».

3 каверзных вопроса на интервью с ответами

1. Почему чтение get() не требует блокировки, даже если в этот момент другой поток перестраивает список коллизий?

Ответ: Поля val и next в нодах объявлены как volatile. При добавлении нового элемента он прилинковывается к концу списка или через CAS, что гарантирует отношение Happens-Before между записью и чтением. Даже если происходит ресайз таблицы, поток-читатель встречает ForwardingNode и продолжает поиск в новой таблице nextTable без задержек.

2. Зачем в блоке synchronized (f) внутри putVal выполняется проверка if (tabAt(tab, i) == f)?

Ответ: Это реализация паттерна Double-Checked Locking. Между моментом, когда поток прочитал ссылку на головной узел f из массива бакетов, и моментом, когда он успешно захватил монитор synchronized (f), другой поток мог изменить структуру бакета (например, удалить головной узел, перенести бакет при ресайзе или превратить список в дерево). Повторная проверка гарантирует, что захваченный объект f всё еще действительно является первым элементом бакета.

3. Почему разработчики Java 8 выбрали synchronized (node), а не ReentrantLock?

Ответ:

  1. ReentrantLock — это отдельный объект в куче, требующий выделения памяти под сам замок и его очередь ожидания (AQS Sync). Использование сотен тысяч объектов ReentrantLock на каждую корзину вызвало бы колоссальный расход памяти.
  2. В Java встроенный synchronized оптимизируется JVM на уровне машинного кода: он использует заголовок самого существующего объекта Node (Mark Word), поддерживает адаптивный спиннинг (Adaptive Spinning) и не требует создания дополнительных объектов.

Типичные ошибки и Red Flags

  • ❌ Утверждение, что ConcurrentHashMap использует блокировку сегментов (Segments): Сегменты были полностью удалены в Java 8 (2014 г.).
  • ❌ Считать, что get() блокирует пишущие потоки: Операции чтения в CHM lock-free.
  • ❌ Использование внешнего synchronized(map) вокруг CHM: Убивает весь параллелизм и сводит преимущества CHM к нулю. Для составных атомарных действий используйте методы compute, merge, putIfAbsent.
  • ❌ Игнорирование риска взаимной блокировки в лямбдах compute: Вызов других методов map внутри лямбды computeIfAbsent может привести к дедлоку.

Связанные темы