1. Обзор карты
Мы все знаем, что HashMap небезопасен для потоков, но частота использования HashMap действительно относительно высока среди всех карт. Потому что он может удовлетворить большинство наших сценариев.
Map类继承图
Map — это интерфейс, и наши наиболее часто используемые классы реализации — это HashMap, LinkedHashMap, TreeMap и HashTable. HashMap сохраняет значение в соответствии со значением hashCode ключа.Следует отметить, что HashMap не гарантирует, что порядок обхода и вставки одинаков. HashMap позволяет ключу записи быть нулевым, но не требует, чтобы значение было нулевым. Класс HashTable является потокобезопасным. Он использует синхронизацию для обеспечения безопасности потоков. В глобальном масштабе существует только одна блокировка. Эффективность хеш-таблицы относительно низка в случае интенсивной конкуренции потоков. Потому что, когда поток обращается к методу синхронизации хэш-таблицы, когда другие потоки пытаются снова получить к нему доступ, он переходит в состояние блокировки или опроса.Например, когда поток 1 использует put для добавления элементов, поток 2 не только не может использовать put для добавления элементы, но также вы не можете использовать get для получения элементов. Поэтому конкуренция будет становиться все более ожесточенной. Напротив, ConcurrentHashMap использует технологию блокировки сегментов для улучшения параллелизма, данные, которые не находятся в одном и том же сегменте, не влияют друг на друга, а операции нескольких потоков в нескольких разных сегментах не будут влиять друг на друга. Каждый сегмент использует один замок. Поэтому рекомендуется использовать ConcurrentHashMap в бизнес-сценариях, требующих безопасности потоков.И HashTable не рекомендуется использовать в новом коде., если требуется безопасность потоков, тоИспользуйте ConcurrentHashMap, в противном случае достаточно использовать HashMap.
LinkedHashMap является подклассом HashMap, и отличие от HashMap в том, что LinkedHashMap сохраняет порядок вставки записей. TreeMap реализует интерфейс SortedMap.TreeMap имеет возможность сортировать вставленные записи по ключу.По умолчанию он сортируется в порядке возрастания.Это также можно настроить.При использовании TreeMap ключ должен реализовывать Comparable.
2. Реализация HashMap
Есть различия между java7 и java8 в реализации HashMap.Конечно, эффективность java8 лучше.Основная причина в том, что HashMap java8 добавляет структуру данных красно-черного дерева на основе java7, что делает сложность поиска данных в ведре с O(n) снижена до O(logn), ну и конечно есть некоторые другие оптимизации, например оптимизация ресайза. Поскольку HashMap для java8 более сложный, в этой статье будет объяснено на основе реализации HashMap для java7. Основные части реализации остались прежними. Реализация java8 в основном оптимизирована. Содержание по-прежнему не изменилось, и это по-прежнему поток -небезопасно.
Реализация HashMap использует массив, и каждый элемент массива имеет связанный список.Поскольку HashMap использует хэш-код ключа для поиска места хранения, разные ключи могут иметь один и тот же хэш-код, и в это время возникает конфликт хэшей.Также называется хэш-коллизия, для разрешения хеш-коллизии существуют методы открытого адреса и методы адресной цепочки. В реализации HashMap выбран метод цепного адреса, то есть запись с одинаковым значением хеш-функции хранится в одном и том же элементе массива, а элемент массива можно рассматривать как ведро, а hashCode ключа ключа запись в ведро такая же.
HashMap的结构模型（java8）
На приведенном выше рисунке показано наше описание, которое имеет очень важную структуру данных Node
final int hash;
final K key;
V value;
Node<K,V> next;
Узел — это узел связанного списка, то есть запись, которую мы вставляем.После понимания того, что HashMap использует метод адресной цепочки для разрешения конфликтов хэшей, нетрудно понять приведенную выше структуру данных.Поле хэша используется для поиска индекса позиция ведра, а значение ключа А - это наши данные. Следует отметить, что наш ключ является окончательным, то есть его нельзя изменить. Это тоже понятно, ведь HashMap использует hashCode ключа для найти положение индекса ведра.После изменения ключа хэш-код ключа, вероятно, изменится, поэтому изменение ключа по желанию приведет к потере записи (не может найти запись). Следующее поле указывает на следующий узел в связанном списке.
Начальное количество ведер HashMap равно 16, а loadFact равно 0,75.Когда записи данных в ведре превышают порог, HashMap будет выполнять операции расширения, и каждый раз он будет удваивать исходный размер до тех пор, пока не будет установлено максимальное значение. больше нельзя изменить размер.
Ниже приводится краткое введение в реализацию HashMap.Конкретная реализация зависит от кода.Для реализации HashMap в java8 также необходимо понимать структуру данных красно-черного дерева.
1. Определите, в какое ведро должна быть помещена запись в соответствии с хэш-кодом ключа. Будь то вставка, поиск или удаление, это первый шаг для вычисления местоположения ведра. Поскольку длина HashMap всегда равна 2 в n-й степени, вы можете использовать следующий метод для выполнения операции по модулю:
h&(length-1)
h — это значение хэш-кода ключа.После вычисления хэш-кода используйте описанный выше метод, чтобы вычислить по модулю количество сегментов и поместить запись данных в определенный сегмент. Конечно, по модулю это практика в java7, java8 была оптимизирована и сделана более умно, потому что наша длина всегда является энной степенью 2, поэтому после изменения размера запись текущей позиции либо сохранит текущую позицию неизменной, либо Просто двигайтесь вперед по длине. Таким образом, изменение размера HashMap в java8 не требует пересчета hashCode. Мы можем абстрагироваться от алгоритма, наблюдая за методом расчета в java7, а затем оптимизировать его.Конкретные детали можно увидеть в коде.
2. Метод put HashMap
HashMap的put方法处理逻辑（java8）
На приведенном выше рисунке показана логика обработки метода put в java8, в котором больше красно-черных частей дерева, чем в java7, и оптимизация в некоторых деталях Логика put согласуется с логикой в java7.
3, механизм изменения размера
Механизм расширения HashMap заключается в повторной подаче заявки на массив сегментов с удвоенной текущей емкостью, затем повторном сопоставлении исходных записей с новыми сегментами один за другим, а затем установлении исходных сегментов в нуль один за другим, чтобы сделать ссылку недействительной. Как будет упомянуто позже, причина, по которой HashMap не является потокобезопасным, заключается в проблеме с изменением размера.
3.1 Почему HashMap не является потокобезопасным? (версия jdk7)
Как упоминалось выше, HashMap выполнит операцию изменения размера, что приведет к небезопасности потока во время операции изменения размера. Вот два возможных места, где может возникнуть небезопасность потока.
1. Многопоточные данные несовместимы при вводе. Эту задачу легко представить, например, есть два потока A и B. Сначала A хочет вставить в HashMap пару ключ-значение, сначала вычислить индексные координаты корзины, в которую попадет запись, и затем получите заголовок связанного списка в ведре.. В этот момент квант времени потока A израсходован, а поток B запланирован для выполнения в это время и выполняется так же, как поток A, за исключением того, что поток B успешно вставляет запись в ведро, предполагая, что ведро вычисляется по записи, вставленной потоком A. Индекс совпадает с индексом ведра, рассчитанным по записи, которая будет вставлена потоком B, а затем, когда поток B успешно вставлен, когда поток A запланирован чтобы запустить снова, он все еще содержит заголовок связанного списка с истекшим сроком действия, но ничего о нем не знает. Настолько, что он думает, что должен это сделать, и, таким образом, перезаписывает запись, вставленную потоком B, так что запись, вставленная потоком B исчезает из ниоткуда, что приводит к непоследовательному поведению данных.
2. Еще одна очевидная проблема, небезопасная для потоков, заключается в том, что операция получения HashMap может вызвать бесконечный цикл (cpu100%) из-за изменения размера.Конкретный анализ выглядит следующим образом:
Следующий код является основным содержимым изменения размера:
Так реализован jdk7, а не jdk8.
// 这个方法的功能是将原来的记录重新计算在新桶的位置，然后迁移过去。
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;
}
}
}
多线程HashMap的resize
Мы предполагаем, что есть два потока, которым необходимо выполнить операцию изменения размера одновременно.Наше исходное количество сегментов равно 2, а количество записей равно 3. Нам нужно изменить размер сегментов до 4. Исходные записи: [3, A], [7, B], [ 5, C] в исходной карте мы обнаружили, что все эти три записи попали во вторую корзину. Предположим, что поток thread1 выполняет Entry next = e.next предложения метода transfer, а затем истекает квант времени, в это время e = [3,A], next = [7,B]. Поток thread2 запланирован для выполнения и успешно завершил операцию изменения размера.Следует отметить, что следующим из [7,B] в это время является [3,A]. В это время поток thread1 перепланируется для запуска, и ссылка, удерживаемая потоком1 в это время, является результатом после изменения размера потоком2. Поток thread1 сначала переносит [3,A] в новый массив, а затем обрабатывает [7,B], и [7,B] связывается с задней частью [3,A], после обработки [7,B] вы нужно иметь дело со следующим из [7,B], и после изменения размера thread2 следующий из [7,B] становится [3,A], в это время [3,A] и [7,B] Формируется циклический связанный список, и если во время get индекс сегмента ключа get совпадает с [3, A] и [7, B], он попадет в бесконечный цикл.
Если связный список берется с начала (сейчас он берется из хвоста), порядок между узлами может быть гарантирован, поэтому такой проблемы нет. Объединив два вышеуказанных момента, можно показать, что HashMap небезопасен для потоков.
3.2 Почему HashMap небезопасен? (версия jdk8)
В соответствии с вышеуказанными проблемами JDK1.7, они были хорошо решены в JDK1.8.Если вы прочитаете исходный код 1.8, вы обнаружите, что функция передачи не может быть найдена, потому что JDK1.8 непосредственно завершает перенос данных в функция изменения размера. . Кроме того, JDK1.8 использует метод вставки хвоста при вставке элементов.
Почему в JDK1.8 есть покрытие данных? Давайте посмотрим на код операции put в JDK1.8 ниже:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) // 如果没有hash碰撞则直接插入元素
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Шестая строка кода предназначена для определения наличия коллизии хэшей.Предполагая, что оба потока A и B выполняют операции размещения, а нижний индекс вставки, вычисленный хэш-функцией, одинаков, когда поток A завершает выполнение шестой строки кода. , из-за времени После того, как срез исчерпан, он приостанавливается, и поток B вставляет элемент в нижний индекс после получения среза времени, завершая обычную вставку, а затем поток A получает срез времени. столкновение было выполнено ранее, все в это время больше не принимается решение, но вставка выполняется напрямую, что приводит к тому, что данные, вставленные потоком B, перезаписываются потоком A, поэтому поток небезопасен.
В дополнение к этому, в строке 38 кода есть размер ++. Мы так думаем, что это все еще тени A и B. Когда эти два потока выполняют операции одновременно, предполагая, что размер зизок Текущий hashmap 10, когда нить при a выполняет 38-й строчку кода, она получает значение размера 10 из основной памяти и готовит к выполнению операции +1, но потому что временной среду исчерпан, он должен отказаться CPU. Thread b Счастливо получает процессор или принимает его из основной памяти к значению размера 10, выполняет операцию +1, выполните операцию поставки и записать размер = 11 обратно в основную память, затем поток A получает ЦП снова И продолжает выполнять (значение размера все еще 10 в настоящее время), когда операция поставлена после этого, размер = 11 все еще записан обратно в память. В это время оба потока A и B выполняют Операция, но значение размера увеличивается только на 1, поэтому говорят, что нить не безопасна из-за перезаписи данных.
Суммировать: Небезопасность потоков HashMap в основном отражается в следующих двух аспектах:
1. В JDK1.7, когда операция расширения выполняется одновременно, это вызовет циклическую цепочку и потерю данных.
2. В JDK1.8 покрытие данных происходит, когда операции размещения выполняются одновременно.