В этой статье будет проанализирован процесс изменения внутренней структуры данных HashMap с помощью следующего простого кода.
public static void main(String[] args) {
Map<String, String> map = new HashMap<>();
for (int i = 0; i < 50; i++) {
map.put("key" + i, "value" + i);
}
}
1 Описание структуры данных
Поля в HashMap, которые необходимо использовать в этой статье, следующие:
Ниже описано значение нескольких полей
1) таблица
// HashMap内部使用这个数组存储所有键值对
transient Node<K,V>[] table;
Структура узла выглядит следующим образом:
2) размер
Записывает количество пар ключ-значение в HashMap.
3) количество модов
Записывает количество структурных изменений HashMap, включая операции, которые могут изменить количество пар ключ-значение, такие как вставка, удаление, и операции, которые могут изменить внутреннюю структуру, например перефразирование.
4) порог
Запишите критическое значение. Если количество сохраненных пар "ключ-значение" превышает это критическое значение, требуется расширение.
5) коэффициент нагрузки
Коэффициент нагрузки, обычно используемый для расчета порога, порог=общая мощность*коэффициент нагрузки.
2.new HashMap
Исходный код нового HashMap выглядит следующим образом:
/**
* The load factor used when none specified in constructor.
* 负载因子，当 已使用容量 > 总容量 * 负载因子 时，需要扩容
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
На этом этапе HashMap только инициализирует коэффициент загрузки (используя значение по умолчанию 0,75) и не инициализирует массив таблиц. На самом деле HashMap использует стратегию отложенной инициализации, когда он ставится в первый раз, таблица инициализируется (таблица в это время пустая).
3. Инициализация табличного массива
При первой установке HashMap определит, пуста ли текущая таблица, и если она пуста, вызовет метод изменения размера для инициализации. Метод resize инициализирует массив емкостью 16 и присваивает его таблице. И вычислить порог = 16 * 0,75 = 12. Состояние табличного массива в этот момент следующее:
4. поставить процесс
map.put("key0", "value0");
Сначала вычислите хэш-значение ключа, хэш("key0") = 3288451 Вычислите значение индекса, которое будет храниться в позиции массива для этого пута: index=(размер массива - 1) & hash = 3 Судя по тому, если (table[index] == null), здесь размещается новый Node, который на данный момент равен null, поэтому новый Node размещается непосредственно на 3. В это время таблица выглядит следующим образом:
Продолжайте ставить. . .
map.put("key1", "value1");
map.put("key1", "value1");
map.put("key2", "value2");
map.put("key3", "value3");
map.put("key4", "value4");
map.put("key5", "value5");
map.put("key6", "value6");
map.put("key8", "value7");
map.put("key9", "value9");
map.put("key10", "value10");
map.put("key11", "value11");
map.put("key12", "value12");
Вычислите хэш-значение ключа, хеш ("key12") = 101945043, вычислите значение индекса, которое будет храниться в таблице position = (общий размер - 1) и хэш = (16 - 1) и 101945043 = 3 Из текущего состояния таблицы видно, что table[3] != null, но ключ, который нужно поставить, не равен table[3].key в этот момент, мы должны его сохранить, и в этот момент происходит конфликт хэшей время (ха греческое столкновение).
В это время пригодится связанный список, и HashMap решает конфликт хэшей через связанный список. HashMap создаст новый узел и поместит его в конец связанного списка table[3]. На данный момент состояние таблицы следующее:
5. Изменение размера расширения
На данный момент в таблице всего 13 элементов, что превышает пороговое значение (12), и необходимо вызвать метод изменения размера для расширения таблицы. HashMap создаст двойную емкость (162=32) и скопируйте старый узел в новую таблицу, новый порог (порог) равен 24 (320,75).
Далее в основном представлен процесс репликации (это не неповрежденная репликация, расположение узла может измениться)
Сначала посмотрите на исходный код:
for (int j = 0; j < oldCap; ++j) { // oldCap：旧table的大小 =16
Node<K,V> e;
if ((e = oldTab[j]) != null) { // oldTab：旧table的备份
oldTab[j] = null;
// 如果数组中的元素没有后继节点，直接计算新的索引值，并将Node放到新数组中
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 忽略这个else if。其实，如果链表的长度超过8，HashMap会把这个链表变成一个树结构，树结构中的元素是TreeNode
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;
// 【说明1】
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;
//【说明2】
newTab[j + oldCap] = hiHead;
}
}
}
}
[Описание 1] Просмотрите связанный список и вычислите положение каждого узла связанного списка в новой таблице.
Позиция рассчитывается следующим образом:
1) Если узел (хэш и oldCap) == 0, то узел все еще находится в исходном положении, почему?
Поскольку oldCap=16, двоичное представление равно 0001 0000, любое число & 16, если оно равно 0, то пятая двоичная цифра этого числа должна быть 0.
В текущем состоянии новая емкость равна 32, тогда максимальный индекс таблицы равен 31, а двоичное представление 31 — 00011111. Способ расчета индекса — хэш & (capacity — 1), то есть метод расчета нового индекса — хеш & (32 — 1) Предполагая, что хэш узла = 01101011, тогда
01101011
& 00011111
----------
00001011 = 11
2) Затем сравните случай (хэш и oldCap) != 0
Если узел (хэш и oldCap) != 0, то позиция узла = старый индекс + старый размер емкости
Предполагая, что хэш узла = 01111011, тогда
01111011
& 00011111
----------
00011011 = 27
Хэш-значение 01101011 предыдущего примера и хэш-значение 01111011 этого примера отличаются только в 5-битном двоичном файле.Можно обнаружить, что эти два значения находятся в одном и том же индексе в старой таблице, как показано ниже:
01101011
& 00001111
----------
00001011 = 11
01111011
& 00001111
----------
00001011 = 11
Так как расширение всегда делается 2-кратным способом, то есть: старая емкость
После расширения статус таблицы следующий:
Добро пожаловать в мой публичный аккаунт WeChat