🔑 Раздел 10 · Вопрос #23

Что такое ConcurrentHashMap и чем он отличается от HashMap

ConcurrentHashMap — это высокопроизводительная потокобезопасная реализация интерфейса ConcurrentMap (и Map), предназначенная для одновременной работы множества параллельных пото...

🔑 HashMap equals hashCode 📄 Исходный Markdown

🟢 Junior Level

ConcurrentHashMap — это высокопроизводительная потокобезопасная реализация интерфейса ConcurrentMap (и Map), предназначенная для одновременной работы множества параллельных потоков без блокировки всей таблицы целиком.

Главные отличия от HashMap

Характеристика HashMap ConcurrentHashMap
Потокобезопасность ❌ Не потокобезопасна ✅ Потокобезопасна
Поддержка null ✅ Разрешает null-ключ и null-значения ❌ Выбрасывает NullPointerException
Поведение итератора Fail-fast (выбрасывает ConcurrentModificationException) Weakly Consistent (никогда не выбрасывает CME)
Производительность в 1 потоке Максимальная (без накладных расходов) Незначительно ниже (на доли наносекунд)
Многопоточная запись Приводит к гонкам, потере данных и зависаниям Безопасная параллельная запись

Пример базового использования

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;

public class ConcurrentMapDemo {
    public static void main(String[] args) {
        ConcurrentMap<String, Integer> stock = new ConcurrentHashMap<>();

        stock.put("MacBook", 10);

        // Атомарное обновление без гонок:
        stock.merge("MacBook", 1, Integer::sum); // Стало 11

        // Попытка передать null вызовет NullPointerException:
        // stock.put(null, 5); // ОШИБКА в runtime!
    }
}

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

🟡 Middle Level

Архитектура многопоточности в Java 8+

В Java 7 ConcurrentHashMap строился на концепции сегментов (Segment[], по умолчанию 16 сегментов), где каждый сегмент представлял собой отдельную блокирующуюся таблицу (ReentrantLock).

Начиная с Java 8, архитектура была радикально переработана на Node-level locking (блокировка на уровне отдельного бакета):

[Bucket 0] -> Node (CAS вставка)
[Bucket 1] -> synchronized (firstNode) { [Node] -> [Node] -> [Node] }
[Bucket 2] -> ForwardingNode (перенос данных при resize)
[Bucket 3] -> TreeBin (блокировка чтения/записи для красно-чёрного дерева)
  1. Чтение (get): Работает абсолютно без блокировок (Lock-Free). Поля val и next в узле Node объявлены как volatile, что гарантирует немедленную видимость изменений между ядрами CPU по модели памяти Java (JMM).
  2. Вставка в пустой бакет: Выполняется через неблокирующую атомарную инструкцию процессора CAS (Compare-And-Swap) через VarHandle / Unsafe: 
    if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
    break; // Успешно вставили без каких-либо мониторов!
  3. Вставка при коллизии: Блокируется только первый узел (голова) бакета через легковесный монитор synchronized (f). Другие потоки могут свободно и параллельно писать в любые другие бакеты таблицы.

Почему в ConcurrentHashMap категорически запрещен null?

Создатель класса Даг Ли (Doug Lea) исключил null из-за проблемы устранения неоднозначности (Ambiguity) в многопоточной среде.

Если в обычной HashMap метод map.get("key") вернул null, в одном потоке можно однозначно выяснить причину:

if (map.get(key) == null) {
    if (map.containsKey(key)) {
        // Значение действительно null
    } else {
        // Ключа в карте нет
    }
}

В конкурентной среде между вызовом map.get(key) и map.containsKey(key) другой поток может успеть добавить, удалить или обновить ключ. Состояние между проверками становится неконсистентным (TOCTOU — Time-of-Check to Time-of-Use). Запрет null гарантирует: если get(k) == null, ключа в таблице нет на 100%.

Атомарные составные операции

В многопоточных программах нельзя использовать классический шаблон if (!map.containsKey(k)) map.put(k, v); — между проверкой и вставкой возникает состояние гонки. ConcurrentHashMap предоставляет атомарные методы:

  • putIfAbsent(key, value): Вставляет значение только если ключа не было.
  • computeIfAbsent(key, mappingFunction): Атомарно вычисляет и кладет значение, только если ключ отсутствует (идеально для потокобезопасных кэшей).
  • merge(key, value, remappingFunction): Атомарно объединяет старое значение с новым (подходит для счетчиков).

🔴 Senior Level

Механизм совместного ресайза (Cooperative Parallel Resize)

В отличие от HashMap, где один поток берет на себя всю тяжесть ресайза ($O(N)$), в ConcurrentHashMap ресайз является распределенным и многопоточным:

  1. ForwardingNode: Когда бакет успешно перенесен в новый массив, в старый бакет на его место помещается специальный маркировочный узел ForwardingNode (с отрицательным хешем -1).
  2. Помощь других потоков (helpTransfer): Если поток-писатель приходит в бакет, в котором видит ForwardingNode, он не блокируется в ожидании. Вместо этого он подключается к помощи в переносе остальных бакетов!
  3. Координатор transferIndex: Глобальный счетчик атомарно выдает каждому потоку «пачку» бакетов для обработки (шаг stride, обычно от 16 до 64 бакетов).
  4. Безопасное чтение: Потоки, вызывающие get(), натыкаясь на ForwardingNode, перенаправляются сразу в новую таблицу nextTable без задержек.

Архитектура подсчета размера: CounterCell (LongAdder Pattern)

В HashMap размер хранится в поле int size. В конкурентной среде атомарный инкремент одного общего AtomicInteger привел бы к катастрофическому падению скорости из-за Cache Line Bouncing (постоянная инвалидация кэш-линий L1/L2 процессора между ядрами).

В ConcurrentHashMap подсчет размера реализован по принципу java.util.concurrent.atomic.LongAdder:

private transient volatile long baseCount;
private transient volatile CounterCell[] counterCells;
  • Поток сначала пытается атомарно обновить baseCount через CAS.
  • При высокой конкуренции поток выбирает ячейку в массиве counterCells по своему потоковому хешу (ThreadLocalRandom.getProbe()) и инкрементирует значение внутри нее.
  • Метод size() / mappingCount() суммирует baseCount и значения всех ячеек counterCells. Это дает сложность $O(1)$ и полное отсутствие блокировок при записи.

Итераторы: семантика Weakly Consistent

Итераторы ConcurrentHashMap (iterator(), spliterator()) обладают свойствами:

  1. Не выбрасывают ConcurrentModificationException.
  2. Могут безопасно обходить таблицу одновременно с выполняющимися записями.
  3. Гарантированно обходят элементы, существовавшие на момент создания итератора, и могут (но не обязаны) отразить последующие модификации.
  4. Создаются без создания полной копии (snapshot) массива, потребляя $O(1)$ памяти.

4 Tricky Questions

1. Почему метод get() в ConcurrentHashMap работает без блокировок, но гарантирует видимость свежих данных?

Ответ: Метод get() не использует ни synchronized, ни явных локов, обеспечивая минимальный latency благодаря трем факторам модели памяти Java (JMM):

  1. volatile ссылки массива: Массив узлов table объявлен как transient volatile Node<K,V>[] table;, а доступ к элементам массива осуществляется через volatile-чтение (Unsafe.getObjectVolatile / VarHandle).
  2. volatile поля узла: Внутри класса Node<K,V> поля значения и ссылки на следующий элемент объявлены как volatile: 
    volatile V val;
volatile Node<K,V> next;

    Согласно JMM, запись в volatile-переменную формирует отношение Happens-Before с последующим чтением этой переменной в другом потоке, гарантируя, что поток-читатель увидит самое последнее значение из оперативной памяти без устаревания в кэше CPU.

  3. Иммутабельность ключа и хеша: Поля final int hash; и final K key; не могут измениться после инициализации узла.

2. Почему код if (!map.containsKey(k)) map.put(k, v); не является потокобезопасным даже с ConcurrentHashMap?

Ответ: Хотя методы containsKey() и put() по отдельности потокобезопасны и атомарны, их композиция (последовательность вызовов) не является атомарной. Между выполнением containsKey() (который вернет false) и следующим вызовом put() поток может быть приостановлен планировщиком ОС. В этот микроинтервал времени другой поток успеет вставить свое значение по ключу k. Первый поток проснется и перезапишет данные второго потока. Это классическое состояние гонки Check-Then-Act (TOCTOU). Решение — использование единого атомарного метода map.putIfAbsent(k, v) или map.computeIfAbsent(k, ...).

3. Что происходит при вызове size() в ConcurrentHashMap, если параллельно идут тысячи записей? Возвращает ли он абсолютно точное значение?

Ответ: Метод size() (или mappingCount()) возвращает снимок размера таблицы на момент вызова, суммируя baseCount и значения распределенного массива CounterCell[]. Спецификация JDK прямо указывает, что в условиях интенсивной многопоточной записи возвращаемое значение является приблизительной оценкой (estimate). К тому моменту, когда метод закончит суммирование всех ячеек, параллельные потоки уже добавят или удалят новые элементы. Поэтому полагаться на map.size() == 0 для логики управления потоками нельзя (для этого служит map.isEmpty()).

4. Может ли возникнуть Deadlock при использовании метода computeIfAbsent() в ConcurrentHashMap?

Ответ: Да, может. Внутри computeIfAbsent поток захватывает монитор бакета synchronized (node). Если внутри переданной лямбда-функции попытаться обратиться к этой же ConcurrentHashMap для обновления ключа из того же или зависимого бакета, возникнет взаимная блокировка или исключение IllegalStateException:

map.computeIfAbsent("key1", k -> {
    // Фатальная ошибка: вызов мутирующих методов этой же карты внутри лямбды!
    map.put("key2", 42);
    return 100;
});

Javadoc ConcurrentHashMap строго запрещает попытки обновления карты внутри функций обратного вызова (mappingFunction).

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

  • Суть ConcurrentHashMap: Потокобезопасная хеш-таблица с высокой конкурентностью (Java 8+: CAS для пустых бакетов, synchronized на первом узле бакета).
  • get() Lock-Free: Чтение выполняется без локов за счет volatile полей val и next в Node.
  • Запрет null: null запрещен для ключей и значений, чтобы исключить неоднозначность (ambiguity) в многопоточной среде.
  • Итераторы: Слабосогласованные (Weakly Consistent), не создают полных копий, не выбрасывают ConcurrentModificationException.
  • Параллельный Resize: Потоки помогают друг другу переносить бакеты через маркер ForwardingNode и transferIndex.
  • Подсчет размера: Выполняется через паттерн LongAdder (CounterCell[] + baseCount), предотвращая Cache Line Bouncing.
  • Правило работы: Избегайте композиций containsKey + put; используйте атомарные методы putIfAbsent, computeIfAbsent, merge.

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