当前位置：首页 > news >正文

HashMap扩容机制

news 2026/5/12 3:45:02

一、HashMap 扩容的核心触发条件

HashMap 扩容的核心触发条件为元素数量达到扩容阈值，阈值计算公式为threshold = capacity * loadFactor（默认容量 16，默认负载因子 0.75，默认阈值 12）。除此之外，JDK1.8 还新增了链表树化的前置扩容条件：当某个链表的节点长度大于 8，但 HashMap 数组的长度小于 64 时，不会直接将链表树化，而是先触发扩容，通过扩大数组容量减少哈希冲突，避免过早树化带来的性能开销。

JDK1.7 和 1.8 的基础扩容触发逻辑一致，且扩容后新数组的容量均为旧数组的 2 倍（newCap = 2 * oldCap），这一设计是为了后续元素迁移时，能通过位运算快速计算新下标，提升迁移效率。

二、HashMap 扩容的通用核心流程

无论是 JDK1.7 还是 1.8，HashMap 扩容的整体流程可分为准备工作和元素迁移两大阶段，其中元素迁移是扩容的核心环节，也是两个版本差异最大的部分。

1. 扩容准备工作

计算新数组容量：newCap = 2 * oldCap，新阈值也随容量同步翻倍；
创建新的空数组，容量为 newCap，作为扩容后的哈希表容器；
计算元素新下标：通过位运算hash & (newCap - 1)计算元素在新数组中的位置，替代取模运算，提升计算效率。

2. 元素迁移四部曲（JDK1.8 核心逻辑）

JDK1.8 的元素迁移覆盖了空位置、单个节点、链表、红黑树四种场景，处理逻辑更全面，也是扩容的标准迁移流程，具体步骤如下：

跳过空位置：遍历旧数组时，若当前数组下标位置为 null，直接跳过，无需处理；
单个节点直接迁移：若旧数组该位置仅有一个节点，直接通过hash & (newCap - 1)计算新下标，将节点放入新数组对应位置；
链表拆分迁移：若该位置是链表，通过hash & 旧容量将原链表拆分为两条子链表：结果为 0 的子链表保留原下标，结果非 0 的子链表新下标为旧下标 + 旧容量，随后将两条子链表整体迁移至新数组对应位置（尾插法）；
红黑树拆分迁移：若该位置是红黑树，按与链表相同的规则（hash & 旧容量）拆分为两棵子树，结果为 0 的子树保留原下标，结果非 0 的子树新下标为旧下标 + 旧容量；拆分后若子树节点数小于 6，会将红黑树退化回链表，再完成整体迁移。

三、JDK1.7 与 1.8 扩容机制的核心差异

JDK1.8 对 HashMap 扩容的优化是全方位的，从元素插入、迁移方式到并发安全、数据结构支持，均与 JDK1.7 存在本质区别，也是面试中的高频考点，核心差异可总结为四大点：

1. 元素插入方式：头插法 vs 尾插法

JDK1.7：采用头插法插入元素，扩容时会将原链表的节点按头插法迁移至新数组，导致链表倒置；这种方式在并发场景下极易出现节点引用闭环，形成环形链表，进而导致死循环。
JDK1.8：采用尾插法插入元素，扩容时链表 / 红黑树拆分后直接整体迁移，保留原节点的顺序，从根源上避免了链表倒置问题，也减少了并发场景下的异常风险。

2. 元素迁移方式：简单遍历 vs 拆分整体迁移

JDK1.7：底层仅支持数组 + 链表，迁移时简单遍历旧数组的每个链表，通过头插法逐个将节点迁移至新数组，无拆分逻辑，迁移效率较低，且容易因多次哈希计算导致冲突。
JDK1.8：底层支持数组 + 链表 + 红黑树，迁移方式更复杂但更高效：通过hash & 旧容量将链表 / 红黑树一次性拆分为两组，无需重复计算哈希，直接按规则确定新下标并整体迁移，大幅提升了扩容的执行效率。

3. 并发安全性：非线程安全（有异常） vs 相对安全

HashMap 本身设计为非线程安全容器，不建议在并发场景下直接使用（推荐 ConcurrentHashMap），但两个版本在并发扩容时的表现不同：

JDK1.7：并发扩容时，头插法会导致链表倒置，多个线程同时操作易形成环形链表，调用get方法时会出现死循环，程序卡死。
JDK1.8：采用尾插法和整体迁移，不会形成环形链表，并发扩容时虽仍可能出现元素丢失、数据覆盖等问题，但避免了死循环这一严重异常，整体更 “安全”。

4. 红黑树支持：无 vs 支持（扩容可退化）

JDK1.7：底层无红黑树实现，仅靠数组 + 链表存储，当哈希冲突严重、链表过长时，查询效率会从 O (1) 退化至 O (n)，性能大幅下降。
JDK1.8：新增红黑树支持，当链表节点数大于 8 且数组容量大于 64 时，链表会树化为红黑树，将查询效率提升至 O (logn)；扩容时红黑树会被拆分，若拆分后子树节点数小于 6，会退化回链表，兼顾了查询效率和存储开销。