Для получения дополнительных технических статей, пожалуйста, обратите внимание на мою общедоступную учетную запись WeChat: Мыши сосны без стоп-кода (WeChat: busy_squirrel), вы также можете отсканировать QR-код ниже, чтобы следовать, чтобы получать последние статьи~
Преамбула
В ежедневной работе по разработке бэкенда,собиратьЭто инструмент, который используется довольно часто, иHashMap, это хороший помощник для нас, чтобы разобраться с бизнес-логикой, и в то же времяHashMapЛежащая в основе реализация и принцип также стали частым гостем в вопросах интервью.
ранее известный в деталяхHashMapПринцип реализации см. в исходном коде (версия JDK7). Но с быстрой итерацией версии jdk (теперь это JDK13, но новые функции никогда не использовались...), основная версия jdk, наконец, перешла с JDK7 на JDK8.
Из-за прямой совместимости JDK он не был обнаружен при использовании JDK8.HashMapЧто особенного, функции не изменились (по-прежнему небезопасны для потоков). Но недавно, движимый любопытством, я зашел из IDE и посмотрел на него.HashMapизput()Метод немного сбивает с толку, почему он отличается от того, что я помню? От JDK7 до JDK8,HashMapТы тоже обновился? Что было обновлено?
С этим любопытством я просмотрел исходный код JDK7 и JDK8 и сравнил принципы их реализации. Версия JDK обновляется со скоростью около полугода. Конечно, наше познание должно не отставать от нее. , держитесь на вершине волны, иначе вас захлестнет этот бурлящий информационный оползень.
Сначала покажите уровень отношений семейства Map, что поможет нам лучше понять следующее содержимое.
HashMapВведение базовых знаний не будет слишком многословным, перейдем сразу к теме и посмотрим на реализацию функций JDK7 и JDK8.
1. Базовая реализация HashMap в JDK7
1.1 Базовые знания
Будь то 1.7 или 1.8, структура реализации HashMapХэш-таблица + связанный списоккомбинация. Структурная схема выглядит следующим образом:
Наиболее часто используетсяput(),get()Операция, если вы хотите понять базовую реализацию, самый прямой способ - начать сput()/get()метод выглядит. Однако, прежде чем подробно рассматривать исходный код, давайте сосредоточимся на нескольких переменных предметной области и заложим основу следующим образом:
На рисунке выше кратко объяснена каждая переменная.
Еще одно слово, последняя переменнаяmodCount, который записывает, сколько раз на карте добавлялись/удалялись пары k-v или внутренняя структура была скорректирована.iterator()Операция проверяется на согласованность.Если значение карты будет изменено во время операции итератора, оно будет выброшено напрямую.ConcurrentModificationExceptionаномальный.
Следует также отметить, что в переменной домена выше есть уравнение:
threshold = table.length * loadFactor;
при исполненииput()Когда операция помещает новое значение, если соответствующий ключ уже существует в карте, он может быть заменен, если он не существует, он будет оцениваться первым.size>=thresholdУстановлена она или нет, является важным фактором при определении возможности расширения хеш-таблицы.
Что касается уровня использования, наиболее часто используемым являетсяput()метод,get()метод. Если вы хотите подробно понять принцип работы, давайте начнем с этих двух методов.После понимания этих двух методов можно в основном прояснить принцип реализации HashMap.
1.2 Метод put()
После понимания вышеуказанных переменных и их использования, давайте посмотримput()Конкретная реализация метода:
Как показано в коде скриншота выше, обработку всего метода put можно разделить на четыре части:
- часть 1: специальная обработка значения ключа, ключ нулевой;
- часть 2: вычислить индекс целевого сегмента в таблице;
- часть 3: укажите целевое ведро, просмотрите связанный список узлов входа и замените, если найден узел входа с тем же ключом;
- часть 4: если целевой узел Entry не найден, добавьте узел Entry.
Не знаю, заметили ли вы, на скриншоте вышеput()Метод имеет возвращаемое значение, и сценарии следующие:
- Сценарий 1: если ключ уже существует до выполнения операции размещения, то новое значение будет использоваться для перезаписи предыдущего старого значения при выполнении операции размещения, и старое значение будет возвращено;
- Сценарий 2. Если ключ не существует, вернуть нулевое значение.
Ниже приводится подробный анализ разборки каждой части метода put.
1.2.1 Обработка специального значения ключа
Специальное значение ключа означает, что ключ имеет значение null.
Вывод первый:
a)В HashMap и ключ, и значение могут быть нулевыми, и если ключ нулевой, сохраняется только одна копия, а многократное хранение перезапишет старое значение;
b)Места хранения, где ключ имеет значение null, единообразно помещаются в нижний индекс как0Ведро, то есть: связанный список в позиции table[0];
c)Если это первый раз, когда выполняется операция размещения по ключу = null, узел Entry будет добавлен в позицию таблицы [0], а связанный список будет вставлен с использованием метода вставки заголовка.
Над кодом:
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
/**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket. It is the responsibility of this
* method to resize the table if appropriate.
*
* Subclass overrides this to alter the behavior of put method.
*/
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);
}
/**
* Like addEntry except that this version is used when creating entries
* as part of Map construction or "pseudo-construction" (cloning,
* deserialization). This version needn't worry about resizing the table.
*
* Subclass overrides this to alter the behavior of HashMap(Map),
* clone, and readObject.
*/
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++;
}
putForNullKey()Код в методе проще: сначала выберитеtable[0]Связанный список местоположения, а затем просмотрите связанный список. Если ключ узла равен нулю, замените старое значение новым значением и верните старое значение. Если не найдено, добавьте узел Entry с нулевым ключом. .точка.
Сосредоточьтесь на втором способеaddEntry().
Вот общий метод:
С учетом индексов хеша, ключа, значения и корзины добавляется узел Entry, который также отвечает за расширение емкости. Если количество пар k-v, хранящихся в хеш-таблице, превышает текущий порог (threshold = table.length * loadFactor), а индекс текущего сегмента имеет связанный список, то выполняется изменение размера. После расширения пересчитайте хеш и, наконец, получите индекс нового сегмента, а затем используйте метод вставки заголовка для добавления новых узлов.
1.2.2 Расширение
Как упоминалось в предыдущем разделе, когда пропускная способность пары k-v превышает определенный предел, хеш-таблицу необходимо расширить. Так вот вопрос, как расширить? Взгляните на исходный код ниже:
Есть два основных момента:a)Размер после расширения вдвое больше, чем до расширения;
oldCapacity=table.length;
newCapacity = 2 * oldCapacity;
b)Перемещение данных из старой таблицы в новую после расширения. Чтобы избежать слишком большого количества коллизий, сначала решите, нужно ли повторно хэшировать каждый узел связанного списка Entry, затем вычислите индекс корзины в соответствии с хеш-значением, а затем используйте метод вставки заголовка для переноса узлов.
1.2.3 Как рассчитать индекс корзины?
① Расчет хэш-значения
Во-первых, должно быть хэш-значение ключа, которое является целым числом, тип int.В методе расчета используется формула (операция высокого порядка), которая может минимизировать коллизии.Конкретный принцип не будет расширяться.Только знайте один вещь: используйте хэш-код ключа в качестве ввода формулы, получите хеш-значение.
Из приведенных выше точек знаний мы можем получитьвывод:
Для двух объектов, если их хэш-код одинаков, то хэш-значение двух объектов должно быть одинаковым.
Вот еще один момент познания. Для типа ключа в HashMap должны быть выполнены следующие условия:
Если два объекта логически равны, то их hashCode должен быть равен, и наоборот не обязательно верно.
Значение логического равенства относительно широкое.Мы можем определить логическое равенство как одинаковый адрес памяти двух объектов, или его можно определить как равенство определенного значения поля объекта.Логическое равенство двух объектов можно определить как переписываниеObjectКатегорияequals()метод достижения.
НапримерStringclass см. следующий код:
String str1 = "abc";
String str2 = new String("abc");
System.out.println(str1 == str2); // false，两个对象的内存地址并不同
System.out.println(str1.equals(str2)); // true 两个对象的域值相同，都存储了 abc 这三个字符
для кода вышеstr1,str2Два объекта, хотя их адреса памяти различны,Stringпара классовObjectКатегорияequals()переопределение метода (@override), переменные предметной области (т. е. массивы символов) двух объектов хранят три символа «a», «b» и «c», поэтому они логически равны. теперь, когдаstr1,str2Если два объекта логически равны, то должен быть следующий результат:
System.out.println(str1.hashCode() == str2.hashCode());
---输出---
true
Таким образом, мы можем знать, что в том же объекте HashMap будут следующие результаты:
String str1 = "abc";
String str2 = new String("abc");
Map<String, Integer> testMap = new HashMap<>();
testMap.put(str1, 12);
testMap.put(str2, 13);
String str3 = new StringBuilder("ab").append("c").toString();
System.out.println(testMap.get(str3));
---输出---
13
Кроме того, мы также можем думать об этом в обратном порядке.
Предполагая, что ключ HashMap не соответствует вышеуказанным условиям, то есть, если два объекта равны, их hashCode может быть несогласованным. Итак, каковы последствия этого? в примере кода вышеstr1,str2Например, если их хэш-коды не равны, то и соответствующие хэши могут быть не равны (Уведомление:вотне может быть равным, также может быть равным), когда testMap выполняет операцию размещения,str1,str2Он будет распределен по разным корзинам, и самым прямым следствием будет сохранение двух копий. Есть и более косвенные последствия, такие как: использованиеstr3выполнение объектаtestMap.get(str3)Во время работы значение может быть не получено, и дальнейшее последствие состоит в том, что эта часть недостижимых объектов не может быть переработана, что приводит кутечка памяти.
следовательно,делать все это снова, тип, соответствующий ключу HashMap, должен удовлетворять следующим условиям:
Если два объекта логически равны, то их hashCode должен быть равен, и наоборот не обязательно верно.
② Логика взятия по модулю
Ранее мы анализировали вычисление хэш-значения, а затем можем перейти к вычислению индекса ведра:
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
Расчет довольно прост: сделайте емкость таблицы со значением хеш-функции.и" для получения нижнего индекса сегмента хеш-таблицы.
③ Развернуть
Каждый может понять такой народный расчет, который уже не может быть популярным, но зачем его делать? Какая мысль стоит за этим? Прежде чем читать объяснение ниже, вы можете сначала подумать об этом ~
В начале документа приведены различные переменные поля в классе HashMap. Среди них начальный размер хеш-таблицы по умолчанию установлен равным 16, что является степенью числа 2. При последующем расширении емкости она будет увеличена кратно 2. Почему размер хэш-таблицы должен контролироваться степенью двойки?
Причина 1: снижает вероятность коллизий и делает хэширование более равномерным. При вычислении позиции нижнего индекса ведра в соответствии с хеш-значением ключа используйте формулу «И»: h & (длина-1).Когда длина хеш-таблицы является степенью 2, это эквивалентно использованию длина таблицы по модулю хэш-значения (если не верите, можете сами посчитать), хэш более равномерный;
Причина 2: длина таблицы равна степени 2, тогда последняя цифра двоичного числа (длина-1) должна быть равна 1. Когда операция «И» выполняется над хэш-значением, последняя цифра может быть 1 или 0. Другими словами, результат взятия по модулю имеет как четные, так и нечетные числа. Предположим, что если (length-1) — четное число, значение после операции «И» может быть только 0, а ведро с нечетным нижним индексом никогда не будет хешировано, что приведет к потере половины пространства.
1.2.4 Обход узла Entry в целевом сегменте
Сначала возьмите эту часть кода:
...
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;
}
}
...
Вычислите индекс по хеш-значению, найдите соответствующий целевой сегмент, а затем просмотрите связанный список и сравните их один за другим следующим образом:
Обратите внимание на критерии поиска здесь:e.hash == hash && ((k = e.key) == key || key.equals(k))Ключ узла равен ключу цели, либо адрес памяти равен, либо он логически равен, и достаточно одного из двух.
1.3 метод get()
по сравнению сput()метод,get()Реализация метода относительно проста. В основном он делится на два этапа: сначала индекс целевого сегмента вычисляется по хеш-значению ключа, затем просматривается связанный список в соответствующем сегменте, и результаты сравниваются один за другим.
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
/**
* Returns the entry associated with the specified key in the
* HashMap. Returns null if the HashMap contains no mapping
* for the key.
*/
final Entry<K,V> getEntry(Object key) {
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;
}
1.4 Итератор в карте
1.4.1 Несколько способов обхода карты
Первый вопрос: сколько способов перемещения по Карте вы можете придумать?
Способ 1: Итератор-итератор
Iterator<Entry<String, Integer>> iterator = testMap.entrySet().iterator();
while (iterator.hasNext()) {
Entry<String, Integer> next = iterator.next();
System.out.println(next.getKey() + ":" + next.getValue());
}
Получите каждый узел Entry в каждом сегменте хеш-таблицы один за другим, что будет подробно описано позже.
Способ 2: самый распространенный способ использования, вы можете получить ключ и значение одновременно.
// 方式一
for (Map.Entry<String, Integer> entry : testMap.entrySet()) {
System.out.println(entry.getKey() + ":" + entry.getValue());
}
Этот метод — синтаксический сахар, мы можем декомпилировать команду javap или проверить скомпилированный оператор через IDE:
Iterator var2 = testMap.entrySet().iterator();
while(var2.hasNext()) {
Entry<String, Integer> entry = (Entry)var2.next();
System.out.println((String)entry.getKey() + ":" + entry.getValue());
}
Нижний слой по-прежнему использует функцию Iterator.
Способ 3: используйте метод foreach (только JDK1.8)
testMap.forEach((key, value) -> {
System.out.println(key + ":" + value);
});
Это тип лямбда-выражения. foreach также является синтаксическим сахаром, который используется внутриСпособ 2Метод обработки метода foreach Map реализован следующим образом:
Способ 4: обход набора ключей
Iterator<String> keyIterator = testMap.keySet().iterator();
while (keyIterator.hasNext()) {
String key = keyIterator.next();
System.out.println(key + ":" + testMap.get(key));
}
Это тоже метод Iterator, но через метод iterator класса Set.
по сравнению сспособ 1, этот способ получитьvalue, необходимо пройтиtestMap.get()образом, производительность по сравнению сспособ 1много понизить. Но у обоих есть свои сценарии использования, если они используются только в обходе карты.key,носпособ 4больше подходит, если вам нужно использоватьvalue,Рекомендуемое использованиеспособ 1.
спередиспособ 1испособ 2Видно, что режим 4 также имеет следующие варианты (синтаксический сахар):
for (String key : testMap.keySet()) {
System.out.println(key + ":" + testMap.get(key));
}
Подводя итог вышесказанному, при обходе карты с точки зрения производительности, если вам нужно использовать ключ и значение одновременно, рекомендуется использоватьспособ 1илиспособ 2, если вы просто используете ключ, рекомендуется использоватьспособ 4. Не рекомендуется ни при каких обстоятельствахспособ 3, т.к. добавится второй запрос (найти значение в Map еще раз через ключ).
Кроме того, используйтеспособ 1, также можно выполнить операцию удаления, о которой речь пойдет ниже.
1.4.2 Принцип реализации Iterator
Сначала взгляните на диаграмму наследования классов/интерфейсов:
Итератор — это интерфейс верхнего уровня, который предоставляет только три основных объявления метода:
public interface Iterator<E> {
boolean hasNext();
E next();
default void remove() {
throw new UnsupportedOperationException("remove");
}
}
Это тоже то, что мы используемIteratorТри метода, которых нельзя избежать.
В HashMap первым делом нужно добавить внутренний абстрактный класс.HashIterator,следующее:
В качестве примера возьмем обход узла Entry (методы обхода ключа и значения Iterator аналогичны):
Iterator<Entry<String, Integer>> iterator = testMap.entrySet().iterator();
while (iterator.hasNext()) {
Entry<String, Integer> next = iterator.next();
System.out.println(next.getKey() + ":" + next.getValue());
}
Во-первых, первая строка кода, найдитеIteratorКонкретный класс реализации интерфейсаEntryIterator:
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() {
return nextEntry();
}
}
Очень просто, дрова есть? ? ? только одинnext()метод, который точноIteratorинтерфейсnext()реализация метода. Внутри метода есть только одна строка, указывающая на родительский классnextEntry()метод, который показан на скриншоте вышеHashIteratorв классеnextEntry()метод.
Принцип реализации Iterator в HashMap точно такой же, настолько он прост и незатейлив, хотите реализовать HashMap самостоятельно? Ну, ты можешь! ! !
1.5 безотказная стратегия
иfail-fastСуществует также класс исключений, который часто встречается вместеConcurrentModificationExceptionДалее поговорим об отношениях между ними и о том, почему была разработана такая стратегия.
чтоfail-fast? Мы можем назвать это «Стратегией быстрого отказа», вот объяснение в Википедии:
In systems design, a fail-fast system is one which immediately reports at its interface any condition that is likely to indicate a failure. Fail-fast systems are usually designed to stop normal operation rather than attempt to continue a possibly flawed process. Such designs often check the system's state at several points in an operation, so any failures can be detected early. The responsibility of a fail-fast module is detecting errors, then letting the next-highest level of the system handle them.
В переводе с народного языка это означает, что при проектировании системы сообщение об ошибке возникает немедленно, когда возникает условие, которое может привести к отказу, а система быстрого отказа часто предназначена для немедленного прекращения нормального рабочего процесса, а не для попытки продолжить работу. процесс, в котором могут быть ошибки.
более кратко, то есть найти проблему как можно раньше, немедленно прекратить текущий процесс выполнения и заняться ею системой более высокого уровня.
В HashMap мы упоминали ранееmodCountПеременные домена, которые используются для реализации hashMapfail-fast. Это часто происходит в асинхронных многопоточных параллельных операциях.
При выполнении операции Iterator на карте он будетmodCountПеременная домена назначаетсяexpectedModCountлокальные переменные. В итеративном процессе он используется для проверки согласованности времени модификации контента. Если другие потоки или другие операции этого потока изменят содержимое этой карты в это время, это вызоветmodCountиexpectedModCountНесовместимо, немедленно выдать исключениеConcurrentModificationException.
Возьмите каштан:
public static void main(String[] args) {
Map<String, Integer> testMap = new HashMap<>();
testMap.put("s1", 11);
testMap.put("s2", 22);
testMap.put("s3", 33);
for (Map.Entry<String, Integer> entry : testMap.entrySet()) {
String key = entry.getKey();
if ("s1".equals(key)) {
testMap.remove(key);
}
}
}
---- output ---
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.HashMap$HashIterator.nextNode(HashMap.java:1437)
at java.util.HashMap$EntryIterator.next(HashMap.java:1471)
at java.util.HashMap$EntryIterator.next(HashMap.java:1469)
...
Правильная поза для удаления элементов Map: только одна, Iteatorremove()метод.
// 方式三
Iterator<Entry<String, Integer>> iterator = testMap.entrySet().iterator();
while (iterator.hasNext()) {
Entry<String, Integer> next = iterator.next();
System.out.println(next.getKey() + ":" + next.getValue());
if (next.getKey().equals("s2")) {
iterator.remove();
}
}
Но следует также отметить, что безопасное удаление не означает, что оно является многопоточным безопасным, При многопоточном параллельном выполнении, если выполняются все вышеперечисленные операции, потому что не установлен метод синхронизации, это также может вызватьmodCountиexpectedModCountнесовместимо, поэтому выбрасывается исключениеConcurrentModificationException.
Проявления и предотвращение небезопасности потоков будут подробно упомянуты в последующих главах.
2. Базовая реализация HashMap в JDK8
Ранее мы подробно разбирали реализацию HashMap в JDK7, нашли ли вы места, которые можно оптимизировать? Например, в структуре связанного списка, вызванной коллизией хэшей в хеш-таблице, если объем данных велик, вероятность коллизии будет увеличиваться, и следствием этого будет увеличение длины связанного списка. . Как улучшить производительность запросов, стало проблемой, которую должен решить HashMap в JDK8.
Таким образом, по сравнению с JDK7, HashMap оптимизирует структуру связанного списка в JDK8 (но по-прежнему небезопасен для потоков) и преобразует связанный список в красно-черное дерево при определенных условиях для повышения эффективности запросов.
Базовая структура хранения HashMap в JDK8 выглядит следующим образом:
По сравнению с JDK7 HashMap в JDK8 преобразует длинный связанный список в красно-черное дерево, что также является основным отличием от JDK7. Посмотрите нижеput()реализация метода.
2.1 операция put()
в дальнейшем анализеput()Перед операцией поясню: помимо настройки базовой структуры хранения, определение узла связанного списка также определяетсяEntryкласс повернулся кNodeclass, но ядро не изменилось и на понимание не влияет.
Сначала перейдите к исходному коду:
Это долго и сложно? На самом деле это не сложно, если вы помните приведенную выше диаграмму базовой структуры хранения, код легко понять. Все та же процедура хранения, сначала определяем индекс в хеш-таблице по ключу, находим соответствующий сегмент, проходим по связанному списку (или красно-черному дереву) и выполняем операцию вставки. В JDK7 новый узел должен использоватьпробка для головы, но в JDK8 в связанном списке используйтевставка хвоста, добавьте добавляемый узел в конец связанного списка.
Для простоты понимания приведенный выше код преобразуется в следующую блок-схему:
Шаг ①: если хеш-таблица пуста или ее длина равна 0, выполняется операция раскрытия;Шаг ②: После нахождения целевого ведра по индексу, если на текущем ведре нет узла, то напрямую добавить новый узел и назначить его на ведро;Шаг ③: если в текущей корзине есть связанный список и головной узел совпадает, замените его напрямую;Шаг ④: если текущий сегмент представляет собой древовидную структуру, он будет преобразован в операцию вставки красно-черного дерева;Шаг ⑤: Если шаги ①, ②, ③ и ④ не выполнены, просмотрите связанный список.
а) Если в связанном списке есть совпадающие узлы, замените их значением;
б) Если ни один узел не соответствует, добавить в конец связанного списка. Тем временем сделайте следующее:
i) Если длина связанного списка больше, чемTREEIFY_THRESHOLD, выполняется операция преобразования красно-черного дерева;
ii) еслиусловие я)Если нет, выполните операцию расширения resize().
После выполнения вышеуказанных 5 шагов проверьте, превышает ли количество пар k-v, хранящихся в текущей карте,threshold, если он превышает, его нужно снова расширить.
Операция преобразования красно-черного дерева выглядит следующим образом:
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 若表为空，或表长度小于MIN_TREEIFY_CAPACITY，也不做转换，直接做扩容处理。
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
2.2 Операция расширения емкости
В каких сценариях будет задействовано расширение мощностей?
Сцена 1: хэш-таблица пуста или имеет длину 0;
сцена 2: количество пар k-v, хранящихся на карте, превышает пороговое значение.threshold;
сцена 3: Длина связанного списка превышаетTREEIFY_THRESHOLD, но длина таблицы меньшеMIN_TREEIFY_CAPACITY.
Общее расширение разделено на 2 шага,шаг 1является расширением (2 раза) длины хеш-таблицы,Шаг 2Это перемещение данных из старой таблицы в новую таблицу.
Итак, как расширяется HashMap в JDK8?
Над фрагментом исходного кода:
...
// 前面已经做了第1步的长度拓展，我们主要分析第2步的操作：如何迁移数据
table = newTab;
if (oldTab != null) {
// 循环遍历哈希table的每个不为null的bucket
// 注意，这里是"++j"，略过了oldTab[0]的处理
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 若只有一个结点，则原地存储
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// "lo"前缀的代表要在原bucket上存储，"hi"前缀的代表要在新的bucket上存储
// loHead代表是链表的头结点，loTail代表链表的尾结点
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 以oldCap=8为例，
// 0001 1000 e.hash=24
// & 0000 1000 oldCap=8
// = 0000 1000 --> 不为0，需要迁移
// 这种规律可发现，[oldCap, (2*oldCap-1)]之间的数据，
// 以及在此基础上加n*2*oldCap的数据，都需要做迁移，剩余的则不用迁移
if ((e.hash & oldCap) == 0) {
// 这种是有序插入，即依次将原链表的结点追加到当前链表的末尾
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// 需要搬迁的结点，新下标为从当前下标往前挪oldCap个距离。
newTab[j + oldCap] = hiHead;
}
}
}
}
}
2.3 операция get()
После понимания описанной выше операции put() операция get() становится относительно простой.
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;
}
Сначала вычисляем значение хеша по ключу, а затем далее вычисляем целевой индекс хеш-таблицы.Если ведро красно-черное дерево, то ищем по красно-черному дереву.Если не красно-черное дерево , пройти по связанному списку.
3. Какая связь между HashMap и HashTable?
Давайте поместим картинку в начале статьи и рассмотрим ее:
3.1 Общие черты, сходства и различия
точки соприкосновения:
- Нижний уровень — это реализация использования хеш-таблицы + связанного списка.
разница:
- С точки зрения иерархической структуры HashMap и HashTable имеют общие
Mapинтерфейс. Кроме того, HashTable также отдельно наследует абстрактный класс.Dictionary; - HashTable родился в JDK1.0, а HashMap был доступен только после JDK1.2;
- HashTable является потокобезопасным, HashMap не является потокобезопасным;
- Начальное значение и метод расширения различны. Начальное значение HashTable равно 11, и оно расширяется до исходного размера.
2*d+1. Все размеры емкости представляют собой нечетные и простые числа, и используется метод по модулю, что делает хеширование более равномерным. Но есть недостаток, заключающийся в том, что производительность при взятии модуля простых чисел низкая (включая операцию деления), а длина HashTable равна всей степени 2, поэтому конструкция более умна.Это прямая битовая операция. , который имеет лучшую производительность. - И ключ, и значение HashMap могут быть нулевыми, и значение может быть нулевым несколько раз.Если ключ имеет значение нуль несколько раз, он будет перезаписан. Когда ключ и значение HashTable не равны нулю, в противном случае прямой NPE (NullPointException).
Пример:
public static void main(String[] args) {
Map<String, Integer> testTable = new Hashtable<>();
testTable.put(null, 23); // 抛NPE
testTable.put("s1", null); // 抛NPE
}
посмотриput()Исходный код метода:
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
Исходный код не допускает, чтобы значение было нулевым. Если оно равно нулю, NPE выбрасывается напрямую.
Когда ключ равен нулю, 9-я строка исходного кода:int hash = key.hashCode();Если операция пустой оценки не выполняется, NPE также будет отброшен.
Кроме того, абстрактный класс, который мы видим сейчасDictionary, является устаревшим классом, комментарии к исходному коду содержат следующие инструкции:
<strong>NOTE: This class is obsolete. New implementations should
implement the Map interface, rather than extending this class.</strong>
3.2 Потокобезопасность HashMap
Существует несколько способов обеспечения безопасности потоков, например добавлениеsynchronizedключевое слово или используйтеlockмеханизм. Разница между ними здесь не раскрывается, в будущем я напишу статью о безопасности потоков, а затем объясню ее подробно. И HashTable использует первое, а именноsynchronizedключевые слова.
поставить операцию, получить операцию, удалить операцию, приравнять операцию, все использоватьsynchronizedМодификация ключевого слова.
Это необходимо для обеспечения потокобезопасности объекта HashTable, но это также приводит к проблемам, наиболее заметной из которых является низкая эффективность. Почему вы сказали, что это неэффективно?
Из-за функции синхронизации для критических ресурсов, совместно используемых несколькими потоками, одновременно может быть занят только один поток, а другие потоки должны ждать на месте Падение мелкого песка выше блокируется по той же причине, когда большое количество потоков, которые должны быть выполненыget()Во время работы тоже бывают такие проблемы, большое количество потоков нужно ставить в очередь на обработку один за другим.
В этот момент кто-то может сказать, что, посколькуget()Метод просто получает данные и не изменяет структуру и данные карты. Можно ли не добавлять его? Прошу прощения, если не добавить, то не работает. Можно добавить другие методы. Если не добавить, будет сценарий, то есть когда поток А делает пут или удаление операцию get одновременно могут выполнять поток B и поток C. Возможно, хеш-таблица была изменена потоком A, что также принесет проблемы, поэтому не добавить ее невозможно.
Что ж, HashMap не является потокобезопасным, а HashTable — потокобезопасным, но его производительность плохая, как его можно сломать? использоватьConcurrentHashMapКлассы не только потокобезопасны, но и эффективны в работе, кто их использует, тот и говорит лучше. Не волнуйтесь, следующая глава объяснит подробноConcurrentHashMapсвоего рода.
4. В чем заключается небезопасность потоков HashMap?
В этой главе в основном обсуждаются проблемы, вызванные небезопасностью потоков HashMap.
4.1 Проблема покрытия данных
Выполняются два потокаput()Во время работы данные могут быть перезаписаны. Эта проблема существует как в версии JDK7, так и в версии JDK8.Здесь в качестве примера используется JDK7.
Предположим, что два потока A и B выполняются одновременно.put()операция, и оба ключа указывают на один и тот же buekct, то оба узла будут выполнять вставку заголовка.
Сначала посмотрите на реализацию кода здесь:
public V put(K key, V value) {
...
addEntry(hash, key, value, i);
}
void addEntry(int hash, K key, V value, int bucketIndex) {
...
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++;
}
увидеть последнийcreateEntry()метода, сначала получите головной узел корзины, а затем используйте новый узел в качестве головной части корзины и укажите на старый головной узел, чтобы завершить операцию вставки головки.
После того, как и поток A, и поток B получили головной узел ведра, если квант времени потока A истекает в это время, поток B завершает операцию вставки головы со своими новыми данными, и наступает очередь потока A действовать, но это Когда старый головной узел, принадлежащий потоку A, устарел (не включая новый узел, только что вставленный потоком B), если поток A снова выполнит операцию вставки заголовка, он удалит только что добавленный узел B, в результате чего данные потерял.
На самом деле не толькоput()Операции, операции удаления и операции модификации также будут иметь проблемы с покрытием.
4.2 Бесконечный цикл, вызванный расширением
Это самая распространенная ситуация и часто задаваемый вопрос в интервью. Но, если честно, проблему бесконечного цикла, вызванную этой многопоточной средой, не так просто объяснить, потому что здесь проникли детали расширения. Здесь максимально просто описан процесс генерации бесконечного цикла.
Кроме того, только JDK7 и предыдущие версии будут иметь явление бесконечного цикла.В JDK8 метод resize() был скорректирован с использованием двух групп связанных списков, и оба используют метод вставки хвоста.При многопоточности во времени, в большинство Сделайте еще один метод вставки хвоста из начального узла, который не вызовет бесконечный цикл. JDK7 может вызвать бесконечный цикл, потому что в resize() используется метод вставки заголовка, а исходный порядок меняется на противоположный, что оставляет возможность для бесконечного цикла.
Перед дальнейшим объяснением процесса бесконечного цикла давайте взглянем на фрагмент кода расширения в JDK7:
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
По сути, это простая инверсия связанного списка, если еще упростить, то он делится на текущий узел.e, а следующий узелe.next. Мы используем связанный списокa->b->c->nullНапример, два потока A и B выполняют операции расширения емкости соответственно.
оригинальные часы:
Каждый из потоков A и B добавляет новую хеш-таблицу.После того как поток A завершил операцию расширения, поток B начинает расширяться. В этот момент для потока B текущий узелeУкажите на узел, следующий узелe.nextПо-прежнему указывает на узел b (в это время в связанном списке потока A он ужеc->b->aпорядок). В соответствии с методом вставки заголовка сегмент хэш-таблицы указывает на узел a, и узел a становится головным узлом связанного списка в потоке B, как показано на следующем рисунке:
После того, как узел a станет головным узлом связанного списка в потоке B, следующий узелe.nextявляется узлом b. Начиная со следующего узлаe.nextне является нулевым, то текущий узелeОн становится узлом b, следующим узломe.nextстановится узлом. Продолжайте выполнять метод вставки головы, измените b на головной узел связанного списка, а указатель next указывает на старый головной узел a, как показано на следующем рисунке:
В этот момент следующий узелe.nextДля узла, отличного от null, продолжите метод вставки заголовка. Переместите указатель назад, затем текущий узелeОн становится узлом, а следующий узел равен нулю. Возьмите узел a в качестве головного узла в связанном списке потока B и укажите следующий указатель на исходный старый головной узел b, как показано на следующем рисунке:
На данный момент связанный список сформирован. При этом следующий узелe.nextЕсли он равен нулю, процесс завершается.
4.3 Резюме
Использование HashMap в многопоточной среде вызовет различные проблемы.Выше приведены лишь два типичных примера небезопасных проблем.Конкретные проблемы нельзя перечислить одну за другой, но их можно условно разделить на следующие три категории:
- бесконечный цикл
- дублирование данных
- Потеря данных (перезапись)
До JDK1.5 многопоточная среда часто использовала HashTable, но в JDK1.5 и более поздних версиях в параллельном пакете была введена многопоточная среда специального назначения.ConcurrentHashMapКласс, использующий блокировку сегмента для достижения потокобезопасности, имеет более высокую производительность, чем HashTable, его рекомендуется использовать.
5. Как избежать небезопасности потоков HashMap?
Как упоминалось выше, упоминаются различные проблемы с безопасностью HashMap в многопоточной среде, так как же можно преобразовать его в потокобезопасный?
5.1 Преобразование карты в класс-оболочку
Как передать? использоватьCollections.SynchronizedMap()метод, пример кода:
Map<String, Integer> testMap = new HashMap<>();
...
// 转为线程安全的map
Map<String, Integer> map = Collections.synchronizedMap(testMap);
Его внутренняя реализация также очень проста, что эквивалентно HashTable, но только добавляет объектную блокировку (синхронизированную) к текущему входящему объекту карты:
// 源码来自Collections类
private static class SynchronizedMap<K,V> implements Map<K,V>, Serializable {
private static final long serialVersionUID = 1978198479659022715L;
private final Map<K,V> m; // Backing Map
final Object mutex; // Object on which to synchronize
SynchronizedMap(Map<K,V> m) {
this.m = Objects.requireNonNull(m);
mutex = this;
}
SynchronizedMap(Map<K,V> m, Object mutex) {
this.m = m;
this.mutex = mutex;
}
public int size() {
synchronized (mutex) {return m.size();}
}
public boolean isEmpty() {
synchronized (mutex) {return m.isEmpty();}
}
public boolean containsKey(Object key) {
synchronized (mutex) {return m.containsKey(key);}
}
public boolean containsValue(Object value) {
synchronized (mutex) {return m.containsValue(value);}
}
public V get(Object key) {
synchronized (mutex) {return m.get(key);}
}
public V put(K key, V value) {
synchronized (mutex) {return m.put(key, value);}
}
public V remove(Object key) {
synchronized (mutex) {return m.remove(key);}
}
public void putAll(Map<? extends K, ? extends V> map) {
synchronized (mutex) {m.putAll(map);}
}
public void clear() {
synchronized (mutex) {m.clear();}
}
}
5.2 Использование ConcurrentHashMap
теперь, когдаHashMapКлассы небезопасны для потоков, поэтому вы также можете найти альтернативу для потоков -ConcurrentHashMapсвоего рода.
Пример использования:
Map<String, Integer> susuMap = new ConcurrentHashMap<>();
susuMap.put("susu1", 111);
susuMap.put("susu2", 222);
System.out.println(susuMap.get("susu1"));
Он полностью совместим с использованием HashMap с точки зрения использования.
Представлен в JDK1.5, находится в параллельном пакете.java.util.concurrentВниз.
В версии JDK7 и более ранних версияхConcurrentHashMapВ классе используется технология блокировки сегмента (segment + Lock), но в jdk8 внесено серьезное изменение, и используется модификатор synchronized.
Конкретные различия будут подробно описаны в следующей статье.
Статья длинная, надеюсь, она окажется полезной для тех, кто ее просматривает.
Для получения дополнительных технических статей, пожалуйста, обратите внимание на мою общедоступную учетную запись WeChat: Мыши сосны без стоп-кода (WeChat: busy_squirrel), вы также можете отсканировать QR-код ниже, чтобы следовать, чтобы получать последние статьи~
Reference
1. Повторное распознавание HashMap в серии Java 8:Специальности.Meituan.com/2016/06/24/…2. Что такое отказоустойчивая стратегия? :blog.ChinaUnix.net/UID-3150784…