What is concurrent map in java

Как работает ConcurrentHashMap

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

Предпосылки к созданию ConcurrentHashMap

• Не каждый программист и не каждое решение нуждались в использовании потокобезопасной хэш-таблицы
• Программисту необходимо было дать выбор, какой вариант ему удобно использовать

ConcurrentHashMap

• Потокобезопасность
• Отсутствие блокировок всей таблицы на время доступа к ней
• Желательно, чтобы отсутствовали блокировки таблицы при выполнении операции чтения

1. Элементы карты

В отличие от элементов HashMap, Entry в ConcurrentHashMap объявлены как volatile. Это важная особенность, также связанная с изменениями в JMM. Ответ Doug Lea о необходимости использования volatile и возможных race condition можно прочитать здесь.

static final class HashEntry  < final K key; final int hash; volatile V value; final HashEntrynext; HashEntry(K key, int hash, HashEntry next, V value) < this .key = key; this .hash = hash; this .next = next; this .value = value; >@SuppressWarnings("unchecked") static final HashEntry[] newArray(int i) < return new HashEntry[i]; >>

2. Хэш-функция

В ConcurrentHashMap также используется улучшенная функция хэширования.
Напомню, какой она была в HashMap из JDK 1.2:

static int hash(int h) < h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); >

Версия из ConcurrentHashMap JDK 1.5:

private static int hash(int h) < h += (h >> 10); h += (h >> 6); h += (h >> 16); >

В чём необходимость усложнения хэш-функции? Таблицы в хэш-карте имеют длину, определяемую степенью двойки. Для хэш-кодов, двоичные представления которых не различаются в младшей и старшей позиции, мы будем иметь коллизии. Усложнение хэш-функции как раз решает данную проблему, уменьшая вероятность коллизий в карте.

3. Сегменты

Карта делится на N различных сегментов (16 по умолчанию, максимальное значение может быть 16-битным и представлять собой степень двойки). Каждый сегмент представляет собой потокобезопасную таблицу элементов карты.
Между хэш-кодами ключей и соответствующими им сегментами устанавливается зависимость на основе применения к старшим разрядам хэш-кода битовой маски.
Вот как в карте хранятся элементы:

final Segment[] segments; transient Set keySet; transient Set entrySet; transient Collection values;

Рассмотрим, что же представляет из себя класс сегмента:

static final class Segment extends ReentrantLock implements Serializable < private static final long serialVersionUID = 2249069246763182397L; transient volatile int count; transient int modCount; transient int threshold; transient volatile HashEntry[] table; final float loadFactor; Segment(int initialCapacity, float lf) < loadFactor = lf; setTable(HashEntry.newArray(initialCapacity)); > . >

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

4. ConcurrencyLevel

Данный параметр влияет на использование картой памяти и количество сегментов в карте.
Посмотрим на создание карты и на то, как влияет заданный в качестве парамента конструктора concurrencyLevel:

public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) < if (!(loadFactor >0) || initialCapacity < 0 || concurrencyLevel MAX_SEGMENTS) concurrencyLevel = MAX_SEGMENTS; // Find power-of-two sizes best matching arguments int sshift = 0; int ssize = 1; while (ssize < concurrencyLevel) < ++sshift; ssize segmentShift = 32 - sshift; segmentMask = ssize - 1; this .segments = Segment.newArray(ssize); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; int c = initialCapacity / ssize; if (c * ssize < initialCapacity) ++c; int cap = 1; while (cap < c) cap (cap, loadFactor); >

Количество сегментов будет выбрано как ближайшая степень двойки, большая чем concurrencyLevel. Ёмкость каждого сегмента, соответственно, будет определяться как отношение округлённого до ближайшей большей степени двойки значения ёмкости карты по умолчанию, к полученному количеству сегментов.
Очень важно понимать две следующие вещи. Занижение concurrencyLevel ведёт к тому, что более вероятны блокировки потоками сегментов карты при записи. Завышение показателя ведёт к неэффективному использованию памяти.

Как же выбрать concurrencyLevel?

Если лишь один поток будет изменять карту, а остальные будут производить чтение — рекомендуется использовать значение 1.

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

Оценки масштабируемости

На javamex можно найти статью о сравнении масштабируемости synchronizedMap и ConcurrentHashMap:

Как видно из графика, между 5 и 10 миллионами операций доступа к карте заметно серьёзное расхождение, что обуславливает эффективность применения ConcurrentHashMap в случае с высоким количеством хранимых данных и операций доступа к ним.

Итого

• Карта имеет схожий с hashmap интерфейс взаимодействия
• Операции чтения не требуют блокировок и выполняются параллельно
• Операции записи зачастую также могут выполняться параллельно без блокировок
• При создании указывается требуемый concurrencyLevel, определяемый по статистике чтения и записи
• Элементы карты имеют значение value, объявленное как volatile

Источник

What is concurrent map in java

A Map providing thread safety and atomicity guarantees. Memory consistency effects: As with other concurrent collections, actions in a thread prior to placing an object into a ConcurrentMap as a key or value happen-before actions subsequent to the access or removal of that object from the ConcurrentMap in another thread. This interface is a member of the Java Collections Framework.

Nested Class Summary

Nested classes/interfaces inherited from interface java.util.Map

Method Summary

Attempts to compute a mapping for the specified key and its current mapped value (or null if there is no current mapping).

If the specified key is not already associated with a value (or is mapped to null ), attempts to compute its value using the given mapping function and enters it into this map unless null .

If the value for the specified key is present and non-null, attempts to compute a new mapping given the key and its current mapped value.

Performs the given action for each entry in this map until all entries have been processed or the action throws an exception.

Returns the value to which the specified key is mapped, or defaultValue if this map contains no mapping for the key.

If the specified key is not already associated with a value or is associated with null, associates it with the given non-null value.

Replaces each entry’s value with the result of invoking the given function on that entry until all entries have been processed or the function throws an exception.

Methods inherited from interface java.util.Map

Method Detail

getOrDefault

default V getOrDefault(Object key, V defaultValue)

Returns the value to which the specified key is mapped, or defaultValue if this map contains no mapping for the key.

forEach

Performs the given action for each entry in this map until all entries have been processed or the action throws an exception. Unless otherwise specified by the implementing class, actions are performed in the order of entry set iteration (if an iteration order is specified.) Exceptions thrown by the action are relayed to the caller.

Specified by: forEach in interface Map Implementation Requirements: The default implementation is equivalent to, for this map :

 for ((Map.Entry entry : map.entrySet()) action.accept(entry.getKey(), entry.getValue()); 

putIfAbsent

If the specified key is not already associated with a value, associate it with the given value. This is equivalent to

 if (!map.containsKey(key)) return map.put(key, value); else return map.get(key); 

remove

replace

boolean replace(K key, V oldValue, V newValue)

replace

 if (map.containsKey(key)) < return map.put(key, value); >else return null; 

replaceAll

default void replaceAll(BiFunctionK,? super V,? extends V> function)

Replaces each entry’s value with the result of invoking the given function on that entry until all entries have been processed or the function throws an exception. Exceptions thrown by the function are relayed to the caller.

Specified by: replaceAll in interface Map Implementation Requirements: The default implementation is equivalent to, for this map :

 for ((Map.Entry entry : map.entrySet()) do < K k = entry.getKey(); V v = entry.getValue(); >while(!replace(k, v, function.apply(k, v))); 

computeIfAbsent

default V computeIfAbsent(K key, Function mappingFunction)

If the specified key is not already associated with a value (or is mapped to null ), attempts to compute its value using the given mapping function and enters it into this map unless null . If the function returns null no mapping is recorded. If the function itself throws an (unchecked) exception, the exception is rethrown, and no mapping is recorded. The most common usage is to construct a new object serving as an initial mapped value or memoized result, as in:

 map.computeIfAbsent(key, k -> new Value(f(k))); 

 map.computeIfAbsent(key, k -> new HashSet()).add(v); 

Specified by: computeIfAbsent in interface Map Implementation Requirements: The default implementation is equivalent to the following steps for this map , then returning the current value or null if now absent:

computeIfPresent

default V computeIfPresent(K key, BiFunction remappingFunction)

If the value for the specified key is present and non-null, attempts to compute a new mapping given the key and its current mapped value. If the function returns null , the mapping is removed. If the function itself throws an (unchecked) exception, the exception is rethrown, and the current mapping is left unchanged.

Specified by: computeIfPresent in interface Map Implementation Requirements: The default implementation is equivalent to performing the following steps for this map , then returning the current value or null if now absent. :

compute

default V compute(K key, BiFunction remappingFunction)

Attempts to compute a mapping for the specified key and its current mapped value (or null if there is no current mapping). For example, to either create or append a String msg to a value mapping:

 map.compute(key, (k, v) -> (v == null) ? msg : v.concat(msg))

(Method merge() is often simpler to use for such purposes.) If the function returns null , the mapping is removed (or remains absent if initially absent). If the function itself throws an (unchecked) exception, the exception is rethrown, and the current mapping is left unchanged.

Specified by: compute in interface Map Implementation Requirements: The default implementation is equivalent to performing the following steps for this map , then returning the current value or null if absent:

 V oldValue = map.get(key); V newValue = remappingFunction.apply(key, oldValue); if (oldValue != null ) < if (newValue != null) map.replace(key, oldValue, newValue); else map.remove(key, oldValue); >else

merge

default V merge(K key, V value, BiFunction remappingFunction)

If the specified key is not already associated with a value or is associated with null, associates it with the given non-null value. Otherwise, replaces the associated value with the results of the given remapping function, or removes if the result is null . This method may be of use when combining multiple mapped values for a key. For example, to either create or append a String msg to a value mapping:

 map.merge(key, msg, String::concat) 

If the function returns null the mapping is removed. If the function itself throws an (unchecked) exception, the exception is rethrown, and the current mapping is left unchanged.

Specified by: merge in interface Map Implementation Requirements: The default implementation is equivalent to performing the following steps for this map , then returning the current value or null if absent:

 V oldValue = map.get(key); V newValue = (oldValue == null) ? value : remappingFunction.apply(oldValue, value); if (newValue == null) map.remove(key); else map.put(key, newValue); 

Submit a bug or feature
For further API reference and developer documentation, see Java SE Documentation. That documentation contains more detailed, developer-targeted descriptions, with conceptual overviews, definitions of terms, workarounds, and working code examples.
Copyright © 1993, 2023, Oracle and/or its affiliates. All rights reserved. Use is subject to license terms. Also see the documentation redistribution policy.

Источник