HashMap扩容机制#

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

扩容流程：

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

JDK 8 的优化（无需重新计算 hash）：

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

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

这个设计避免了对每个 key 重新做 hash() 计算，显著提升扩容性能。

负载因子为什么是 0.75：

• 太大（如 0.9）：冲突多，链表长，查询慢
• 太小（如 0.5）：扩容频繁，空间浪费
• 0.75 是时间与空间的折中（泊松分布下 0.75 时碰撞概率最低）

HashMap扩容发生在元素数量超过阈值时，阈值等于容量乘以负载因子，默认是16乘0.75等于12。扩容时新容量变为旧容量的2倍，始终保持2的幂次方，然后创建新数组并将所有元素重新分配位置。JDK8对rehash做了重要优化：不需要重新计算每个key的hash值，而是通过hash与旧容量做一次位与运算判断元素去向。因为容量翻倍后新增的有效位只有一位，如果该位为0元素留在原位置，为1则迁移到原位置加旧容量的位置。这样一次位运算就能确定元素去向，大幅提升了扩容性能。负载因子选择0.75是时间和空间的折中，根据泊松分布，0.75时哈希碰撞概率较低，链表长度达到8的概率只有千万分之六。太大则冲突严重链表变长查询退化为O(n)，太小则扩容频繁浪费内存。另外需要注意HashMap扩容不是线程安全的，JDK7中并发扩容由于头插法可能导致链表成环造成死循环，JDK8改用尾插法虽然解决了死循环但仍然存在数据覆盖问题。

追问方向：

• “扩容时元素怎么重新分配？JDK8 优化了什么？”→ 无需重新计算 hash，通过 (hash & oldCap) 判断高位 bit：为 0 留原位，为 1 迁移到原位 + oldCap，一次位运算确定去向
• “扩容是线程安全的吗？”→ 不安全。JDK7 头插法并发扩容可形成环形链表导致死循环；JDK8 尾插法解决了死循环但仍存在数据覆盖问题，并发场景应用 ConcurrentHashMap
• “负载因子为什么是 0.75？”→ 时间与空间的折中：太大（如 0.9）碰撞多链表长查询慢，太小（如 0.5）扩容频繁浪费内存，0.75 在泊松分布下碰撞概率较低

易错点：

• ❌ 认为扩容时所有元素都要重新计算 hash——JDK8 通过 (hash & oldCap) 判断新位置
• ❌ 扩容只是数组变大——还需要将链表/红黑树中的节点重新分配