HashMap — одна из наиболее часто используемых структур данных Java-программистами. Кроме того, JDK1.8 оптимизирует базовую реализацию HashMap, например, введение структуры данных красно-черного дерева и оптимизацию расширения для повышения производительности. В этой статье объединен исходный код JDK1.8 для обсуждения реализации структуры и принципа действия HashMap.
UML-диаграмма HashMap
UML-диаграмма HashMap
Переменные-члены HashMap и их значения
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
/**
* HashMap的默认初始化大小为16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* HashMap的最大容量。
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 负载因子的大小，一般HashMap的扩容的临界点是当前HashMap的大小 > DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 这是JDK1.8在底层做的一个优化，当一个Entry挂载的节点超过8个，就会将当前Entry的链表结构转化为红黑树的数据结构
*/
static final int TREEIFY_THRESHOLD = 8;
/**
*
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 红黑树的最大节点数
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* 是hash表中，Entry的节点.
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
/* ---------------- Static utilities -------------- */
/**
* 计算key的hash值。
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* 这个方法时HashMap中比较实用的方法，用于计算传入值的2倍，也算是JDK源码部分的最佳实践。
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
/* ---------------- Fields -------------- */
/**
* hash表
*/
transient Node<K,V>[] table;
/**
* 保存缓存的entrySet。
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* map中键值对的数量。
*/
transient int size;
/**
*
* 这个HashMap被结构修改的次数结构修改是那些改变HashMap中的映射数量或者修改其内部结构（例如，重新散列）的修改。 该字段用于在HashMap失败快速的Collection-views上创建迭代器。
*/
transient int modCount;
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
int threshold;
/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
}
Расскажите о реализации основного метода HashMap
Внутренняя реализация
Чтобы разобраться в HashMap, нужно, во-первых, узнать, что такое HashMap, то есть его структуру-поле хранения; во-вторых, разобраться, что он может делать, то есть его функцию-метод реализации. Ниже мы подробно объясним эти два аспекта.
Структура хранилища — поля
С точки зрения структурной реализации HashMap реализуется массивом + связанным списком + красно-черным деревом (JDK1.8 добавляет красно-черную часть дерева), как показано ниже.
Диаграмма структуры памяти Hashmap
Здесь необходимо уточнить два вопроса: какое основное хранение данных? Каковы преимущества этого метода хранения?
(1) Из исходного кода в классе HashMap есть очень важное поле, которое представляет собой таблицу Node[], которая представляет собой массив хэш-сегментов, который, очевидно, является массивом узлов. Давайте посмотрим, что такое Node [JDK1.8].
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //用来定位数组索引位置
final K key;
V value;
Node<K,V> next; //链表的下一个node
Node(int hash, K key, V value, Node<K,V> next) { ... }
public final K getKey(){ ... }
public final V getValue() { ... }
public final String toString() { ... }
public final int hashCode() { ... }
public final V setValue(V newValue) { ... }
public final boolean equals(Object o) { ... }
}
Node — это внутренний класс HashMap, который реализует интерфейс Map.Entry, который по сути является картой (пара ключ-значение). Каждая черная точка на изображении выше — это объект Node.
(2) HashMap хранится с использованием хеш-таблицы. Чтобы решить конфликт в хэш-таблице, можно использовать метод открытого адреса и метод цепного адреса.HashMap в Java использует метод цепного адреса. Проще говоря, метод цепных адресов представляет собой комбинацию массива и связанного списка. Для каждого элемента массива существует структура связанного списка.При хэшировании данных получается индекс массива, и данные помещаются в связанный список, соответствующий элементу индекса. Например, программа выполняет следующий код:
map.put("name","makefeixiang");
Система вызовет метод hashCode() ключа «имя», чтобы получить его значение hashCode (этот метод применим к каждому объекту Java), а затем определит место хранения пары ключ-значение с помощью последних двух шагов Алгоритм хеширования.Каждый ключ будет находиться в одной и той же позиции, указывая на то, что произошла коллизия хэшей. Разумеется, чем однороднее результаты вычислений алгоритма Hash, тем меньше вероятность Hash-коллизии и выше эффективность доступа к карте.
/**
* 计算key的hash值。
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Конечно, если массив массива хэш-сегментов большой, даже плохой алгоритм хеширования будет разбросан и будет давать лучшие результаты. Однако, если массив массива хэш-сегментов мал, даже хороший алгоритм хеширования будет иметь больше хэш-коллизий. необходимо, чтобы сбалансировать стоимость пространства и стоимость времени.На самом деле размер массива хеш-багет определяется в соответствии с реальной ситуацией, и алгоритм хеширования разработан на этой основе для уменьшения хеш-коллизий. Так как же управлять картой, чтобы вероятность Hash-коллизии была небольшой, а массив хеш-баг (таблица Node[]) занимал меньше места? Ответ — хороший алгоритм хеширования и механизм расширения.
Механизм расширения HashMap через порог =
длина * Коэффициент нагрузки для принятия решения о расширении. Другими словами, после определения длины массива, чем больше коэффициент загрузки, тем больше пар ключ-значение он может содержать. Конечно, коэффициент загрузки не настолько велик, насколько это возможно. Разработчики JDK дали относительно сбалансированное решение. Коэффициент загрузки — это коэффициент загрузки (значение по умолчанию — 0,75), как правило, мы не изменяем этот параметр.
Реализация функции - метод
Есть много внутренних функций HashMap.В этой статье в основном выбраны несколько репрезентативных моментов, таких как получение индекса массива HashMap в соответствии с ключом, выполнение метода put, расширение емкости и получение значения ключа, соответствующего HashMap.
1. Определите позицию индекса массива хэш-баг.
Будь то добавление, удаление или поиск пар ключ-значение, поиск индекса массива хэш-контейнеров является важным первым шагом. Структура данных HashMap представляет собой комбинацию массива и связанного списка или красно-черного дерева, поэтому мы надеемся, что позиции элементов в этой HashMap распределены максимально равномерно, чтобы количество элементов в каждой позиции было только один, затем, когда мы используем хэш-алгоритм для получения значения этой позиции. Когда возникает запрос, его можно найти сразу, без обхода связанного списка, а временная сложность запроса составляет всего O (n). Давайте посмотрим на реализацию исходного кода:
// 方法1，代码段1
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 当我们使用hash时，代码段2
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
Алгоритм хеширования здесь состоит из трех шагов:Возьмите значение hashCode ключа, операцию высокого порядка и операцию по модулю.
2. Проанализируйте метод put HashMap
① Определите, является ли таблица массива пар ключ-значение [i] пустой или нулевой, в противном случае выполните resize() для расширения;
②. Вычислите хеш-значение в соответствии с ключом значения ключа, чтобы получить вставленный индекс массива i, если таблица [i] == null, непосредственно создайте новый узел для добавления, перейдите к ⑥, если таблица [i] не пуста, перейти к ③;
③.Определить, является ли первый элемент таблицы[i] таким же, как ключ, если он напрямую перезаписывает значение, в противном случае перейдите к ④, здесь то же самое относится к hashCode и равно;
④ Определите, является ли table[i] treeNode, то есть является ли table[i] красно-черным деревом, если это красно-черное дерево, вставьте пару ключ-значение непосредственно в дерево, в противном случае перейдите к ⑤;
⑤. Просмотрите таблицу [i], чтобы определить, больше ли длина связанного списка 8. Если она больше 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;
// 步骤①：tab为空则创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步骤②：计算index，并对null做处理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 步骤③：节点key存在，直接覆盖value
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);
//链表长度大于8转换为红黑树进行处理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// key已经存在直接覆盖value
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;
}
3. Реализация механизма расширения
Изменение размера заключается в пересчете емкости и непрерывном добавлении элементов в объект HashMap.Когда длина массива внутри объекта HashMap больше, чем DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY, HashMap необходимо увеличить длину массива, чтобы вместить больше элементов. Метод заключается в использовании нового массива для замены существующего массива меньшей емкости.
Разберем исходный код ресайза.Ввиду того, что JDK1.8 интегрирован в красно-черное дерево, он сложнее.Для облегчения понимания все же используем код JDK1.7, который проще чтобы понять.Разницы по сути мало.Конкретная разница будет рассмотрена позже.
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 超过最大值就不再扩充了
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 没超过最大值，就扩充为原来的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 把每个bucket都移动到新的buckets中
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 { // 链表优化重hash的代码块
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
4. Реализация кода для получения значения по ключу в HashMap
По сравнению с вышеизложенным, получить значение в HashMap относительно просто.Основная логика состоит в том, чтобы вычислить значение хеш-функции и найти индекс хэш-сегмента в соответствии с ключом.Когда это может быть значение текущего индекса, он напрямую возвращает соответствующее значение, и наоборот.Используйте ключ для обхода ключа под равным индексом, пока не будет найдена позиция.
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;
}
Потокобезопасность HashMap
В многопоточных сценариях использования следует стараться не использовать потокобезопасный HashMap, а вместо этого использовать потокобезопасный ConcurrentHashMap. Так в чем же заключается небезопасная для потоков природа HashMap? Давайте проанализируем проблему, заключающуюся в том, что использование HashMap в параллельных сценариях может привести к бесконечному циклу. В методе изменения размера HashMap мы видим
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
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);
Из-за отсутствия таланта и знаний арендодателя, конкретный процесс не в анализе.Если вы хотите узнать больше, пожалуйста, перейдитеВакцины: бесконечный цикл JAVA HASHMAP
резюме
(1) Расширение — это особенно ресурсоемкая операция, поэтому задайте значение при инициализации HashMap, чтобы избежать частого расширения карты.
(2) Коэффициент нагрузки можно изменить, но в целом не рекомендуется изменять его легко.
(3) HashMap небезопасен для потоков. Не используйте HashMap в параллельной среде. Рекомендуется использовать ConcurrentHashMap или Collections.synchronizedMap().
(4) Введение красно-черного дерева в JDK1.8 значительно оптимизировало производительность HashMap.