# 问题
2. HashMap 的 put 方法执行流程是怎样的?涉及哪些关键操作?
# 标准答案
HashMap 的 put(K key, V value)
方法用于向 Map 中插入键值对,其执行流程包含 计算哈希值、确定桶索引、插入节点、链表或红黑树处理、扩容检查 等关键步骤。JDK 1.8 采用 数组 + 链表 + 红黑树 结构,优化了哈希冲突处理,同时提升了查询和插入性能。
- 计算 key 的哈希值:通过
(h = key.hashCode()) ^ (h >>> 16)
计算哈希值,降低哈希碰撞概率。 - 确定索引位置:通过
(n - 1) & hash
计算 key 在 table 数组中的索引。 - 插入节点:
- 如果该索引为空,直接放入新节点。
- 如果已存在节点,则遍历链表:
- 如果 key 已存在,则更新 value。
- 如果是链表,插入到链表尾部。
- 如果链表长度达到 8,转换为红黑树。
- 扩容检查:若当前存储元素超过
threshold
(负载因子 * 数组容量),则触发 resize() 进行扩容。
# 答案解析
# 1. put()
方法的核心流程
put()
方法的核心流程如下(JDK 1.8 源码简化版):
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) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
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 { // 发生哈希冲突,处理链表或红黑树
Node<K,V> e; K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p; // key 已存在,更新 value
else if (p instanceof TreeNode)
e = ((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);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash); // 转换为红黑树
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break; // key 已存在,退出循环
p = e;
}
}
if (e != null)
e.value = value; // 更新已有 key 的 value
}
if (++size > threshold)
resize(); // 扩容检查
return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# 2. 关键操作解析
# (1) 计算哈希值
调用 hash()
方法计算 key 的哈希值:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
1
2
3
4
2
3
4
- 通过 高 16 位和低 16 位进行异或,使高位也参与索引计算,减少哈希冲突。
- 避免了直接使用
hashCode()
可能导致的哈希分布不均问题。
# (2) 计算数组索引
i = (n - 1) & hash;
1
- 由于
n
是 2 的幂,(n - 1) & hash
等价于hash % n
,但 比取模运算更高效(位运算速度更快)。
# (3) 处理哈希冲突
- 如果该位置为空,直接插入新节点。
- 如果该位置已有节点:
- 若 key 已存在,则更新 value。
- 若是链表,则插入到链表末尾,并检查是否需要转为红黑树。
- 若是红黑树,则调用
putTreeVal()
进行插入。
# (4) 可能转换为红黑树
- 当链表长度 ≥ 8 且数组长度 ≥ 64 时,会调用
treeifyBin()
转换为红黑树:void treeifyBin(Node<K,V>[] tab, int hash) { if (tab.length < MIN_TREEIFY_CAPACITY) resize(); else { // 转换链表为红黑树 } }
1
2
3
4
5
6
7
# (5) 可能触发扩容
- 当
size > threshold
时,调用resize()
进行扩容:final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int newCap = oldCap << 1; // 容量翻倍 Node<K,V>[] newTab = new Node[newCap]; // 重新计算元素位置 return newTab; }
1
2
3
4
5
6
7
8 - 由于
n
是 2 的幂,扩容时只需判断(hash & oldCap) == 0
来决定元素去新索引还是保留原索引,避免了重新计算哈希值,提高性能。
# 4. HashMap 的常见问题
# ❌ 常见误区
# 1. put 过程是线程安全的吗?
- 误区:很多人误认为
put()
是线程安全的,但它在并发环境下可能导致数据丢失、死循环。 - 正确方案:使用
ConcurrentHashMap
或Collections.synchronizedMap(new HashMap<>())
。
# 2. 哈希冲突是否一定会转换为红黑树?
- 误区:有人认为链表长度达到 8 就一定转红黑树,但实际上,只有数组大小 ≥ 64 时才会转。
- 正确方案:如果数组较小,JDK 1.8 仍然会扩容,而不是立即转换红黑树。
# 3. 扩容时为什么采用 2 的幂次?
- 误区:有些人认为 10 这样的值也可以作为初始容量,但实际上,HashMap 要求容量始终是 2 的幂,否则会被调整为最接近的 2 的幂次方(如 10 会变为 16)。
- 正确方案:初始化时应直接指定 2 的幂,避免不必要的调整。
# 深入追问
🔹 为什么 hash()
方法采用 (h = key.hashCode()) ^ (h >>> 16)
?
🔹 为什么 HashMap 采用 链地址法 解决哈希冲突,而不是开放地址法?
🔹 扩容时 resize()
为什么不重新计算哈希值?
🔹 为什么链表长度达到 8 才转换为红黑树,而不是更小?
# 相关面试题
• get()
方法的执行流程是怎样的?
• HashMap 扩容的详细过程?
• ConcurrentHashMap
的 put 操作和 HashMap 有什么不同?
• 为什么 HashMap 采用 0.75 作为默认负载因子?
这就是 HashMap put()
方法的详细执行过程,如果有需要,可以深入解析某个具体的部分!