предисловие
Вот такая картаKey ValueЭто очень классическая структура в разработке программного обеспечения, которая часто используется для хранения данных в памяти.
В этой статье в основном хочется обсудить concurrent контейнер такой как ConcurrentHashMap.Перед официальным стартом считаю необходимым рассказать о HashMap.Без него не будет последующего ConcurrentHashMap.
HashMap
Как мы все знаем, нижний слой HashMap основан на数组 + 链表Он составлен, но конкретная реализация немного отличается в jdk1.7 и 1.8.
Base 1.7
Диаграмма структуры данных в 1.7:
Давайте сначала посмотрим на реализацию в 1.7.
Это основные переменные-члены HashMap, что они означают?
- Инициализируйте размер корзины, так как нижний слой представляет собой массив, так что это размер массива по умолчанию.
- Ковш макс.
- Коэффициент нагрузки по умолчанию (0,75)
-
tableМассив, который фактически содержит данные. -
MapРазмер хранимого количества. - Размер сегмента, который можно указать явно при инициализации.
- Коэффициент нагрузки, который можно указать явно при инициализации.
Сосредоточьтесь на объяснении коэффициента нагрузки:
Поскольку размер емкости данного HashMap фиксирован, например, инициализация по умолчанию:
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}
Заданная емкость по умолчанию равна 16, а коэффициент загрузки равен 0,75. Карта постоянно сохраняет данные в ней во время использования, и когда число достигает16 * 0.75 = 12Необходимо расширить текущую емкость 16, а процесс расширения включает в себя такие операции, как перехеширование, копирование данных и т. д., поэтому потребляет много производительности.
Поэтому обычно рекомендуется заранее оценить размер HashMap, чтобы свести к минимуму потери производительности, вызванные расширением.
По коду видно, что на самом деле данные хранятся
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
Этот массив, то как он определен?
Entry — это внутренний класс в HashMap, что легко увидеть по его переменным-членам:
- ключ - это ключ при письме.
- ценность, естественно, ценность.
- В начале было упомянуто, что HashMap состоит из массивов и связанных списков, поэтому следующий используется для реализации структуры связанного списка.
- Хэш хранит хэш-код текущего ключа.
Зная базовую структуру, давайте взглянем на важные функции записи и получения:
положить метод
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
- Определяет, нужно ли инициализировать текущий массив.
- Если ключ пуст, поместите в него пустое значение.
- Вычислить хэш-код на основе ключа.
- Найдите ведро в соответствии с рассчитанным хэш-кодом.
- Если ведро представляет собой связанный список, вам нужно пройти, чтобы определить, равны ли хэш-код и ключ в нем входящему ключу.Если они равны, перезапишите и верните исходное значение.
- Если ведро пусто, это означает, что в текущем расположении нет данных; добавьте объект Entry для записи в текущее расположение.
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
При вызове addEntry для записи Entry необходимо определить, требуется ли расширение.
Удвойте расширение, если это необходимо, повторно хешируйте и найдите текущий ключ.
пока вcreateEntryМидл передаст ведро в текущем местоположении во вновь созданное ведро, и если текущее ведро имеет значение, в этом месте будет сформирован связанный список.
получить метод
Давайте еще раз посмотрим на функцию get:
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
- Сначала хэш-код вычисляется на основе ключа, а затем располагается в определенном сегменте.
- Определите, является ли позиция связанным списком.
- Не связанный список основан на
key、key 的 hashcodeравно, чтобы вернуть значение. - Для связанного списка он должен проходить до тех пор, пока ключ и хэш-код не сравняются и не вернут значение.
- Возвращает null, если ничего не получено.
Base 1.8
Я не знаю, есть ли в реализации 1.7 моменты, которые нужно оптимизировать?
На самом деле, одно очевидное место:
Когда конфликт хэшей является серьезным, связанный список, сформированный в корзине, будет становиться все длиннее и длиннее, так что эффективность запроса будет становиться все ниже и ниже; временная сложность
O(N).
Поэтому в версии 1.8 основное внимание уделяется оптимизации эффективности этого запроса.
1.8 Структурная схема HashMap:
Давайте взглянем на несколько основных переменных-членов:
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
transient Node<K,V>[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
Это в основном то же самое, что и 1.7, с несколькими важными отличиями:
-
TREEIFY_THRESHOLDПорог, используемый для определения необходимости преобразования связанного списка в красно-черное дерево. - HashEntry изменен на Node.
Основной состав Node на самом деле такой же, как HashEntry в 1.7, который хранит всеkey value hashcode nextданные.
Давайте еще раз посмотрим на основной метод.
положить метод
Вроде сложнее 1.7, разбираем пошагово:
- Чтобы определить, пусто ли текущее ведро, его необходимо инициализировать, если оно пусто (изменение размера определит, следует ли его инициализировать).
- По хэш-коду текущего ключа найдите конкретное ведро и определите, пусто ли оно, если оно пусто, значит, конфликта хэшей нет и новое ведро можно создать прямо в текущем местоположении.
- Если в текущей корзине есть значение (Конфликт хэшей), то сравните значения в текущей корзине
key、key 的 hashcodeРавно ли оно написанному ключу, если равно, то присвоеноe, на шаге 8 присваивание и возврат будут выполняться единообразно. - Если текущее ведро представляет собой красно-черное дерево, данные должны быть записаны в виде красно-черного дерева.
- Если это связанный список, необходимо инкапсулировать текущий ключ и значение в новый узел и записать его в конец текущего сегмента (для формирования связанного списка).
- Затем оценивается, больше ли размер текущего связанного списка заданного порога, и если он больше, то он будет преобразован в красно-черное дерево.
- Если в процессе обхода обнаруживается, что ключ один и тот же, обход сразу завершается.
- если
e != nullЭто эквивалентно существованию одного и того же ключа, тогда значение необходимо перезаписать. - Наконец, определите, требуется ли расширение.
получить метод
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
Метод get выглядит намного проще.
- Сначала получите найденное ведро после хэша ключа.
- Возвращает null, если ведро пусто.
- В противном случае оценивается, является ли ключ первой позиции корзины (возможно, связанный список или красно-черное дерево) ключом запроса, и значение возвращается напрямую.
- Если первый не совпадает, то рассудите, является ли его следующий красно-черным деревом или связным списком.
- Красно-черное дерево возвращает значение в соответствии с методом поиска дерева.
- В противном случае он проходит по соответствующему возвращаемому значению в соответствии со связанным списком.
Из этих двух основных методов (get/put) видно, что большой связанный список оптимизирован в версии 1.8, а эффективность запросов напрямую повышается после модификации красно-черного дерева.O(logn).
Однако также существуют исходные проблемы HashMap, такие как бесконечные циклы, которые могут возникать при использовании в параллельных сценариях.
final HashMap<String, String> map = new HashMap<String, String>();
for (int i = 0; i < 1000; i++) {
new Thread(new Runnable() {
@Override
public void run() {
map.put(UUID.randomUUID().toString(), "");
}
}).start();
}
Но почему? Простой анализ.
Прочитав вышеизложенное, я вспомнил, что при расширении HashMap он будет называтьсяresize()Метод заключается в том, что параллельная операция здесь легко формирует круговой связанный список на ведре; таким образом, когда получен несуществующий ключ, вычисляемый индекс является в точности нижним индексом кругового связанного списка, и бесконечный цикл произойдет.
Как показано ниже:
Обход
Еще стоит отметить метод обхода HashMap, который обычно включает в себя следующее:
Iterator<Map.Entry<String, Integer>> entryIterator = map.entrySet().iterator();
while (entryIterator.hasNext()) {
Map.Entry<String, Integer> next = entryIterator.next();
System.out.println("key=" + next.getKey() + " value=" + next.getValue());
}
Iterator<String> iterator = map.keySet().iterator();
while (iterator.hasNext()){
String key = iterator.next();
System.out.println("key=" + key + " value=" + map.get(key));
}
强烈建议Используйте первый тип EntrySet для обхода.
Первый может забрать значение ключа одновременно, а второму нужно взять значение через ключ один раз, что неэффективно.
Кратко о HashMap: Будь то 1.7 или 1.8, видно, что JDK не выполняет над ним никаких операций синхронизации, поэтому будут возникать проблемы параллелизма, и даже бесконечный цикл приведет к недоступности системы.
Поэтому JDK запустил специальный выделенный ConcurrentHashMap, который находится вjava.util.concurrentВ рамках пакета он специально используется для решения проблем параллелизма.
Друзья, которые настаивают на просмотре здесь, уже заложили прочную основу для ConcurrentHashMap, и анализ официально начинается ниже.
ConcurrentHashMap
ConcurrentHashMap также делится на версии 1.7 и 1.8, которые немного отличаются по реализации.
Base 1.7
Давайте сначала посмотрим на реализацию версии 1.7. Ниже приведена его структурная схема:
Как показано на рисунке, он состоит из массива сегментов и HashEntry.Как и HashMap, он по-прежнему является массивом и связанным списком.
Его основные переменные-члены:
/**
* Segment 数组，存放数据时首先需要定位到具体的 Segment 中。
*/
final Segment<K,V>[] segments;
transient Set<K> keySet;
transient Set<Map.Entry<K,V>> entrySet;
Segment — это внутренний класс ConcurrentHashMap, основными компонентами которого являются:
static final class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
// 和 HashMap 中的 HashEntry 作用一样，真正存放数据的桶
transient volatile HashEntry<K,V>[] table;
transient int count;
transient int modCount;
transient int threshold;
final float loadFactor;
}
Взгляните на состав HashEntry:
Он очень похож на HashMap, единственное отличие состоит в том, что все основные данные, такие как значение и связанный список, являются изменчивыми, измененными для обеспечения видимости во время получения.
В принципе: ConcurrentHashMap использует технологию блокировки сегментов, где Segment наследуется от ReentrantLock. В отличие от HashTable, операции ввода и получения должны быть синхронизированы.Теоретически ConcurrentHashMap поддерживает параллелизм потоков CurrencyLevel (количество массивов сегментов). Всякий раз, когда поток занимает блокировку для доступа к сегменту, он не влияет на другие сегменты.
Давайте также посмотрим на ядроput getметод.
положить метод
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
Во-первых, найти сегмент с помощью ключа, а затем выполнить конкретную вставку в соответствующий сегмент.
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
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;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else {
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();
}
return oldValue;
}
Хотя значение в HashEntry изменяется с помощью ключевого слова volatile, оно не гарантирует атомарности параллелизма, поэтому операцию put по-прежнему необходимо заблокировать.
Во-первых, на первом этапе он попытается получить блокировку.Если получение не удается, должны быть другие конкурирующие потоки.scanAndLockForPut()Блокировка спина.
- Попытка вращения получить блокировку.
- Если количество попыток достигло
MAX_SCAN_RETRIESИзмените получение блокировки на блокировку, чтобы обеспечить успешное получение.
Взгляните на процесс пут в сочетании с рисунком.
- Найдите таблицу в текущем сегменте в HashEntry по хэш-коду ключа.
- Пройдите HashEntry и, если он не пуст, оцените, равен ли входящий ключ текущему пройденному ключу, и если они равны, перезапишите старое значение.
- Если он не пустой, нужно создать новый HashEntry и добавить его в Segment, при этом он сначала определит, требуется ли расширение.
- Наконец, блокировка текущего сегмента, полученная в 1, будет снята.
получить метод
public V get(Object key) {
Segment<K,V> s; // manually integrate access methods to reduce overhead
HashEntry<K,V>[] tab;
int h = hash(key);
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
e != null; e = e.next) {
K k;
if ((k = e.key) == key || (e.hash == h && key.equals(k)))
return e.value;
}
}
return null;
}
Логика получения относительно проста:
Вам нужно только найти ключ к определенному сегменту после прохождения через хеш, а затем найти его к определенному элементу через хеш.
Поскольку атрибут value в HashEntry изменен с помощью ключевого слова volatile для обеспечения видимости памяти, это самое последнее значение каждый раз, когда оно извлекается.
Метод get ConcurrentHashMap очень эффективен,Потому что весь процесс не нужно блокировать.
Base 1.8
В версии 1.7 проблема параллелизма решена, и он может поддерживать так много параллелизма N сегментов, но в версии 1.7 по-прежнему существует проблема с HashMap.
То есть эффективность запроса по связному списку слишком низкая.
Поэтому в версии 1.8 были внесены некоторые коррективы в структуру данных.
Сначала посмотрите на базовую структуру:
Похоже ли это на структуру 1.8 HashMap?
Который отказался от оригинальной блокировки сегмента сегмента и принялCAS + synchronizedдля обеспечения безопасности параллелизма.
Также изменил HashEntry, который хранит данные в 1.7, на Node, но эффект тот же.
один из нихval nextОба украшены летучими для обеспечения видимости.
положить метод
Сосредоточьтесь на функции put:
- Вычислить хэш-код на основе ключа.
- Определите, требуется ли инициализация.
-
fЭто узел, расположенный по текущему ключу. Если он пуст, это означает, что текущая позиция может записывать данные. Используйте CAS, чтобы попытаться записать, и если это не удается, спин гарантирует успех. - если текущее местоположение
hashcode == MOVED == -1, его необходимо расширить. - Если ни один из них не удовлетворен, используйте синхронизированную блокировку для записи данных.
- Если количество превышает
TREEIFY_THRESHOLDЕго нужно преобразовать в красно-черное дерево.
получить метод
- В соответствии с рассчитанной адресацией хэш-кода, если он находится в корзине, верните значение напрямую.
- Если это красно-черное дерево, получите значение в соответствии с деревом.
- Если он не удовлетворен, пройдите по связанному списку, чтобы получить значение.
1.8 Существенные изменения внесены в структуру данных 1.7.После использования красно-черного дерева можно гарантировать эффективность запроса (
O(logn)), и даже отменил ReentrantLock и изменил его на синхронизированный, так что видно, что в новой версии JDK оптимизация синхронизации есть.
Суммировать
После прочтения различных реализаций HashMap и ConcurrentHashMap в версиях 1.7 и 1.8 я считаю, что все должны понимать их лучше.
Собственно, это и является ключевым содержанием интервью.Обычная рутина такова:
- Расскажите о HashMap, который вы понимаете, и обсудите с ним процесс get put.
- 1.8 Какие оптимизации были сделаны?
- Это потокобезопасно?
- Какие проблемы может вызвать неуверенность?
- Как решить? Существуют ли потокобезопасные параллельные контейнеры?
- Как реализован ConcurrentHashMap? В чем разница между реализациями 1.7 и 1.8? Зачем это делать?
Я считаю, что эту серию вопросов можно вернуть интервьюеру после внимательного прочтения.
В дополнение к интервью будет задано, есть на самом деле довольно много приложений, как упоминалось ранееКэш в ГуавеРеализация заключается в использовании идеи ConcurrentHashMap.
В то же время вы также можете узнать об идеях оптимизации и параллельных решениях авторов JDK.
Фактически, идея написания этой статьи взята с GitHub.Issues, Я также надеюсь, что все смогут участвовать и совместно поддерживать этот проект.
Дополнительный
Недавно я обобщил некоторые знания, связанные с Java, и заинтересованные друзья могут поддерживать их вместе.
Добро пожаловать, чтобы обратить внимание на публичный аккаунт, чтобы общаться вместе: