HashMap扩容机制#

触发条件： size > threshold（threshold = capacity × loadFactor，默认 16 × 0.75 = 12）

扩容流程：

1. 新容量 = 旧容量 × 2（始终保持 2 的幂次）
2. 创建新的数组（newTab = new Node[newCap]）
3. Rehash：遍历旧数组，将每个元素重新计算位置放入新数组

JDK 8 的优化（按一位拆分 lo/hi 链，保持原顺序）：

• 旧容量 = 16（...0001 0000），新容量 = 32（...0010 0000）
• 新增的判断位就是旧容量对应的那一位（第5位）
• 原位置的元素只有两种去向：
  • 原下标（hash 第5位 = 0）
  • 原下标 + 旧容量（hash 第5位 = 1）

// 判断元素去向，只需一次位运算
if ((e.hash & oldCap) == 0) {
    // 放入 lo 链（原下标）
} else {
    // 放入 hi 链（原下标 + oldCap）
}

注意：JDK7 的 Entry 也缓存了 hash，只在开启 alternative hashing 时才重算；JDK8 的改进在于按 lo/hi 两条链整体迁移、保持原顺序（不再像 JDK7 头插那样倒序，也就不会并发成环），红黑树桶也按同样方式拆分。

负载因子为什么是 0.75：

• 太大（如 0.9）：冲突多，链表长，查询慢
• 太小（如 0.5）：扩容频繁，空间浪费
• 0.75 是时间与空间的经验折中；源码注释是在 0.75 的前提下按泊松分布（λ≈0.5）估算桶内链表长度，并不是说 0.75 时碰撞概率最低

HashMap扩容发生在元素数量超过阈值时，阈值等于容量乘以负载因子，默认是16乘0.75等于12。扩容时新容量变为旧容量的2倍，始终保持2的幂次方，然后创建新数组并将所有元素重新分配位置。JDK8对rehash做了重要优化：直接用节点里缓存的hash与旧容量做一次位与运算判断元素去向，把原链表拆成lo、hi两条并保持原顺序。因为容量翻倍后新增的有效位只有一位，如果该位为0元素留在原位置，为1则迁移到原位置加旧容量的位置。这样一次位运算就能确定元素去向，并且迁移后顺序不变。负载因子选择0.75是时间和空间的经验折中，源码注释在0.75下按泊松分布估算，单个桶恰好有8个元素的概率约0.00000006，也就是亿分之六。太大则冲突严重链表变长查询退化为O(n)，太小则扩容频繁浪费内存。另外需要注意HashMap扩容不是线程安全的，JDK7中并发扩容由于头插法可能导致链表成环造成死循环，JDK8改用尾插法虽然解决了死循环但仍然存在数据覆盖问题。

追问方向：

• “扩容时元素怎么重新分配？JDK8 优化了什么？”→ 用节点缓存的 hash 做 (hash & oldCap) 判断高位 bit：为 0 留原位，为 1 迁移到原位 + oldCap，一次位运算确定去向，链表拆成 lo/hi 两条并保持原顺序
• “扩容是线程安全的吗？”→ 不安全。JDK7 头插法并发扩容可形成环形链表导致死循环；JDK8 尾插法解决了死循环但仍存在数据覆盖问题，并发场景应用 ConcurrentHashMap
• “负载因子为什么是 0.75？”→ 时间与空间的折中：太大（如 0.9）碰撞多链表长查询慢，太小（如 0.5）扩容频繁浪费内存，源码注释在 0.75 下按泊松分布估算，链表长度到 8 的概率约亿分之六，树化只是极端情况的保底

易错点：

• ❌ 认为扩容时所有元素都要重新调用 hash()——JDK7/8 都用节点缓存的 hash，JDK8 再用 (hash & oldCap) 直接判断新位置
• ❌ 扩容只是数组变大——还需要将链表/红黑树中的节点重新分配