Java for Beginner

ConcurrentHashMap, отличие от HashMap

ConcurrentHashMap — это класс в пакете java.util.concurrent, который представляет собой потокобезопасную версию HashMap. Он разработан для использования в многопоточных приложениях, где необходимо гарантировать корректность и производительность при одновременном доступе к коллекции из нескольких потоков.

Основные характеристики ConcurrentHashMap

Потокобезопасность: ConcurrentHashMap реализует эффективные механизмы блокировок для обеспечения потокобезопасного доступа к данным. В отличие от Hashtable, который синхронизирует все методы, ConcurrentHashMap использует более изящные механизмы управления доступом.

Производительность: За счет использования сегментации (в старых версиях) или уменьшенных блокировок (в новых версиях), ConcurrentHashMap обеспечивает высокую производительность в условиях многопоточного доступа.

Структура ConcurrentHashMap

Сегментация (в старых версиях): В старых версиях ConcurrentHashMap использовалась сегментация, при которой таблица хешей разбивалась на сегменты, каждый из которых был самостоятельной хеш-таблицей с собственной блокировкой. Это позволяло одновременно выполнять операции в разных сегментах без конфликтов.

Lock Striping (в новых версиях): В новых версиях ConcurrentHashMap используется механизм Lock Striping, который включает в себя более мелкие блокировки на уровне бакетов или групп бакетов, что снижает вероятность блокировок и увеличивает производительность.

Отличия ConcurrentHashMap от HashMap

Потокобезопасность: HashMap не является потокобезопасным. При одновременном доступе нескольких потоков к HashMap могут возникнуть состояния гонки и непредсказуемое поведение. В отличие от этого, ConcurrentHashMap специально разработан для безопасного использования в многопоточной среде.

Блокировки: HashMap не использует блокировки, что делает его небезопасным для многопоточного использования. ConcurrentHashMap, напротив, использует сегментацию или мелкие блокировки, что позволяет безопасно выполнять параллельные операции.

Производительность: В условиях многопоточного доступа HashMap может демонстрировать низкую производительность и некорректное поведение. ConcurrentHashMap оптимизирован для многопоточного доступа и обеспечивает более высокую производительность за счет эффективного управления блокировками.

Методы атомарных операций: ConcurrentHashMap предоставляет методы атомарных операций, такие как putIfAbsent, remove с проверкой значения и replace, которые отсутствуют в HashMap.

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

import java.util.concurrent.ConcurrentHashMap;
import java.util.Map;

public class ConcurrentHashMapExample {
    public static void main(String[] args) {
        // Создание ConcurrentHashMap
        Map<String, Integer> map = new ConcurrentHashMap<>();
        // Добавление элементов
        map.put("Apple", 50);
        map.put("Banana", 30);
        map.put("Orange", 20);
        // Получение значения по ключу
        System.out.println("Price of Apple: " + map.get("Apple"));
        // Проверка наличия ключа
        if (map.containsKey("Banana")) {
            System.out.println("Banana is in the list.");
        }
        // Удаление элемента
        map.remove("Orange");
        // Перебор элементов
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        // Использование атомарных операций
        map.putIfAbsent("Grapes", 40);
        map.replace("Banana", 35);
        // Перебор элементов после атомарных операций
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

Полезные ссылки для более полного ознакомления с ConcurrentHashMap (спасибо авторам за их кропотливую работу):
https://habr.com/ru/articles/132884/
https://www.baeldung.com/java-concurrent-map

#Java #Training #Medium #ConcurrentHashMap

Baeldung

A Guide to ConcurrentMap | Baeldung

A quick and practical guide to ConcurrentMap in Java.

176 viewsДен, 05:09

Java for Beginner

Внутренняя структура ConcurrentHashMap

ConcurrentHashMap состоит из хеш-таблицы, которая делится на сегменты (в старых версиях) или использует мелкие блокировки (в новых версиях), чтобы минимизировать блокировки и увеличить параллелизм.

Бакеты (Buckets):

Подобно HashMap, ConcurrentHashMap использует массив бакетов для хранения пар "ключ-значение".
Внутри каждого бакета используется связанный список (или дерево в случае большого числа элементов) для хранения элементов, что позволяет управлять коллизиями.

Сегменты (Segments) (в старых версиях):

В старых версиях ConcurrentHashMap массив бакетов разбивался на сегменты, каждый из которых имел свою собственную блокировку. Это позволяло нескольким потокам одновременно модифицировать разные сегменты без взаимных блокировок.
Каждый сегмент был отдельной хеш-таблицей с собственными методами вставки, поиска и удаления.

Lock Striping (в новых версиях):

В новых версиях (Java 8 и позже) ConcurrentHashMap использует более мелкие блокировки, известные как lock striping.
Вместо сегментов используется механизм блокировок на уровне бакетов или групп бакетов, что уменьшает вероятность блокировок и увеличивает производительность.

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

Мелкие блокировки (Fine-Grained Locks):

ConcurrentHashMap использует мелкие блокировки для управления доступом к отдельным бакетам или небольшим группам бакетов.
Это позволяет нескольким потокам одновременно выполнять операции над различными частями хеш-таблицы, минимизируя блокировки и повышая параллелизм.

CAS (Compare-And-Swap):

Для некоторых операций, таких как вставка и обновление значений, используется механизм CAS, который позволяет атомарно обновлять значения без использования явных блокировок.
CAS операции обеспечивают высокую производительность и минимизируют затраты на синхронизацию.

Механизм Reentrant Lock:

Внутренне для блокировок ConcurrentHashMap использует ReentrantLock, что позволяет потокам безопасно входить в блокировку несколько раз.
ReentrantLock предоставляет больше возможностей управления, таких как блокировка с тайм-аутом и попытка блокировки без ожидания.

Внутреннее устройство бакетов

Каждый бакет в ConcurrentHashMap представлен объектом типа Node:

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V value;
    volatile Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey() {
        return key;
    }

    public final V getValue() {
        return value;
    }

    public final String toString() {
        return key + "=" + value;
    }

    public final int hashCode() {
        return key.hashCode() ^ value.hashCode();
    }

    public final V setValue(V value) {
        throw new UnsupportedOperationException();
    }

    public final boolean equals(Object o) {
        Object k, v, u;
        Map.Entry<?,?> e;
        return ((o instanceof Map.Entry) &&
                (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
                (v = e.getValue()) != null &&
                (k == key || k.equals(key)) &&
                (v == (u = value) || v.equals(u)));
    }
}

#Java #Training #Medium #ConcurrentHashMap

159 viewsДен, 13:24

Java for Beginner

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

Пример использования CAS для вставки элемента:

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;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.value;
                                if (!onlyIfAbsent)
                                    e.value = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                           value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                              value)) != null) {
                            oldVal = p.value;
                            if (!onlyIfAbsent)
                                p.value = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

#Java #Training #Medium #ConcurrentHashMap

155 viewsДен, 13:24

About

Blog

Apps

Platform