Предупреждение от HashMap: Это 56-я статья рубрики «Путь к продвинутым программистам Java». В тот день Сяо Эр подошел ко мне с удрученным выражением лица: «Фараон, младший Сяо Мо спросил меня о механизме расширения HashMap. Мое сердце было разбито, и я чуть не плакал!»
Я некоторое время утешал Сяо Эра, и его волнение стабилизировалось. Я сказал ему, что сложно понять механизм расширения HashMap, особенно после того, как JDK8 добавил красно-черное дерево. Сначала на основе JDK7, затем добавление красно-черного дерева облегчит понимание.
Сяо Эр внезапно понял это и восхищенно кивнул.
Голос HashMap: для тех, у кого есть учетная запись GitHub, не забудьте устроить волну звезд. Учебник с открытым исходным кодом «Дорога к продвинутым программистам Java» в настоящее время имеет 244 звезды на GitHub и вот-вот достигнет 1000. Умоляю вас всех.
Адрес гитхаба:GitHub.com/IT Ван Эр/до…
Адрес онлайн-чтения:ITwang two.git ee.IO/быть лучше J…
Всем известно, что размер массива нельзя изменить после его инициализации, поэтомуArrayListЭтот «динамический массив» может быть автоматически расширен.
Нижний слой HashMap также является массивом. Постоянно добавляя элементы в HashMap, когда массив не может содержать больше элементов, массив необходимо расширить, чтобы загрузить больше элементов.
Конечно, массив нельзя расширить автоматически, поэтому, если вы хотите расшириться, вам нужно создать новый большой массив, а затем скопировать элементы маленького массива.
Расширение HashMap реализовано методом resize.Красно-черное дерево интегрировано в более сложный JDK 8. Для облегчения понимания мы также используем исходный код JDK 7 для понимания JDK 7. Мы объясним JDK 8 и JDK 7 подробно позже. Различия между JDK 7.
Исходный код метода изменения размера:
// newCapacity为新的容量
void resize(int newCapacity) {
// 小数组，临时过度下
Entry[] oldTable = table;
// 扩容前的容量
int oldCapacity = oldTable.length;
// MAXIMUM_CAPACITY 为最大容量，2 的 30 次方 = 1<<30
if (oldCapacity == MAXIMUM_CAPACITY) {
// 容量调整为 Integer 的最大值 0x7fffffff（十六进制）=2 的 31 次方-1
threshold = Integer.MAX_VALUE;
return;
}
// 初始化一个新的数组（大容量）
Entry[] newTable = new Entry[newCapacity];
// 把小数组的元素转移到大数组中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 引用新的大数组
table = newTable;
// 重新计算阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
Сдвиг влево появляется в комментариях к коду (<<), вот краткое введение:
a=39
b = a << 2
Десятичное число 39 представлено 8-битным двоичным числом, то есть 00100111, сдвинутым влево на два бита до 10011100 (нижние биты заполнены 0), а затем преобразованным в десятичное число 156.
Операции сдвига часто можно использовать вместо операций умножения и деления. Например, сдвиг 0010011 (39) влево на две позиции дает 10011100 (156), что ровно в 4 раза больше исходного размера.
На самом деле двоичное число станет в 2, 4 и 8 раз больше исходного после сдвига влево.
Метод Transfer используется для переноса, копирования элементов небольшого массива в новый массив.
void transfer(Entry[] newTable, boolean rehash) {
// 新的容量
int newCapacity = newTable.length;
// 遍历小数组
for (Entry<K,V> e : table) {
while(null != e) {
// 拉链法，相同 key 上的不同值
Entry<K,V> next = e.next;
// 是否需要重新计算 hash
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 根据大数组的容量，和键的 hash 计算元素在数组中的下标
int i = indexFor(e.hash, newCapacity);
// 同一位置上的新元素被放在链表的头部
e.next = newTable[i];
// 放在新的数组上
newTable[i] = e;
// 链表上的下一个元素
e = next;
}
}
}
e.next = newTable[i], то есть используется метод вставки заголовка односвязного списка, и новый элемент в той же позиции всегда будет помещаться в позицию заголовка связанного списка; таким образом, элемент, помещенный первым в индексе, в конечном итоге будет помещаться в конец связанного списка (если возникает конфликт хэшей), что отличается от JDK 8.
Элементы в одном и том же связанном списке в старом массиве могут быть помещены в разные позиции в новом массиве после пересчета позиции индекса.(Внимательный взгляд на следующее ясно объяснит это).
Предположим, алгоритм хеширования (В предыдущей главе упоминалось, щелкните ссылку и просмотрите ее еще раз) просто берет хэш-значение ключа (значение типа int) и модуль размера массива (то есть hashCode % table.length).
Продолжайте считать:
- Длина таблицы массива равна 2
- Хэш-значение ключа 3, 7, 5
После операции по модулю все коллизии хэшей попадают в таблицу [1], потому что остаток равен 1. Затем изображение до расширения показано на следующем рисунке.
Емкость маленького массива равна 2, а ключи 3, 7 и 5 находятся в связанном списке таблицы [1].
Предположим, что коэффициент загрузки loadFactor равен 1, то есть когда фактический размер элемента больше фактического размера таблицы, емкость будет увеличена.
Емкость расширенного большого массива равна 4.
- Модуль (3%4) ключа 3 равен 3, который помещается в таблицу[3].
- Модуль ключа 7 (7% 4) равен 3, который помещается в начало связанного списка в таблице [3].
- Ключ 5 по модулю (5%4) равен 1 и помещается в таблицу[1].
По нашим ожиданиям расширенная 7 все же должна отставать от списка 3, а по факту? 7 отправились в начало связанного списка из 3. Какие оптимизации сделаны в JDK 8 для этой ситуации в JDK 7?
См. рисунок ниже.
n — длина таблицы, значение по умолчанию — 16.
- n-1 — это 0000 1111 в двоичном формате (1X+1X+1X+1X=1+2+4+8=15);
- Последние 8 цифр Key1 Hash Value 0000 0101
- Последние 8 цифр хэша ключа 2 равны 0001 0101 (отличается от ключа 1).
- После выполнения операции AND происходит коллизия хэшей, и все индексы включены (0000 0101).
32 после расширения.
- n-1 — это 0001 1111 в двоичном формате (1X+1X+1X+1X+1X=1+2+4+8+16=31), 0000 1111 до расширения.
- Младшие биты хеш-значения key1 равны 0000 0101.
- Младшие биты хеш-значения key2 равны 0001 0101 (отличаются от key1).
- После того, как ключ 1 по И, индекс равен 0000 0101.
- После операции И ключа 2 индекс равен 0001 0101.
Новый индекс изменится следующим образом:
- Исходный индекс был 5 (00101)
- Первоначальная вместимость была 16
- Расширенная вместимость 32
- Расширенный индекс равен 21 (10101), что равно 5+16, что является исходным индексом + исходная емкость
То есть JDK 8 не нужно пересчитывать хеш, как JDK 7. Ему нужно только увидеть, равен ли новый бит исходного значения хеш-функции 1 или 0. Если он равен 0, это означает, что индекс не изменился. , Если он равен 1, индекс становится «исходный индекс + исходная емкость».
Этот дизайн JDK 8 очень изобретателен, что экономит время на пересчет хэша, В то же время, поскольку вновь добавленный 1 бит равен 0 или 1 является случайным, процесс расширения может равномерно распределить предыдущие узлы на новые. позиция.
woc, можно только сказать, что авторы HashMap, Дуг Леа, Джош Блох, Артур ван Хофф и Нил Гафтер действительно сильны.
Исходный код для расширений JDK 8:
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) {
// 小数组复制到大数组
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
// 链表优化重 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;
}
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;
}
Ссылка на ссылку:
Расширенный путь программистов Java, юмористический, простой для понимания, чрезвычайно дружелюбный и удобный для начинающих Java😘, включая, помимо прочего, синтаксис Java, структуру сбора Java, Java IO, параллельное программирование Java, виртуальную машину Java и другие основные знания.