Импортировать
ConcurrentHashMap — это версия реализации потокобезопасной версии HashMap.Для анализа и обобщения HashMap вы можете обратиться к статьеАнализ исходного кода Java 8 HashMap. В этой статье будет проанализирован ConcurrentHashMap на основе реализации Java 8 в java 8. По сравнению с предыдущей версией реализации ConcurrentHashMap в java 8 были внесены значительные коррективы. В этой статье анализируется только реализация java 8, а реализация до java 8 будет анализу пока не подлежит. Чтобы лучше импортировать эту статью, сначала покажите структуру ConcurrentHashMap, см. следующую картинку:
Структурная схема ConcurrentHashMap
Подобно HashMap, ConcurrentHashMap использует таблицу для хранения узла. записи будут храниться в одном и том же.В позиции формируется связанный список.При длине связанного списка больше 8, связанный список будет преобразован в красно-черное дерево, тем самым уменьшив сложность поиска с от O(N) до O(lgN). Далее будет подробно проанализирована реализация ConcurrentHashMap и то, как ConcurrentHashMap обеспечивает безопасность потоков в параллельной среде.
Подробное объяснение ConcurrentHashMap
Инициализация таблицы хэш-контейнера
Во-первых, давайте посмотрим, как инициализируется таблица.Работа по инициализации таблицы будет происходить при выполнении операции put.Если обнаружится, что таблица не была инициализирована, будет вызван метод initTable для инициализации таблицы. Ниже показан конкретный процесс инициализации таблицы.Код:
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
Здесь есть более критичное место, то есть переменная sizeCtl, вот ее определение:
/**
* Table initialization and resizing control. When negative, the
* table is being initialized or resized: -1 for initialization,
* else -(1 + the number of active resizing threads). Otherwise,
* when table is null, holds the initial table size to use upon
* creation, or 0 for default. After initialization, holds the
* next element count value upon which to resize the table.
*/
private transient volatile int sizeCtl;
sizeCtl — это общая переменная, используемая для синхронизации нескольких потоков. Если ее текущее значение отрицательное, это означает, что таблица инициализируется или расширяется потоком. Поэтому, если поток хочет инициализировать или расширить таблицу, ему нужно перейти к Конкурируя за общую переменную sizeCtl, поток, получивший переменную, получает разрешение на выполнение следующей операции. установить его после завершения работы обратно, чтобы другие нити могли выйти из закрутки для следующей операции. В методе initTable мы видим, что когда поток обнаружит, что sizeCtl меньше 0, он отдаст процессорное время и повторит попытку позже, а когда обнаружит, что sizeCtl больше не меньше 0, он вызовет метод compareAndSwapInt. вызвав метод compareAndSwapInt, С точки зрения общей переменной sizeCtl становится -1, чтобы сообщить другим потокам, пытающимся получить переменную sizeCtl, эта переменная в настоящее время используется этим потоком, вы можете немного отдохнуть, прежде чем я закончу свою задачу, повторите попытку позже , я выпущу его, когда закончу. Другие потоки поймут это сообщение, когда обнаружат, что sizeCtl меньше 0. Они откажутся от процессорного времени и будут ждать следующего планирования, чтобы попытаться заставить sizeCtl выполнять свою работу. После выполнения задачи инициализации таблицы потоку необходимо установить sizeCtl в состояние, позволяющее другим потокам получать переменную.Есть еще один момент, на который следует обратить внимание, то есть до и после того, как поток устанавливает sizeCtl через U .compareAndSwapInt метод Дважды проверьте, была ли таблица инициализирована.Это обнаружение необходимо, поскольку в параллельной среде предыдущий поток может инициализировать таблицу, но она не была успешно инициализирована, то есть таблица по-прежнему имеет значение null, и когда поток обнаружит, что таблица пустая, он будет конкурировать за sizeCtl для инициализации таблицы, но после того, как текущий поток завершит инициализацию, поток, пытающийся инициализировать таблицу, получит sizeCtl, но таблица уже была инициализирована в на этот раз, поэтому, если снова нет решения, может перезаписать обновление потока, который выполняет операцию размещения позже, что является крайне небезопасным поведением.
Подробное объяснение метода записи запроса ConcurrentHashMap
Инициализация таблицы ConcurrentHashMap была проанализирована выше. Теперь давайте взглянем на детали реализации операции запроса ConcurrentHashMap. Чтобы запросить запись в ConcurrentHashMap, вам сначала нужно знать расположение таблицы, в которой хранится запись (это может быть слотом для карт, и каждый слот для карт будет иметь связанный список или красно-черное дерево), позиция может быть нулевой, если она нулевая, это означает, что запись, которую вы хотите запросить, не существует в ConcurrentHashMap, в противном случае ищем запись в связном списке или красно-черном дереве на этой позиции, разберем подробно детали реализации метода get ConcurrentHashMap:
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
Сначала вычислите hashCode ключа записи, а затем используйте метод вычисления (hashCode & (length - 1)) для получения индекса записи в таблице, а затем оцените, является ли позиция нулевой, если она равно null, вернуть null, иначе, если первый элемент в этой позиции (головной узел связного списка или корневой узел красно-черного дерева) совпадает с искомой нами первой записью, значение этого узла будет возвращается напрямую, в противном случае, если hashCode узла меньше 0, это означает, что позиция является красно-черным деревом, а почему значение hashCode меньше 0, это означает, что это красно-черное дерево вместо этого связанного списка. Это зависит от следующего кода:
static final int TREEBIN = -2; // hash for roots of trees
TreeBin(TreeNode<K,V> b) {
super(TREEBIN, null, null, null);
......
}
Значение TREEBIN равно -2, то есть меньше 0. Согласно его описанию, TREEBIN хочет представлять корневой узел красно-черного дерева, поэтому после оценки первого узла в определенной позиции таблицы Когда значение hashCode меньше 0, можно судить, что позиция представляет собой красно-черное дерево, и продолжать возвращаться к методу get.Если это красно-черное дерево, узел можно найти, вызвав метод find узла, и метод find этого узла. Метод переопределен в подклассе, поэтому метод find подкласса будет вызываться непосредственно для поиска. Также возможен случай, когда индексная позиция таблицы представляет собой связанный список, тогда поиск записи выполняется методом поиска связанного списка. Последнее, что нужно отметить, это то, что ConcurrentHashMap является потокобезопасным HashMap, но мы не нашли никаких компонентов, эквивалентных блокировкам, используемым для синхронизации потоков в процессе метода get.Почему? Для чтения обычно разрешается совместное чтение нескольких потоков, и в реализации Node ConcurrentHashMap делает некоторые трюки:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
....
}
/**
* The array of bins. Lazily initialized upon first insertion.
* Size is always a power of two. Accessed directly by iterators.
*/
transient volatile Node<K,V>[] table;
Мы обнаружили, что массив таблиц модифицируется ключевым словом volatile, что означает, что нам не нужно беспокоиться о видимости потока для массива таблиц, и нет необходимости добавлять блокировки для достижения параллелизма.
Подробное объяснение метода вставки записи ConcurrentHashMap
Метод запроса ConcurrentHashMap разобран выше, давайте проанализируем, как завершается операция вставки ConcurrentHashMap. Следует отметить, что при выполнении операции put мы можем обнаружить, что табличный массив не был инициализирован, или что количество записей, содержащихся в таблице, превышает пороговое значение.В первом случае нам необходимо инициализировать таблицу, в то время как последнее требует Расширяем вместимость стола. Процесс инициализации таблицы был проанализирован выше, а ниже будет проанализирована только операция расширения таблицы. Для начала рассмотрим процесс проставления записи.Сначала нам нужно вычислить хэш-код ключа этой записи, и вычислить индекс, который он должен хранить в массиве таблицы по хэш-коду, а затем сохранить его в связанном список или красный список в соответствующем месте Переход к черному дереву, а в некоторых случаях необходимо преобразовать связанный список в красно-черное дерево, а также операцию расширения таблицы. Еще одним важным моментом является изменение размера таблицы, что будет специально проанализировано позже. Ниже сначала показан процесс, связанный с операцией размещения:
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
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.val;
if (!onlyIfAbsent)
e.val = 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.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
Сначала вычислить hashCode ключа записи, затем вычислить позицию индекса таблицы, а затем получить значение индекса.Если позиция по-прежнему равна нулю, это означает, что в этой позиции нет записи, тогда новая запись вставляется вызовом метода casTabAt.Перейдите к позиции индекса таблицы, в противном случае заблокируйте позицию индекса таблицы с помощью ключевого слова synchronized.Следует отметить, что текущий поток будет блокировать только позицию индекса таблицы , а другие позиции не заблокированы, поэтому в это время могут быть заблокированы другие потоки. Безопасно получите другие местоположения таблицы для работы. Это также улучшает параллелизм ConcurrentHashMap. Затем оцените значение hashCode первого узла в позиции индекса таблицы.Этот узел является либо головным узлом связанного списка, либо корневым узлом красно-черного дерева.Если значение hashCode меньше 0, то это является красно-черным деревом.Настолько почему Да, как было сказано выше, если оно не меньше 0, то это все еще связанный список.Если это связанный список, то выяснить, является ли ключ существующей записи соответствует текущей записи, которую вы хотите вставить.Если она соответствует, то это Эффект второго размещения заключается в замене, в противном случае запись добавляется в связанный список. Если это красно-черное дерево, операция вставки выполняется вызовом метода putTreeVal. После завершения операции вставки необходимо определить, является ли операция операцией обновления. Если это операция обновления, она не вызовет изменения размера. В противном случае, если операция размещения является операцией добавления, то размер требуется операция обновления. Обновление размера связано с параллельной средой, поэтому оно более сложное, и операция расширения таблицы также будет происходить при обновлении размера. Если обнаружено, что количество записей в таблице достигает порогового значения после обновления размера необходимо выполнить операцию расширения, что также является более сложным шагом. Еще один момент, который следует отметить, заключается в том, что разница между ConcurrentHashMap и HashMap заключается в том, что HashMap позволяет ключу и значению быть нулевыми, в то время как ConcurrentHashMap не позволяет ключу и значению быть нулевыми. NPE, этот момент требует особого внимания, и это также показывает, что в ConcurrentHashMap вы можете использовать операцию get для проверки наличия записи, потому что, пока метод get возвращает значение null, это означает, что в массиве не должно быть записей. таблица, соответствующая текущему запросу, и в HashMap, если операция get возвращает значение null, возможно, значение записи, которую мы запрашиваем, равно null, поэтому метод get нельзя использовать для проверки существования записи в таблице.
Количество обновленных записей ConcurrentHashMap
При анализе операции put выше было упомянуто, что после завершения операции put необходимо обновить количество записей в таблице, и если после обновления будет обнаружено, что порог превышен, то операцию расширения таблицы необходимо Проанализируем этот процесс подробно в контексте. Операция обновления количества записей выполняется путем вызова метода addCount, детали которого следующие:
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
s = sumCount();
}
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
if (sc < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
s = sumCount();
}
}
}
ConcurrentHashMap поддерживает baseCount для представления текущего количества записей, которое будет использоваться в методе size для последующего получения количества записей, и обновляется путем вызова метода addCount во время операций размещения и удаления. Если массив CounterCell пуст, инициализируйте массив counterCells, вызвав метод fullAddCount, так как содержимое этой части слишком сложное и не подходит для анализа в настоящее время. При обновлении количества записей в таблице также необходимо учитывать ситуацию.Количество записей достигает порога, тогда требуется операция расширения.Эта часть кода также слишком сложна, и условия операции расширения ConcurrentHashMap кажутся отличными от HashMap. Точно так же в нем говорится, что «если таблица слишком мала и не была расширена, ее необходимо расширить». Расширение требует метода переноса для переноса старых записей в новый стол. В настоящее время нам нужно понять, что ConcurrentHashMap может расширить емкость, когда мы обновим количество записей в таблице, но предпосылка заключается в том, что «таблица слишком мала и не была расширена», эта часть кода будет быть пригодным в будущем, в момент анализа и подведения итогов.
ConcurrentHashMap удалить операцию записи
Теперь разберем, как ConcurrentHashMap удаляет записи. Ниже сначала показан вызывающий код метода удаления:
public V remove(Object key) {
return replaceNode(key, null, null);
}
final V replaceNode(Object key, V value, Object cv) {
int hash = spread(key.hashCode());
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0 ||
(f = tabAt(tab, i = (n - 1) & hash)) == null)
break;
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
boolean validated = false;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
validated = true;
for (Node<K,V> e = f, pred = null;;) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
V ev = e.val;
if (cv == null || cv == ev ||
(ev != null && cv.equals(ev))) {
oldVal = ev;
if (value != null)
e.val = value;
else if (pred != null)
pred.next = e.next;
else
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
if ((e = e.next) == null)
break;
}
}
else if (f instanceof TreeBin) {
validated = true;
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> r, p;
if ((r = t.root) != null &&
(p = r.findTreeNode(hash, key, null)) != null) {
V pv = p.val;
if (cv == null || cv == pv ||
(pv != null && cv.equals(pv))) {
oldVal = pv;
if (value != null)
p.val = value;
else if (t.removeTreeNode(p))
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
if (validated) {
if (oldVal != null) {
if (value == null)
addCount(-1L, -1);
return oldVal;
}
break;
}
}
}
return null;
}
Операция удаления является операцией записи, поэтому при удалении необходимо заблокировать положение индекса в таблице. ConcurrentHashMap использует ключевое слово synchronized для блокировки положения индекса в таблице, а затем удаляет его. Метод удаления вызывает метод replaceNode выполнить фактическую операцию, а шаг операции удаления по-прежнему заключается в том, чтобы сначала вычислить хэш-код записи, затем вычислить значение индекса в таблице в соответствии с хэш-кодом, а затем использовать различные методы в зависимости от того, находится ли позиция индекса в таблица представляет собой связанный список или красно-черное дерево, для удаления этой записи операция удаления записи должна обновить количество записей (вызвать метод addCount).
Подробное объяснение метода размера ConcurrentHashMap
Наконец, давайте проанализируем, как ConcurrentHashMap получает количество записей в таблице. ConcurrentHashMap получает количество записей с помощью метода размера. Детали метода размера показаны ниже:
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a;
long sum = baseCount;
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}
Количество записей в ConcurrentHashMap нужно получить, объединив массивы baseCount и counterCells.Накопив количество обоих, можно получить общее количество записей в текущем ConcurrentHashMap.
Реализация ConcurrentHashMap в java7
Реализация ConcurrentHashMap в java8 была разобрана выше, теперь давайте проанализируем реализацию в java7. Реализация в java7 использует метод массива + связанный список внизу Ниже показана структура данных ConcurrentHashMap в java7:
Структурная схема ConcurrentHashMap в java7
Вся структура представляет собой массив сегментов. Размер массива сегментов определяет параллелизм ConcurrentHashMap. Значение по умолчанию равно 16. Почему вы так говорите? Это связано с тем, что в реализации ConcurrentHashMap в java7 используется так называемый метод блокировки сегмента, а так называемая блокировка сегмента заключается в хранении записей в сегментах, и доступ разных сегментов не влияет друг на друга. чтобы получить доступ к сегменту, он Сегмент должен быть заблокирован, и другие потоки не могут получить доступ к сегменту, заблокированному другими потоками.Это большое улучшение по сравнению с общим методом блокировки.Специфический анализ операций в java7 здесь не проводится. , при необходимости он будет проанализирован и обобщен в других статьях.
В этой статье анализируются детали реализации ConcurrentHashMap на основе исходного кода в jdk 8, но, поскольку реализация ConcurrentHashMap слишком сложна, в этой статье анализируется только очень поверхностное содержание.Значение анализа исходного кода ConcurrentHashMap заключается в том, чтобы понять, почему ConcurrentHashMap является потокобезопасным, а для достижения потокобезопасности, каковы дополнения ConcurrentHashMap по сравнению с HashMap? В этой статье анализируется реализация ConcurrentHashMap и сравнивается реализация HashMap. Можно четко обнаружить, что сложность их реализации не на том же самом уровень, HashMap является скорее структурой данных, однако ConcurrentHashMap должен учитывать, как эффективно реализовать потокобезопасность в параллельной среде.Короче говоря, ConcurrentHashMap не только реализует все функции, поддерживаемые HashMap, но также поддерживает ту же эффективность, что и HashMap. безопасность достигается.Анализ исходного кода показывает, что ConcurrentHashMap основан на CAS для достижения потокобезопасности.CAS представляет собой облегченную блокировку, которая не блокирует потоки, а ждет, пока будет получена переменная, а затем выполняет бизнес-операции.Блокировка должна заблокировать поток для обеспечения потокобезопасности, что является большим улучшением, поскольку управление синхронизацией на основе блокировки требует, чтобы поток получил блокировку, и до того, как блокировка будет получена, он должен заблокировать и ждать, и ему нужен другой поток для пробуждения он снова пошел соревноваться за замок, вы можете обратиться к статье об этой частиФреймворк синхронизации Java AbstractQueuedSynchronizer, AQS — это базовая поддержка для реализации блокировок в java, а также базовая структура для реализации синхронизации потоков для программистов.Реализовать собственный синхронизатор потоков на основе AQS очень просто. Из-за сложности ConcurrentHashMap эта статья считается началом анализа ConcurrentHashMap, и анализ и сводка ConcurrentHashMap будут время от времени дополняться в будущем.