【集合框架HashMap扩容机制】

艾伦耶格尔

发布于 2025-08-28 15:55:01

1920

文章被收录于专栏：Java基础Java基础

“HashMap 不仅是面试常客，更是 Java 集合的‘心脏’。” 你是否曾好奇：

为什么 HashMap 的默认容量是 16？
为什么加载因子是 0.75？
为什么链表长度达到 8 才转红黑树？
为什么树化阈值是 64？
JDK 1.7 和 1.8 的扩容机制到底有何本质区别？

本文将带你深入 JDK 源码，从数据结构、扩容流程、参数设计原理到红黑树转换机制，全面剖析 HashMap 的底层实现。

📌 本文导读

✅ HashMap 基本结构回顾
✅ 扩容机制核心流程（put → 扩容 → rehash）
✅ JDK 1.7 与 1.8 扩容机制对比
✅ 关键参数设计原理（16、0.75、8、64）
✅ 红黑树何时形成？为何是 8？
✅ 扩容时的性能优化与线程安全问题
✅ 总结与最佳实践

一、HashMap 基本结构回顾

HashMap 是基于 数组 + 链表 + 红黑树 实现的哈希表：

transient Node<K,V>[] table; // 哈希桶数组

数组：存储 Node 节点，初始容量 16
链表：解决哈希冲突（拉链法）
红黑树：当链表过长时，转换为红黑树，提升查找性能

⚠️ HashMap 不是线程安全的，多线程环境下推荐使用 ConcurrentHashMap。

二、扩容机制核心流程

1. 何时触发扩容？

当 HashMap 中的元素个数（size）超过 阈值（threshold） 时，触发扩容。

threshold = capacity * loadFactor

capacity：当前数组容量（如 16、32、64…）
loadFactor：加载因子，默认 0.75

✅ 触发条件：size > threshold

2. 扩容流程（以 JDK 1.8 为例）

步骤 1：判断是否需要初始化

if (table == null || table.length == 0)
    resize(); // 初始化数组，容量为 16

步骤 2：计算新容量与新阈值

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;
    }
    // 新容量 = 旧容量 << 1（即 ×2）
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
        newThr = oldThr << 1; // 新阈值也 ×2
}

✅ 扩容后容量翻倍：16 → 32 → 64 → 128…

步骤 3：rehash（重新计算索引）

这是扩容最核心的步骤：将原数组中的每个元素重新分配到新数组中。

JDK 1.8 的优化：无需重新 hash

在 JDK 1.8 中，由于数组长度始终是 2 的幂，扩容时只需判断：

原索引位置是否需要迁移？

// e.hash & oldCap == 0 ? 原位置 : 原位置 + oldCap

如果 (e.hash & oldCap) == 0，元素留在原索引
否则，迁移到 原索引 + oldCap 位置

✅ 优势：无需重新计算 hash % n，性能大幅提升！

三、JDK 1.7 vs JDK 1.8 扩容机制对比

特性	JDK 1.7	JDK 1.8
数据结构	数组 + 单向链表	数组 + 链表 + 红黑树
扩容后 rehash 方式	全部重新 hash（indexFor(hash, capacity)）	利用 hash & oldCap 判断是否迁移
链表插入方式	头插法（导致环形链表）	尾插法（避免环）
并发问题	多线程扩容可能形成环，导致死循环	仍非线程安全，但避免了环形链表
性能	扩容慢，rehash 开销大	扩容快，rehash 仅位运算

🔥 关键区别：头插法 vs 尾插法

JDK 1.7 头插法：

e.next = newTable[bucketIndex];
newTable[bucketIndex] = e;

扩容时链表逆序，多线程下可能形成环形链表
get() 时无限循环，CPU 100%

JDK 1.8 尾插法：

loTail.next = e; // 追加到链表尾部

保持原有顺序，避免环形链表

✅ JDK 1.8 的设计更安全、更高效。

四、关键参数设计原理

1. 为什么默认容量是 16？

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

2 的幂次：便于通过 hash & (n-1) 快速计算索引（替代取模）
大小适中：太小频繁扩容，太大浪费内存
经验值：大多数场景下，16 足够应对初始数据量

✅ index = hash & (capacity - 1) 等价于 hash % capacity，但位运算更快。

2. 为什么加载因子是 0.75？

static final float DEFAULT_LOAD_FACTOR = 0.75f;

这是时间与空间的权衡：

加载因子	空间利用率	冲突概率	查找性能
过小（如 0.5）	低	低	快，但浪费内存
过大（如 0.9）	高	高	慢，链表变长
0.75	适中	适中	平衡

🔬 数学依据：根据泊松分布，当加载因子为 0.75 时，链表长度超过 8 的概率极低（见下文），既能保证空间利用率，又能控制冲突。

3. 为什么链表长度 ≥ 8 才转红黑树？

static final int TREEIFY_THRESHOLD = 8;

这是基于泊松分布（Poisson Distribution） 的统计结果：

JDK 源码注释中明确说明：

Because TreeNodes are about twice the size of regular nodes, we
use them only when bins contain enough nodes to warrant use
(see TREEIFY_THRESHOLD). And when they become too small (due to
removal or resizing) they are converted back to plain bins. In
usages with well-distributed user hashCodes, tree bins are
rarely used. Ideally, under random hashCodes, the frequency of
nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution)
with a parameter of about 0.5 on average for the default resizing
threshold of 0.75...

泊松分布计算结果：

链表长度	出现概率（理论值）
0	0.60653066
1	0.30326533
2	0.07581633
3	0.01263606
4	0.00157952
5	0.00015795
6	0.00001316
7	0.00000094
8	0.00000006

✅ 长度 ≥ 8 的概率仅为 0.00000006，几乎不可能在正常哈希下出现。一旦达到 8，说明：

哈希函数不够均匀
数据量极大
链表性能已严重下降

此时转换为红黑树（O(log n)）是合理选择。

4. 为什么树化阈值是 64？

static final int MIN_TREEIFY_CAPACITY = 64;

即使链表长度 ≥ 8，也不会立即转红黑树，必须满足：

table.length >= 64

否则，优先选择扩容。

为什么？

小数组下链表长是暂时现象：扩容后可能自动分散
红黑树节点占用空间是普通 Node 的 2 倍，过早树化浪费内存
扩容成本低：数组小，rehash 快

✅ 只有当数组足够大（≥64）且链表仍长（≥8），才说明哈希冲突严重，值得树化。

五、红黑树何时形成？何时退化？

1. 树化条件（同时满足）

链表长度 ≥ TREEIFY_THRESHOLD（8）
数组长度 ≥ MIN_TREEIFY_CAPACITY（64）

if (binCount >= TREEIFY_THRESHOLD - 1) {
    if (tab == null || tab.length < MIN_TREEIFY_CAPACITY)
        resize(); // 先扩容
    else
        treeifyBin(tab, i); // 转红黑树
}

2. 退化条件（删除或扩容时）

红黑树节点数 ≤ 6 时，退化为链表
扩容后，如果红黑树分裂，可能部分退化为链表

✅ 保持结构最优，避免“过度树化”。

六、扩容性能优化与线程安全

1. 扩容性能

JDK 1.8 优化：rehash 仅需位运算，无需重新 hash
扩容是耗时操作：应尽量避免频繁扩容
建议：预设合理初始容量，如 new HashMap<>(32)

2. 线程安全问题

HashMap 非线程安全
多线程下 put 可能导致：
- 数据覆盖
- 扩容时形成环形链表（JDK 1.7）
- 并发 rehash 数据错乱

✅ 多线程环境使用：

ConcurrentHashMap
Collections.synchronizedMap()

七、🔧 扩容流程图结构

+-----------------------------+
|        开始 put 操作         |
+-----------------------------+
               |
               v
+------------------------------+
|  计算 hash 值 & 索引位置     |
|   index = hash & (n - 1)     |
+------------------------------+
               |
               v
+------------------------------+
|  当前桶位是否为空？           |
+------------------------------+
         /           \
       是             否
       /               \
      v                 v
+-------------+   +------------------------+
| 直接创建新   |   | 遍历链表/红黑树         |
| Node 放入    |   | 查找 key 是否已存在     |
| 桶位         |   +------------------------+
+-------------+               |
                              |
                              v
                  +--------------------------+
                  |    key 是否已存在？       |
                  +--------------------------+
                       /               \
                     是                 否
                     /                   \
                    v                     v
         +------------------+   +------------------------+
         |  更新旧 value     |   |  添加新节点到末尾       |
         |  返回旧值         |   |  (尾插法)               |
         +------------------+   +------------------------+
                                       |
                                       v
                    +----------------------------------+
                    |   size++ 后是否 > threshold ?     |
                    |    (size > capacity * loadFactor) |
                    +----------------------------------+
                                 |
                                是
                                 |
                                 v
                    +-----------------------------+
                    |         触发 resize()        |
                    +-----------------------------+
                                 |
                                 v
                    +-----------------------------+
                    |   当前 table 是否为 null ?    |
                    +-----------------------------+
                         /               \
                       是                 否
                       /                   \
                      v                     v
          +---------------------+   +-----------------------------+
          | 初始化 table        |   | oldCap = oldTab.length      |
          | capacity = 16       |   | newCap = oldCap << 1 (×2)   |
          | threshold = 12      |   | newThr = oldThr << 1        |
          +---------------------+   +-----------------------------+
                      \                             /
                       \                           /
                        \                         /
                         \                       /
                          \                     /
                           \                   /
                            \                 /
                             \               /
                              \             /
                               \           /
                                \         /
                                 \       /
                                  \     /
                                   \   /
                                    \ /
                                     v
                    +----------------------------------+
                    |       创建新 table 数组           |
                    |       newTab = new Node[newCap]   |
                    +----------------------------------+
                                     |
                                     v
                    +----------------------------------+
                    |     遍历 oldTab 中每个桶位        |
                    +----------------------------------+
                                     |
                                     v
                    +----------------------------------+
                    |     当前桶位是否有元素？          |
                    +----------------------------------+
                                 |
                                否 --(继续下一个桶位)--> [循环]
                                 |
                                是
                                 |
                                 v
                    +----------------------------------+
                    |   元素是单节点？链表？红黑树？     |
                    +----------------------------------+
                       /            |             \
                      /             |              \
                     /              |               \
                    v               v                v
         +---------------+   +--------------+   +------------------+
         | 直接 rehash   |   | 遍历链表     |   | 调用 treeifyBin?  |
         | 计算新索引    |   | 计算新索引   |   | 或 split 拆分树    |
         | 放入 newTab   |   | 尾插法迁移   |   | 迁移到 newTab      |
         +---------------+   +--------------+   +------------------+
                     \               |               /
                      \              |              /
                       \             |             /
                        \            |            /
                         \           |           /
                          \          |          /
                           \         |         /
                            \        |        /
                             \       |       /
                              \      |      /
                               \     |     /
                                \    |    /
                                 \   |   /
                                  \  |  /
                                   \ | /
                                    \|/
                                     v
                    +----------------------------------+
                    |    所有元素迁移完成？             |
                    +----------------------------------+
                                 |
                                否 --(继续循环)--> [上一步]
                                 |
                                是
                                 |
                                 v
                    +----------------------------------+
                    |   table = newTab;                |
                    |   threshold = newThr;            |
                    |   resize 完成，返回新 table       |
                    +----------------------------------+
                                 |
                                 v
                    +----------------------------------+
                    |        put 操作继续执行           |
                    +----------------------------------+
                                 |
                                 v
                            [结束]

🎯 总结：HashMap 扩容核心要点

机制	原理	数值/条件
扩容触发	size > capacity * loadFactor	默认 0.75
扩容方式	容量 ×2	16 → 32 → 64…
rehash 优化	hash & oldCap 判断迁移	位运算，高效
链表转树	长度 ≥8 且容量 ≥64	基于泊松分布
树退化	节点 ≤6	保持结构最优
插入方式	尾插法（1.8）	避免环形链表