Как реализовать ConcurrentHashMap?

Реализация ConcurrentHashMap: подходы и внутреннее устройство

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

📊 Эволюция архитектуры: от сегментов до CAS

В Java 7 использовалась архитектура на основе сегментов (Segments), где карта делилась на несколько независимых блоков (по умолчанию 16), и каждый управлялся отдельным ReentrantLock. Это позволяло разным потокам работать с разными сегментами одновременно.

// Упрощенная структура сегментов (Java 7)
public class ConcurrentHashMap<K, V> {
    private final Segment<K, V>[] segments;
    
    static final class Segment<K, V> extends ReentrantLock {
        volatile HashEntry<K, V>[] table;
    }
}

В Java 8 произошел принципиальный переход к более эффективной реализации, основанной на:

• Массиве Node[] вместо сегментов
• CAS (Compare-And-Swap) операциях для атомарных модификаций
• Синхронизации на уровне отдельных бакетов при коллизиях

🔧 Ключевые компоненты реализации

1. Структура узлов (Nodes)

Базовый элемент хранения — это Node<K, V>, который может быть нескольких типов:

• Обычный Node — для цепочек в одном бакете
• TreeBin — корень красно-черного дерева при больших цепочках
• ForwardingNode — специальный узел при ресайзинге

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

2. Основные операции и их реализация

Get операция — не требует блокировок

public V get(Object key) {
    int hash = spread(key.hashCode());
    Node<K, V>[] tab = table;
    if (tab != null) {
        Node<K, V> e = tabAt(tab, (tab.length - 1) & hash);
        while (e != null) {
            if (e.hash == hash && key.equals(e.key))
                return e.val;
            e = e.next;
        }
    }
    return null;
}

Особенности:

• Использует volatile чтение через tabAt()
• Не блокирует другие операции
• Гарантирует happens-before благодаря volatile полям

Put операция — умная синхронизация

public V put(K key, V value) {
    return putVal(key, value, false);
}

final V putVal(K key, V value, boolean onlyIfAbsent) {
    // 1. Проверка на нулевые значения
    if (key == null || value == null) throw new NullPointerException();
    
    // 2. Вычисление хэша
    int hash = spread(key.hashCode());
    
    // 3. Цикл вставки с CAS операциями
    for (Node<K, V>[] tab = table;;) {
        Node<K, V> f; int n, i, fh;
        
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();  // ленивая инициализация
            
        // CAS попытка вставить в пустой бакет
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null, new Node<K, V>(hash, key, value)))
                break;
        }
        // При ресайзинге — помощь в перемещении
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            // Синхронизация на первом узле бакета
            synchronized (f) {
                // Вставка в цепочку или дерево
            }
        }
    }
    // 4. Проверка необходимости преобразования в дерево
    addCount(1L, binCount);
    return null;
}

3. Ресайзинг (расширение таблицы)

Процесс инкрементального ресайзинга — одна из самых сложных частей реализации:

• Происходит постепенно, не блокируя всю карту
• Потоки помогают в перемещении узлов при своих операциях
• Используется ForwardingNode для маркировки перемещенных бакетов

// Упрощенный процесс ресайзинга
private final void transfer(Node<K, V>[] tab, Node<K, V>[] nextTab) {
    int n = tab.length;
    
    // Создание новой таблицы в 2 раза больше
    if (nextTab == null) {
        nextTab = new Node<?, ?>[n << 1];
    }
    
    // Постепенное перемещение бакетов
    while (advance) {
        // Перемещение узлов из старого бакета
        synchronized (f) {
            // Разделение цепочки на две части
            // (сохранение в старом и новом индексе)
        }
    }
}

🛠️ Технические особенности и оптимизации

Атомарные операции через Unsafe

// Получение элемента из массива с volatile семантикой
static final <K, V> Node<K, V> tabAt(Node<K, V>[] tab, int i) {
    return (Node<K, V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}

// CAS установка элемента
static final <K, V> boolean casTabAt(Node<K, V>[] tab, int i,
                                      Node<K, V> c, Node<K, V> v) {
    return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}

Счетчики размера с разделением (Striped Counters)

Для подсчета элементов используется LongAdder-подобная структура с массивом счетчиков (CounterCell[]) чтобы минимизировать конкуренцию:

• Каждый поток обновляет свой счетчик
• Сумма вычисляется при необходимости
• Используется @sun.misc.Contended для предотвращения false sharing

// Базовая структура счетчиков
@sun.misc.Contended static final class CounterCell {
    volatile long value;
    CounterCell(long x) { value = x; }
}

Конверсия в дерево (Treeification)

При длине цепочки > 8 (и общем размере таблицы > 64) происходит преобразование связанного списка в TreeBin:

• Используется красно-черное дерево
• Гарантирует O(log n) поиск при коллизиях
• TreeBin содержит несколько специальных методов для конкурентного доступа

📈 Практические аспекты использования

Преимущества над Collections.synchronizedMap():

• ✅ Высокая параллельность — одновременный доступ к разным бакетам
• ✅ Меньшие задержки — тонкая блокировка на уровне бакета
• ✅ Лучшая масштабируемость — производительность растет с количеством ядер
• ✅ Продвинутые атомарные операции — compute(), merge(), search()

Ограничения и особенности:

• ⚠️ Не гарантирует абсолютную консистентность итераторов (weakly consistent)
• ⚠️ Нет поддержки null ключей и значений
• ⚠️ Размер (size()) вычисляется приблизительно и может быть неточным
• ⚠️ Ресайзинг может временно увеличивать потребление памяти

Рекомендации по использованию:

1. Выбор начальной емкости для минимизации ресайзингов

// Предотвращаем ресайзинги при известном количестве элементов
ConcurrentHashMap<String, Integer> map = 
    new ConcurrentHashMap<>(initialCapacity, loadFactor, concurrencyLevel);

1. Использование продвинутых методов для атомарных операций

// Атомарное обновление значения
map.compute(key, (k, v) -> (v == null) ? 1 : v + 1);

// Атомарное слияние
map.merge(key, 1, Integer::sum);

🎯 Заключение

Реализация ConcurrentHashMap — блестящий пример баланса между производительностью, потокобезопасностью и масштабируемостью. Переход от сегментной архитектуры к CAS-ориентированному подходу в Java 8 позволил достичь качественного скачка в производительности при высокой конкуренции потоков.

Ключевые инновации — инкрементальный ресайзинг, разделенные счетчики, деревья вместо длинных цепочек и умное использование volatile с CAS — делают CHM одной из самых оптимизированных структур данных в стандартной библиотеке Java. Понимание этих механизмов критически важно для написания высокопроизводительных многопоточных приложений на Android, где эффективное использование памяти и процессора особенно значимо.