Вы можете выполнить поиск в общедоступной учетной записи WeChat [Jet and Programming], чтобы просмотреть другие интересные статьи.
Оригинальный текст был опубликован на моей собственной блог-платформе [ву ву ву Джет Чен талант/анализ-ха…】
Структура данных HashMap, будь то ежедневная разработка или собеседование при приеме на работу, это всегда участь, которой не могут избежать все программисты Java, поэтому я решил написать статью, чтобы подробно проанализировать структуру данных HashMap, сколько загадок существует во время период разведки.
задний план
Я давно хотел написать несколько статей о структурах данных, но спустя много лет, наконец, решил официально начать писать, поэтому начнем с самого популярного HashMap.
HashMap — одна из наиболее часто используемых структур данных в программах на Java, и она в основном используется для работы с парами ключ-значение. Более того, в JDK 1.8 была оптимизирована базовая реализация, например добавление красно-черных деревьев и оптимизация механизма расширения.
Эта статья в основном основана на наиболее часто используемой версии 1.8 JDK и подробно анализирует несколько наиболее важных параметров и методов, таких как вычисление индекса, расширение массива, метод put() и т. д. В конце будет небольшое сравнение между версиями 1.8 и 1.7 разница между ними.
Введение
Функции
HashMap наследуется от Map и имеет следующие характеристики:
- Store key - структура типа значения, тип данных не ограничен
- Хранить данные в соответствии со значением хэш-кода ключа
- Максимум один ключ записи (ключ) может быть нулевым (без ограничений на значение значения)
- Он неупорядочен (на самом деле мы знаем это, когда видим хэш)
- Запрос очень эффективный
- Он не является потокобезопасным (для обеспечения потокобезопасности используйте synchronizedMap из коллекций или более рекомендуемый ConcurrentHashMap)
У него также есть несколько общих братьев и сестер, таких как LinkedHashMap, TreeMap и Hashtable, которые не будут сравниваться в этой статье.
Базовая структура
Структура HashMap представляет собой структуру массив + связанный список + красно-черное дерево, скетч можно увидеть на рисунке ниже.
Красно-черное дерево было введено в версии JDK1.8, цель состоит в том, чтобы ускорить эффективность запроса связанного списка.
Как видно из рисунка выше, нижний слой HashMap представляет собой массив хеш-багет с именем table, в котором хранятся данные на основе типа узла.NodeЭто очень важно и будет подробно объяснено ниже.
Тогда один и тот же массив может хранить несколько Узлов во всех позициях и реализовать его в виде связанного списка или красно-черного дерева, так что несложно догадаться, что раз это связанный список, то каждый Узл должен записывать Узлы. Однако, если связанный список очень длинный, эффективность запроса будет снижена, поэтому красно-черное дерево было введено начиная с JDK1.8, то есть, когда длина связанного списка превышает 8, связанный список будет преобразован в красно-черное дерево, кроме того, когда длина связанного списка меньше At 6, он будет преобразован из красно-черного дерева в связанный список.
метод цепного адреса
HashMap использует хеш-таблицу для хранения данных. Для разрешения конфликтов хэш-таблицы обычно имеют два решения:закон об открытых адресахиметод цепного адреса.
Метод открытого адреса: если после хеширования возникает конфликт, найдите вакансию для вставки по определенным правилам.
HashMap используетметод цепного адреса, то есть структуру связанного списка по каждому индексу массива, чтобы можно было эффективно разрешать конфликты хэшей.
Когда хеш-значения двух ключей совпадают, они будут помещены в одну и ту же позицию массива и представлены в виде связанного списка.
Однако, если большая часть данных сосредоточена по одному и тому же индексу в массиве, а данных по остальным индексам относительно мало, то есть распределение не сбалансировано, значит, хэш-коллизий много.
Поэтому, чтобы повысить эффективность доступа HashMap, нам нужно максимально рассредоточить данные по массиву, то есть уменьшить хэш-коллизии, для чего самым прямым решением является улучшение алгоритма хеширования. , с последующим расширением хеша Размер массива бакетов (расширение), о котором будет подробно рассказано ниже.
Поля и свойства
некоторые параметры по умолчанию
// 默认的初始容量为 16 （PS：aka 应该是 as know as）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量（容量不够时需要扩容）
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表长度为 8 的时候会转为红黑树
static final int TREEIFY_THRESHOLD = 8;
// 长度为 6 的时候会从红黑树转为链表
static final int UNTREEIFY_THRESHOLD = 6;
// 只有桶内数据量大于 64 的时候才会允许转红黑树
static final int MIN_TREEIFY_CAPACITY = 64;
Начальная емкость равна 16, которую можно увеличить, но емкость после расширения также равна степени 2, например 32, 64, почему? Здесь задействовано много оригинальных конструкций, которые будут подробно представлены ниже, когда будет представлен метод resize().
Кроме того, мы объясняемMIN_TREEIFY_CAPACITY, хотя и сказано, что когда длина связанного списка больше 8, связанный список будет преобразован в красно-черное дерево, но также необходимо выполнить требование, чтобы объем данных, хранящихся в ведре, был больше значения вышеуказанного параметра, иначе оно не только не будет преобразовано в красно-черное дерево, а вместо этого будет расширено. .
Например, следующий код предназначен для определения того, следует ли преобразовать связанный список в красно-черное дерево.На первый взгляд, это только длина связанного списка иUNTREEIFY_THRESHOLDДля сравнения, на самом деле это не так, нажмите наtreeifyBin(tab, hash)С помощью этого метода мы можем видеть, что если количество данных в массиве ведра меньше, чемMIN_TREEIFY_CAPACITY, связанный список не будет преобразован в красно-черное дерево, а будет развернут, как показано на следующем рисунке:
некоторые важные поля
// Map 中存储的数据量，即 key-value 键值对的数量
transient int size;
// HashMap 内部结构发生变化的次数，即新增、删除数据的时候都会记录，
// 注意：修改某个 key 的值，并不会改变这个 modCount
transient int modCount;
// 重点，代表最多能容纳的数据量
// 即最多能容纳的 key-value 键值对的数量
int threshold;
// 负载因子，默认为 0.75
// 注意，这个值是可以大于 1 的
final float loadFactor;
Есть два параметра, на которые следует обратить внимание, один из нихthreshold, а другой естьloadFactor.
thresholdПредставляет максимальное количество узлов, которое может быть размещено, как правилоthreshold = length * loadFactor, то есть для того, чтобы HashMap хранил больше данных (то есть для получения большего порога), есть два варианта, один — расширить емкость (то есть увеличить длину массива), и другой заключается в увеличении коэффициента нагрузки.
порог и длина массива не одно и то же
Значение коэффициента нагрузки по умолчанию, равное 0,75, является относительно сбалансированной точкой, основанной на соображениях времени и пространства, поэтому мы обычно не корректируем коэффициент нагрузки, если нет особых требований:
- Напримерпоменять пространство на время, а это значит, что если память относительно велика и требуется высокая эффективность доступа, коэффициент загрузки можно соответствующим образом уменьшить, при этом вероятность коллизии хэшей снизится.
- Другой примеробмен времени на пространство, что означает, что если память относительно мала, а эффективность доступа соответствующим образом снижена, коэффициент загрузки можно соответствующим образом увеличить, даже если он больше 1. При этом будет увеличена вероятность коллизии хэшей.
Подробное объяснение коэффициента загрузки 0,75 требует создания математической модели для анализа, и в связи с недостатком знаний я пока не буду ее обсуждать.
Node<K,V>
Нижний слой HashMap — это таблица Node[], поэтому Node — очень важная структура данных.
Node реализует интерфейс Entry, поэтому Node по сути является структурой данных Key-Value.
static class Node<K,V> implements Map.Entry<K,V> {
// key 的 hash 值
final int hash;
final K key;
V value;
// 记录下一个 Node
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {...}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {...}
public final V setValue(V newValue) {...}
public final boolean equals(Object o) {...}
}
Конструктор
Всего имеется четыре конструктора, которые будут объяснены по очереди.
HashMap()
Создает пустой HashMap с начальной емкостью 16 и коэффициентом загрузки 0,75.
// 构造一个空的 HashMap，初始容量为 16，负载因子为默认值 0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
HashMap(int initialCapacity)
Создает пустой HashMap, указывая начальную емкость и коэффициент загрузки по умолчанию 0,75.
Внутри конструктора вызывается третий конструктор, описанный непосредственно ниже.
// 构造一个空的 HashMap，并指定初始化容量，负载因子采用默认的 0.75
public HashMap(int initialCapacity) {
// 调用另一个构造函数
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
HashMap(int initialCapacity, float loadFactor)
Создает пустой HashMap, указывая начальную емкость, указывая коэффициент загрузки.
// 构造一个空的 HashMap，并指定初始化容量，指定负载因子
public HashMap(int initialCapacity, float loadFactor) {
// 初始容量不为负数
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
// 初始容量大于最大值时，则取最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 负载因子不能小于 0，并且必须是数字，否则抛异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
// 最大容量 MAXIMUM_CAPACITY 为 1 << 30
}
В конструкторе выполняется ряд оценок параметров и выполняются операции инициализации.
- Выбрасывает, если начальная емкость меньше 0, или если коэффициент загрузки меньше 0 или не является числом
IllegalArgumentExceptionаномальный. - Если начальная емкость больше максимального значения (2^30), будет использована максимальная емкость.
- Установите порог и вызовите его напрямую
tableSizeFor()метод, который возвращает целое число, большее или равное указанной емкости в степени 2. Например, если передано 6, будет возвращено 8.
tableSizeFor()Подробное объяснение метода будет дано ниже.В качестве альтернативы, непосредственно присвойте полученное значение
threshold, разве это не должно быть так, как это должно быть сделано?this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;, На самом деле, если мы снова посмотрим на исходный код, мы обнаружим, что действие инициализации помещается в операцию put.
HashMap(Map<? extends K, ? extends V> m)
Создайте непустую HashMap, чтобы гарантировать, что начальная емкость может полностью вместить входящую карту.Кроме того, коэффициент загрузки использует значение по умолчанию 0,75.
// 构造一个非空的 HashMap，指定了默认的负载因子 0.75
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 将 Map 中的 key-value 赋值到新的 Map 中去
putMapEntries(m, false);
}
putMapEntries()Этот метод заключается в сохранении всех данных из переданной карты в текущий HashMap. Подробнее об этом методе см. ниже.
ключевой метод
tableSizeFor(int cap)
Как следует из названия, инициализирует размер массива сегментов.
Функция этого метода состоит в том, чтобы вернуть значение, большее или равное входящему параметру, и возвращаемое значение будет удовлетворять следующим двум пунктам:
- Возвращаемое значение является степенью числа 2
- Возвращаемое значение — это значение, ближайшее к переданному параметру.
Например: сдать 5, вернуть 8, сдать 8, вернуть 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;
}
Степень числа 2 имеет особенность, заключающуюся в том, что ее байт-код равен 0, кроме самого старшего бита, равного 1.
Например, 2, байт-код: 10, старший бит 1, а остальные 0
Другой пример — 16, байт-код: 10000, старший бит — 1, а остальные — 0.
Таким образом, в методе используется множество операций «или» и «правый сдвиг», чтобы гарантировать, что каждый бит, начиная с самого старшего бита, равен 1.
- первая строка
int n = cap - 1;Функция состоит в том, чтобы сам входящий параметр не был степенью числа 2, иначе он вернет удвоенное значение параметра; -
n |= n >>> 1;Функция состоит в том, чтобы убедиться, что предпоследний старший бит также равен 1, и следующий код аналогичен. - Перед последней строкой полученное число похоже на 0000 1111, что равно 1, начиная с первого старшего бита, поэтому, пока добавляется 1, возвращаемое значение должно быть степенью двойки.
Подробный процесс расчета показан на следующем рисунке:
putMapEntries(Map<? extends K, ? extends V> m, boolean evict)
Этот метод предназначен для сохранения всех данных параметра m в текущий HashMap, например, этот метод вызывается в четвертом конструкторе, упомянутом выше.
Этот метод относительно прост, и следующий код аннотирован, а два основных задействованных метода:resize()иputVal()Метод, функции расширения и присвоения соответственно, и эти два метода будут подробно описаны ниже.
// 将参数 m 中的所有元素存入到当前的 HashMap 中去
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// 获取 m 中的参数个数（key-value 的数量）
int s = m.size();
if (s > 0) {
// 判断 table 是否被初始化过，否则初始化一遍。（PS：table 是在 put 操作的时候进行初始化的，所以如果当前的 HashMap 没有进行过 put 操作，则当前的 table 并不会被初始化）
if (table == null) { // pre-size
// 根据传进来的 map 的元素数量来计算当前 HashMap 需要的容量
float ft = ((float)s / loadFactor) + 1.0F;
// 计算而得的容量是不能大于最大容量的
int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
// 将计算而得的容量赋值给 threshold，前提是大于当前容量（即不会减小当前的 HashMap 的容量）
if (t > threshold)
// 将容量转换为最近的 2 的 幂次方
threshold = tableSizeFor(t);
}
// table 不为空，即已经初始化过了，
// 如果 m 中的元素数量超过了当前 HashMap 的容量，则要进行扩容
else if (s > threshold)
resize();
// 遍历 m 的每个元素，将它的 key-value 插入到当前的 HashMap 中去
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
// 插入数据（注意，为什么不是 put() 呢，因为 put() 其实也是调用的 putVal() 方法）
putVal(hash(key), key, value, false, evict);
}
}
}
hash(Object key)
Алгоритм хеширования в HashMap заключается в вычислении хэш-кода ключа для получения h, а затем выполнении операции исключающее ИЛИ над старшими 16 битами и младшими 16 битами h.
Это делается на основе всестороннего рассмотрения скорости, качества и т. д., а биты старшего и младшего разрядов смешиваются, что может эффективно снизить вероятность конфликта.
Кроме того, старшие биты могут гарантированно оставаться неизменными, а младшие изменены, а младшие биты легированы старшими битами информации, а случайность окончательно сгенерированного хэш-значения повысится.
На следующем рисунке показано вычисление XOR (например, h равно 467 926 597):
Из приведенного выше рисунка также видно, что старшие числа не изменились.
// (h = key.hashCode()) ^ (h >>> 16);
static final int hash(Object key) {
int h;
// 高 16 位与低 16 位进行异或运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Кроме того, функция hash() состоит в том, чтобы вычислить хеш-значение в соответствии с ключом, а затем вычислить индекс i массива в соответствии с хеш-значением.На основе этого индекса мы можем выполнять связанные добавления, удаления, изменения, и операции поиска, поэтому этот индекс очень важен.
Формула расчета:i = hash(key) & (n-1), то есть следующий метод, но этот метод ограничен версиями до 1.8:
// jdk1.7 的源码，jdk1.8 没有这个方法，但是原理一样
static int indexFor(int h, int length) {
// 取模运算
return h & (length-1);
}
Вот еще одна очень тонкая конструкция.В общем, мы хотим получить индекс i.Самый распространенный метод расчета — операция по модулю:hash % length, но вот:hash & （length-1）, Мяозай Мяозай.
Зачем ты это делаешь? Поскольку операция '%' более требовательна к производительности, чем битовая, используется странный трюк '&'. Но почему результат согласуется с операцией по модулю? На самом деле, это еще из-за длины стола.
Как мы упоминали выше, длина HashMap всегда является степенью 2, которая является ключом, поэтому есть такой результат.Для простого анализа см. следующий рисунок:
Использование битовой операции & для замены обычной операции % по модулю значительно повышает производительность. Это одно из преимуществ такого проектирования длины массива таблицы. Еще одним большим преимуществом является то, что при расширении емкости она будет проанализирована. ниже.
resize()
resize() — очень важный метод, который используется для расширения емкости, чтобы HashMap мог хранить больше данных.
Поскольку, когда мы продолжаем добавлять данные в HashMap, они всегда будут превышать верхний предел объема данных, разрешенных для хранения, поэтому он обязательно будет испытыватьРасширениеЭтот шаг выполняется, но нижний слой HashMap представляет собой массив.Все мы знаем, что емкость массива нельзя увеличить, поэтому процесс изменения размера фактически заключается в создании массива большей емкости для хранения данных в текущей HashMap.
Метод resize() очень тонкий, давайте взглянем на исходный код JDK1.8.
final Node<K,V>[] resize() {
// 当前 table
Node<K,V>[] oldTab = table;
// 当前的 table 的大小
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 当前 table 的 threshold，即允许存储的数据量阀值
int oldThr = threshold;
// 新的 table 的大小和阀值暂时初始化为 0
int newCap, newThr = 0;
// ① 开始计算新的 table 的大小和阀值
// a、当前 table 的大小大于 0，则意味着当前的 table 肯定是有数据的
if (oldCap > 0) {
// 当前 table 的大小已经到了上线了，还咋扩容，自个儿继续哈希碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 新的 table 的大小直接翻倍，阀值也直接翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// b、当前的 table 中无数据，但是阀值不为零，说明初始化的时候指定过容量或者阀值，但是没有被 put 过数据，因为在上文中有提到过，此时的阀值就是数组的大小，所以直接把当前的阀值当做新 table 的数组大小即可
// 回忆一下：threshold = tableSizeFor(t);
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// c、这种情况就代表当前的 table 是调用的空参构造来初始化的，所有的数据都是默认值，所以新的 table 也只要使用默认值即可
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新的阀值是 0，那么就简单计算一遍就行了
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// ② 初始化新的 table
// 这个 newTab 就是新的 table，数组大小就是上面这一堆逻辑所计算出来的
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 遍历当前 table，处理每个下标处的 bucket，将其处理到新的 table 中去
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 释放当前 table 数组的对象引用（for循环后，当前 table 数组不再引用任何对象）
oldTab[j] = null;
// a、只有一个 Node，则直接 rehash 赋值即可
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// b、当前的 bucket 是红黑树，直接进行红黑树的 rehash 即可
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// c、当前的 bucket 是链表
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 遍历链表中的每个 Node，分别判断是否需要进行 rehash 操作
// (e.hash & oldCap) == 0 算法是精髓，充分运用了上文提到的 table 大小为 2 的幂次方这一优势，下文会细讲
do {
next = e.next;
// 根据 e.hash & oldCap 算法来判断节点位置是否需要变更
// 索引不变
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);
// 原 bucket 位置的尾指针不为空(即还有 node )
if (loTail != null) {
// 链表末尾必须置为 null
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
// 链表末尾必须置为 null
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
Что ж, давайте введем операцию вычисления индекса, упомянутую в исходнике выше, то есть судитьif ((e.hash & oldCap) == 0).
На следующем рисунке показан метод расчета индекса до и после расширения, в основном с акцентом на содержимое в красной рамке. С этим решением проблем нет, но, как мы упоминали ранее, размер таблицы равен степени 2. Зачем это сделано?Здесь отражена еще одна загадка того периода, см. примечания на рисунке.
Так как правила генерации нового индекса каждого ключа после расширения фиксированы и регулярны, то есть есть только две формы, либо неизменный i, либо увеличенный на величину исходного размера массива (i+n), поэтому мы не На самом деле не нужно вычислять индекс каждого ключа, а нужно только определить, не изменился ли индекс. Итак, вот умное использование(e.hash & oldCap) == 0Это суждение действительно тонкое, и подробный процесс расчета можно увидеть на рисунке ниже.
put(K key, V value)
Здесь представленоputVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict), потому что put() на самом деле является прямым вызовом putVal();
Метод put() является одним из наиболее часто используемых методов в HashMap. Давайте сначала сосредоточимся на процессе работы метода put() Текст не будет повторяться, но это будет понятно из следующего рисунка:
Ниже приводится краткий анализ исходного кода:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 参数 onlyIfAbsent，true：不修改已存在的 value，false：已存在则进行修改
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 为空则进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// (n - 1) & hash 计算得到索引 i，算法在上文有提到，然后查看索引处是否有数据
// ② 如果没有数据，则新建一个新的 Node
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 索引处有数据
else {
Node<K,V> e; K k;
// ③ 索引处的第一个 Node 的 key 和参数 key 是一致的，所以直接修改 value 值即可（修改的动作放在下面）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// ④ 索引处的 bucket 是红黑树，按照红黑树的逻辑进行插入或修改
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// ⑤ 索引处的 bucket 是链表
else {
// 遍历链表上面的所有 Node
for (int binCount = 0; ; ++binCount) {
// 索引处的 Node 为尾链
if ((e = p.next) == null) {
// 直接新建一个 Node 插在尾链处
p.next = newNode(hash, key, value, null);
// 判断是否需要转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 链表转换为红黑树，此方法在上文中也有介绍
treeifyBin(tab, hash);
break;
}
// 当前 Node 的 key 值和参数 key 是一致的，即直接修改 value 值即可（修改的动作放在下面）
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 找到了相同 key 的 Node，所以进行修改 vlaue 值即可
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 修改 value 值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
// 修改操作，直接 return 结束掉代码逻辑
return oldValue;
}
}
// 记录结构发生变化的次数
++modCount;
// ⑥ 判断是否需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
// 新增的 Node，返回 null
return null;
}
get(Object key)
Здесь представленоgetNode(int hash, Object key, потому что get() на самом деле является прямым вызовом getNode();
Метод get() также относительно прост, он заключается в получении индекса таблицы по ключу, а затем поиске узла с таким же ключом в зависимости от ситуации;
Исходный код примерно такой:
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 当前 table 不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 判断索引处的第一个 Node 的 key 值是否和参数 key 相同，相同则返回该 Node
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 索引处的第一个 Node 不是想要的，则接着查 next
if ((e = first.next) != null) {
// bucket 是红黑树结构
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// bucket 是链表结构
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
JDK1.8 VS JDK1.7
Наиболее важным отличием 1.7 от 1.8 являются следующие три аспекта.Конечно, я думаю изменения в этих трех пунктах можно расценивать как относительно удачную оптимизацию.
- После расширения метод расчета индекса узла изменился. Как упоминалось выше, из-за волшебного дизайна размера таблицы при вычислении индекса во время расширения вам нужно просто использовать операцию &, чтобы определить, равен ли он 0 в 1.8.Вам не нужно использовать его каждый раз, как 1.7 Оператор & для вычисления значения индекса.
- Красно-черная древовидная структура была введена в версии 1.8. Как было сказано выше, когда длина связанного списка больше 8, он будет преобразован в красно-черное дерево, но в 1.7 это комбинация массив + связанный список.
- В 1.8 используется метод вставки хвоста, а в 1.7 — метод вставки головы. Например, при расширении емкости метод вставки головы изменит порядок узлов в связанном списке, а метод вставки хвоста — нет.Кроме того, метод вставки головы также вызовет такие проблемы, как бесконечные циклы круговой цепочки. , которые не будут подробно обсуждаться в этой статье.
разное
HashMap небезопасен для потоков, потому что он позволяет нескольким потокам одновременно работать с одним и тем же массивом, например, put(), например, resize(), что вызовет исключения данных или даже бесконечные циклы.
Поэтому, если вы хотите использовать поточно-ориентированную карту, вы можете использовать HashTable, но это не рекомендуется, или вы можете использовать ConcurrentHashMap в пакете Concurrent, представленном начиная с JDK1.8, что более рекомендуется, и конкретное введение будет обсуждаться ниже.
См. Технический блог Meituan:портал