Сначала посмотрите, а потом лайкните, дайте себе время подумать, поиск в WeChat [Тихий король 2] Обратите внимание на этого красивого программиста, который делает вид, что полагается на талант. Эта статья GitHub github.com/itwangerОн был включен, а также есть вопросы для интервью, организованные ведущими производителями, а также моя серия статей.
Серия List почти закончена, самое главное в однопоточной среде этоArrayListа такжеLinkedList, самое главное в многопоточной среде этоCopyOnWriteArrayList, новые учащиеся могут щелкнуть ссылку, чтобы просмотреть точки знаний List. Затем я возьму HashMap, чтобы подняться на гору.Обратите внимание, что это не гора Люфэн, это чисто для тренировки моего тела, нет-нет-нет, это просто для того, чтобы приблизиться к HashMap, студенты будьте осторожны, чтобы не отстать.
Проще говоря, HashMap — это карта, в которой хранятся пары ключ-значение, каждый ключ может быть точно сопоставлен со значением, и тогда мы можем быстро найти соответствующее значение по этому ключу.
Для списка, если вы хотите найти значение временной сложности, если список отсортирован, временная сложность может быть уменьшена до(метод бинарного поиска), но если это Карта, то в большинстве случаев временная сложность может быть снижена до.
Давайте посмотрим на характеристики HashMap:
-
Ключи HashMap должны быть уникальными и не могут повторяться.
-
Ключи HashMap могут быть нулевыми, но такой ключ может быть только один, значения могут иметь несколько нулей.
-
HashMap неупорядочен, он не гарантирует какой-либо определенный порядок элементов.
-
HashMap не является потокобезопасным; в многопоточной среде рекомендуется использовать ConcurrentHashMap или использовать
Collections.synchronizedMap(hashMap)Преобразование HashMap в синхронизацию потоков. -
Только связанный ключ может быть использован для получения значения.
-
HashMap может хранить только объекты, поэтому примитивный тип данных должен использовать свой тип оболочки, например, int должен быть Integer.
-
HashMap реализует интерфейсы Cloneable и Serializable, поэтому его можно копировать и сериализовать.
01. Важные поля HashMap
HashMap имеет 5 очень важных полей, давайте посмотрим. (версия JDK — 14)
transient Node<K,V>[] table;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;
1) таблица представляет собой массив типа Node, длина по умолчанию 16, в первом исполненииresize()метод при инициализации.
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
final HashMap.Node<K,V>[] resize() {
newCap = DEFAULT_INITIAL_CAPACITY;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
}
Node — это внутренний класс HashMap, реализующий интерфейс Map.Entry, который по сути является парой ключ-значение.
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
HashMap.Node<K,V> next;
Node(int hash, K key, V value, HashMap.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) {
...
}
}
2) размер — это количество пар ключ-значение, фактически хранящихся в HashMap, которое отличается от длины таблицы.
Чтобы проиллюстрировать это, давайте посмотрим на следующий код:
HashMap<String,Integer> map = new HashMap<>();
map.put("1", 1);
Объявите HashMap, затем поместите пару ключ-значение. существуетput()Установите точку останова в методе и добавьте часы, когда метод приближается к концу (table.length), и можно наблюдать следующие результаты.
То есть размер массива равен 16, а размер HashMap равен 1.
3) modCount в основном используется для записи количества реальных операций HashMap, чтобы итератор выполнялсяremove()ConcurrentModificationException выбрасывается быстро при ожидании операций, потому что HashMap, как и ArrayList, также отказоустойчив.
Для получения дополнительной информации о ConcurrentModificationException щелкните ссылку ниже, чтобы просмотреть содержание подраздела 03.
4) Пороговое значение используется для определения максимального количества пар клавишных пар, которые могут удерживать HASHMAP, и его значение равно размеру массива * коэффициент нагрузки. По умолчанию это 12 (16 * 0,75), которое является первым выполнениемresize()Время метода.
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
final HashMap.Node<K,V>[] resize() {
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
5) loadFactor - коэффициент загрузки. Значение по умолчанию 0.75 - это сбалансированный выбор по пространственной и временной эффективности. Как правило, изменять его не рекомендуется. Как и я, старый новичок, проработавший более десяти лет, никогда не модифицировал это значение.
02. Хэш-алгоритм HashMap
Хэш, обычно переводится как «хэш», также напрямую транслитерируется как «хеш», что это значит? Это отображение данных любой длины в поле фиксированной длины (хеш-значение) с помощью алгоритма.
Чтобы быть более интуитивным, нужно смешать строку данных wang и вывести другую er данных фиксированной длины в качестве функции data wang. Обычно мы используем строку отпечатков пальцев для отображения определенного человека. Не стоит недооценивать отпечатки пальцев размером с палец. Трудно найти второй такой же, как у вас в вашем диапазоне (алгоритм хэширования людей очень мощный, у вас есть?).
Для любых двух разных блоков данных вероятность одинакового значения хеш-функции крайне мала, то есть для заданного блока данных крайне сложно найти блок данных с одинаковым значением хеш-функции. Более того, для блока данных, даже если изменить всего один его бит, изменение его хеш-значения будет очень большим — это и есть значение Hash!
Студенты уже знают, что базовая структура данных HashMap представляет собой массив. Будь то добавление, удаление или поиск пар ключ-значение, очень важно найти индекс массива.
Какой путь - это Hashmap, чтобы найти индекс?
первый шаг,hash()метод:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Второй шаг,putVal()Строка кода в методе:
n = (tab = resize()).length;
i = (n - 1) & hash;
Чтобы упростить понимание, я объединил двухэтапный подход:
String [] keys = {"沉","默","王","二"};
for (String k : keys) {
int hasCode = k.hashCode();
int right = hasCode >>> 16;
int hash = hasCode ^ right;
int i = (16 - 1) & hash;
System.out.println(hash + " 下标：" + i);
}
1)k.hashCode()Значение hashCode, используемое для вычисления ключа. Для любого данного объекта, пока егоhashCode()Возвращаемое значение такое же, тогдаhash()Хэш-код, рассчитанный методом, всегда один и тот же.
Для этого требуется, чтобы объект, являющийся ключом, был неизменяемым, иhashCode()Метод должен быть достаточно умным, чтобы возвращать значения hashCode, которые максимально не повторяются, например класс String.
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;
}
2)>>>Это беззнаковый оператор сдвига вправо, старшие биты заполнены 0, а количество сдвинутых битов заполнено 0.
3)^является оператором исключающее ИЛИ, и правила его работы: 1^0 = 1, 1^1 = 0, 0^1 = 1, 0^0 = 0.
4)&Для побитового оператора И правило операции состоит в том, чтобы преобразовать числа с обеих сторон в двоичные биты, а затем вычислить окончательное значение.Правило операции (только два истинны) 1&1=1, 1&0=0, 0&1=0, 0&0= 0.
о>>>,^,&В этой статье не будут подробно изучаться операторы с участием бинарников, желающие могут изучить ее самостоятельно.
Если четыре строки «Шэнь», «Мо», «Ван», «Эр», они проходятhash()Метод рассчитанных значений и индексов выглядит следующим образом:
27785 下标：9
40664 下标：8
29579 下标：11
20108 下标：12
Надо сказать, что такой алгоритм хеширования очень хитрый, особенно второй шаг.
Длина базового массива HashMap всегда равна 2 в n-й степени, когда длина всегда равна 2 в n-й степени,
(length - 1) & hashОперация эквивалентна модулю длины массива, то естьhash%length, но & более эффективен, чем % .
03. Хэш-картаput()метод
Мы понимаем хеш-алгоритм HashMap, но, кажется, есть небольшие сомнения, что, если вычисленное значение хеш-функции столкнется?
Например, значение хеш-функции, рассчитанное «Shen X», равно 27785, его нижний индекс равен 9, и он находится на позиции нижнего индекса массива 9; через некоторое время приходит другое значение хеш-функции, рассчитанное «Shen Y». 27785, а нижний индекс тоже 9. Его тоже нужно поставить в позицию, где нижний индекс 9. Что делать?
Чтобы смоделировать эту ситуацию, давайте создадим новый пользовательский класс ключей.
public class Key {
private final String value;
public Key(String value) {
this.value = value;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass())
return false;
Key key = (Key) o;
return value.equals(key.value);
}
@Override
public int hashCode() {
if (value.startsWith("沉")) {
return "沉".hashCode();
}
return value.hashCode();
}
}
существуетhashCode()В метод добавлено суждение.Если ключ начинается с «Shen», будет возвращено значение hashCode «Shen», что означает, что «Shen X» и «Shen Y» появятся в одном и том же индексе массива. , превосходный.
HashMap<Key,String> map = new HashMap<>();
map.put(new Key("沉X"),"沉默王二X");
map.put(new Key("沉Y"),"沉默王二Y");
Тогда взглянитеput()Исходный код метода:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
put()метод будет вызываться первымhash()Метод вычисляет хеш-значение ключа, а затем вызывает внутренний методputVal():
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
// ①、数组 table 为 null 时，调用 resize 方法创建默认大小的数组
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// ②、计算下标，如果该位置上没有值，则填充
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
HashMap.Node<K,V> e; K k;
// ③、如果键已经存在了，并且 hash 值相同，直接覆盖
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
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) {
p.next = newNode(hash, key, value, null);
// 如果链表长度大于 8 转换为红黑树处理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果键已经存在了，并且 hash 值相同，直接覆盖
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;
}
Я добавил несколько комментариев к коду, студенты должны потратить некоторое время на его изучение.
Если есть конфликт хэшей, соответствующий оператор else в ② будет выполнен, чтобы сначала определить, равны ли ключи, и если они равны, они будут перезаписаны напрямую; в противном случае выполните ④, чтобы выполнить красно-черную обработку дерева; если нет, выполните ⑤, чтобы назначить следующее значение предыдущего узла для нового узла.
То есть, если хеш столкнется, то в ту же позицию массива будет добавлен связанный список, если длина связанного списка больше 8, он будет преобразован в красно-черное дерево для обработки.
Это большие пасти крупного рогатого скота, которые часто говорят «метод цепных адресов», проще говоря, он добавляется в список массивов, потому что список эффективности запросов относительно низок (сложность времени), в Java 8 добавлено красно-черное дерево (временная сложность).
Оставьте небольшую домашнюю работу, студенты могут учиться, когда ключ равен нулю, где хранится пара ключ-значение?
04. Хэш-картаget()метод
Понимать алгоритм хеширования HashMap иput()метод,get()метод прост для понимания.
public V get(Object key) {
HashMap.Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
Сначала вычислить хеш-значение ключа, когда хэш-значение определено, определяется позиция нижнего индекса пары ключ-значение в массиве, а затем вызватьgetNode()метод:
final HashMap.Node<K,V> getNode(int hash, Object key) {
HashMap.Node<K,V>[] tab; HashMap.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 HashMap.TreeNode)
return ((HashMap.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;
}
вfirst = tab[(n - 1) & hash]Значение, соответствующее ключу, можно быстро определить, если ключ равен и хэш ключа равен, то он будет возвращен напрямую, если хеш ключа конфликтует, сначала определить, является ли это красно-черным деревом. , а если нет, пройтись по связанному списку.
05. Наконец
Если честно, прежде чем написать эту статью, у меня не было такого глубокого понимания Hashmap, но после написания этой статьи я осмелился ударить мою грудь и клянусь: «Я действительно освоил Hashmap, одноклассников. Тот, кто просит меня в Будущее может сбросить эту статью на него ».
Хотя это восхождение на гору очень утомительно, оно действительно полезно и того стоит!
Я Тихий Король Эр, красивый программист, который делает вид, что полагается на свой талант.Подпишитесь, чтобы повысить эффективность обучения, не забудьте три раза подряд ах, лайк, избранное, оставить сообщение, я не выбираю, Олли дает 🌹.
Примечание. Если в статье есть какие-либо проблемы, пожалуйста, исправьте их.
Если вы считаете, что статья полезна для вас, добро пожаловать в поиск WeChat »Тихий король 2«Первый раз, чтобы прочитать, ответьте ключевое слово»новичек«Вы можете бесплатно получить версию 2.0 «Java Xiaobai от новичка до самонадеянного» с более чем 40 000 слов моей печени; эта статьяGitHub github.com/itwangerОн был записан, добро пожаловать в звезду.