1. 扩容触发条件

当满足以下条件时会触发扩容：

// 当元素数量 size 大于等于阈值 threshold 时
if (++size > threshold)
    resize();

其中：

// 阈值 = 容量 × 负载因子
threshold = capacity * loadFactor;

2. 默认参数

// 默认初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;  // 16

// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;  // 1073741824

3. 扩容机制详解

3.1 扩容时机

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;
    
    // 计算索引
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 处理哈希冲突
        // ...
    }
    
    // 检查是否需要扩容
    if (++size > threshold)
        resize();
    
    return null;
}

3.2 扩容过程

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    // 1. 计算新容量
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 新容量 = 旧容量 × 2
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 新阈值 = 旧阈值 × 2
            newThr = oldThr << 1; 
    }
    // ... 其他情况处理
    
    // 2. 创建新数组
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    
    // 3. 迁移数据
    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)
                    // 单个节点，直接重新计算位置
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 红黑树节点
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { 
                    // 链表节点，优化迁移
                    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;
                        }
                        // 原索引 + oldCap 位置
                        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;
                    }
                }
            }
        }
    }
    
    // 4. 更新阈值
    threshold = newThr;
    return newTab;
}

4. 扩容优化（JDK 1.8）

4.1 索引计算优化

JDK 1.7：

// 每个元素都需要重新计算索引
int index = indexFor(e.hash, newCapacity);

static int indexFor(int h, int length) {
    return h & (length - 1);
}

JDK 1.8：

// 通过位运算判断元素位置
// (e.hash & oldCap) == 0 → 位置不变
// (e.hash & oldCap) != 0 → 位置 = 原位置 + oldCap

// 示例：
// oldCap = 16 (10000)
// newCap = 32 (100000)
// 
// 元素 hash = 5 (00101)
// 5 & 16 = 0 → 位置不变
//
// 元素 hash = 21 (10101)
// 21 & 16 = 16 → 位置 = 原位置 + 16

4.2 链表迁移优化

// 将链表分成两个链表
// loHead/loTail: 位置不变的节点
// hiHead/hiTail: 位置 = 原位置 + oldCap 的节点

Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;

do {
    next = e.next;
    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);

5. 扩容过程图解

5.1 扩容前

容量: 16
阈值: 12 (16 * 0.75)
元素数量: 12

数组结构:
[0] → null
[1] → Node1 → Node2 → Node3
[2] → null
...
[15] → null

5.2 扩容后

容量: 32
阈值: 24 (32 * 0.75)
元素数量: 12

数组结构:
[0] → null
[1] → Node1 → Node3  (hash & 16 == 0)
[2] → null
...
[17] → Node2  (hash & 16 != 0, 位置 = 1 + 16)
...
[31] → null

6. 红黑树处理

6.1 链表转红黑树

// 当链表长度 >= 8 且数组长度 >= 64 时
if (binCount >= TREEIFY_THRESHOLD)
    treeifyBin(tab, hash);

static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;

6.2 红黑树转链表

// 当红黑树节点 <= 6 时
if (lc <= UNTREEIFY_THRESHOLD)
    tab[index] = untreeify(loHead);

static final int UNTREEIFY_THRESHOLD = 6;

6.3 扩容时红黑树处理

// 红黑树节点也会被分成两部分
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> e = this;
    // 分成低位和高位两个树
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    
    for (TreeNode<K,V> p = e; p != null; p = p.next) {
        int ph = p.hash;
        if ((ph & bit) == 0) {
            // 低位树
            if ((p.prev = loTail) == null)
                loHead = p;
            else
                loTail.next = p;
            loTail = p;
            ++lc;
        } else {
            // 高位树
            if ((p.prev = hiTail) == null)
                hiHead = p;
            else
                hiTail.next = p;
            hiTail = p;
            ++hc;
        }
    }
    
    // 根据节点数量决定是否转回链表
    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            if (hiHead != null)
                loHead.treeify(tab);
        }
    }
    // ... 类似处理高位树
}

7. 扩容示例

public class HashMapResizeDemo {
    public static void main(String[] args) {
        // 创建 HashMap，默认容量 16，负载因子 0.75
        HashMap<Integer, String> map = new HashMap<>();
        
        // 添加元素
        for (int i = 0; i < 20; i++) {
            map.put(i, "Value" + i);
            
            // 打印容量信息
            if (i == 11 || i == 12) {
                System.out.println("添加第 " + (i + 1) + " 个元素后:");
                printCapacityInfo(map);
            }
        }
    }
    
    static void printCapacityInfo(HashMap<?, ?> map) {
        try {
            // 使用反射获取内部信息
            java.lang.reflect.Field tableField = 
                HashMap.class.getDeclaredField("table");
            tableField.setAccessible(true);
            Object[] table = (Object[]) tableField.get(map);
            
            java.lang.reflect.Field thresholdField = 
                HashMap.class.getDeclaredField("threshold");
            thresholdField.setAccessible(true);
            int threshold = (int) thresholdField.get(map);
            
            java.lang.reflect.Field sizeField = 
                HashMap.class.getDeclaredField("size");
            sizeField.setAccessible(true);
            int size = (int) sizeField.get(map);
            
            System.out.println("  容量: " + (table != null ? table.length : 0));
            System.out.println("  阈值: " + threshold);
            System.out.println("  大小: " + size);
            System.out.println();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

8. 扩容性能分析

8.1 时间复杂度

// 扩容操作
resize() - O(n)  // n 是元素数量

// 均摊分析
// 假设扩容从 16 → 32 → 64 → 128
// 每次扩容需要复制所有元素
// 但扩容次数是 log(n)
// 所以均摊到每次 put 操作是 O(1)

8.2 空间复杂度

// 扩容时需要创建新数组
// 临时占用 2 倍内存
// 旧数组会被 GC 回收

9. 扩容优化建议

9.1 预估初始容量

// 如果知道大概的元素数量，设置初始容量
int expectedSize = 1000;
// 计算合适的初始容量：expectedSize / 0.75 + 1
int initialCapacity = (int) (expectedSize / 0.75) + 1;

HashMap<Integer, String> map = new HashMap<>(initialCapacity);

9.2 调整负载因子

// 内存敏感场景，提高负载因子
Map<Integer, String> map = new HashMap<>(16, 0.9f);

// 性能敏感场景，降低负载因子
Map<Integer, String> map = new HashMap<>(16, 0.5f);

9.3 批量操作优化

// 批量添加时，先设置足够大的容量
HashMap<Integer, String> map = new HashMap<>(1000);
for (int i = 0; i < 1000; i++) {
    map.put(i, "Value" + i);
}

10. 扩容流程总结

1. 添加元素
   ↓
2. size++ > threshold?
   ↓ 是
3. 计算新容量 newCap = oldCap × 2
   ↓
4. 计算新阈值 newThr = oldThr × 2
   ↓
5. 创建新数组 newTab[newCap]
   ↓
6. 遍历旧数组，迁移元素：
   - 单个节点：重新计算位置
   - 链表：分成两个链表
   - 红黑树：分成两个树
   ↓
7. 更新 table = newTab
   ↓
8. 更新 threshold = newThr
   ↓
9. 完成扩容

11. JDK 版本差异

JDK 1.7 vs JDK 1.8

特性 JDK 1.7 JDK 1.8
扩容方式 重新计算所有元素索引 优化索引计算
链表处理 重新插入 分成两个链表
数据结构 数组 + 链表 数组 + 链表 + 红黑树
头插法 是 否（尾插法）
并发问题 可能死循环 不会死循环

总结

HashMap 扩容机制的核心要点：

  1. 触发条件：size > threshold（容量 × 负载因子）
  2. 扩容倍数：新容量 = 旧容量 × 2
  3. 索引优化：通过位运算快速确定新位置
  4. 链表优化：将链表分成两部分，避免重新计算
  5. 红黑树处理：树节点也会被分成两部分
  6. 性能：单次 O(n)，均摊 O(1)

优化建议：

  • 预估初始容量，避免频繁扩容
  • 根据场景调整负载因子
  • 批量操作前设置合适容量
  • 注意 JDK 1.8 的优化特性
# java # 哈希算法 # 开发语言
Logo
https://edu.csdn.net/learn/39067/627173?utm_source=2019755004

汇聚全球AI编程工具，助力开发者即刻编程。

更多推荐

cover

四天蒸发近2000亿，宇树科技股价近乎“腰斩”；苹果举办库克告别派对：9月1日正式卸任CEO；Anthropic两款新Claude模型曝光 | 极客头条

avatar AI编程社区
cover

Claude Code反超GitHub Copilot登顶第一、90%程序员已用上Agent，最新AI编码调查报告来了

avatar AI编程社区
cover

如何用好 Claude Code 写后端代码

avatar AI编程社区