Я — воздушный змей, официальный аккаунт «Воздушный змей в древние времена», вдохновитель программистов с глубиной и широтой, а также фермер-пастор, который планировал писать стихи, но написал код! Статьи будут включены вJavaNewBeeТакже есть карта знаний Java back-end, и в ней путь от Xiaobai до Daniel.
Это предыдущая статьяИнтересная комическая версия HashMap, 25-летний дядя может понятьтекстовая версия. Многие студенты говорили, что шуточная версия более интересна и понятна, но ведь картинки не могут быть прорисованы так подробно, а могут быть поняты только в широком ракурсе.
Чтобы действительно понять детали, вы должны прочитать эту статью. На самом деле сначала была написана эта статья, а потом я нарисовал много картинок, поэтому написал вариант с картинками. В этой статье более 7000 слов, ее рекомендуется запускать в течение трех лет подряд.
Версия JDK на момент написания этой статьи — 1.8.
В Java наиболее часто используемыми типами данных являются 8 основных типов, их типы-оболочки и строковые типы, за которыми следуютArrayListа такжеHashMapНу давай же.HashMapОн хранит данные в виде пары ключ-значение, которая имеет высокую скорость хранения и поиска и высокую производительность.Это очень простая в использовании структура данных, и каждый разработчик Java должен использовать ее.
а такжеHashMapДизайн оригинален, а его структура и принципы часто используются в качестве вопросов для интервью. Существует множество оригинальных алгоритмов и конструкций, таких как алгоритм хеширования, метод застежки-молнии, дизайн красно-черного дерева и т. д., которые стоит изучить каждому разработчику.
После долгих раздумий, как мне изложить это простым и понятным языком?HashMapЧтобы было ясно, давайте поговорим о моем мышлении и процессе его понимания. Лучший способ понять что-либо — сначала понять общую структуру, а затем вдаваться в детали. Итак, начнем со структуры.
Начнем со структуры
Возьмем в качестве примера собственный опыт.Как профессиональный дорожный идиот,я абсолютно однозначно отношусь к тому,чтобы заблудиться.Хотя я много лет живу в Пекине,но различать север и юг могу только в Чжунгуаньцуне.В других местах,даже если я жить каждый день. Сообщество, в котором я работаю, и компания, в которой я работаю каждый день, не могут указать направление. Я могу распознать только один способ вернуться домой. Если я возьму такси и изменю путь домой, я должен быть запутался на некоторое время домой. Чтобы отправиться в новое место, приходится долго смотреть на карту. В этот момент я подумал, что если бы я мог смотреть на улицы с высоты города, то я бы никогда не боялся найти дорогу домой. Не является ли это ударом по уменьшению размерности в задаче трех тел?Много проще понять низкоразмерные вещи с многомерной точки зрения.
Понимание структуры данных — тоже истина.Большую часть времени мы остаемся на том уровне, который можем использовать, а понимание некоторых принципов лишь фрагментарно, запутались в лабиринте организации данных, споткнулись и срочно нужна карта или карта. вертолет.
Давайте посмотрим в целомMapИнтеграционная схема семейства, на первый взгляд много всего, но остальные могут мало использоваться, толькоHashMapсамый знакомый.
Следующее описание может быть недостаточно профессиональным, это всего лишь простое описаниеHashMapСтруктура, пожалуйста, обратитесь к следующему рисунку, чтобы понять.
HashMapОсновная часть представляет собой структуру массива. Каждая позиция индекса называется bin на английском языке. Давайте сначала назовем ее сегментом. Например, вы определяете длину 8.HashMap, можно сказать, что это массив из 8 сегментов. Когда мы вставляем данные в массив, большую часть времени мы сохраняем элемент типа Node.HashMapСтатический внутренний класс, определенный в .
При вставке данных (то есть вызове метода put) они не сохраняются в обратном порядке по порядку.HashMapНабор специального алгоритма выбора индекса определен в , который называется вычислением хэша, но есть ситуация в вычислении хеширования, называемая коллизией хэшей, то есть значения хеш-функции, вычисленные по двум разным ключевым хэшам, непротиворечивы. в этом случае используйте метод застежки-молнии для расширения, такой как синяя часть связанного списка на рисунке, чтобы разные ключи с одинаковым значением хеш-функции могли попасть в одно и то же ведро без перезаписи предыдущего содержимого.
Однако по мере того, как вставляется все больше и больше элементов, увеличивается вероятность коллизии, и связанный список в определенной корзине будет становиться все длиннее и длиннее, пока не достигнет порога.HashMapЯ больше не могу. Для повышения производительности связанный список, превышающий порог, будет преобразован в красно-черную древовидную структуру. Порог равен 8. То есть, если количество узлов связанного списка в одном сегменте больше 8, связанный список будет преобразован в красно-черное дерево.
Приведенное выше общее описаниеHashMapОбщая структура также является планом для дальнейшего изучения деталей. Мы выделим несколько ключевых моментов, чтобы объяснить их один за другим, от целого к деталям, уменьшению размерности и атаке.HashMap.
Следующий шаг — объяснить, почему он разработан в такой структуре, и подробный процесс генерации из простого массива в связанный список в ведре, а затем преобразование связанного списка в красно-черное дерево.
Знать несколько ключевых понятий
контейнер для хранения
потому чтоHashMapВнутренне для хранения содержимого используется массив, который определяется следующим образом:
transient Node<K,V>[] table;
Тип узла
стол - этоNodeмассив типа,NodeОпределен ли в нем статический внутренний класс, в основном включающий атрибуты hash, key, value и next. Например, когда мы используем метод put для добавления к нему пар ключ-значение позже, он будет преобразован в тип Node.
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
TreeNode
Как упоминалось ранее, когда связанный список в ведре достигает 8, связанный список будет преобразован в красно-черное дерево, котороеTreeNodeТипа, это тожеHashMapСтатический внутренний класс, определенный в .
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
}
емкость и емкость по умолчанию
Емкость — это длина массива таблиц, которую мы называем количеством сегментов. Его определение выглядит следующим образом
int threshold;
По умолчанию 16, если мы не укажем размер при инициализации, будет 16. Конечно, мы также можем сами указать начальный размер, иHashMapНачальный размер должен быть степенью числа 2.
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
количество элементов
Емкость указывает количество ведер, а размер означаетHashMapСколько пар ключ-значение на самом деле хранится в файлах .
transient int size;
Максимальная емкость
Длина таблицы также ограничена и не может быть бесконечной.HashMapУказанная максимальная длина равна 2 в 30-й степени.
static final int MAXIMUM_CAPACITY = 1 << 30;
коэффициент нагрузки
Это коэффициент, который работает вместе с порогом, по умолчанию 0,75. В обычных условиях не меняется.
final float loadFactor;
Порог расширения
阈值 = 容量 x 负载因子, предполагая текущийHashMapЕмкость составляет 16, а коэффициент загрузки по умолчанию равен 0,75, затем, когда размер достигает16 x 0.75=В 12 будет запущено расширение.
Инициализировать хэш-карту
использоватьHashMapОн должен быть инициализирован. Во многих случаях он создается с помощью конструктора без аргументов.
Map<String,String> map = new HashMap<>();
В этом случае все свойства являются значениями по умолчанию, например, мощность равна 16, а коэффициент загрузки равен 0,75.
Другой рекомендуемый метод инициализации — указать емкость по умолчанию, например указать емкость по умолчанию, равную 32.
Map<String,String> map = new HashMap<>(32);
ноHashMapТребуется, чтобы начальный размер был равен 2 в n-й степени, но нельзя требовать от каждого разработчика указывать требуемую начальную емкость.Например, что, если мы укажем начальный размер 7 или 18?
Ничего страшного,HashMapСуществует метод, специально отвечающий за преобразование переданного значения параметра в значение, которое ближе всего и больше или равно n-й степени указанного параметра, например, если указанный размер равен 7, конечная фактическая емкость равна 8. Если указанный размер равен 18. Если это так, конечная фактическая емкость составляет 32.
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);
}
Тот, кто выполняет это преобразование,tableSizeForметод, после преобразования присвойте окончательный результатthresholdПеременной, то есть начальной вместимостью, является количество ковшей, упомянутых в этой статье.
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;
}
tableSizeForИнтересен этот способ, сначала уменьшаем начальный параметр на 1, а потом делаем或等于а также无符号右移операцию и, наконец, вычислить близкую степень числа 2. На следующем рисунке показана серия операций, когда начальный параметр равен 18, а окончательный начальный размер равен 32.
Этот алгоритм очень интересен.Например, если начальный размер, который вы даете, равен 63, полученный результат равен 64. Если начальный размер задан 65, полученный результат равен 128, который всегда можно получить.Не меньше заданного начального размера и ближайшие 2 в n-й степениконечное значение .
Расшифровать основной принцип метода put
putЭтот метод является наиболее часто используемым методом добавления пар ключ-значение, а также самым сложным процессом.Процесс добавления пар ключ-значение включает в себяHashMapОсновные принципы в основном включают следующие пункты:
- При каких обстоятельствах он будет расширен и каковы правила расширения?
- Как определить индекс при вставке пар ключ-значение,
HashMapОн не вставлен по порядку, так что он действительно не станет массивом. - Как обеспечить уникальность ключа?
- Как справиться с коллизией хэшей?
- Что такое метод застежки-молнии?
- Как преобразовать связанный список в одном ведре в красно-черное дерево?
Ниже приведен исходный код метода put, где я прокомментировал.
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) {
HashMap.Node<K,V>[] tab; // 声明 Node 数组 tab
HashMap.Node<K,V> p; // 声明一个 Node 变量 p
int n, i;
/**
* table 定义 transient Node<K,V>[] table; 用来存储 Node 节点
* 如果 当前table为空，则调用resize() 方法分配数组空间
*/
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// n 总是为 2 的幂次方，(n-1) & hash 可确定 tab.length （也就是table数组长度）内的索引
// 然后 创建一个 Node 节点赋给当前索引
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//如果当前索引位置已经有值了，怎么办
// 拉链法出场
HashMap.Node<K,V> e;
K k;
// 判断 key 值唯一性
// p 是当前待插入索引处的值
// 哈希值一致并且（当前位置的 key == 待插入的key(注意 == 符号)，或者key 不为null 并且 key.equals(k)）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) //如果当前节点只有一个元素，且和待插入key一样 则覆盖
// 将 p（当前索引）节点临时赋予 e
e = p;
else if (p instanceof HashMap.TreeNode) // 如果当前索引节点是一颗树节点
//插入节点树中 并返回
e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 当前索引节点即不是只有一个节点，也不是一颗树，说明是一个链表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) { //找到没有 next 的节点，也就是最后一个
// 创建一个 node 赋给 p.next
p.next = newNode(hash, key, value, null);
// 如果当前位置+1之后大于 TREEIFY_THRESHOLD 则要进行树化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//执行树化操作
treeifyBin(tab, hash);
break;
}
//如果又发生key冲突则停止 后续这个节点会被相同的key覆盖
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;
// 当实际长度大于 threshold 时 resize
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Инициализировать массив в первый раз и расширить
в исполненииputпервым шагом является проверка того, является ли массив таблицы пустым или его длина равна 0. Если это так, это означает, что это первый раз, когда вставляется пара ключ-значение, и необходимо выполнить операцию инициализации массива таблицы. .
Кроме того, по мере добавления все большего количества пар ключ-значениеHashMapРазмер становится все больше и больше. Обратите внимание, что размер - это фактическое количество пар ключ-значение. Затем размер необходимо увеличить. Это не тогда, когда размер равен порогу (емкости) до расширения, а при достижении порога.Он начал расширяться,о пороге тоже говорилось выше,да容量 x 负载因子.
Зачем собирать, ведь для начальной инициализации и расширения используется один и тот же метод, называемыйresize(). Вот что я отметилresize()метод.
final HashMap.Node<K,V>[] resize() {
// 保存 table 副本，接下来 copy 到新数组用
HashMap.Node<K,V>[] oldTab = table;
// 当前 table 的容量，是 length 而不是 size
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 当前桶大小
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { //如果当前容量大于 0，也就是非第一次初始化的情况（扩容场景下）
if (oldCap >= MAXIMUM_CAPACITY) { //不能超过最大允许容量
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) // 双倍扩容
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // 初始化的场景（给定默认容量），比如 new HashMap(32)
newCap = oldThr; //将容量设置为 threshold 的值
else { // 无参数初始化场景，new HashMap()
// 容量设置为 DEFAULT_INITIAL_CAPACITY
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"})
HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
HashMap.Node<K,V> e;
//遍历 获得得到元素 赋给 e
if ((e = oldTab[j]) != null) { //如果当前桶不为空
oldTab[j] = null; // 置空回收
if (e.next == null) //节点 next为空的话 重新寻找落点
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof HashMap.TreeNode) //如果是树节点
//红黑树节点单独处理
((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 保持原顺序
HashMap.Node<K,V> loHead = null, loTail = null;
HashMap.Node<K,V> hiHead = null, hiTail = null;
HashMap.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;
}
Инициализировать в первый раз
putЦентральная строка метода сначала проверяет, пуст ли массив таблицы, и инициализирует его, если он пуст.
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
Первая инициализация делится на два случая: инициализация без параметров и инициализация с параметрами.HashMapПри инициализации я сказал, что по умолчанию значение отсутствия параметров равно 16, то есть длина таблицы равна 16. При инициализации с параметрами сначала используйтеtableSizeFor()Метод определяет фактическую емкость, и, наконец, выходит новый массив узлов.
HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
вnewCapЕмкость, по умолчанию 16 или пользовательская.
Еще одним важным этапом в этом процессе является техническое обслуживание.扩容阈值.
Расширение
putВ методе оценивается, когда размер (фактическое количество пар ключ-значение) достигаетthreshold(порог), запускается операция расширения емкости.
// 当实际长度大于 threshold 时 resize
if (++size > threshold)
resize();
HashMapСледуя правилу двойного расширения, размер после каждого расширения в два раза превышает размер до расширения. Кроме того, в конечном счете, базовое хранилище по-прежнему представляет собой массив. В Java нет настоящего динамического массива. Насколько велик массив при инициализации, тогда он всегда был таким большим. Как происходит расширение? ответ - создать новый массив, а затем скопировать в него данные старого массива.
При копировании могут возникнуть следующие ситуации:
- Если следующий атрибут узла пустой, значит, это самый обычный узел, а не связанный список в ведре и не красно-черное дерево, такой узел пересчитает позицию индекса и потом вставит.
- Если это красно-черное дерево, используйте
splitПринцип обработки метода заключается в том, чтобы разбить красно-черное дерево на два связанных списка TreeNode, а затем определить, меньше или равна ли длина каждого связанного списка 6. Если да, преобразовать TreeNode в связанный список в ведре , в противном случае преобразуйте его в красно-черное дерево. - Если это связанный список в сегменте, скопируйте связанный список в новый массив, чтобы убедиться, что порядок связанного списка остается неизменным.
Определить точку вставки
когда мы звонимputВ методе первым шагом является вычисление хеш-функции по ключу, вычисление этого значения заключается в последующем поиске точки приземления, то есть в какую корзину массива таблицы вставляться.
Алгоритм хэширования таков: получите хэш-код ключа, выполните 16-битный сдвиг вправо для хэш-кода, а затем XOR результата сдвига вправо с хэш-кодом. Этот код называется "функция возмущения», причина, по которой мы не используем hashCode напрямую, заключается в увеличении случайности и уменьшении количества коллизий хэшей.
/**
* 用来计算 key 的 hash 值
**/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
После получения этого хэш-значения эта операция будет выполненаi = (n - 1) & hash,вiявляется конечной рассчитанной позицией индекса.
Существует два сценария, в которых используется эта формула расчета индекса.putметод при вставке пар ключ-значение. Второй сценарий — когда resize используется для расширения емкости, после создания нового массива, и существующий узел перемещается в новый массив, если узел не связанный список или красно-черное дерево, а обычный Node node, он будет создан заново.Вычислите, чтобы найти позицию индекса в новом массиве.
Затем посмотрите на картинку, или картинка четкая.
HashMapТребуемая емкость должна быть равна 2 в степени n. Каждый должен знать двоичное представление числа 2 в степени n. Шестая степень числа 2 равна 6 0 справа налево, а затем седьмой бит равен 1. На следующем рисунке показан двоичный представление числа 2 в шестой степени.
тогда этоn-1После вычитания единицы все 0 после 1 в предыдущем двоичном представлении становятся 1, а бит, в котором находится 1, становится 0. Например, 64-1 становится 63, и его двоичное представление выглядит следующим образом.
На приведенном ниже рисунке в первых 4 строках указано, когда емкость карты равна 8, 16, 32 и 64, при условии, что емкость равна n, соответствующиеn-1Двоичное представление выглядит следующим образом: хвост красный, все 1 , вы можете предсказать, какая операция произойдет.
Правильно, подставьте такое бинарное представление в эту формулу(n - 1) & hash, индексный бит, который должен быть вставлен, наконец может быть определен. Затем посмотрите на три нижние линии рисунка, демонстрирующие предположение, что текущийHashMapЕмкость равна 64, а результат ключа, который будет вставлен после вычисления хэша, равен 99, подставьте формулу для расчета значения индекса, то есть（64-1）& 99, окончательный результат вычисления равен 35, то есть ключ упадет на позицию table[35].
ПочемуHashMapНеобходимо следить за тем, чтобы емкость была степенью двойки. Из двоичного представления видно, что если битов 1 несколько, то она сравнивается со значением хеша.与运算При лучше обеспечить однородность результата конечного хеша, что во многом определяется значением хеша.
Как обеспечить уникальность ключа
HashMapЕсли один и тот же ключ не разрешен, как обеспечить уникальность ключа?Код решения выглядит следующим образом.
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
Во-первых, значения, вычисляемые алгоритмом хеширования, должны быть равны, а вычисляемый результат — это int, поэтому о нем можно судить по символу ==. Только этого условия недостаточно.Чтобы узнать, что означает коллизия хэшей, возможно, что итоговое значение хеш-функции, сгенерированное двумя разными ключами, будет одинаковым.
И вставляемый ключ == ключ, который уже существует в текущем индексе, или ключ, который нужно вставить.equals (ключ, который уже существует в текущем индексе), обратите внимание, что==и equals является отношением ИЛИ. Символ == означает, что это один и тот же объект, а равенство используется, чтобы убедиться, что два объекта имеют одинаковое содержимое.
Если ключ представляет собой базовый тип данных, такой как int, одно и то же значение должно быть равно, и сгенерированный хэш-код также будет таким же.
StringТип является наиболее часто используемым типом ключа.Все мы знаем, что хэш-код, сгенерированный одной и той же строкой, одинаков, и строка может быть оценена как равная по равенству.
Но что, если в качестве ключа используется ссылочный тип, например, я определяюMoonKeyкак тип значения ключа
public class MoonKey {
private String keyTile;
public String getKeyTile() {
return keyTile;
}
public void setKeyTile(String keyTile) {
this.keyTile = keyTile;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
MoonKey moonKey = (MoonKey) o;
return Objects.equals(keyTile, moonKey.keyTile);
}
}
Затем используйте следующий код, чтобы добавить дважды, вы говорите, что длина размера равна 1 или 2?
Map<MoonKey, String> m = new HashMap<>();
MoonKey moonKey = new MoonKey();
moonKey.setKeyTile("1");
MoonKey moonKey1 = new MoonKey();
moonKey1.setKeyTile("1");
m.put(moonKey, "1");
m.put(moonKey1, "2");
System.out.println(hash(moonKey));
System.out.println(hash(moonKey1));
System.out.println(m.size());
Ответ 2, почему, потому чтоMoonKeyне переписыватьhashCodeметод, значение хеш-функции moonkey и moonKey1 не может быть одинаковым, если оно не переписаноhashCodeметод, значение по умолчанию наследуется отObjectметод hashCode, и каждыйObjectХэш-значение объекта уникально.
фокус, правильный подход должен состоять в том, чтобы добавитьhashCodeпереписать.
@Override
public int hashCode() {
return Objects.hash(keyTile);
}
Вот почему требуется переписываниеequalsметод также должен быть переопределенhashCodeОдна из причин метода. Если два объекта равны при вызове метода equals, то вызов метода hashCode для обоих объектов должен возвращать одно и то же целое число. С этой основой мы можем гарантироватьHashMapилиHashSetКлюч уникален.
Что делать, если произошла коллизия хэшей
Как упоминалось ранее, хэш-код, сгенерированный равными объектами, также должен быть равен, но неравные объекты используют один и тот же хэш-код.hashТакже возможно сгенерировать такое же значение после вычисления метода, что называется коллизией хэшей. Хотя столкновение в значительной степени удалось избежать с помощью алгоритма, его нельзя избежать.
После возникновения коллизии естественный производный индекс (то есть сегмент) в массиве таблиц также остается тем же. Что мне теперь делать? Как поместить несколько пар "ключ-значение" в сегмент?
молния метод
Как упоминалось в начале статьи,HashMapНе просто массив. Когда происходит столкновение, примите его спокойно. Существует метод, называемый методом застежки-молнии, а не застежка-молния на одежде. Вместо этого, когда происходит столкновение, в текущей корзине вытягивается связанный список, так что объяснение разумно.
Ключевые понятия, упомянутые ранееNodeтип, который имеет свойство, называемоеnext, предназначенный для такого рода связанных списков, как показано на следующем рисунке. Узел 1, узел 2 и узел 3 попадают в одно и то же ведро.В настоящее время для обработки должен использоваться связанный список, узел1.следующий=узел2, узел2.следующий=узел3, чтобы связанный список был связан вместе. А node3.next = null, значит, это хвост связанного списка.
Когда новый элемент готов к вставке в связанный список, вместо метода вставки заголовка используется метод вставки конца.В версии JDK 1.7 используется метод вставки заголовка, но есть проблема с методом вставки заголовка, т.е. , он выполняется в два потока.Когда resize() расширяется, он, вероятно, вызовет круговой связанный список, что приведет к бесконечному циклу в методе get.
Преобразование связанного списка в дерево
Связный список не является конечной структурой для обработки коллизий.Окончательной структурой является красно-черное дерево.Когда длина связанного списка достигает 8 и появляются новые элементы, преобразование из связанного списка в красно-черное дерево должен начаться. методtreeifyBinзаключается в завершении этого процесса.
Красно-черное дерево используется из соображений производительности, а скорость поиска красно-черного дерева лучше, чем у связанного списка. Тогда почему бы сразу не сгенерировать красно-черное дерево в начале, а перейти на дерево после того, как длина связанного списка превысит 8?
Во-первых, вероятность коллизии хэшей все же очень мала, в большинстве случаев это ведроNode, даже если произойдет коллизия, вероятность попадания в ведро еще меньше, поэтому длина связанного списка имеет мало шансов достичь 8. Если длина связанного списка достигает 8, это означает, что текущийHashMapКоличество элементов в уже очень велико, и целесообразно использовать красно-черное дерево для повышения производительности в это время. И наоборот, еслиHashMapОбщее количество элементов очень мало, и даже если используется красно-черное дерево, улучшение производительности невелико, а использование пространства красно-черным деревом намного больше, чем у связанного списка.
получить метод
T value = map.get(key);
Например, получение значения значения через ключ с помощью приведенного выше оператора является наиболее часто используемым методом.
Посмотрите на картинку, чтобы понять, при звонкеgetПосле метода первым шагом является определение позиции индекса, которую мы называем позицией ведра, метода иputМетод тот же, он используется первымhashэтофункция возмущенияОпределите хэш-значение, затем используйте(n-1) & hashПолучить индекс. Разве это не ерунда, конечно, это должно быть сputВремя одинаковое, как я могу найти правильное положение, если оно отличается.
Как только местоположение ведра определено, могут произойти три вещи:
Тип одного узла:То есть в этом сегменте есть только одна пара ключ-значение, которая такжеHashMapВ , если нет коллизии хэшей, есть большинство типов. фактическиHashMapВ идеале, это было бы так, и это было бы идеально для всего этого типа.
Тип списка:Если вы обнаружите, что ключ get находится в структуре связанного списка, вам нужно просмотреть связанный список, пока не найдете узел с тем же ключом.
Виды красно-черных деревьев:Когда длина связанного списка превышает 8, он преобразуется в красно-черное дерево, а если обнаруживается, что найденное ведро является красно-черным деревом, то выполняется его поиск с использованием метода быстрого поиска, свойственного красно-черному дереву. .
Кроме того,Map.containsKeyМетод действительно работаетgetметод.
метод удаления
removeа такжеput,getМетод аналогичен, все сначала находят хэш-значение ключа, а потом(n-1) & hashПолучите позицию индекса, а затем выполните различные действия в зависимости от типа узла.
Тип одного узла:Непосредственно замените текущий элемент Bucket удаленным node.next , который на самом деле равен нулю.
Тип списка:Если это тип связанного списка, задайте для следующего свойства узла перед удаляемым узлом значение node.next.
Виды красно-черных деревьев:Если это красно-черное дерево, вызывается метод удаления узлов красно-черного дерева.Здесь, если количество узлов находится в диапазоне от 2 до 6, структура дерева упрощается до структуры связанного списка.
Не потокобезопасный
HashMapКонтроля параллелизма нет. Если вы хотите использовать его в многопоточной среде с высоким параллелизмом, используйтеConcurrentHashMap. В то же время, если несколько потоков выполняют операцию размещения одновременно, если позиции вычисляемого индекса (сегмента) совпадают, это приведет к тому, что предыдущий ключ будет перезаписан последним ключом.
Например, поток A и поток B на рисунке ниже выполняют операцию размещения одновременно.По случайному совпадению вычисленные индексы равны 2. В это время и поток A, и поток B считают, что ведро с индексом 2 пусто, а затем вставить значение.Да, поток A сначала поставил пару ключ-значение key1 = 1, но затем поток B снова поставил key2 = 2, поток A сказал, что он плачет и занят работой напрасно. Последнее значение в корзине с индексом 2 — key2=2, то есть сохраненное значение потока A перезаписывается.
Суммировать
Я не говорил этого раньше,HashMapНе зря его так усложняют, самый большой его плюс в том, что он быстрый, особенноgetДанные уровня O(1) напрямую определяют положение индекса.
HashMapЭто не простая структура массива.При возникновении коллизии хэшей для создания связанного списка будет использоваться метод молнии.Когда связанный список больше 8, он будет преобразован в красно-черное дерево.Красно-черный дерево может значительно улучшить производительность.
HashMapЕмкость должна быть равна 2 в степени n. Это сделано для того, чтобы расчет хэша для нахождения индекса был более однородным. Формула для расчета индекса:(n - 1) & hash.
HashMapКогда количество пар ключ-значение достигает порога раскрытия"容量 x 负载因子», чтобы расширить возможности, и каждое расширение в два раза больше, чем предыдущее. В процессе расширения позиция индекса элемента типа одиночного узла будет пересчитана.Если это красно-черный узел дерева, используйтеsplitМетод пересматривает, следует ли превратить красно-черное дерево в связанный список.
Не жди сильного мужика, сначала поставь лайк, меня вечно трахают зря, и мое тело этого не выдерживает!
Я коршун, общественный номер "Воздушный змей в древности". Программист-поощритель с глубиной и широтой, пастырский фермер-кодировщик, который планировал писать стихи, но написал код! Вы можете подписаться на меня сейчас или никогда не поздно читать исторические статьи.