Можно сказать, что HashMap является наиболее часто используемой структурой данных для обработки сопоставления ключ-значение.Она не гарантирует порядок вставки и позволяет вставлять нулевые ключи и значения. В этой статье используется исходный код JDK8 для глубокого анализа принципа, реализации и оптимизации HashMap. Впервые опубликовано в публичном аккаунте WeChatИсходный код Крещения.
1. Базовая структура
HashMap реализован на основе хеш-таблицы с использованиеммолния методОбработка коллизий, в JDK8, когда длина связанного списка больше 8, он преобразуется вкрасно-черное деревоХранение, основная структура выглядит следующим образом:
В HashMap есть поле таблицы Node
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) { ... }
...
}
Массив хеш-контейнеров инициализируется при первом использовании, имеет размер по умолчанию 16 и изменяется по мере необходимости, а длина всегда является степенью двойки. Если исходная емкость, заданная конструктором, не является степенью числа 2, используйте следующий метод, чтобы вернутьбольше и ближе всегоЕго значение степени двойки:
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;
}
Принцип состоит в том, чтобы установить все биты справа от старшего бита от 1 до 1, затем добавить 1, старший бит продвигается к 1, а все биты справа становятся 0, таким образом получая значение степени 2. . В JDK7 используется метод Integer.highestOneBit(int i), который использует n - (n >>> 1) в последнем вычислении и возвращаетменьше и ближе всегоСтепень 2 для входного параметра.
Другие поля внутри HashMap:
// 键值对的数量
transient int size;
// 记录结构修改次数，用于迭代时的快速失败
transient int modCount;
// 负载因子，默认 0.75f
final float loadFactor;
// 扩容的下一个容量值，也就是键值对个数的最大值，它等于(capacity * loadFactor)
int threshold;
Основные параметры, влияющие на производительность HashMap:начальная мощностьикоэффициент нагрузки. Когда количество элементов в хеш-таблице превышает произведение коэффициента загрузки и текущей емкости, она расширяется до исходной емкости.двойной, и перефразирует ключ.
- Если начальная емкость слишком мала, расширение и повторная обработка будут запускаться много раз, поэтому эффективнее предварительно выделить достаточно большую емкость.
- Значение коэффициента загрузки по умолчанию — 0,75 f, что является хорошим балансом между затратами времени и места и, как правило, не требует изменения. Чем выше значение, тем меньше накладных расходов на пространство, но увеличивается стоимость поиска.
Каким бы разумным ни был алгоритм хеширования, связанный список неизбежно будет слишком длинным, что повлияет на производительность HashMap, поэтому, когда длина связанного списка больше 8, JDK8 преобразует его в красно- черное дерево, чтобы использовать красно-черное дерево для быстрого добавления, удаления, изменения и проверки.
2. Хеш-функция
Наиболее распространенный способ хэширования целого числаостаточный метод. Для равномерного хеширования хеш-значений ключей размер массива обычно берется равнымпростое число(Исходный размер HashTable равен 11), потому что множители простых чисел малы, вероятность равных остатков мала, и вероятность конфликта мала.
Емкость HashMap всегда является степенью двойки, т.е.Составное число, причиной этого дизайна является преобразование операции по модулю в битовую операцию для повышения производительности. это уравнениеh % length = h & (length-1)Причины его создания следующие:
2^1 = 10 2^1 -1 = 01
2^2 = 100 2^2 -1 = 011
2^3 = 1000 2^3 -1 = 0111
2^n = 1(n个零) 2^n -1 = 0(n个1)
Правая часть — это бинарная характеристика 2 ^ n, а левая — характеристика 2 ^ n — 1. Можно обнаружить, что когда длина = 2 ^ n, результат h & (длина — 1) точно равен между 0 и length-1, что эквивалентно операции по модулю.
После преобразования в битовую операцию длина-1 эквивалентнамладшая битовая маска, при побитовом И оно будет равно 0 старшему положению исходного хеш-значения, что приводит к тому, что хеш-значение изменяется только в небольшом диапазоне маски, что, очевидно, увеличивает вероятность коллизии. Чтобы уменьшить коллизии, HashMap используетвысокий-низкий XOR, в замаскированном виде в операции участвуют и старшие биты ключа.Код выглядит следующим образом:
static final int hash(Object key) { // JDK8
int h;
// h = key.hashCode() 1. 取hashCode值
// h ^ (h >>> 16) 2. 高16位与低16位异或，变相保留高位的比特位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// JDK7 的源码，JDK8 没有这个方法，但原理一样
static int indexFor(int h, int length) {
return h & (length-1); // 3. 取模运算
}
Исключающее ИЛИ с высоким битовым сдвигом может не только обеспечить эффективное использование старшей и младшей битовой информации ключа, но и снизить нагрузку на систему.Этот дизайн представляет собой компромисс между скоростью, эффективностью и качеством.
3. поставить операцию
Операция put в основном выполняет следующие действия:
- Когда таблица массива хеш-контейнеров пуста, она инициализируется методом resize().
- Вставляемый ключ уже существует, напрямую перезапишите значение
- Если он не существует, вставьте пару ключ-значение в соответствующий связанный список или красно-черное дерево.
- При вставке связанного списка определите, нужно ли преобразовывать в красно-черное дерево
- Определите, требуется ли расширение
Основной код выглядит следующим образом:
public V put(K key, V value) {
// 将 key 的 hashCode 散列
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1. table 为 null，初始化哈希桶数组
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2. 计算对应的数组下标 (n - 1) & hash
if ((p = tab[i = (n - 1) & hash]) == null)
// 3. 这个槽还没有插入过数据，直接插入
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 4. 节点 key 存在，直接覆盖 value
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 5. 该链转成了红黑树
else if (p instanceof TreeNode) // 在树中插入
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 6. 该链是链表
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;
// 7. 超过最大容量，扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
JDK8 использует метод вставки конца при вставке в связанный список, то есть последовательную вставку, в то время как JDK7 использует метод вставки начала, который вставляется в обратном порядке.
6. Механизм расширения
По умолчанию начальная емкость равна 16, коэффициент загрузки — 0,75f, а порог — 12, что означает, что емкость будет расширена за счет вставки 12 пар ключ-значение.
При расширении он увеличится в два раза по сравнению с исходным размером, потому чторасширение степени 2, то положение элемента либо остается прежним, либо смещается на степень 2 от исходного положения.
Как видно из приведенного выше рисунка, расширение в 2 раза эквивалентно сдвигу n влево на один бит, тогда в старшей позиции n-1 есть лишняя 1. В это время операция И с исходным значение хеш-функции будет участвовать еще в одном бите, эти биты равны либо 0, либо 1:
- Если 0, индекс не меняется
- 1, тогда индекс становится "исходный индекс + oldCap"
Итак, как определить, равен ли этот бит 0 или 1? Если значение «исходное хеш-значение и oldCap» равно 0, это означает, что бит равен 0. Код расширения выглядит следующим образом:
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
// 初始化时，threshold 暂时保存 initialCapacity 参数的值
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) {
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
// 拆链表，拆成两个子链表并保持原有顺序
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);
// 放到新的哈希桶中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
При пересчете позиции элемента в связанном списке можно получить толькодва подсписка: связанный список элементов с постоянным индексом и связанный список элементов с одинаковым смещением. В процессе построения подсвязного списка головной узел и хвостовой узел используются для обеспечения упорядочения после разбиения:
Глядя на метод TreeNode.split(), обнаруживается, что логика разбиения красно-черного дерева такая же, как и у связанного списка, за исключением того, что после завершения разбиения будет выполняться следующая обработка в соответствии с длиной из подчиненного списка:
- Если длина меньше 6, вернуть обычный связанный список, не содержащий TreeNode.
- В противном случае преобразовать подссылочный список в красно-черное дерево.
Причина, по которой красно-черное дерево может быть разбито по логике связанного списка, заключается в том, что при преобразовании связанного списка в красно-черное дерево ссылка на цепочку исходного связанного списка сохраняется, что также удобно.траверсработать.
7. Связанный список с красно-черным деревом
Связанный список с красно-черным деревом в основном выполняет следующие действия:
- Определить, соответствует ли вместимость ковша минимальным требованиям для формирования дерева, в противном случае расширить вместимость
- Преобразование исходного связанного списка в двусвязный список, состоящий из TreeNodes
- Преобразуйте новый связанный список в красно-черное дерево
код показывает, как показано ниже:
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 如果哈希桶容量小于树化的最小容量，优先进行扩容
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); // 将链表转为红黑树
}
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
Дизайн HashMap не должен предусматривать введение красно-черных деревьев позже, поэтому он не предоставляет компаратор ключей или требует ключ для реализации интерфейса Comparable. Чтобы сравнить размер двух ключей, HashMap обрабатывается следующим образом:
- Если хэш-значения двух ключей не равны, сравните размер хэш-значений
- При равенстве, если ключ реализует интерфейс Comparable, используйте метод compareTo для сравнения
- Если результаты по-прежнему равны, используйте пользовательский метод tieBreakOrder для сравнения, логика следующая.
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null || // 比较 className 的大小
(d = a.getClass().getName().compareTo(b.getClass().getName())) == 0)
// 比较由本地方法生成的 hash 值大小，仍然有可能冲突，几率太小，此时认为是小于的结果
d = (System.identityHashCode(a) <= System.identityHashCode(b) ? -1 : 1);
return d;
}
8. Резюме
Код HashMap в JDK8 все еще относительно сложен, и есть три основных аспекта оптимизации:
- Оптимизируйте алгоритм хэширования для выполнения только одной операции смещения.
- Введение красно-черных деревьев снижает временную сложность операций get с O(n) до O(logn) в случае серьезных конфликтов.
- При расширении используются бинарные характеристики степени двойки, что не только экономит время на пересчет хэша, но и хэширует ранее конфликтующие узлы в другие места.
Кроме того, HashMapНе потокобезопасныйДа, между нитямисостояние гонкиВ основном это отключение и продолжение связанного списка при возникновении конфликта или расширения. Расширение также означает копирование памяти, что является очень ресурсоемкой операцией, поэтому предварительное выделение достаточно большой начальной емкости для уменьшения количества расширений может повысить производительность HashMap.
Поиск в общедоступной учетной записи WeChat "Исходный код Крещения” для более подробного анализа исходного кода и создания колес.