HashMap 在 get 和 put 时，底层流程是怎样的？

结论先行：put 的关键动作是：算扰动 hash → 必要时初始化表 → 定位桶 → 空桶直接放 → 命中 key 就覆盖旧值 → 树桶走树插入 → 否则尾插链表并在必要时树化 → size 超过阈值再扩容。get 完全对称：定位桶 → 先比桶头 → 树桶查树 → 否则遍历链表。两者都不会全表扫描。

1. put 的决策流程

put(key, value)
   │
   ├─ table 为 null 或长度为 0 ──> resize() 建表（默认 16）
   │
   ├─ 桶 i = (n-1) & hash 为空 ──> new Node 放入 ──> ++size，必要时扩容
   │
   ├─ 桶头 hash 相等且 key 匹配 ──> 覆盖 value，返回旧值
   │
   ├─ 桶头是 TreeNode ──> putTreeVal()：树中查找/插入
   │
   └─ 否则遍历链表
         ├─ 中途找到相同 key ──> 覆盖 value，返回旧值
         └─ 走到尾部 ──> 尾插新节点
                          └─ binCount ≥ 7（桶内已有 8 个）──> treeifyBin
   │
   └─ 结构变化后：++modCount；++size > threshold ──> resize()

2. get 的决策流程

get(key)
   │
   ├─ hash = (h = key.hashCode()) ^ (h >>> 16)，key 为 null 时 hash = 0
   ├─ table 为空或桶 i = (n-1) & hash 为空 ──> 返回 null
   │
   ├─ 桶头匹配（hash 相等且 == 或 equals）──> 返回 value
   │
   ├─ 桶头是 TreeNode ──> getTreeNode(hash, key)
   │
   └─ 否则沿 next 逐个比较 hash 与 equals ──> 命中返回，走到 null 返回 null

3. 源码骨架

// put 入口：只做 hash 扰动，其余交给 putVal
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;                                         // 命中桶头
        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;                                // 链中找到，覆盖
                p = e;
            }
        }
        if (e != null) {                                  // 覆盖分支
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null) e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold) resize();
    afterNodeInsertion(evict);
    return null;
}

getNode 的骨架与 putVal 的查找部分一致：命中桶头直接返回，树桶交给 getTreeNode，否则沿 next 比较 hash 与 equals，走到底返回 null；区别是它不写节点、不改 modCount。

4. 代码：put 的返回值与 null 语义

import java.util.HashMap;
import java.util.Map;

public class PutGetDemo {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>(16);
        System.out.println(map.put("a", 1)); // 输出：null，此前没有映射
        System.out.println(map.put("a", 2)); // 输出：1，返回被覆盖的旧值
        System.out.println(map.get("a"));    // 输出：2
        System.out.println(map.get("b"));    // 输出：null，key 不存在

        // 只在缺失时计算，避免“先 get 再 put”的重复计算
        map.computeIfAbsent("b", k -> k.length());
        System.out.println(map.get("b"));    // 输出：1

        // 值为 null 时，get 无法区分“不存在”和“值为 null”
        map.put("c", null);
        System.out.println(map.get("c"));         // 输出：null
        System.out.println(map.containsKey("c")); // 输出：true
    }
}

5. 流程里的几个设计细节

• 先比 hash 再比 equals：hash 不同直接跳过，省掉昂贵的 equals 调用。
• 桶头单独判断：大多数桶只有一个节点，这是最高频路径的优化。
• 尾插而非头插：保持链表顺序，既避免 JDK 7 扩容成环，也让遍历顺序稳定。
• 覆盖不改 modCount：覆盖 value 不算结构性修改，迭代器不应因此失效。
• 树化与扩容的顺序：treeifyBin 发现容量不足 64 会先 resize()，把节点摊开比建树更划算。

常见追问

• 为什么下标是 (n-1) & hash？ 容量是 2 的幂，位与等价于取模，且没有除法开销。
• put 的平均复杂度？ 平均 O(1)，最坏 O(log n)（桶已树化）。
• get 为什么比 put 快？ 少了一次写入与可能的扩容判断；读路径不修改结构。
• key 为 null 放在哪？ hash 记 0，落在 0 号桶，get/put 都走同一条路径。
• putAll 会扩容几次？ putMapEntries 先按 size / loadFactor + 1 预估阈值，通常一次到位。
• 树化为什么要求容量 ≥ 64？ 小表出现长链更可能是表太小，扩容的收益高于建树。

小结

get 与 put 共享同一套定位逻辑：扰动 hash、掩码取桶、桶头优先、链表兜底、树化加速。put 多了三步判断——空桶新建、命中覆盖、超阈值扩容；get 则纯粹是只读查找。把这张决策图记住，再配合“先 hash 后 equals、覆盖不改 modCount、树化先看容量”三个细节，回答这类流程题就能讲得又准又有层次。