HashMap是如何扩容的？

面试记录 2026-10-09

题目：HashMap 是如何扩容的？

难度：medium

标签：java/collections, general/knowledge

评分：⭐⭐☆☆☆（2/5）

我的回答

hashMap 的扩容，首先是要判断节点数，有多少节点了，达到多大量级进行扩容。扩容的触发条件应该是 75%，我记得有一个参数可以设置扩容比例默认是 0.75，当前容量达到了这个量级之后进行扩容。

点评

优点：

• 说对了触发条件：size > capacity * 0.75（默认 threshold = 16 × 0.75 = 12）
• 知道 0.75 是 loadFactor 参数可调

不足：

• 只答了触发条件，完全没说扩容过程——这是本题 60% 的核心
• 没提扩容倍数：容量翻倍（16→32→64）
• 没提 JDK7 vs JDK8 的核心差异：JDK7 头插法+重算 hash，JDK8 尾插法+位运算迁移
• 没提 JDK8 的关键优化：e.hash & oldCap 判断元素留在原位还是搬到 index+oldCap
• 没提红黑树退化：扩容后如果树桶 size < 6，会退化回链表
• 没提 +1 陷阱：threshold = newCap * 0.75f，浮点四舍五入时需注意

补充：

• JDK8 resize 完整流程：①首次扩容 newCap=16；②后续 newCap=oldCap<<1，最大 MAX_CAP=1<<30；③若达 MAX_CAP 只增大 threshold；④重算 threshold=(int)(newCap*loadFactor)；⑤遍历旧桶迁移：红黑树根调 split()（size<6 退化），普通节点按 e.hash & oldCap 决定原位或 index+oldCap，用尾插法挂新桶
• 位运算优化的原理：容量 2 的幂时，newCap-1 相当于 oldCap-1 前多一位 1，所以新 hash 结果要么等于旧 index，要么是 旧 index + oldCap
• JDK7 vs JDK8：JDK7 头插法+重算 hash，并发扩容形成环形链表；JDK8 尾插法+单 bit 判断，安全且高效；JDK8 新增树桶处理逻辑
• 工程实践：预估容量时用 new HashMap<>(expectedSize / 0.75f + 1) 避免多次扩容抖动；单线程大初始化也可以用 HashMap(int, float) 指定 loadFactor

完整讲解

第一部分：知识重点剖析

核心考点定位：验证对 HashMap 扩容机制的完整掌握，尤其是 JDK8 相对 JDK7 的位运算优化，以及红黑树退化规则。

知识点拆解：

1. 底层原理：HashMap 用负载因子控制"空间 vs 时间"折中。当 size > threshold 时扩容，避免链表过长导致 O(n) 查找。默认 loadFactor=0.75 是泊松分布下的经验值。
2. 扩容流程（JDK8 resize）：①判断是否首次初始化（table==null）→ newCap=initialCapacity；②否则 newCap=oldCap<<1（最大 1<<30）；③若达 MAX_CAP 只增大 threshold；④重算 threshold=(int)(newCap*loadFactor)；⑤遍历旧表迁移所有元素到新表。
3. JDK8 迁移优化：对每个节点 e，只需判断 e.hash & oldCap：为 0 则留在原 index（因为新表容量翻倍后 index 位不变），非 0 则搬到 index+oldCap。这是利用"容量是 2 的幂"这一约束——新旧 index 只在旧低位置的基础上多了一位。
4. 红黑树处理：树形桶扩容时调用 treeifyBin → split，若树 size < 6（TREEIFY_THRESHOLD-1）退化回链表，因为扩容后冲突已减少。
5. 性能成本：每次扩容 O(n) 遍历全部元素；多次小步扩容累积开销大，所以预估容量时主动传入 new HashMap<>(expected/0.75f+1) 可显著减少 GC 与 CPU 抖动。

按「底层原理 → 设计权衡 → 工程实践」递进排列。

第二部分：考察方向与延伸递进

考察方向：

• 深度：能否推导出 e.hash & oldCap 判定新 index 的数学原理
• 广度：能否对比 ConcurrentHashMap 的协助扩容（多线程迁移）
• 应用：能否根据业务负载预估初始容量，规避扩容抖动

延伸递进面试题：

1. e.hash & oldCap == 0 为什么就留在原 index？

• 解答要点：newCap = 2*oldCap，所以 (newCap-1) 和 (oldCap-1) 相比，多出来一个 bit（第 n 位）。当 e.hash 的第 n 位为 0 时，(newCap-1) & hash 的低 n 位与 (oldCap-1) & hash 相同，index 不变；为 1 时 index 增加 oldCap。

1. ConcurrentHashMap 如何协助扩容？

• 解答要点：JDK8 用 transferIndex 变量协调多线程，每个线程负责迁移一段桶（步长 16）；用 FORWARD_NODE 占位表示已迁移；读操作遇到正在迁移的桶会 helpTransfer 或走 find 兜底。

1. 为什么负载因子默认 0.75 而不是 1.0 或 0.5？

• 解答要点：泊松分布下，0.75 时平均链长期望约 0.5，冲突概率极低；1.0 内存浪费小但冲突高，0.5 冲突低但内存翻倍。0.75 是空间和时间成本的经验最优点。

1. HashMap 大量扩容时怎么优化？

• 解答要点：预估容量传入构造器；使用 computeIfAbsent 减少重哈希；批量导入用 Collectors.toMap 后合并；避免高并发扩容（ConcurrentHashMap 更适合）。

第三部分：面试者参考回答（300-600 字口语化）

面试官您好，HashMap 的扩容由 resize() 方法完成，触发条件是 size > threshold，threshold 默认是容量 × 0.75。默认容量 16、loadFactor 0.75，所以第一次扩容阈值是 12。

扩容的具体过程 JDK7 和 JDK8 差别很大。JDK7 每次扩容都重新计算每个元素的 hash 值定位到新桶，然后用头插法挂接，这在并发场景下会形成环形链表导致 CPU 100%。

JDK8 做了两个关键优化。第一个是尾插法，保留了原链表的顺序，不再形成环。第二个是位运算迁移——不用重新算 hash，只需判断 e.hash & oldCap：如果结果是 0，说明元素 hash 的第 n 位是 0，扩容后新 index 等于旧 index，元素留在原位；如果结果非 0，说明第 n 位是 1，元素要搬到 index + oldCap 位置。这个优化的原理是容量是 2 的幂，新旧桶号只有在第 n 位上有差别，所以一个 bit 判断就能决定新位置。

扩容时如果桶是红黑树，会调用 split() 把树节点分拆到新旧两个桶；扩容后如果树 size 小于 6（TREEIFY_THRESHOLD - 1），会退化回链表，因为桶分散后冲突降低。

最大容量是 1 << 30，达到后不再扩容，只把 threshold 设为 Integer.MAX_VALUE 避免溢出。

工程上的最佳实践是预估容量时主动传入构造器，比如预估 1000 个元素就 new HashMap<>(1334)（1000/0.75+1 向上取 2 的幂前值），这样避免多次扩容抖动，能省掉大约 50% 的初始化时间开销。如果场景是并发写多，直接选 ConcurrentHashMap，它有协助扩容机制让多线程一起迁移。