предисловие
На этот раз я буду учиться с тобойHashMap,HashMapМы часто используем его на работе, и его также часто спрашивают на собеседованиях, потому что он содержит много точек знаний, которые могут быть хорошей проверкой личной подготовки. Но такая важная вещь, почему я не выучил ее в начале, ведь она состоит из множества базовых структур данных и некоторых идей оформления кода. Мы должны изучить эти основы, а затем научитьсяHashMap, так что мы можем понять это лучше. Древние говорили: Нет спешки, нет малой прибыли. Спешка не поможет, а маленькая прибыль сделает невозможными большие дела.
HashMapНа самом деле этоArrayListиLinkedListструктура данных плюсhashCodeиequalsидея метода. Учащиеся, которые не понимают вышеупомянутые знания, могут открыть мои прошлые записи статей.
Ниже я узнаю наши в виде вопросов интервью-HashMap(Анализ исходного кода основан на JDK8, дополненном JDK7), содержание вопроса и ответа является только правильнымHashMapКраткое изложениеHashMapПростой для понимания анализ, я узналHashMapЭто также в основном изучается из этой статьи, настоятельно рекомендуется: техническая команда Meituan Dianping.Переосмысление HashMap в серии Java 8
Эта статья одновременно публикуется в Цзяньшу:у-у-у. Краткое описание.com/afraid/32 67 9 oh 7…
Вопросы и ответы
1.
просить:HashMapВы использовали его? Можете ли вы рассказать мне о его основном использовании?
отвечать:
- Работал, часто использую в повседневной работе
HashMapЭта структура данных,HashMapоснован наMapПара ключ-значение, реализованная интерфейсом<key,value>структура хранения, позволяющаяnullзначение, в то же время неупорядоченное, несинхронизированное (т.е. небезопасное для потоков).HashMapБазовая реализация представляет собой массив + связанный список + красно-черное дерево (JDK1.8 добавил красно-черную часть дерева). Когда он сохраняет и ищет данные, он основывается на ключеkeyизhashCodeЗначение , вычисляет конкретное место хранения.HashMapКлюч, который разрешает не более одной записиkeyзаnull,HashMapРутинные операции, такие как добавление, удаление, изменение и поиск, имеют хорошую эффективность выполнения.ArrayListиLinkedListКомпромиссная реализация других структур данных.
Образец кода:
// 创建一个HashMap，如果没有指定初始大小，默认底层hash表数组的大小为16
HashMap<String, String> hashMap = new HashMap<String, String>();
// 往容器里面添加元素
hashMap.put("小明", "好帅");
hashMap.put("老王", "坑爹货");
hashMap.put("老铁", "没毛病");
hashMap.put("掘金", "好地方");
hashMap.put("王五", "别搞事");
// 获取key为小明的元素 好帅
String element = hashMap.get("小明");
// value : 好帅
System.out.println(element);
// 移除key为王五的元素
String removeElement = hashMap.remove("王五");
// value : 别搞事
System.out.println(removeElement);
// 修改key为小明的元素的值value 为 其实有点丑
hashMap.replace("小明", "其实有点丑");
// {老铁=没毛病, 小明=其实有点丑, 老王=坑爹货, 掘金=好地方}
System.out.println(hashMap);
// 通过put方法也可以达到修改对应元素的值的效果
hashMap.put("小明", "其实还可以啦,开玩笑的");
// {老铁=没毛病, 小明=其实还可以啦,开玩笑的, 老王=坑爹货, 掘金=好地方}
System.out.println(hashMap);
// 判断key为老王的元素是否存在(捉奸老王)
boolean isExist = hashMap.containsKey("老王");
// true , 老王竟然来搞事
System.out.println(isExist);
// 判断是否有 value = "坑爹货" 的人
boolean isHasSomeOne = hashMap.containsValue("坑爹货");
// true 老王是坑爹货
System.out.println(isHasSomeOne);
// 查看这个容器里面还有几个家伙 value : 4
System.out.println(hashMap.size());-
HashMapБазовая реализация представляет собой массив + связанный список + красно-черное дерево (JDK1.8 добавил красно-черную часть дерева), основные компоненты:
-
int size;для записиHashMapФактическое количество элементов хранения; -
float loadFactor;Коэффициент нагрузки (по умолчанию 0,75, это свойство подробно объясняется позже). -
int threshold;Порог следующего расширения, при достижении порога сработает механизм расширенияresize(пороговое значение = вместимость контейнера * коэффициент загрузки). Другими словами, после того, как контейнер имеет определенную емкость, чем больше коэффициент загрузки, тем больше элементов пары ключ-значение он может содержать. -
Node<K,V>[] table;Базовый массив, который действует как хеш-таблица, используется для хранения элементов, соответствующих хеш-позиции.Node<K,V>, длина этого массива всегда равна 2 в степени N. (Конкретные причины будут подробно объяснены позже)
Образец кода:
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
·····
/* ---------------- Fields -------------- */
/**
* 哈希表，在第一次使用到时进行初始化，重置大小是必要的操作，
* 当分配容量时，长度总是2的N次幂。
*/
transient Node<K,V>[] table;
/**
* 实际存储的key - value 键值对 个数
*/
transient int size;
/**
* 下一次扩容时的阈值
* (阈值 threshold = 容器容量 capacity * 负载因子 load factor).
* @serial
*/
int threshold;
/**
* 哈希表的负载因子
*
* @serial
*/
final float loadFactor;
·····
}- в
Node<K,V>[] table;Основными элементами хранилища хеш-таблиц являютсяNode<K,V>,Node<K,V>Включают:
-
final int hash;Хэш-значение элемента, которое определяет, где хранится элементNode<K,V>[] table;позицию в хеш-таблице. Зависит отfinalмодификация, известно, что когдаhashПосле того, как значение определено, его нельзя изменить. -
final K key;ключ, поfinalмодификация, известно, что когдаkeyПосле того, как значение определено, его нельзя изменить. -
V value;ценность -
Node<K,V> next;Запишите узел следующего элемента (структура с одним связанным списком, используемая для разрешения конфликтов хэшей)
Образец кода:
/**
* 定义HashMap存储元素结点的底层实现
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//元素的哈希值 由final修饰可知，当hash的值确定后，就不能再修改
final K key;// 键，由final修饰可知，当key的值确定后，就不能再修改
V value; // 值
Node<K,V> next; // 记录下一个元素结点(单链表结构，用于解决hash冲突)
/**
* Node结点构造方法
*/
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;//元素的哈希值
this.key = key;// 键
this.value = value; // 值
this.next = next;// 记录下一个元素结点
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
/**
* 为Node重写hashCode方法，值为：key的hashCode 异或 value的hashCode
* 运算作用就是将2个hashCode的二进制中，同一位置相同的值为0，不同的为1。
*/
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
/**
* 修改某一元素的值
*/
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
/**
* 为Node重写equals方法
*/
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}2.
В: Можете ли вы сказать мнеHashMapЯвляется ли это основополагающим принципом реализации общих операций? как хранилищеput(K key, V value), найтиget(Object key),Удалитьremove(Object key),Исправлятьreplace(K key, V value)и так далее.
отвечать:
- перечислить
put(K key, V value)Добавить действиеkey-valueПри использовании пар ключ-значение выполняются следующие операции:
-
Хэш-таблица суждений
Node<K,V>[] tableпусто илиnull, если да, выполнитьresize()метод расширения. -
Согласно вставленному значению ключа
keyизhashзначение, через(n - 1) & hashтекущего элементаhashценность &hashДлина таблицы - 1 (фактическиhashценность %hashдлина таблицы) для расчета места храненияtable[i]. Если в месте хранения нет элемента, новый узел будет сохранен в этом месте.table[i]. -
Если в месте хранения уже есть элемент пары ключ-значение, определите значение элемента в этом месте.
hashценность иkeyНезависимо от того, согласуется ли значение с текущим элементом операции, согласованность оказывается модификацией.valueдействовать, покрыватьvalueВот и все. -
В текущем месте хранения есть элементы, но они не согласуются с текущим элементом операции, это доказывает, что это место
table[i]Произошел конфликт хэшей, тогда, определив, является ли головной узелtreeNode,еслиtreeNodeЭто доказывает, что структура этой позиции представляет собой красно-черное дерево, и добавлен новый узел в виде красно-черного дерева. -
Если это не красно-черное дерево, оно оказывается односвязным списком, вставьте новый узел в последнюю позицию связанного списка, а затем оцените, больше или равна ли длина текущего связанного списка 8 , а затем преобразовать связанный список текущего места хранения в красно-черное дерево. Если обнаружено во время обхода
keyуже существует, он напрямую перезаписываетсяvalue. -
После успешной вставки определите, что количество хранимых в настоящее время пар ключ-значение превышает пороговое значение.
thresholdДа, расширить.
Образец кода:
/**
* 添加key-value键值对
*
* @param key 键
* @param value 值
* @return 如果原本存在此key，则返回旧的value值，如果是新增的key-
* value，则返回nulll
*/
public V put(K key, V value) {
//实际调用putVal方法进行添加 key-value 键值对操作
return putVal(hash(key), key, value, false, true);
}
/**
* 根据key 键 的 hashCode 通过 “扰动函数” 生成对应的 hash值
* 经过此操作后，使每一个key对应的hash值生成的更均匀，
* 减少元素之间的碰撞几率（后面详细说明）
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* 添加key-value键值对的实际调用方法（重点）
*
* @param hash key 键的hash值
* @param key 键
* @param value 值
* @param onlyIfAbsent 此值如果是true, 则如果此key已存在value，则不执
* 行修改操作
* @param evict 此值如果是false，哈希表是在初始化模式
* @return 返回原本的旧值, 如果是新增，则返回null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 用于记录当前的hash表
Node<K,V>[] tab;
// 用于记录当前的链表结点
Node<K,V> p;
// n用于记录hash表的长度，i用于记录当前操作索引index
int n, i;
// 当前hash表为空
if ((tab = table) == null || (n = tab.length) == 0)
// 初始化hash表，并把初始化后的hash表长度值赋值给n
n = (tab = resize()).length;
// 1）通过 (n - 1) & hash 当前元素的hash值 & hash表长度 - 1
// 2）确定当前元素的存储位置，此运算等价于 当前元素的hash值 % hash表的长度
// 3）计算出的存储位置没有元素存在
if ((p = tab[i = (n - 1) & hash]) == null)
// 4) 则新建一个Node结点，在该位置存储此元素
tab[i] = newNode(hash, key, value, null);
else { // 当前存储位置已经有元素存在了(不考虑是修改的情况的话，就代表发生hash冲突了)
// 用于存放新增结点
Node<K,V> e;
// 用于临时存在某个key值
K k;
// 1)如果当前位置已存在元素的hash值和新增元素的hash值相等
// 2)并且key也相等，则证明是同一个key元素，想执行修改value操作
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;// 将当前结点引用赋值给e
else if (p instanceof TreeNode) // 如果当前结点是树结点
// 则证明当前位置的链表已变成红黑树结构，则已红黑树结点结构新增元素
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {// 排除上述情况，则证明已发生hash冲突，并hash冲突位置现时的结构是单链表结构
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
// 大于等于8则将链表转换成红黑树
treeifyBin(tab, hash);
break;
}
// 如果链表中已经存在对应的key，则覆盖value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // 已存在对应key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) //如果允许修改，则修改value为新值
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 当前存储键值对的数量 大于 阈值 是则扩容
if (++size > threshold)
// 重置hash大小，将旧hash表的数据逐一复制到新的hash表中（后面详细讲解）
resize();
afterNodeInsertion(evict);
// 返回null，则证明是新增操作，而不是修改操作
return null;
}- перечислить
get(Object key)Действие по ключуkeyнайти соответствующийkey-valueПри использовании пар ключ-значение выполняются следующие операции:
1. Звоните первымhash(key)метод расчетаkeyизhashценность
2. По ключевому значению поискаkeyизhashзначение, через(n - 1) & hashтекущего элементаhashценность &hashДлина таблицы - 1 (фактическиhashценность %hashдлина таблицы) для расчета места храненияtable[i], чтобы определить, есть ли элемент в месте хранения.
- Если в ячейке хранения есть элемент, сначала сравнивается элемент головного узла, если элемент головного узла
keyизhashценность и получитьkeyизhashзначение равно, а головной узелkeyсебя и приобретатьkeyЕсли они равны, верните головной узел в эту позицию. - Если в месте хранения нет элемента, вернуть
null.
3. Если в ячейке хранения хранятся элементы, но элемент головного узла не является элементом для поиска, вам необходимо пройти по ячейке для поиска.
4. Сначала определите, является ли головной узелtreeNode,еслиtreeNodeДокажите, что структура этой локации представляет собой красно-черное дерево, пройдите, чтобы найти узел в виде красного дерева, если нет, вернитесьnull.
5. Если это не красно-черное дерево, то оно оказывается односвязным списком. Пройдите по односвязному списку и сравните узлы связанного списка один за другим.keyизhashценность и получитьkeyизhashзначение равно, и узел связанного спискаkeyсебя и приобретатьkeyЕсли они равны, узел возвращается, а соответствующий узел не найден в конце обхода.keyузел, возвратnull.
Образец кода:
/**
* 返回指定 key 所映射的 value 值
* 或者 返回 null 如果容器里不存在对应的key
*
* 更确切地讲，如果此映射包含一个满足 (key==null ? k==null :key.equals(k))
* 的从 k 键到 v 值的映射关系，
* 则此方法返回 v；否则返回 null。（最多只能有一个这样的映射关系。）
*
* 返回 null 值并不一定 表明该映射不包含该键的映射关系；
* 也可能该映射将该键显示地映射为 null。可使用containsKey操作来区分这两种情况。
*
* @see #put(Object, Object)
*/
public V get(Object key) {
Node<K,V> e;
// 1.先调用 hash(key)方法计算出 key 的 hash值
// 2.随后调用getNode方法获取对应key所映射的value值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* 获取哈希表结点的方法实现
*
* @param hash key 键的hash值
* @param key 键
* @return 返回对应的结点，如果结点不存在，则返回null
*/
final Node<K,V> getNode(int hash, Object key) {
// 用于记录当前的hash表
Node<K,V>[] tab;
// first用于记录对应hash位置的第一个结点，e充当工作结点的作用
Node<K,V> first, e;
// n用于记录hash表的长度
int n;
// 用于临时存放Key
K k;
// 通过 (n - 1) & hash 当前元素的hash值 & hash表长度 - 1
// 判断当前元素的存储位置是否有元素存在
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {//元素存在的情况
// 如果头结点的key的hash值 和 要获取的key的hash值相等
// 并且 头结点的key本身 和要获取的 key 相等
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) // 如果当前结点是树结点
// 则证明当前位置的链表已变成红黑树结构
// 通过红黑树结点的方式获取对应key结点
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {// 当前位置不是红黑树，则证明是单链表
// 遍历单链表，逐一比较链表结点
// 链表结点的key的hash值 和 要获取的key的hash值相等
// 并且 链表结点的key本身 和要获取的 key 相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 找到对应的结点则返回
return e;
} while ((e = e.next) != null);
}
}
// 通过上述查找均无找到，则返回null
return null;
}- перечислить
remove(Object key)Действие по ключуkeyудалить соответствующийkey-valueПри использовании пар ключ-значение выполняются следующие операции:
1. Звоните первымhash(key)метод расчетаkeyизhashценность
2. По ключевому значению поискаkeyизhashзначение, через(n - 1) & hashтекущего элементаhashценность &hashДлина таблицы - 1 (фактическиhashценность %hashдлина таблицы) для расчета места храненияtable[i], чтобы определить, есть ли элемент в месте хранения.
-
Если в ячейке хранения есть элемент, сначала сравнивается элемент головного узла, если элемент головного узла
keyизhashценность и получитьkeyизhashзначение равно, а головной узелkeyсебя и приобретатьkeyравно, то головной узел этой позиции является удаляемым узлом, запишите этот узел в переменнуюnodeсередина. -
Если в месте хранения нет элемента, соответствующий удаляемому узлу не найден, то возвращаем
null.
3. Если в ячейке хранения есть элемент, но элемент головного узла не является удаляемым элементом, вам нужно пройти по ячейке, чтобы найти его.
4. Сначала определите, является ли головной узелtreeNode,еслиtreeNodeДокажите, что структура этой локации представляет собой красно-черное дерево, обходом найдите и удалите узел в виде красного дерева, если нет, вернитесьnull.
5. Если это не красно-черное дерево, то оно оказывается односвязным списком. Пройдите по односвязному списку и сравните узлы связанного списка один за другим.keyизhashценность и получитьkeyизhashзначение равно, и узел связанного спискаkeyсебя и приобретатьkeyравно, то это удаляемый узел, запишите этот узел в переменнуюnode, обход заканчивается и соответствующийkeyузел, возвратnull.
6. Если узел, подлежащий удалению, найденnode, затем определите, следует ли сравниватьvalueтакже непротиворечиво, еслиvalueЗначения совпадают или сравнение не требуетсяvalueЕсли значение установлено, выполняется операция удаления узла, и операция удаления обрабатывается по-разному в соответствии с различными ситуациями и структурами.
-
Если текущий узел является узлом дерева, это доказывает, что связанный список в текущей позиции стал красно-черной древовидной структурой, и соответствующий узел удаляется с помощью красно-черного узла дерева.
-
Если это не красно-черное дерево, то оно оказывается односвязным списком. Если головной узел должен быть удален, текущее место хранения
table[i]Головной узел указывает на следующий узел удаленного узла. -
Если удаляемый узел не является головным узлом, то узел-преемник удаляемого узла
node.nextНазначается узлу-предшественнику удаляемого узлаnextдомен, то естьp.next = node.next;.
7.HashMapТекущее количество сохраненных пар ключ-значение — 1, и возвращает узел удаления.
Образец кода:
/**
* 从此映射中移除指定键的映射关系（如果存在）。
*
* @param key 其映射关系要从映射中移除的键
* @return 与 key 关联的旧值；如果 key 没有任何映射关系，则返回 null。
* （返回 null 还可能表示该映射之前将 null 与 key 关联。）
*/
public V remove(Object key) {
Node<K,V> e;
// 1.先调用 hash(key)方法计算出 key 的 hash值
// 2.随后调用removeNode方法删除对应key所映射的结点
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* 删除哈希表结点的方法实现
*
* @param hash 键的hash值
* @param key 键
* @param value 用于比较的value值，当matchValue 是 true时才有效, 否则忽略
* @param matchValue 如果是 true 只有当value相等时才会移除
* @param movable 如果是 false当执行移除操作时，不删除其他结点
* @return 返回删除结点node，不存在则返回null
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
// 用于记录当前的hash表
Node<K,V>[] tab;
// 用于记录当前的链表结点
Node<K,V> p;
// n用于记录hash表的长度，index用于记录当前操作索引index
int n, index;
// 通过 (n - 1) & hash 当前元素的hash值 & hash表长度 - 1
// 判断当前元素的存储位置是否有元素存在
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {// 元素存在的情况
// node 用于记录找到的结点，e为工作结点
Node<K,V> node = null, e;
K k; V v;
// 如果头结点的key的hash值 和 要获取的key的hash值相等
// 并且 头结点的key本身 和要获取的 key 相等
// 则证明此头结点就是要删除的结点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 记录要删除的结点的引用地址至node中
node = p;
else if ((e = p.next) != null) {// 头结点不相等
if (p instanceof TreeNode)// 如果当前结点是树结点
// 则证明当前位置的链表已变成红黑树结构
// 通过红黑树结点的方式获取对应key结点
// 记录要删除的结点的引用地址至node中
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {// 当前位置不是红黑树，则证明是单链表
do {
// 遍历单链表，逐一比较链表结点
// 链表结点的key的hash值 和 要获取的key的hash值相等
// 并且 链表结点的key本身 和要获取的 key 相等
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
// 找到则记录要删除的结点的引用地址至node中，中断遍历
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 如果找到要删除的结点，则判断是否需要比较value也是否一致
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// value值一致或者不需要比较value值，则执行删除结点操作
if (node instanceof TreeNode) // 如果当前结点是树结点
// 则证明当前位置的链表已变成红黑树结构
// 通过红黑树结点的方式删除对应结点
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p) // node 和 p相等，则证明删除的是头结点
// 当前存储位置的头结点指向删除结点的下一个结点
tab[index] = node.next;
else // 删除的不是头结点
// p是删除结点node的前驱结点，p的next改为记录要删除结点node的后继结点
p.next = node.next;
++modCount;
// 当前存储键值对的数量 - 1
--size;
afterNodeRemoval(node);
// 返回删除结点
return node;
}
}
// 不存在要删除的结点，则返回null
return null;
}- перечислить
replace(K key, V value)Действие по ключуkeyнайти соответствующийkey-valueпара ключ-значение, затем замените соответствующее значениеvalue, сделал следующее:
-
сначала позвони
hash(key)метод расчетаkeyизhashценность -
тогда позвони
getNodeметод получения соответствующегоkeyнанесен на картуvalueценность . -
Запишите старое значение элемента, присвойте новое значение элементу, верните старое значение элемента и верните, если элемент не найден
null.
Образец кода:
/**
* 替换指定 key 所映射的 value 值
*
* @param key 对应要替换value值元素的key键
* @param value 要替换对应元素的新value值
* @return 返回原本的旧值，如果没有找到key对应的元素，则返回null
* @since 1.8 JDK1.8新增方法
*/
public V replace(K key, V value) {
Node<K,V> e;
// 1.先调用 hash(key)方法计算出 key 的 hash值
// 2.随后调用getNode方法获取对应key所映射的value值
if ((e = getNode(hash(key), key)) != null) {// 如果找到对应的元素
// 元素旧值
V oldValue = e.value;
// 将新值赋值给元素
e.value = value;
afterNodeAccess(e);
// 返回元素旧值
return oldValue;
}
// 没有找到元素，则返回null
return null;
}3.
Вопрос 1: Вы сказали выше, что при сохранении элемента сначала вычислите его хэш-значение, чтобы определить его место хранения, а затем поместите элемент в соответствующее место. Что, если элемент уже существует в этом месте? Что насчет этого элемента?
Вопрос 2:hashконфликт (илиhashстолкновение) что это? Почему это происходит и как это исправитьhashконфликт?
отвечать:
-
hashконфликт: когда мы звонимput(K key, V value)Добавить действиеkey-valueпара ключ-значение, этоkey-valueМесто хранения пары ключ-значение определяется функцией возмущения(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)Вычислить ключkeyизhashценность. Тогда этоhashзначение % по модулю хеш-таблицыNode<K,V>[] tableдлина, чтобы получить конкретное место хранения. такput(K key, V value)Для нескольких элементов можно рассчитать одно и то же место хранения. Это явлениеhashконфликт или звонокhashстолкновение. -
Примеры следующие:
элемент Аhashзначение равно 9, элемент BhashСтоимость 17. хеш-таблицаNode<K,V>[] tableДлина 8. Тогда место хранения элемента A равно9 % 8 = 1, место хранения элемента B17 % 8 = 1. Оба элемента хранятся вtable[1],случилосьhashконфликт. -
hashИзбегание конфликтов: когда это происходитhashконфликт, мы должны найти способ избежать этого явления.Ключ к решению этой проблемы, если элемент генерируется.hashценность. Java использует «функции возмущения» для генерации элементовhashценность.
Образец кода:
/**
* JDK 7 的 hash方法
*/
final int hash(int h) {
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/**
* JDK 8 的 hash方法
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}В Java 7 смешивание 16-битного исключающего ИЛИ со сдвигом вправо выполнялось 4 раза. В Java 8 этот шаг был упрощен. Выполняется только одно 16-битное смешивание XOR со сдвигом вправо вместо четырех, но принцип остается прежним. Примеры следующие:
Правый сдвиг составляет 16 бит, что составляет ровно половину битов 32. Старшая и младшая половина собственной области подвергаются операции XOR, чтобы смешать старшие и младшие биты исходного хэш-кода, чтобы увеличить случайность младших битов. Более того, смешанные младшие биты дополняются некоторыми свойствами старших битов, так что старшие биты также сохраняются в замаскированном виде.
Объяснение приведенной выше функции возмущения взято из:Каков принцип хэш-метода HashMap в исходном коде JDK?
-
hashРазрешение конфликта: РазрешениеhashМетодов разрешения конфликтов много, наиболее распространенными являются: метод адресации развития,
Метод перехеширования, метод цепного адреса, метод общедоступной зоны переполнения (подробности см. в моей статье).Основы JAVA - самостоятельный вопрос и самостоятельный ответ, чтобы узнать hashCode и equals).HashMapрешается методом цепных адресовhashЕсли возникает конфликт, когда конфликтующий элемент вставлен, этот элемент будет вставлен в последнюю цифру связанного списка в этой позиции, чтобы сформировать односвязный список. Но поскольку это односвязный список, всякий раз, когда вы проходитеhash % lengthПри нахождении элемента в этой позиции необходимо пройтись по связному списку с самого начала и сравнить их по одному.hashзначение, найдите соответствующий элемент. Если в этой позиции слишком много элементов, связанный список будет слишком длинным, и время обхода будет сильно увеличено.O(N), что приводит к низкой эффективности поиска. Поэтому, когда длина связанного списка существующих позиций больше или равна 8,HashMapСвязный список будет преобразован в красно-черное дерево, а временная сложность красно-черного дерева в наихудшем случае равнаO(logn). Это повышает эффективность поиска.
4.
просить:HashMapПочему емкость числа 2 должна быть энной степенью числа 2?
отвечать:
-
Потому что звонок
put(K key, V value)Добавить действиеkey-valueКогда используется пара ключ-значение, конкретное расположение этого элемента определяетсяhashзначение % по модулю хеш-таблицыNode<K,V>[] tableдлинаhash % lengthвычислительный. Однако потребление операции «по модулю» относительно велико из-за битовой операции.h & (length-1)Место хранения после модуля также может быть получено, и эффективность работы побитовой операции высока, но толькоlengthКогда длина равна 2 в энной степени,h & (length-1)эквивалентноh % length. -
Более того, когда длина массива равна n-й степени двойки, вероятность того, что один и тот же индекс, рассчитанный по разным ключам, мала, то данные распределяются по массиву равномерно, то есть мала вероятность коллизии, относительно, при запросе нет необходимости перемещаться по связанному списку в определенной позиции, поэтому эффективность запроса выше.
пример:
-
На приведенном выше рисунке длина массива двух групп слева равна 16 (2 в 4-й степени), а длина массива двух групп справа равна 15. две группы
hashЗначения равны как 8, так и 9. -
При длине массива 15, когда они и
1110провести&При выполнении операции И (одинаково 1, разность 0) результатом вычисления является1000, поэтому все они будут храниться в одном местеtable[8], это произошлоhashЕсли есть конфликт, вам нужно пройти по связанному списку при запросе и сравнить их один за другим.hashзначение, снижающее эффективность запроса. -
В то же время мы можем обнаружить, что при длине массива 15,
hashзначение будет таким же, как14（1110）провести&операция И, то последний бит всегда равен 0, и0001,0011,0101,1001,1011,0111,1101Элементы никогда не могут быть сохранены в этих местах, и трата места довольно велика.Что еще хуже, в этом случае доступные места массива намного меньше, чем длина массива, а это означает, что вероятность коллизии увеличивается, что снижает эффективность запроса.
- так,
HashMapЕмкость числа 2 является n-й степенью числа 2, что способствует повышению эффективности расчета места хранения элементов, а также снижаетhashвероятность конфликта. Поэтому мы используемHashMapПри хранении большого объема данных лучше заранее указать размер контейнера как n-ю степень 2, даже если мы не указываем его как n-ю степень 2,HashMapОн также установит размер контейнера в n-й степени 2, ближайшей к установленному числу, например, установитеHashMapимеет размер 7, тоHashMapУстановит размер контейнера на ближайшие 7 в n-й степени 2, что равно 8 .
Приведенный выше ответ взят из:Глубокое понимание HashMap
Образец кода:
/**
* 返回一个比指定数cap大的，并且大小是2的n次方的数
* Returns a power of two size for the given target capacity.
*/
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;
}5.
просить:HashMapЧто такое коэффициент нагрузки и что он делает?
Ответ: Коэффициент загрузки указывает на использование пространства хеш-таблицы (или использование пространства хэш-таблицы).
-
Примеры следующие:
базовая хеш-таблицаNode<K,V>[] tableразмер емкостиcapacity16, коэффициент загрузкиload factorравно 0,75, тогда, когда количество хранимых элементовsize = capacity 16 * load factor 0.75При значении 12 срабатываетHashMapМеханизм расширения , вызываяresize()метод расширения. -
Когда коэффициент нагрузки больше,
HashMapчем выше уровень загрузки. То есть он может вместить больше элементов, а элементов больше.hashВероятность коллизий увеличится, поэтому связанный список удлинится, а эффективность запросов в это время снизится. -
Когда коэффициент загрузки меньше, количество данных в связанном списке меньше, что приводит к трате места, но эффективность запросов в это время высока.
-
мы можем создать
HashMapдолжным образом корректироваться в соответствии с фактическими потребностямиload factorЕсли программу больше беспокоят накладные расходы пространства и памяти относительно мало, коэффициент загрузки можно соответствующим образом увеличить; если программу больше беспокоят накладные расходы времени и памяти относительно много, коэффициент загрузки можно соответствующим образом уменьшить. Как правило, коэффициент загрузки по умолчанию (0,75) ищет компромисс между затратами времени и места, и программисту не нужно изменять значение коэффициента загрузки. -
Итак, если мы инициализируем
HashMap, считается, что его нужно загрузитьkey-valueЕмкость пар ключ-значениеsize, мы можем пройтиsize / load factorРассчитаем размер емкости, которую нам нужно инициализироватьinitialCapacity, что позволяет избежатьHashMapПоскольку сохраненный элемент достигает порогаthresholdпри частых звонкахresize()метод расширения. Тем самым обеспечивая лучшую производительность.
6.
В: Можете ли вы сказать мнеHashMapиHashTableразница?
отвечать:HashMapиHashTableИмеются следующие отличия:
1) Общая структура контейнера:
-
HashMapизkeyиvalueразрешено бытьnull,HashMapвстретитьсяkeyзаnullпри звонкеputForNullKeyспособ обработки, в то время какvalueБез обработки. -
Hashtableизkeyиvalueне разрешеноnull.Hashtableвстретитьсяnull, вернуться напрямуюNullPointerException.
2) Механизм установки и расширения мощности:
-
HashMapНачальная емкость по умолчанию равна 16, а емкость контейнера должна быть n-й степенью числа 2. При расширении емкость увеличивается в 2 раза по сравнению с исходной емкостью. -
HashtableНачальная емкость по умолчанию — 11. При расширении емкость увеличивается в 2 раза по сравнению с исходной емкостью плюс 1. которыйint newCapacity = (oldCapacity << 1) + 1;.
3) Метод распределения хэшей (рассчитать место хранения):
-
HashMapэто первый генералkeyключhashCodeПосле возмущения функцией возмущения получимhashзначение, а затем использоватьhash & (length - 1)Вместо того, чтобы брать по модулю, получите место хранения элемента. -
HashtableЗатем метод остатка используется для вычисления места хранения (поскольку его емкость по умолчанию не является n-й степенью числа 2. Таким образом, невозможно заменить операцию по модулю битовой операцией),int index = (hash & 0x7FFFFFFF) % tab.length;. -
так как
HashMapЕмкость контейнера должна быть равна 2 в n-й степени, чтобы его можно было использовать.hash & (length - 1)Способ замены модуля для вычисления положения элемента повышает эффективность работы, ноHashtableЕмкость контейнера не обязательно равна n-й степени числа 2, поэтому вместо этого нельзя использовать этот метод работы.
4) Безопасность потока (самое важное):
-
HashMapНе потокобезопасный, если вам нужна потокобезопасность, вы можете позвонитьsynchronizedMap(Map<K,V> m)Сделайте его потокобезопасным. Тем не менее, эффективность работы будет снижаться при использовании, поэтому рекомендуется использоватьConcurrentHashMapТаким образом, контейнер обеспечивает потокобезопасность. -
HashtableОн потокобезопасен, и каждый метод операции имеетsynchronizedМодификация, чтобы сделать его синхронным, но он не очень эффективен, поэтому рекомендуется использоватьConcurrentHashMapТаким образом, контейнер обеспечивает потокобезопасность.
следовательно,Hashtableявляется устаревшим контейнером и рекомендуется, если нам не нужна синхронизация потоковHashMap, если требуется синхронизация потоков, рекомендуется использоватьConcurrentHashMap.
Исходный код Hashtable не будет анализироваться здесь по отдельности, если вы хотите узнать о нем больше, вы можете обратиться к этой статье.
Анализ исходного кода хэш-таблицы
7.
В: ты сказалHashMapОн не является потокобезопасным, так как же он справляется с многопоточностью? И при каких обстоятельствах возникает небезопасность потока?
отвечать:
-
HashMapНе потокобезопасный, если несколько потоков одновременноHashMapЕсли данные изменены, это приведет к несогласованности данных или загрязнению данных. Если происходит небезопасная для потоков операция,HashMapбросить как можно большеConcurrentModificationExceptionПредотвратите аномалии данных, когда мы находимся наHashMapПри обходе, при обходе мы не можемHashMapВыполняйте такие операции, как добавление, удаление и т. д., чтобы изменить данные, иначе он также выкинетConcurrentModificationExceptionИсключение, это отказоустойчивый механизм. Из анализа исходного кода мы находимся вput,removeждать переменHashMapdata, это приведет к изменению modCount, когдаexpectedModCount != modCount, затем броситьConcurrentModificationException. Если вам нужна безопасность потоков, рассмотрите возможность использованияConcurrentHashMap. -
Более того, работая под несколькими потоками
HashMap, за счет механизма расширения, когдаHashMapперечислитьresize()Когда выполняется автоматическое расширение, может возникнуть бесконечный цикл.
Из-за нехватки времени я пока не возьму вас для совместного анализа.resize()Причина в том, что метод приводит к возникновению бесконечного цикла. Я добавлю его позже, когда у меня будет время. Пожалуйста, простите меня. Вы можете обратиться к следующим статьям:
Переосмысление HashMap в серии Java 8
Расскажите о воплощении небезопасности потока HashMap
8.
Вопрос: мы используемHashMapКогда , какой объект выбран в качествеkeyКлючи лучше, почему?
отвечать:
-
Изменяемый объект: относится к объекту, состояние которого может измениться после создания. Другими словами, изменяемый объект — это объект, хеш-значение которого может измениться после создания объекта.
-
мы используем
HashMap, в качестве неизменяемых объектов лучше выбиратьkey. НапримерString,Integerи т. д. неизменяемые типы какkeyочень разумно. -
если
keyобъект изменчив, тоkeyЗначение хеша может измениться. существуетHashMapИспользование изменяемого объекта в качестве ключа приведет к потере данных. потому что мы продолжаемhash & (length - 1)Когда операция по модулю вычисляет позицию для поиска соответствующего элемента, позиция могла измениться, что привело к потере данных.
Подробные примеры см.:Опасность! Использовать изменяемый объект в качестве ключа в HashMap
Суммировать
-
HashMapоснован наMapПара ключ-значение, реализованная интерфейсом<key,value>структура хранения, позволяющаяnullзначение, в то же время неупорядоченное, несинхронизированное (т.е. небезопасное для потоков).HashMapБазовая реализация представляет собой массив + связанный список + красно-черное дерево (JDK1.8 добавил красно-черную часть дерева). -
HashMapПоложение локационного элемента осуществляется клавишейkeyПосле возмущения функцией возмущения получимhashзначение, а затем передатьhash & (length - 1)Позиционирование элемента выполняется вместо модуля. -
HashMapрешается методом цепных адресовhashЕсли возникает конфликт, когда конфликтующий элемент вставлен, этот элемент будет вставлен в последнюю цифру связанного списка в этой позиции, чтобы сформировать односвязный список. Когда длина связанного списка существующих позиций больше или равна 8,HashMapСвязанный список будет преобразован в красно-черное дерево для повышения эффективности поиска. -
HashMapЕмкость числа 2 является n-й степенью числа 2, что способствует повышению эффективности расчета места хранения элементов, а также снижаетhashвероятность конфликта. Поэтому мы используемHashMapПри хранении большого объема данных лучше заранее указать размер контейнера как n-ю степень 2, даже если мы не указываем его как n-ю степень 2,HashMapОн также установит размер контейнера в n-й степени 2, ближайшей к установленному числу, например, установитеHashMapимеет размер 7, тоHashMapУстановит размер контейнера на ближайшие 7 в n-й степени 2, что равно 8 . -
HashMapКоэффициент загрузки представляет собой степень использования пространства хеш-таблицы (или использования пространства хэш-таблицы). Когда коэффициент нагрузки больше,HashMapчем выше уровень загрузки. То есть он может вместить больше элементов, а элементов больше.hashВероятность коллизий увеличится, поэтому связанный список удлинится, а эффективность запросов в это время снизится. Когда коэффициент загрузки меньше, количество данных в связанном списке меньше, что приводит к трате места, но эффективность запросов в это время высока. -
HashMapне является потокобезопасным,HashtableЭто потокобезопасно. ноHashtableявляется устаревшим контейнером и рекомендуется, если нам не нужна синхронизация потоковHashMap, если требуется синхронизация потоков, рекомендуется использоватьConcurrentHashMap. -
Работает в нескольких потоках
HashMap, за счет механизма расширения, когдаHashMapперечислитьresize()Когда выполняется автоматическое расширение, может возникнуть бесконечный цикл. -
мы используем
HashMap, в качестве неизменяемых объектов лучше выбиратьkey. НапримерString,Integerи т. д. неизменяемые типы какkeyочень разумно.
- В связи с загруженностью работой и проблемой проволочек в последнее время, статья не доделана к публикации.На самом деле законченная статья для меня не очень, но я все же планирую выслать ее на всеобщее обозрение.Вместе Изучаем и учимся, посмотрите, что не так, я буду постепенно улучшать ее, если эта статья будет вам полезна, пожалуйста, поставьте лайк, спасибо.
Справочная статья
Переосмысление HashMap в серии Java 8
Каков принцип хэш-метода HashMap в исходном коде JDK?
Глубокое понимание HashMap
Коэффициент загрузки HashMap
Анализ исходного кода хэш-таблицы
Опасность! Использовать изменяемый объект в качестве ключа в HashMap
Расскажите о воплощении небезопасности потока HashMap