Какие механизмы синхронизации используются в ConcurrentHashMap

Механизмы синхронизации в ConcurrentHashMap

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

1. Segmentation (Сегментация) — Java 7 и ниже

До Java 8, ConcurrentHashMap использовал архитектуру, разделяющую карту на несколько segments (сегментов):

public class ConcurrentHashMap<K, V> {
    private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
    private final Segment[] segments;
    
    static class Segment<K, V> extends ReentrantLock {
        private volatile int count;
        private HashEntry<K, V>[] table;
    }
}

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>(16, 0.75f, 16);

Как это работает:

• Карта разделяется на 16 (по умолчанию) независимых сегментов
• Каждый сегмент имеет собственный ReentrantLock
• Разные потоки могут работать с разными сегментами одновременно
• При вставке элемента определяется его сегмент, и синхронизируется только этот сегмент

2. Node-based Locking (Блокировка на уровне узлов) — Java 8+

С Java 8, архитектура изменилась на более эффективную, основанную на блокировке отдельных узлов:

public class ConcurrentHashMap<K, V> {
    private transient volatile Node<K, V>[] table;
    private static final int DEFAULT_CAPACITY = 16;
    
    static class Node<K, V> implements Map.Entry<K, V> {
        final int hash;
        final K key;
        volatile V value;
        volatile Node<K, V> next;
    }
}

Как это работает:

• Вместо сегментов используются отдельные узлы в бакетах
• Блокировка происходит на уровне главного узла (bucket head)
• Это обеспечивает ещё более fine-grained синхронизацию

final V putVal(K key, V value, boolean onlyIfAbsent) {
    int hash = spread(key.hashCode());
    Node<K, V>[] tab;
    Node<K, V> f;
    int n, i;
    
    while (true) {
        if ((tab = table) == null || (n = tab.length) == 0) {
            tab = initTable();
        } else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // Если bucket пуст, используем CAS (Compare-And-Swap)
            if (casTabAt(tab, i, null, new Node<K, V>(hash, key, value, null)))
                break;
        } else {
            // Если bucket занят, блокируем узел
            synchronized (f) {
                // Вставляем в цепь или заменяем значение
            }
            break;
        }
    }
}

3. Atomic Variables и CAS (Compare-And-Swap)

ConcurrentHashMap использует Atomic переменные для блокировок без явного synchronized:

// tabAt - атомарное чтение
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);
}

// casTabAt - atomically сравнивает и заменяет
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);
}

// setTabAt - атомарная установка
static final <K, V> void setTabAt(Node<K, V>[] tab, int i, Node<K, V> v) {
    U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}

CAS (Compare-And-Swap) — низкоуровневая операция:

1. Прочитать текущее значение
2. Сравнить с ожидаемым
3. Если совпадает, атомарно заменить на новое
4. Если нет, повторить попытку

public class CounterWithCAS {
    private AtomicInteger counter = new AtomicInteger(0);
    
    public void increment() {
        int current;
        int next;
        do {
            current = counter.get();
            next = current + 1;
        } while (!counter.compareAndSet(current, next));
    }
}

4. Volatile переменные

ConcurrentHashMap активно использует volatile для обеспечения видимости:

// В Node классе
volatile V value;
volatile Node<K, V> next;

// В самой карте
private transient volatile Node<K, V>[] table;
private transient volatile int sizeCtl;

Гарантии volatile:

• Операции чтения/записи всегда идут в main memory (не кэш)
• Visibility между потоками
• Happens-before отношения

5. Fine-grained Locking (Минимальная синхронизация)

В ConcurrentHashMap области синхронизации максимально уменьшены:

final V putVal(K key, V value, boolean onlyIfAbsent) {
    synchronized (f) {  // f - это узел в bucket
        // Только эта критическая секция блокируется
        // Другие потоки могут работать с другими buckets
    }
}

// Два потока могут одновременно добавлять в разные buckets
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
map.put("apple", 1);   // Блокирует bucket для apple
map.put("banana", 2);  // Блокирует другой bucket для banana

6. MVCC-подобный подход для size() и isEmpty()

Операции подсчёта размера не блокируют всю карту:

private transient volatile long baseCount;
private transient volatile CounterCell[] counterCells;

public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 : (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n);
}

private final long sumCount() {
    CounterCell[] as = counterCells;
    long sum = baseCount;
    if (as != null) {
        for (CounterCell a : as) {
            if (a != null)
                sum += a.value;
        }
    }
    return sum;
}

Идея: вместо одного глобального счётчика, каждый поток обновляет свой локальный счётчик, избегая contention.

7. Red-Black Trees при высокой коллизии

Когда в одном bucket много элементов, структура меняется:

static final int TREEIFY_THRESHOLD = 8;

static final class TreeNode<K, V> extends Node<K, V> {
    TreeNode<K, V> parent;
    TreeNode<K, V> left;
    TreeNode<K, V> right;
    TreeNode<K, V> prev;
    boolean red;
}

Преимущество: O(log n) поиск вместо O(n) в длинной цепи.

8. Многопоточный Resize

Резайз использует многопоточный подход:

private final void transfer(Node<K, V>[] tab, Node<K, V>[] nextTab) {
    int n = tab.length;
    int stride;
    
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE;
    
    // Несколько потоков могут одновременно двигать элементы в новую таблицу
}

Сравнение механизмов

Практический пример

public class ConcurrentHashMapExample {
    public static void main(String[] args) throws Exception {
        ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
        
        Thread t1 = new Thread(() -> {
            for (int i = 0; i < 1000; i++) {
                map.put("key1_" + i, i);
            }
        });
        
        Thread t2 = new Thread(() -> {
            for (int i = 0; i < 1000; i++) {
                map.put("key2_" + i, i);
            }
        });
        
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        
        System.out.println("Map size: " + map.size());
    }
}

Преимущества ConcurrentHashMap

• Высокий параллелизм — множество потоков могут работать одновременно
• Отсутствие deadlock'ов — благодаря тонкой гранулярности синхронизации
• Лучшая производительность — чем Collections.synchronizedMap()
• Масштабируемость — производительность растёт с числом потоков

Когда использовать

• Многопоточные приложения с интенсивным доступом к map
• Когда нужна потокобезопасность без явной синхронизации
• Вместо HashMap + synchronized или Collections.synchronizedMap()

Заключение

ConcurrentHashMap достигает высокой производительности в многопоточной среде за счёт комбинации CAS операций, volatile переменных, fine-grained locking, lock-free алгоритмов, многопоточного resize и Red-Black trees. Это делает её идеальным выбором для параллельных Java приложений.