I. Обзор
HashMap — это класс коллекции, с которым мы сталкиваемся очень часто и который очень важен в программировании.Очень ценно, если мы сможем дополнительно оптимизировать производительность HashMap, и JDK 1.8 сделал это, поэтому очень важно изучить ключевой исходный код HashMap. и понять основной метод.
Во-вторых, базовая структура данных
Так почему бы не заменить все связанные списки бинарными деревьями? Здесь есть два основных аспекта.
-
Во-первых, структура связного списка проще, чем у красно-черного дерева, а построение красно-черного дерева сложнее, чем построение связанного списка, поэтому при небольшом количестве узлов в связанный список, с точки зрения общей производительности, Структура массив + связанный список + красно-черное дерево не обязательно выше, чем структура массив + связанный список.
-
Второе — это частый ресайз (расширение) HashMap, при расширении индекс позиции узла нужно пересчитывать, то есть красно-черное дерево будет расщеплено и реорганизовано. Это очень сложно.Включает в себя раскрашивание и вращение красно-черного дерева.Если интересно,можете посмотреть на принцип красно-черного дерева.Это еще одна трудоемкая операция,чем структура связанного списка,поэтому установить порог для дерева связанных списков.Очень необходимо.
3. Анализ исходного кода
3.1 Структура класса
3.2 Аннотации классов
Я предлагаю вам посмотреть на аннотации классов при чтении исходного кода.Часто аннотации классов дают нам некоторую важную информацию.Здесь LZ резюмирует ее для вас.
(1) Разрешить значения NULL, ключи NULL
(2) Не изменяйте коэффициент загрузки легко. Если коэффициент загрузки слишком высок, связанный список будет слишком длинным, и временная сложность поиска пар ключ-значение увеличится. Если коэффициент загрузки слишком низок, число хеш-баг увеличится, а сложность пространства увеличится.
(3) Хеш-таблица будет расширяться в два раза дольше, чем раньше.
(4) HashMap небезопасен для многопоточности.Я выполняю многопоточную операцию ввода в JDK 1.7, а затем прохожу ее, прямо в бесконечном цикле, процессор взлетает до 100%, а многопоточная операция в JDK 1.8 будет привести к потере узла и значения. , почему многопоточная работа JDK1.7 и JDK1.8 сильно отличается, потому что автор JDK 1.8 оптимизировал метод изменения размера и не будет генерировать замкнутый цикл связанного списка. Это также является одним из основных направлений этой главы, и вы можете обратиться к информации для получения более подробной информации. Я не буду объяснять слишком много здесь
(5) Попробуйте установить начальную емкость HashMap, особенно при большом объеме данных, чтобы предотвратить многократное изменение размера.
3.3 Константы класса
//默认hash桶初始长度16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//hash表最大容量2的30次幂
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认负载因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表的数量大于等于8个并且桶的数量大于等于64时链表树化
static final int TREEIFY_THRESHOLD = 8;
//hash表某个节点链表的数量小于等于6时树拆分
static final int UNTREEIFY_THRESHOLD = 6;
//树化时最小桶的数量
static final int MIN_TREEIFY_CAPACITY = 64;
3.4 Переменные экземпляра
//hash桶
transient Node<K,V>[] table;
//键值对的数量
transient int size;
//HashMap结构修改的次数
transient int modCount;
//扩容的阀值，当键值对的数量超过这个阀值会产生扩容
int threshold;
//负载因子
final float loadFactor;
3.5 Конструкторы
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;
//下面介绍一下这行代码的作用
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
HashMap имеет 4 конструктора.
Хэш-сегмент не инициализируется в конструкторе, но инициализируется при первом сохранении пары ключ-значение. Сосредоточьтесь здесь Метод tableSizeFor(initialCapacity), функция этого метода состоит в том, чтобы вычислить переданное вами значение initialCapacity и вернуть значение, большее или равное InitialCapacity. Наименьшая степень числа 2.
Таким образом, эта операция гарантирует, что независимо от того, какой параметр длины инициализированного сегмента хэша вы передаете, длина окончательной инициализации хеш-таблицы является степенью двойки. Например, если вы введете 6, расчетный результат будет равен 8.
Исходный код размещен ниже.
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;
}
3.6 Вставка
public V put(K key, V value) {
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;
//当table为空时，这里初始化table，不是通过构造函数初始化，而是在插入时通过扩容初始化，有效防止了初始化HashMap没有数据插入造成空间浪费可能造成内存泄露的情况
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//存放新键值对
if ((p = tab[i = (n - 1) & hash]) == null)
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);
//当链表的长度大于等于树化阀值，并且hash桶的长度大于等于MIN_TREEIFY_CAPACITY，链表转化为红黑树
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;
}
}
//map中含有旧key，返回旧值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//map调整次数加1
++modCount;
//键值对的数量达到阈值需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Вставка HashMap похожа на то, что мы обычно чувствуем при ее использовании.Подведем итоги ниже.
(1) Вставленная пара ключ-значение является новой парой ключ-значение. Если хеш-таблица не инициализирована, она будет инициализирована. В противном случае пара ключ-значение будет вставлена в конец связанного списка, что может требуют древовидной структуры связанного списка и Расширение
(2) Ключ во вставленной паре ключ-значение уже существует. Чтобы обновить пару ключ-значение, следует обратить внимание на метод hash(key) в методе put.Это метод вычисления хеш-значения пара ключ-значение.Исходный код приведен ниже.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hashCode() - это собственный метод типа int, который заключается в беззнаковом сдвиге вправо хэш-кода ключа на 16 бит, а затем XOR с хэш-кодом для получения хеш-значения.В методе putVal (n - 1) & hash вычисляет положение индекса ведра, Итак, теперь есть два вопроса, зачем вычислять значение хеш-функции? Почему бы не использовать хэш %n?
-
Зачем вычислять значение хеша вместо hashCode?Обычно n очень мало, а hashCode 32 бита.Если (n - 1) & hashCode, то когда n больше 2 в 16-й степени, прибавляем 1, то есть после 65537 ( Данные старшего порядка n - 1) можно сравнить с данными старшего порядка hashCode. Когда n мало, можно использовать только меньший hashCode. 16-битных данных, это вызовет проблему, т. е. пары ключ-значение неравномерно распределены в хэш-базе, что приводит к чрезмерно длинному связанному списку. Старшие 16 бит косвенно и (n - 1) участвуют в вычислении, так что пары ключ-значение распределяются равномерно. Уменьшите коллизии хэшей.
-
Зачем использовать (n - 1) & hash вместо hash% n? На самом деле эти два результата эквивалентны, но эффективность & выше, чем у %, потому что операция & - это два База управляется напрямую, а компьютер создан для распознавания двоичного кода. Ниже приведен рисунок для иллюстрации
3.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;
//如果旧hash桶不为空
if (oldCap > 0) {
//超过hash桶的最大长度，将阀值设为最大值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//新的hash桶的长度2被扩容没有超过最大长度，将新容量阀值扩容为以前的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//如果hash表阈值已经初始化过
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//如果旧hash桶，并且hash桶容量阈值没有初始化，那么需要初始化新的hash桶的容量和新容量阀值
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//新的局部变量阀值赋值
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"})
//初始化hash桶
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//如果旧的hash桶不为空，需要将旧的hash表里的键值对重新映射到新的hash桶中
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 {
//如果是多个节点的链表，将原链表拆分为两个链表，两个链表的索引位置，一个为原索引，一个为原索引加上旧Hash桶长度的偏移量
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//链表1
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//链表2
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//链表1存于原索引
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//链表2存于原索引加上原hash桶长度的偏移量
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
Так когда вернётся расширение?
(1) При инициализации HashMap выполняется первая операция размещения
(2) Когда количество пар ключ-значение превышает пороговое значение, происходит расширение емкости, порог=размер*коэффициент нагрузки.
Выше приведен исходный код расширения HashMap, я добавил комментарии, думаю, всем понятно. Подводя итог, расширение HaspMap заключается в том, чтобы сначала вычислить Емкость новой хэш-таблицы и новое пороговое значение емкости, затем инициализируйте новую хэш-таблицу и переназначьте старые пары ключ-значение в новой хэш-таблице. Детали реализации здесь конечно Все не так просто, как я сказал: если красно-черное дерево участвует в старой хэш-таблице, то разбиение красно-черного дерева также участвует в отображении на новую хеш-таблицу.
В исходниках расширения у автора очень умное использование, то есть распределение пар ключ-значение более равномерное, не знаю, увидят ли это читатели. При обходе исходного хеш-ковша В случае связанного списка, поскольку длина расширенной хэш-таблицы в два раза превышает длину исходной хэш-таблицы, предполагается, что расширенная хэш-таблица разделена на две половины, которые разделены на младшие и высокие позиции. пары ключ-значение исходного связанного списка можно разделить на Половина в низком порядке и половина в высоком порядке, эта эффективность индексации является самой высокой. Тогда посмотрите, как это написано в исходном коде. Мастер судит по e.hash и oldCap == 0, В чем разница между этим и e.hash & (oldCap - 1). Позвольте мне объяснить это, нарисовав картинку.
На самом деле основное содержание HashMap в основном закончено, и я думаю, что у каждого есть определенное представление об исходном коде HashMap. В исходном коде запрос и удаление пар ключ-значение относительно просты, поэтому я не буду здесь вдаваться в подробности.Что касается построения, поворота и раскраски красно-черного дерева, думаю всем интересно и можно узнать об этом. Ведь мы не Он разработчик HashMap, поэтому ему не нужно знать слишком много деталей и углубляться в угол. Просто знайте общий принцип.
3.8 Очистить
На этом он подходит к концу, но LZ все еще хочет поговорить с вами об общем методе clear() HashMap и вставить исходный код ниже.
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
HashMap на самом деле очень простой, зачем вы его выложили, потому что у меня были вопросы в других блогах, очищать его или создавать новый. HashMap — это хорошо. Я думаю, что clear() лучше, чем создание нового HashMap. Пространственная сложность и временная сложность объясняются ниже.
С точки зрения времени этот цикл очень прост, не имеет сложной логики и не очень ресурсоемок. Для создания нового HashMap, в первую очередь, он проверяет, достаточно ли места в молодом поколении для хранения в памяти кучи. молодому поколению трудно иметь достаточно места для хранения.Если в возрасте достаточно места для хранения этой HashMap, то JVM будет напрямую хранить HashMap в старости.Если в старости недостаточно места, в это время сработает minor gc, что вызовет паузу мелкомасштабного gc.HashMap нельзя хранить, тогда будет происходить gc всей кучи, т.е. полный сборщик мусора, эта пауза сбора мусора ужасна. Фактический порядок gc таков, и может возникнуть несколько второстепенных gc и полных gc, если будут обнаружены молодое поколение и старое поколение. HashMap не может быть сохранен, тогда будет запущен OOM, а clear() точно не вызовет OOM, поэтому, когда данные особенно велики, не создавайте Новый HashMap заменяет метод clear().
С пространственной точки зрения, хотя исходный HashMap не используется, если данные не очищены, они не могут быть повторно использованы JVM, поскольку HashMap является строго ссылочным типом, что приводит к утечкам памяти. Итак, в целом я Не рекомендуется создавать новый HashMap вместо clear(), и метод clear() очень распространен во многих исходных кодах, что является лучшим доказательством.
4. Резюме
(1) HashMap допускает значения NULL, ключи NULL
(2) Не изменяйте коэффициент загрузки легко. Если коэффициент загрузки слишком высок, связанный список будет слишком длинным, и временная сложность поиска пар ключ-значение увеличится. Если коэффициент загрузки слишком низок, число хеш-баг увеличится, а сложность пространства увеличится.
(3) Хеш-таблица будет расширяться в два раза дольше, чем раньше.
(4) HashMap не безопасен для многопоточности, я выполнил многопоточную операцию put в JDK 1.7, а потом прошел ее напрямую, и процессор взлетел до 100%.В JDK 1.8 Узел и значение значения будут потеряны в многопоточной операции.Почему многопоточная операция JDK1.7 и JDK1.8 сильно отличается, потому что автор JDK 1.8 изменяет размер Метод оптимизирован, чтобы не создавать замкнутый цикл связанного списка. Это также является одним из основных направлений этой главы, и вы можете обратиться к информации для получения более подробной информации. Я не буду объяснять слишком много здесь
(5) Попробуйте установить начальную емкость HashMap, особенно при большом объеме данных, чтобы предотвратить многократное изменение размера.
(6) HashMap значительно улучшил производительность в JDK 1.8.Я видел, что в JDK1.7 и JDK1.8 производительность операции get лучше, чем в JDK1.8 по сравнению с JDK 1.7, Если вам интересно, вы можете сделать тест самостоятельно, так что те, кто еще не обновился до JDK1.8, поторопитесь.
Таким образом, аннотации классов перемещены.На самом деле, в этой статье есть точка знаний, которая не была подробно проанализирована, что является причиной того, что HashMap небезопасен в многопоточности, особенно при расширении JDK 1.7 будет генерировать замкнутый цикл связанного списка, т.к. мне нужно рисовать много картинок, не нашел подходящего инструмента, добавлю позже.