# 问题

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. 关键操作解析

# (1) 计算哈希值

调用 hash() 方法计算 key 的哈希值:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
1
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() 是线程安全的,但它在并发环境下可能导致数据丢失、死循环
  • 正确方案:使用 ConcurrentHashMapCollections.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() 方法的详细执行过程,如果有需要,可以深入解析某个具体的部分!