面经策

Java 中 HashMap 的扩容机制是怎样的？ ​

  • 标签：Java 集合、Java

🏛 业务架构师 ​

HashMap 扩容机制：元素数超过 容量 × 0.75 时，数组翻倍，全部元素重新分布。JDK 8 的关键优化——因为容量是 2 的 n 次方，扩容后每个元素只有两个去处：hash 在"新增高位 bit"为 0 则留在原索引，为 1 则移动到"原索引 + 旧容量"，不需要重算 hash，一条链按 bit 拆成高低两条（lo/hi chain），迁移效率大幅提升。

业务视角我抓三个实践点：

  • 容量预估是零成本优化：能预估规模就 new HashMap<>((int)(expected / 0.75f) + 1)，一次到位避免多次扩容。本地缓存预熱、批处理攒批的场景收益明显——默认 16 起、翻倍到 4096 要 rehash 六次，每次都是全量搬迁；
  • 1.7 的历史教训要记住：并发扩容在 JDK 7 会形成环形链表导致 get 死循环（CPU 100% 线上事故的经典根因），JDK 8 改为尾插法解决了成环，但并发写依然会丢数据——多线程场景没有侥幸，必须 ConcurrentHashMap。这段历史的价值是提醒：容器线程安全问题的爆发形态往往是"大促时才出现的高 CPU/数据错乱"，平时功能测试完全正常；
  • 扩容是集中式开销：虽然摊销后单次 put 是 O(1)，但单次扩容是瞬时抖动源——对延迟极敏感的交易路径，集中 rehash 造成的几十毫秒毛刺也要纳入考虑，预估容量同样能消掉它。

理解扩容，最终落成一句团队规约：已知规模就声明规模。

🏗 系统架构师 ​

HashMap 扩容机制我按"触发 → 计算 → 迁移"讲：

  • 触发：size > threshold（capacity × 0.75），或链表树化时发现 capacity < 64（优先扩容不树化）；
  • 计算：新容量翻倍（newCap = oldCap << 1），threshold 同步翻倍，putVal 后判断 size 是否越界；
  • 迁移（1.8 的精华）：因为容量是 2 的幂，hash 与 oldCap 按位与——结果为 0 的留原下标 i，为 1 的去 i + oldCap。不需要重算 hash，只需把一条链表按该位拆成高低两条尾插到新表，保持相对顺序（1.7 头插在并发扩容时会成环丢数据，1.8 改尾插 + 拆分逻辑消除了成环）；
  • JDK 8 仍有一次 put 中先插入后扩容的细节，以及树节点拆分时按需退化回链表（节点数 ≤ 6）。

工程视角：

  • 均摊 O(1)：单次 rehash O(n)，代价均摊到每次写入，但尖刺在百万级大 Map 的一次性扩容时仍明显（一次几十毫秒），所以已知规模时我一定预设初始容量 new HashMap<>((int)(n/0.75f)+1)，一步到位零扩容——这是低延迟服务里 hashmap 使用规范的标准条目。

💻 全栈开发专家 ​

触发条件：size > capacity × loadFactor(0.75) → 容量翻倍（resize）。另外树化前检查：链表到 8 但数组 < 64，优先扩容不树化。

JDK 8 的高明迁移算法（面试重点）：容量是 2 的幂，扩容后每个节点不用重算 hash，只需看 hash & oldCap：

  • 该位为 0 → 留在原索引 i；
  • 该位为 1 → 挪到 i + oldCap。

一条链按这一位拆成"低位链/高位链"两条，用尾插保持相对顺序，一次遍历完成。

java
// 1.8 resize 核心片段（示意）
do {
    Node<K,V> e = head.next;
    if ((e.hash & oldCap) == 0) { /* 挂到 lo 链，位置 = 原索引 */ }
    else { /* 挂到 hi 链，位置 = 原索引 + oldCap */ }
} while (...);

对比 JDK 7：头插法 + 重新 indexFor，并发 resize 时可能成环导致 get 死循环（经典 CPU 100% 事故）；JDK 8 改尾插解决了成环，但并发 put 仍会丢数据/覆盖，HashMap 线程不安全的结论没变。

工程提醒：扩容是全量搬迁，单次 put 可能突然慢（大 map），对延迟敏感的场景（比如网关每请求都查的本地缓存）要预估容量预分配，或者换 Caffeine 这类带异步调优的缓存。