深入理解 Java HashMap 扩容机制：从源码到原理全解析

一、为什么需要扩容？

HashMap 底层是一个数组 + 链表/红黑树的结构。数组长度是固定的，随着元素不断插入，哈希冲突概率增大，链表越来越长，查询效率从 O(1) 退化为 O(n)。

为了维持高效的查询性能，HashMap 在元素数量达到一定阈值后会自动进行扩容（resize）。

二、核心参数

扩容触发条件：

当前元素数量（size）> threshold（容量 × 负载因子）

默认情况下：16 × 0.75 = 12，即插入第 13 个元素时触发扩容。

三、扩容策略：容量翻倍

每次扩容，新数组容量 =旧容量 × 2。

// JDK 8 源码（resize 方法节选） int newCap = oldCap << 1; // 左移1位 = ×2 int newThr = oldThr << 1; // 阈值也同步翻倍

容量始终保持 2 的幂次方，这是 HashMap 设计的核心约束，与后续的位运算寻址密切相关。

四、扩容全过程（JDK 8）

4.1 resize() 方法整体流程

final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { // 已达最大容量，不再扩容 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 正常扩容：容量和阈值均翻倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; } else if (oldThr > 0) newCap = oldThr; // 使用指定初始容量 else { // 使用默认值初始化 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 创建新数组 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; // 将旧数组元素迁移到新数组 // ...（见下文） return newTab; }

4.2 数据迁移（rehash）

扩容后，所有元素需要重新计算在新数组中的位置。

JDK 8 的优化：利用容量是 2 的幂次这一特性，元素在新数组中的位置只有两种情况：

• 原位置不变：新增高位 bit 为 0
• 原位置 + 旧容量：新增高位 bit 为 1

// 判断高位 bit if ((e.hash & oldCap) == 0) { // 放到低位链表（原位置） } else { // 放到高位链表（原位置 + oldCap） }

这个设计避免了重新计算 hash，极大提升了扩容效率。

图示说明（以 oldCap=16 为例）：

五、链表与红黑树的处理

JDK 8 中，链表长度 ≥ 8 时会转为红黑树。扩容时对两种结构分别处理：

5.1 链表拆分

// 将链表拆分为两条：lo（低位）和 hi（高位） Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { // 低位链表 if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { // 高位链表 if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }

5.2 红黑树拆分

红黑树同样按高低位拆分。拆分后：

• 若子树节点数 ≤ 6，退化回链表（untreeify）
• 若节点数 > 6，重新构建红黑树（treeify）

六、疑问

JDK 7 与 JDK 8 扩容对比

⚠️JDK 7 头插法的并发危险：多线程扩容时，头插法可能导致链表成环，引发get()死循环。JDK 8 改为尾插法解决了这一问题，但 HashMap 仍非线程安全，多线程场景请使用ConcurrentHashMap。

负载因子为什么是 0.75？

这是空间与时间的权衡：

• 过小（如 0.5）：扩容频繁，空间浪费多，但冲突少
• 过大（如 1.0）：内存利用率高，但冲突多，链表变长，查询慢
• 0.75：在泊松分布下，桶中元素碰撞概率较低，综合性能最优

官方注释中也提到，在理想随机 hash 下，0.75 的负载因子使得链表长度超过 8 的概率约为 0.00000006，极低。

初始容量的选择？

如果能预估元素数量，建议手动指定初始容量，避免多次扩容带来的性能损耗：

// 预计存放 1000 个元素 // 初始容量 = 预计数量 / 负载因子 + 1 int initialCapacity = (int)(1000 / 0.75) + 1; // ≈ 1334，HashMap 会向上取2的幂 = 2048 Map<String, Object> map = new HashMap<>(initialCapacity);

或者直接使用 Guava 的工具方法：

// Guava Map<String, Object> map = Maps.newHashMapWithExpectedSize(1000);

七、总结