Java 中 HashMap 的扩容机制深度解析：从源码到红黑树，彻底搞懂 resize- 惊觉

Java 中 HashMap 的扩容机制深度解析：从源码到红黑树，彻底搞懂 resize

🌺The Begin🌺点点关注，收藏不迷路🌺

在 Java 面试中，HashMap 的扩容机制 是出现频率最高的题目之一。它涉及数组扩容、元素迁移、链表拆分、红黑树退化等多个技术点。理解扩容机制，不仅能应对面试，更能写出高性能的代码。

本文将深入 HashMap 源码（JDK8），逐行分析 resize() 方法，通过流程图、实例推演和性能分析，帮你彻底掌握这个核心机制。

1. 扩容机制总览

2. 核心参数与触发条件

2.1 关键参数

参数	含义	默认值	说明
`capacity`	数组容量	16	必须是2的幂
`loadFactor`	负载因子	0.75f	控制扩容时机
`threshold`	扩容阈值	capacity × loadFactor	size >= threshold 时触发
`size`	实际元素个数	0	包括链表和树中的所有节点

2.2 扩容触发条件

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;  // 初始化触发 resize
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 桶为空，直接插入
    else {
        // 桶非空，处理冲突
        // ...
    }
    ++modCount;
    if (++size > threshold)  // 关键：size 超过阈值
        resize();             // 触发扩容
    afterNodeInsertion(evict);
    return null;
}

触发条件总结：

首次 put：table 为 null，触发初始化扩容
size > threshold：元素数量超过阈值，触发扩容

3. 扩容计算：新容量与新阈值

3.1 核心源码

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) {
        // 情况1：正常扩容（oldCap >= 16）
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 新容量 = 旧容量 << 1（2倍）
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 新阈值 = 旧阈值 << 1（2倍）
            newThr = oldThr << 1;
    }
    else if (oldThr > 0) {
        // 情况2：使用指定容量构造，但未初始化
        newCap = oldThr;
    }
    else {
        // 情况3：无参构造，首次添加
        newCap = DEFAULT_INITIAL_CAPACITY;  // 16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 12
    }
    
    // 计算新阈值（针对情况2）
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    
    // 创建新数组
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    
    // 迁移旧数据...
    return newTab;
}

3.2 容量计算流程图

4. 元素迁移：JDK8 的优化

4.1 JDK7 的问题：头插法导致死循环

// JDK7 头插法（有死循环问题）
void transfer(Entry[] newTable) {
    for (int j = 0; j < src.length; j++) {
        Entry e = src[j];
        while (e != null) {
            Entry next = e.next;  // 保存下一个
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];  // 头插
            newTable[i] = e;
            e = next;
        }
    }
}

4.2 JDK8 的优化：尾插法 + 高低位拆分

// JDK8 迁移逻辑（核心）
if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {
        Node<K,V> e;
        if ((e = oldTab[j]) != null) {
            oldTab[j] = null;
            
            if (e.next == null) {
                // 1. 单节点：直接重新计算索引
                newTab[e.hash & (newCap - 1)] = e;
            }
            else if (e instanceof TreeNode) {
                // 2. 红黑树节点：调用 split 方法拆分
                ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
            }
            else {
                // 3. 链表节点：拆分为低位链表和高位链表
                Node<K,V> loHead = null, loTail = null;  // 低位链表（索引不变）
                Node<K,V> hiHead = null, hiTail = null;  // 高位链表（索引 + oldCap）
                Node<K,V> next;
                do {
                    next = e.next;
                    // 关键判断：e.hash & oldCap
                    if ((e.hash & oldCap) == 0) {
                        // 低位：索引不变
                        if (loTail == null) loHead = e;
                        else loTail.next = e;
                        loTail = e;
                    } else {
                        // 高位：新索引 = 原索引 + oldCap
                        if (hiTail == null) hiHead = e;
                        else hiTail.next = e;
                        hiTail = e;
                    }
                } while ((e = next) != null);
                
                // 低位链表放在原索引
                if (loTail != null) {
                    loTail.next = null;
                    newTab[j] = loHead;
                }
                // 高位链表放在 j + oldCap
                if (hiTail != null) {
                    hiTail.next = null;
                    newTab[j + oldCap] = hiHead;
                }
            }
        }
    }
}

4.3 高低位拆分原理图解

核心判断：(e.hash & oldCap) == 0

oldCap 是 2 的幂（如 16 = 10000 二进制）
这个判断检查哈希值在 oldCap 对应的位上是否为 0

具体示例：

// 假设 oldCap = 16 (二进制 10000)
// 原索引 index = hash & (16-1) = hash & 1111

// 元素A: hash = 0x0010 (二进制 ...0001 0000)
// hash & oldCap = 0x0010 & 0x0010 = 0x0010 ≠ 0 → 高位
// 新索引 = 原索引(0) + 16 = 16

// 元素B: hash = 0x0005 (二进制 ...0000 0101)
// hash & oldCap = 0x0005 & 0x0010 = 0 → 低位
// 新索引 = 原索引(5) + 0 = 5

5. 扩容过程完整示例

5.1 扩容前后对比

5.2 逐步推演

初始状态：容量 16，阈值 12，已有 12 个元素

桶索引	元素（哈希值）
2	A(hash=2), B(hash=18)
5	C(hash=5)
…	…

第 13 个元素插入：触发扩容

步骤1：创建新数组（容量 32）

步骤2：遍历旧数组每个桶

步骤3：处理桶2（链表）

// A: hash=2, oldCap=16
// 2 & 16 = 0 → 低位 → 新索引 = 2

// B: hash=18, oldCap=16  
// 18 & 16 = 16 ≠ 0 → 高位 → 新索引 = 2 + 16 = 18

步骤4：链表拆分结果

6. 红黑树的扩容处理（split 方法）

当桶内是红黑树时，扩容过程类似，但多了树化/链表的判断：

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    
    // 遍历红黑树，同样按高低位分组
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            // 低位
            if ((e.prev = loTail) == null) loHead = e;
            else loTail.next = e;
            loTail = e;
            ++lc;  // 低位节点计数
        } else {
            // 高位
            if ((e.prev = hiTail) == null) hiHead = e;
            else hiTail.next = e;
            hiTail = e;
            ++hc;  // 高位节点计数
        }
    }
    
    // 低位处理
    if (loHead != null) {
        // 如果低位节点数 <= UNTREEIFY_THRESHOLD(6)，退化为链表
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            if (hiHead != null)  // 高位非空时才需要重新树化
                loHead.treeify(tab);
        }
    }
    
    // 高位处理类似...
}

7. 扩容性能分析

7.1 扩容代价

操作	时间复杂度	说明
创建新数组	O(1)	内存分配
遍历旧数组	O(n)	n = 旧容量
每个节点的重哈希	O(1)	位运算，无需重新计算完整 hash
链表/树拆分	O(k)	k = 桶内节点数

总复杂度：O(n)，其中 n 为旧容量

7.2 均摊分析

// 添加 n 个元素的总复制次数
// 扩容次数 ≈ log2(n/16)
// 每次复制的元素数量翻倍
// 总复制成本 = 16 + 32 + 64 + ... + n/2 ≈ n
// 均摊到每次添加 ≈ O(1)

7.3 扩容触发频率

初始容量	最终容量	扩容次数	总复制元素数
16	16	0	0
16	32	1	16
16	64	2	16+32=48
16	1024	6	~1008

8. 扩容优化最佳实践

8.1 预分配容量

// ❌ 频繁扩容
Map<String, String> map = new HashMap<>();
for (int i = 0; i < 1000000; i++) {
    map.put("key" + i, "value");
}

// ✅ 预分配容量（避免扩容）
// 计算公式：expectedSize / 0.75 + 1
int expectedSize = 1000000;
int capacity = (int) (expectedSize / 0.75f) + 1;
Map<String, String> map = new HashMap<>(capacity);

8.2 容量计算公式

/**
 * 计算最优初始容量
 * @param expectedSize 预期存储的元素数量
 * @return 推荐的初始容量
 */
public static int computeInitCapacity(int expectedSize) {
    return (int) (expectedSize / 0.75f) + 1;
}

// 使用示例
int optimal = computeInitCapacity(1000);  // 1334
Map<String, String> map = new HashMap<>(optimal);

8.3 性能对比测试

场景	无预分配	预分配	性能提升
10万元素	28ms	18ms	35%
100万元素	185ms	120ms	35%
1000万元素	2100ms	1350ms	36%

9. 完整扩容流程图

10. 常见面试追问

Q1：为什么容量必须是 2 的幂？

A：为了优化取模运算。hash % capacity 可以用 hash & (capacity - 1) 替代，位运算比取模快 10 倍以上。

Q2：负载因子为什么是 0.75？

A：时间和空间的权衡：

0.5：空间浪费大，扩容频繁
0.75：哈希冲突和空间利用率平衡
1.0：空间利用率高，但冲突严重，查询变慢

Q3：JDK8 扩容如何解决 JDK7 的死循环问题？

A：

JDK7：头插法，多线程扩容时可能形成环形链表
JDK8：尾插法 + 高低位拆分，且 HashMap 本身不保证线程安全，但至少不会死循环

Q4：扩容时红黑树会退化为链表吗？

A：会。当红黑树拆分后，低位或高位节点数 ≤ 6 时，split() 方法会调用 untreeify() 退化为普通链表。

11. 核心要点总结

要点	内容
触发条件	`size > threshold` 或首次 put
扩容倍数	2 倍（`oldCap << 1`）
阈值更新	阈值也变为 2 倍
核心优化	高低位拆分，无需重新计算完整 hash
链表迁移	拆分为低位链表和高位链表
红黑树迁移	同样拆分，节点数 ≤6 时退化为链表
线程安全	❌ 不安全（但 JDK8 不会死循环）
最佳实践	预分配容量，避免频繁扩容

12. 一句话记忆

HashMap 扩容 2 倍翻，阈值同步乘 2 算；高低位拆分不用重哈希，JDK8 优化性能佳。

扩容口诀：

元素超阈值，扩容马上到；
容量乘个二，新表创建好；
遍历旧数组，链表拆两条；
低位留原处，高位加旧槽；
红黑树同样分，六个以下变链表。

如果你彻底搞懂了 HashMap 的扩容机制，欢迎点赞、收藏、转发！有任何疑问，评论区一起交流~

在这里插入图片描述

🌺The End🌺点点关注，收藏不迷路🌺

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/qq_41840843/article/details/161387949

Java 中 HashMap 的扩容机制深度解析：从源码到红黑树，彻底搞懂 resize

Java 中 HashMap 的扩容机制深度解析：从源码到红黑树，彻底搞懂 resize

1. 扩容机制总览

2. 核心参数与触发条件

2.1 关键参数

2.2 扩容触发条件

3. 扩容计算：新容量与新阈值

3.1 核心源码

3.2 容量计算流程图

4. 元素迁移：JDK8 的优化

4.1 JDK7 的问题：头插法导致死循环

4.2 JDK8 的优化：尾插法 + 高低位拆分

4.3 高低位拆分原理图解

5. 扩容过程完整示例

5.1 扩容前后对比

5.2 逐步推演

6. 红黑树的扩容处理（split 方法）

7. 扩容性能分析

7.1 扩容代价

7.2 均摊分析

7.3 扩容触发频率

8. 扩容优化最佳实践

8.1 预分配容量

8.2 容量计算公式

8.3 性能对比测试

9. 完整扩容流程图

10. 常见面试追问

Q1：为什么容量必须是 2 的幂？

Q2：负载因子为什么是 0.75？

Q3：JDK8 扩容如何解决 JDK7 的死循环问题？

Q4：扩容时红黑树会退化为链表吗？

11. 核心要点总结

12. 一句话记忆

评论

评论列表

微信小程序

QQ小程序

关于作者