Почему ConcurrentHashMap потокобезопасен?

Java задняя часть опрос
Почему ConcurrentHashMap потокобезопасен?

«Это третий день моего участия в первом испытании обновлений 2022 года. Подробную информацию о мероприятии см.:Вызов первого обновления 2022 г.".

ConcurrentHashMap — это многопоточная версия HashMap, которая будет иметь различные проблемы при параллельной работе, такие как проблемы с бесконечным циклом, покрытие данных и другие проблемы. И эти проблемы прекрасно решаются с помощью ConcurrentHashMap.Вопрос в том, как ConcurrentHashMap обеспечивает потокобезопасность? Как это реализовано внизу? Дальше посмотрим вместе.

Базовая реализация JDK 1.7

ConcurrentHashMap реализован по-разному в разных версиях JDK,В JDK 1.7 он реализован в виде массива плюс связанный список, причем массив разбит на: большой массив Segment и маленький массив HashEntry.Сегмент большого массива можно понимать как базу данных в MySQL, и каждая база данных (сегмент) имеет много таблиц HashEntry, и каждый HashEntry имеет несколько фрагментов данных, которые связаны связанным списком, как показано на следующем рисунке:image.png

Поточно-ориентированная реализация JDK 1.7

Разобравшись с базовой реализацией ConcurrentHashMap, можно относительно просто взглянуть на ее поточно-безопасную реализацию. Затем мы добавляем метод элемента put, чтобы увидеть, как ConcurrentHashMap в JDK 1.7 обеспечивает безопасность потоков.Исходный код конкретной реализации выглядит следующим образом:

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    // 在往该 Segment 写入前，先确保获取到锁
    HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value); 
    V oldValue;
    try {
        // Segment 内部数组
        HashEntry<K,V>[] tab = table;
        int index = (tab.length - 1) & hash;
        HashEntry<K,V> first = entryAt(tab, index);
        for (HashEntry<K,V> e = first;;) {
            if (e != null) {
                K k;
                // 更新已有值...
            }
            else {
                // 放置 HashEntry 到特定位置，如果超过阈值则进行 rehash
                // 忽略其他代码...
            }
        }
    } finally {
        // 释放锁
        unlock();
    }
    return oldValue;
}

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

Базовая реализация JDK 1.8

В JDK 1.7 ConcurrentHashMap является потокобезопасным, но поскольку его базовая реализация представлена ​​в виде массива + связанный список, доступ очень медленный, когда данных много, потому что нужно пройти весь связанный список, в то время как JDK 1.8 использует Реализация ConcurrentHashMap оптимизирована методом массив + связанный список/красно-черное дерево Конкретная структура реализации выглядит следующим образом:image.pngПравила обновления связанного списка до красно-черного дерева: Когда длина связанного списка больше 8 и длина массива больше 64, связанный список будет обновлен до красно-черной древовидной структуры.

PS: хотя ConcurrentHashMap сохраняет определение Segment в JDK 1.8, это делается только для обеспечения совместимости во время сериализации, и больше не имеет никакого структурного применения.

Поточно-ориентированная реализация JDK 1.8

В JDK 1.8 ConcurrentHashMap использует CAS + volatile или synchronized для обеспечения безопасности потоков. Его основной исходный код реализации выглядит следующим образом:

final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh; K fk; V fv;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 节点为空
            // 利用 CAS 去进行无锁线程安全操作，如果 bin 是空的
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
                break; 
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else if (onlyIfAbsent
                 && fh == hash
                 && ((fk = f.key) == key || (fk != null && key.equals(fk)))
                 && (fv = f.val) != null)
            return fv;
        else {
            V oldVal = null;
            synchronized (f) {
                   // 细粒度的同步修改操作... 
                }
            }
            // 如果超过阈值，升级为红黑树
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

Как видно из приведенного выше исходного кода, в JDK 1.8 при добавлении элементов сначала будет определяться, пустой ли контейнер, и если он пустой, использовать volatile плюс CAS для инициализации. Если контейнер не пуст, вычислите, пусто ли местоположение в соответствии с сохраненными элементами.Если он пуст, используйте CAS для установки узла, если он не пуст, используйте синхронизацию для блокировки, просмотра данных в ведре и заменить или добавить узлы в бакет. , и, наконец, определить, нужно ли его преобразовать в красно-черное дерево, чтобы обеспечить потокобезопасность при параллельном доступе. Упростим вышеописанный процесс.Можно просто считать, что в JDK 1.8 ConcurrentHashMap блокируется на головном узле для обеспечения потокобезопасности.Дробность блокировок меньше, чем у Segment, а частота конфликтов и блокировок снижена. повышается производительность параллельных операций. Более того, JDK 1.8 использует красно-черное дерево для оптимизации предыдущего фиксированного связанного списка, поэтому, когда объем данных относительно велик, производительность запросов также значительно улучшилась: от предыдущей оптимизации O (n) до O (logn). время сложности, конкретная схема блокировки выглядит следующим образом:image.png

Суммировать

В JDK 1.7 ConcurrentHashMap реализован в виде данных плюс связанный список, в котором массивы разделены на две категории: сегмент большого массива и небольшой массив HashEntry, а блокировка достигается путем добавления блокировки ReentrantLock к сегменту для обеспечения безопасности потоков. В JDK 1.8 ConcurrentHashMap реализован методом массив + связанный список/красно-черное дерево, он потокобезопасен через CAS или синхронизирован, детализация блокировок у него меньше, а производительность запросов выше. ​

Самостоятельно судить о правильном и неправильном, слушать других и подсчитывать выгоды и потери.

Официальная учетная запись: Анализ вопросов Java-интервью

Сборник статей:git ee.com/oppo/inter V…

Категории