Обзор хэш-карты
HashMap реализует интерфейс Map.Мы часто используем HashMap для операций ввода и получения для чтения и хранения данных пар ключ-значение. Далее представлено глубокое понимание основных принципов HashMap на основе jdk1.8.
Структура данных HashMap
HashMap на самом деле представляет собой структуру данных «массив + связанный список». В операции размещения нижний индекс массива находится с помощью внутреннего алгоритма определения, и данные непосредственно помещаются в элемент массива.Если элемент массива, полученный алгоритмом, уже имеет элементы (обычно известный как конфликт хэшей, фактическое значение структура связанного списка также предназначена для решения проблемы хеш-конфликта). Будет пройден связанный список элементов этого массива, и новые данные будут помещены в конец связанного списка.
объект для хранения данных
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}Из исходного кода jdk1.8 видно, что объект хранилища Node фактически реализует интерфейс объекта Map.Entry.
hash: значение, полученное с помощью алгоритма хеширования. Алгоритм хэширования Давайте посмотрим на реализацию исходного кода HashMap
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}Методы расчета hashCode для разных типов данных разные, рассмотрим алгоритм hashCode для типов данных String и Integer.
String.hashCode()
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}Вычисляется путем преобразования строки в массив символов по формуле s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] из конечное значение. Значение val[i] является значением ASCII соответствующего символа.Когда я вижу это, почему 31 используется в качестве коэффициента умножения (почему, это не из соображений производительности, тогда почему производительность 31 может быть оптимизирована) , обсуждение можно продолжить здесь.
Integer.hashCode()
public static int hashCode(int value) {
return value;
}Вернуть значение напрямую.
ключ: ключ для хранения данных
значение: значение сохраненных данных
следующий: следующие данные, когда возникает конфликт хэшей, элемент массива будет иметь структуру связанного списка, а следующий будет использоваться для указания на следующий объект элемента в связанном списке
Проблемы, вызванные структурой связанного списка
Соответствующий индекс можно эффективно найти из поиска и остановки с помощью алгоритма хеширования, но по мере роста данных возникает слишком много коллизий хэшей. При поиске данных, если связанный список найден, соответствующие данные будут искаться путем обхода, что будет делать эффективность получения данных все ниже и ниже. В jdk1.8, если количество элементов связанного списка больше или равно 8, структура связанного списка будет реорганизована для формирования «красно-черной древовидной структуры».Эта структура делает эффективность получения намного выше, чем у связанный список, когда слишком много хеш-коллизий.
Как обрабатываются данные хранилища HashMap put
HashMap имеет несколько важных переменных
transient Node<K,V>[] table;
int threshold;
final float loadFactor;
int modCount;
int size;table: Переменная, в которой хранится массив.Начальная длина равна 16. Из исходного кода видно, что выполняется первое расширение resize (java — статический язык. При определении инициализации массива длина массива необходимо определить.После роста данных карты внутренний механизм переопределит массив для расширения его емкости) при инициализации статическая переменная по умолчанию будет
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;Назначьте длину массива для инициализации.
loadFactor: коэффициент роста данных, по умолчанию 0,75. Он будет использоваться в операции расширения.
порог: максимальное количество сохраняемых элементов, полученное с помощью длины массива длины * коэффициента роста loadFactor
modCount: записывает, сколько раз менялась внутренняя структура, операции ввода (значения переопределения не учитываются) и прочее...
размер: количество фактически сохраненных элементов
положить процесс
Непосредственно через анализ исходного кода
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 判断数组是否为空，长度是否为0，是则进行扩容数组初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 通过hash算法找到数组下标得到数组元素，为空则新建
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 找到数组元素，hash相等同时key相等，则直接覆盖
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 该数组元素在链表长度>8后形成红黑树结构的对象
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 该数组元素hash相等，key不等，同时链表长度<8.进行遍历寻找元素，有就覆盖无则新建
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 新建链表中数据元素
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 链表长度>=8 结构转为 红黑树
treeifyBin(tab, hash);
break;
}
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;
}Для простоты понимания сделал фото. Как показано ниже (художник не очень, извините за это)
На следующем рисунке изображен великий бог, пожалуйста, процитируйте его для облегчения понимания.
1. Желательно определить, пуста ли таблица и пуста ли длина массива, и будет выполнена первая инициализация. (При создании экземпляра HashMap массив не будет инициализирован)
2. После первого расширения resize(). Начните находить индекс массива с помощью адресации алгоритма хеширования. Если элемент массива пуст, создается новый элемент массива. Если элементы массива не пусты, хэши равны, ключи не равны и они не являются объектами данных TreeNode, будут пройдены элементы связанного списка под элементами массива. Если соответствующий элемент будет найден, он будет перезаписан. Если он не найден, будет создан новый элемент и помещен в следующий из предыдущего элемента связанного списка. После размещения элемента, если удовлетворяет условию "длина элемент связанного списка > 8», структура связанного списка будет преобразована в «красно-черную древовидную структуру».
3. Найдите соответствующий элемент массива или элемент связанного списка и одновременно создайте новый элемент данных или перезапишите элемент. Если условие удовлетворяет размеру элемента size > максимально допустимого порога числа элементов, операция расширения выполняется снова. Для каждой операции расширения размер нового массива будет в два раза больше размера исходного массива.
4. Операция размещения завершена.
Пример вызова метода put
Ниже описан этот процесс на примере
HashMap<Integer, String> hashMap = new HashMap<Integer, String>(4, 0.75f);// 1
int a1 = 1;
int a2 = 2;
int a3 = 5;
System.out.println(String.valueOf(a1&3) + " " + String.valueOf(a2&3)+ " " + String.valueOf(a3&3));// 1 2 1 数组下标
hashMap.put(a1, "1");// 2
hashMap.put(a2, "2");// 3
hashMap.put(a3, "5");// 41. Создайте объект HashMap, инициализируйте initialCapacity равным 4 и коэффициентом роста равным 0,75. порог инициализируется до 4
2. Выполняется первое размещение. Поскольку таблица пуста, выполняется первая операция расширения resize(), и массив инициализируется. Значение по умолчанию равно 16. Порог становится равным 3. В то же время алгоритм хеширования (длина массива n-1 и хэш) равен 1.
3. Для второй операции put при этом нижний индекс массива получается как 2. В это время нижний индекс массива равен 2. Элемента массива в это время нет, а элемент данных непосредственно создали и вложили в него.
4. В третьей операции put индекс массива равен 1 и элемент массива уже есть. В то же время мы знаем, что в узле есть еще один следующий объект, который хранит данные, тогда новый элемент данных в это время помещается в следующий в узле, чей следующий пуст в предыдущем связанном списке.
Формируется следующая структура данных
Вывод: Нижний индекс массива, рассчитанный алгоритмом хеширования, имеет определенную вероятность вызвать конфликт хэшей, в элементе массива есть ключи с одинаковым хеш-значением, но ключи не равны. Чтобы решить эту проблему конфликта хэшей, для обработки используется структура связанного списка.
Изменение размера расширения HashMap()
Java является статическим методом, и при инициализации массива должна быть задана длина массива. HashMap определяет длину массива по умолчанию 16. Условие удовлетворяет размеру элемента > максимально допустимому порогу числа элементов. расширен. Вообще говоря, в операции put HashMap расширяется по крайней мере один раз (первый раз — это инициализация).
Добавим к исходному примеру следующее
int a4 = 6;
hashMap.put(a4, "6");Формируется новая структура, как показано на рисунке ниже.
Он помещается в следующий из 2:2, в это время размер=4, порог>3, условие удовлетворяет размер>порог, и выполняется операция расширения resize()
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);
}
// 第一次初始化
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;
}После put6:6 расширение выполняется напрямую, новая длина массива равна 8, а новая структура выглядит следующим образом.
В новой структуре исходные индексы массива 1 и 2 равномерно распределены среди других элементов массива нового массива. Процесс изменения мощности расширения выглядит следующим образом
Длина старого массива равна 4. Благодаря алгоритму нижний индекс данных 1:1 равен 1, 5:5 равен 1, 2:2 и 6:6 равен 2.
1(1:1 == > 5:5)
2(2:2 == > 6:6)Во время операции расширения первый индекс массива в связанном списке элементов массива не изменится.При обходе других элементов связанного списка элементы связанного списка помещаются под новый массив данных по алгоритму "e.hash & oldCap"! =0 Помечен как [индекс необработанных данных + длина необработанных данных]
Обратившись снова к диаграмме Великого Бога, легко понять изменения движения данных расширения.
В операции расширения, поскольку нет необходимости пересчитывать хеш-значение, конфликтующие элементы связанного списка равномерно распределяются в новый массив. Этот дизайн действительно гениальный.
получить данные поиска
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;
}Метод get относительно прост.Основной процесс заключается в получении индекса массива через hashCode ключа и алгоритма адресации.Если ключ и хэш в элементах массива совпадают, он будет возвращен напрямую. Если вы не хотите ждать и в то же время есть элементы связанного списка, пройдитесь по элементам связанного списка, чтобы найти соответствие. Так как 1.8 относится к красно-черной древовидной структуре, когда элементов связанного списка слишком много, реализация 1.8 будет намного эффективнее, чем 1.7 в операциях get и put.
В данной статье преимущества алгоритма адресации и преимущества красно-черного дерева подробно не объясняются. Здесь нет обсуждения.
В следующем разделе изучите и докажите, почему HashMap небезопасен для потоков.
[Я код-фермер, а не код-фермер] Программное обеспечение — сосредоточьтесь на идеях и логике