HashMap 的扩容机制是什么？｜阿里巴巴后端开发面经解析

60 秒回答模板

HashMap 里有几个核心量：capacity 是底层数组长度，size 是实际键值对数量，loadFactor 是负载因子，threshold 通常等于 capacity * loadFactor。put 新键后如果 size 超过 threshold，就会触发 resize。默认初始容量是 16，默认负载因子是 0.75，所以默认阈值是 12。扩容时通常创建一个原容量 2 倍的新数组，然后迁移旧数组里的链表节点或红黑树节点。JDK 8 的关键优化是：因为容量保持为 2 的幂，扩容后某个节点的新下标只可能是旧下标，或者旧下标加 oldCap，判断依据是 hash & oldCap 是否为 0。为 0 留在低位桶，不为 0 移到高位桶。链表桶会拆成 lo 链和 hi 链，红黑树桶也按同样逻辑拆分，拆分后节点少时可能退化回链表。扩容单次成本是 O(n)，会带来延迟尖刺；加载因子则是在空间利用率和冲突概率之间做权衡。HashMap 不是线程安全容器，并发 put 或 resize 仍可能导致数据丢失、覆盖、结构不一致和读取到中间状态。

考点 核心变量

主线 触发时机

易错点 说 HashMap 在数组满了以后才扩容，忽略真正触发…

深入解析

核心变量

HashMap 扩容要先抓住 capacity、loadFactor、threshold、size。capacity 是 table 数组长度，不是当前元素个数；size 是实际键值对数量；loadFactor 是负载因子；threshold 是下一次扩容触发线，通常等于 capacity 乘以 loadFactor。默认容量 16、默认负载因子 0.75，因此默认阈值是 12。准确说法是插入新键导致 size 超过 threshold 时触发扩容。

触发时机

resize 通常发生在 put 新键之后，而不是每次 put 都检查数组是否满。HashMap 允许同一个桶中有多个节点，所以数组并不需要真正填满才扩容。插入已有 key 只更新 value，一般不会增加 size，也不会因为这次更新触发扩容。第一次 put 时如果 table 还没初始化，也会走 resize 完成懒初始化。因此 resize 同时承担初始化和容量翻倍迁移两类职责。

容量为 2 的幂

HashMap 的容量设计为 2 的幂，扩容时通常从 oldCap 变成 oldCap * 2，同时 threshold 也相应翻倍。容量为 2 的幂让下标计算可以从 hash % length 优化成 hash & (length - 1)。这不只是性能优化，也让迁移规则可预测：容量翻倍后，新寻址掩码只多出 oldCap 对应的二进制位，因此节点新位置只有两种可能。

高低位拆分

JDK 8 扩容迁移不是把每个节点重新执行完整寻址逻辑，而是利用 hash 的某一位判断去向。旧下标是 hash & (oldCap - 1)，新容量翻倍后多参与计算的是 oldCap 对应的那一位。如果 hash & oldCap 等于 0，节点仍放在旧下标；如果不等于 0，节点移动到旧下标加 oldCap。这降低了重复计算，也避免了旧版本头插迁移造成的顺序反转问题。

链表迁移

链表桶迁移时，JDK 8 会把原链表拆成 lo 链和 hi 链。lo 链中的节点保留在原桶下标，hi 链中的节点放到原桶下标加 oldCap。拆分过程中维护 loHead、loTail、hiHead、hiTail，因此链表内部相对顺序保持不变。这个点说明扩容不是简单逐个重新 put；resize 内部是按桶批量迁移，避免引入额外插入逻辑和结构变化。

红黑树迁移

如果某个桶已经树化，扩容时并不是把整棵树直接搬到一个位置，而是同样按照 hash & oldCap 拆成低位组和高位组。拆分后每组节点数量不同，如果某一组数量低于退化阈值，可能 untreeify 回链表；如果仍然足够多，则保持或重建红黑树。树化只是桶内冲突严重时的结构优化，扩容后冲突可能被稀释，所以红黑树也可能回到链表。

负载因子

loadFactor 的作用是在空间占用和冲突概率之间做权衡。默认 0.75 是经验折中：数组不会过于稀疏，冲突也不会太严重。负载因子设置得很小会更早扩容，查询更稳定但更浪费内存；设置得很大能推迟扩容，提高数组利用率，但桶内链表或红黑树更容易变长，put 和 get 的平均成本会变差。它控制的是扩容阈值，不是直接控制链表长度。

性能与并发风险

扩容是比较重的操作，因为它要遍历旧 table 的所有桶并迁移所有节点，单次复杂度是 O(n)。平时 put 的均摊复杂度接近 O(1)，但触发 resize 的那次可能明显更慢。实际工程中如果能预估元素数量，应设置合理 initialCapacity。HashMap 也不是线程安全容器，并发 put、remove、resize 可能出现覆盖写、size 不准、数据丢失和结构不一致，多线程读写应使用 ConcurrentHashMap 或外部同步。

易错点

说 HashMap 在数组满了以后才扩容，忽略真正触发线是 threshold。
把 capacity 和 size 混为一谈，分不清底层数组长度和键值对数量。
认为扩容时所有元素都会重新完整计算 hash 和下标，忽略 JDK 8 的高低位拆分。
只会说容量翻倍，但说不清为什么新下标只有 oldIndex 或 oldIndex + oldCap 两种可能。
认为负载因子越大越好，因为更省内存，忽略冲突和查询成本会上升。
认为 JDK 8 没有并发链表成环问题就可以并发使用 HashMap。

面试官追问

为什么 HashMap 的容量要是 2 的幂？

主要是为了让下标计算从取模变成位运算，同时让扩容后的迁移规则足够简单。capacity 为 2 的幂时，capacity - 1 的低位全是 1。扩容翻倍后，只新增一个参与寻址的二进制位，所以节点位置只会保持不变或移动 oldCap。

加载因子为什么默认是 0.75？

0.75 是空间利用率和冲突概率之间的折中。过低会导致 table 很稀疏，内存占用高；过高会导致冲突增多，链表变长或树化概率升高。默认值不是绝对最优，而是面向通用场景的经验选择。

JDK 8 的 resize 为什么不用重新完整寻址？

因为新容量是旧容量的 2 倍，新的寻址掩码只比旧掩码多了一位。旧下标已经由低位决定，扩容后只需要看 hash 在 oldCap 那一位上是 0 还是 1。为 0 保持旧下标，为 1 移到旧下标加 oldCap。

扩容和树化之间是什么关系？

桶内链表长度达到树化阈值时，不一定立刻树化。如果 table 容量还小，HashMap 会优先扩容，因为扩容可能把冲突节点分散到不同桶。只有容量达到一定规模后冲突仍严重，才更适合把链表转成红黑树。

HashMap 并发扩容会有什么问题？

HashMap 没有为并发写提供一致性保障。多个线程同时 put 或 resize，可能导致节点迁移丢失、覆盖更新、size 统计错误，或读线程看到不完整结构。即使 JDK 8 改善了迁移方式，也不能把 HashMap 当线程安全容器使用。