我要评论今天来给大家再讲解一下hashmap的扩容机制。一个小小的数据结构里面隐藏着许多优化与细节！
一、为什么需要扩容？
hashmap 的底层数据结构是 数组 + 链表（jdk 1.8 引入了红黑树）。
数组的长度是固定的。随着我们不断执行 put 操作，越来越多的键值对（entry/node）被放入容器。为了解决哈希冲突，链表会越来越长。
问题：链表越长，查询效率越低，时间复杂度从 o(1) 退化为 o(n)。
解决：当元素数量达到一定阈值时，hashmap 会自动创建一个更大的数组，并将所有数据重新搬家到新数组中。这个过程就是 扩容（resize）。
核心参数
capacity (容量)：hashmap 中数组（bucket）的长度，默认 16。
loadfactor (负载因子)：衡量 hashmap 满的程度，默认 0.75f。
threshold (扩容阈值)：
capacity * loadfactor。当size超过这个值时，触发扩容。
思考：为什么负载因子是 0.75？ 这是一个空间与时间的折中（trade-off）。
如果是 1.0：空间利用率高，但哈希冲突概率大，查询慢。
如果是 0.5：哈希冲突少，查询快，但浪费一半空间。
0.75 是基于泊松分布统计学原理得出的黄金平衡点。
二、扩容的触发时机
在 put 方法存入数据后，hashmap 会检查当前元素个数 size 是否大于 threshold。
// 伪代码逻辑
if (++size > threshold)
resize();jdk 1.8 是先插入数据，再判断是否需要扩容；而 jdk 1.7 是先判断是否需要扩容，再插入数据。
三、扩容流程
当我们的hashmap中的元素个数（size）达到负载因子*容量之后，会触发扩容
此时会建一个新数组，数组容量为old数组的俩倍 ：newcap = oldcap*2
扩容分三种情况：
- 仅有一节点
- 已形成链表
- 已形成红黑树
接下来分情况讨论
3.0 高低位拆分原理
jdk 8 利用容量为 2 的幂次方的特性，通过 (e.hash & oldcap) == 0 判断元素在新数组中的位置：
- 低位（lo）：
hash & oldcap == 0→ 新索引 = 原索引 - 高位（hi）：
hash & oldcap != 0→ 新索引 = 原索引 + oldcap
为什么呢？
我们在进行索引计算的时候，是使用hash(k) & (cap - 1) 计算的，那么这里面其实有个规律
我们每次扩容都是容量*2，假设旧的容量为16，那么新容量为16 * 2 = 32
原本是通过hash(k) & (01111)进行计算索引的（01111是16-1的二进制），新数组的索引是通过hash(k) & (011111) 进行计算的，会发现其实是否迁移新的位置取决于第原本hash的第
log(cap) + 1位，对于16就是4 + 1 = 5位，也就是说，如果我们的hash&cap == 0就放置原索引，如果hash&cap != 0就放到原索引+oldcap
3.1 仅有一节点
这是最简单的情景，只要把这个节点迁移到新数组即可
if (e.next == null)
newtab[e.hash & (newcap - 1)] = e;假设原桶（索引 3）中有一条链表：a → b → c → d → null
3.2 已形成链表
迁移步骤：
- 初始化两条空链表
- 低位链表：
lohead=null, lotail=null - 高位链表：
hihead=null, hitail=null
- 低位链表：
- 逐节点判断并拆分
节点
hash & 16 结果
操作
a
==0（低位）
lohead=a, lotail=a→ 低位链表：a → ?b
!=0（高位）
hihead=b, hitail=b→ 高位链表：b → ?c
==0（低位）
lotail.next=c, lotail=c→ 低位链表：a → c → ?d
!=0（高位）
hitail.next=d, hitail=d→ 高位链表：b → d → ? - 断尾与安置
lotail.next = null→ 低位链表变为a → c → nullhitail.next = null→ 高位链表变为b → d → null- 低位链表放入
newtab[3] - 高位链表放入
newtab[19]
对于每个形成链表的桶都会重复这个步骤
也就是说会通过对每个桶的链表通过hash&oldcap的情况来分成俩个链表，然后再进行迁移
3.3 已形成红黑树
红黑树节点（treenode）同时维护两种结构：
- 红黑树结构：
parent/left/right（用于查找） - 双向链表：
prev/next（用于遍历和扩容）
扩容时只利用双向链表进行拆分，不操作树结构。
阶段 1：拆分为两条 treenode 链表
假设原桶（索引 3）中有 9 个 treenode 节点，按双向链表顺序遍历：
- 初始化：
- 低位：
lohead=null, lotail=null, lc=0 - 高位：
hihead=null, hitail=null, hc=0
- 低位：
- 逐节点拆分（与链表逻辑一致，但维护
prev指针）：节点
hash & 16
操作
低位链表
高位链表
lc/hc
n1
==0
插入低位
n1-
lc=1
n2
!=0
插入高位
n1n2hc=1
n3
==0
插入低位
n1→n3n2lc=2
n4
!=0
插入高位
n1→n3n2→n4hc=2
...
...
...
...
...
...
n9
==0
插入低位
n1→n3→n5→n7→n9n2→n4→n6→n8lc=5, hc=4
每次插入时：
- 设置
e.prev = lotail（维护双向链表） lotail.next = e（连接到尾部）lotail = e（更新尾指针）e.next = null（立即断开原链表引用，防止内存泄漏）
- 设置
阶段 2：计数完成后的决策
拆分结束后，根据每条链表的节点数做决策：
链表 | 节点数 | 决策逻辑 | 结果 |
|---|---|---|---|
低位 | 5 |
| 调用 |
高位 | 4 |
| 调用 |
退化阈值 = 6（
untreeify_threshold）
树化阈值 = 8（treeify_threshold）
6 < 8 的设计是为了防止"抖动"：避免扩容拆分后频繁在树/链表间切换
阶段 3：树化条件（仅当节点数 > 6 时触发）
若某条链表节点数 > 6，还需满足两个条件才重建红黑树：
- 节点数 > 6（已满足）
- 数组总长度 ≥ 64（
min_treeify_capacity）
满足条件后执行 treeify()：
- 按链表顺序逐个插入到新红黑树中
- 每次插入后调用
balanceinsertion()进行平衡调整（旋转 + 变色） - 最后调用
moveroottofront()将树根移到双向链表头部
若数组长度 < 64（如刚扩容到 32），即使节点数 > 6 也不树化，保持为 treenode 链表。原因：容量仍较小，下次扩容可能又拆分退化，避免无效树化。
也就是拆分成俩个链表->判断是否树化->迁移至新桶
3.4 talk is cheap show me code
看看源码加注释吧
单节点、链表迁移
// hashmap.resize() 方法片段 - 链表迁移
for (int j = 0; j < oldcap; ++j) { // 遍历旧数组每个桶
node<k,v> e;
if ((e = oldtab[j]) != null) { // 桶非空
oldtab[j] = null; // 清空原桶，便于gc
if (e.next == null) // 单节点：直接迁移
newtab[e.hash & (newcap - 1)] = e;
else if (e instanceof treenode) // 红黑树：调用split()（见下文）
((treenode<k,v>)e).split(this, newtab, j, oldcap);
else { // ===== 链表迁移核心逻辑 =====
// 初始化两条新链表的头尾指针
// lo = low（低位），hi = high（高位）
node<k,v> lohead = null, lotail = null; // 低位链表：新索引 = 原索引
node<k,v> hihead = null, hitail = null; // 高位链表：新索引 = 原索引 + oldcap
node<k,v> next;
// 遍历原链表，逐节点拆分
do {
next = e.next; // 1. 保存当前节点的next，防止断链后无法继续遍历
// 2. 高低位判断：(hash & oldcap) == 0 ?
// oldcap是2的幂（如16=0b10000），此操作等价于判断hash的第5位是否为0
// - 为0：新索引 = 原索引（低位）
// - 非0：新索引 = 原索引 + oldcap（高位）
if ((e.hash & oldcap) == 0) {
// ===== 低位链表插入（尾插法）=====
if (lotail == null) // 首次插入：设置头节点
lohead = e;
else // 非首次：尾节点的next指向当前节点
lotail.next = e;
lotail = e; // 更新尾指针为当前节点
} else {
// ===== 高位链表插入（尾插法）=====
if (hitail == null)
hihead = e;
else
hitail.next = e;
hitail = e;
}
} while ((e = next) != null); // 移动到下一个节点，继续遍历
// 3. 断尾操作：必须将两条链表的尾节点next置为null！
// 原因：遍历时未断开原链表引用，若不置null可能形成跨桶环形引用
if (lotail != null) {
lotail.next = null; // 低位链表尾部断开
newtab[j] = lohead; // 放入新数组的原索引位置
}
if (hitail != null) {
hitail.next = null; // 高位链表尾部断开
newtab[j + oldcap] = hihead; // 放入新数组的原索引+oldcap位置
}
}
}
}红黑树迁移
/**
* 红黑树拆分方法（定义在 treenode 内部类中）
*
* @param map 当前 hashmap 实例
* @param tab 扩容后的新数组
* @param index 原桶在旧数组中的索引
* @param bit 旧容量 oldcap（2的幂，如16）
*/
final void split(hashmap<k,v> map, node<k,v>[] tab, int index, int bit) {
// 1. 获取当前桶的树根节点（同时也是双向链表头节点）
treenode<k,v> b = this;
// 2. 初始化两条新链表的头尾指针（注意：此时仍是treenode，非普通node）
treenode<k,v> lohead = null, lotail = null; // 低位链表
treenode<k,v> hihead = null, hitail = null; // 高位链表
// 3. 计数器：记录高低位链表的节点数量，用于后续退化判断
int lc = 0, hc = 0;
// ===== 阶段1：按双向链表顺序遍历拆分 =====
// 注意：这里遍历的是双向链表（通过next指针），不是红黑树结构！
for (treenode<k,v> e = b, next; e != null; e = next) {
// 保存当前节点的next指针（双向链表的next，非树结构的right）
next = (treenode<k,v>)e.next;
// 【关键】断开原链表引用！
// 原因：防止残留引用导致内存泄漏，也为后续重建树做准备
e.next = null;
// 高低位判断（与链表迁移逻辑完全相同）
if ((e.hash & bit) == 0) {
// 低位链表插入（维护双向链表的prev指针）
// e.prev = lotail：设置当前节点的prev指向原尾节点
// 若lotail为null（首次插入），则e.prev = null
if ((e.prev = lotail) == null)
lohead = e; // 首次插入：设置头节点
else
lotail.next = e; // 非首次：原尾节点的next指向当前节点
lotail = e; // 更新尾指针
++lc; // 低位计数+1
} else {
// 高位链表插入（逻辑同上）
if ((e.prev = hitail) == null)
hihead = e;
else
hitail.next = e;
hitail = e;
++hc; // 高位计数+1
}
}
// ===== 阶段2：低位链表处理 =====
if (lohead != null) {
// 退化判断：节点数 ≤ 6 时退化为普通链表
// untreeify_threshold = 6（定义在hashmap类中）
if (lc <= untreeify_threshold) {
// untreeify()：将treenode链表转换为普通node链表
// 过程：遍历每个treenode，创建对应的node对象，丢弃树结构指针
tab[index] = lohead.untreeify(map);
} else {
// 节点数 > 6：保留为treenode，准备重建红黑树
tab[index] = lohead;
// 优化：仅当高位链表非空时才重建树
// 原因：若高位为空，说明所有节点都在低位，树结构未被破坏，无需重建
if (hihead != null) {
// treeify()：将treenode链表重建为红黑树
// 过程：按链表顺序逐个插入，每次插入后进行平衡调整
((treenode<k,v>)lohead).treeify(tab);
}
}
}
// ===== 阶段3：高位链表处理（逻辑同低位）=====
if (hihead != null) {
if (hc <= untreeify_threshold) {
tab[index + bit] = hihead.untreeify(map);
} else {
tab[index + bit] = hihead;
if (lohead != null) {
((treenode<k,v>)hihead).treeify(tab);
}
}
}
}四、总结
会发现java众多数据结构中的一个hashmap就已经有很多优化了，通过一次次版本的迭代，优化成了现在的样子！
到此这篇关于java hashmap扩容机制的文章就介绍到这了,更多相关java hashmap扩容机制内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！
发表评论