HashMap 的扩容机制（JDK 8）

分类：集合

底层结构

JDK 8 的 HashMap 由数组、链表和红黑树组成。数组的每个位置叫一个桶，哈希冲突的元素先挂成链表，链表过长时转成红黑树。

几个关键参数

参数	默认值	说明
初始容量	16	第一次 `put` 时才真正分配数组；容量总是 2 的幂
负载因子	0.75	在时间和空间之间折中
阈值 threshold	容量 × 负载因子	元素个数超过阈值就扩容
TREEIFY_THRESHOLD	8	链表长度达到 8 时考虑树化
MIN_TREEIFY_CAPACITY	64	数组长度不足 64 时优先扩容，不树化
UNTREEIFY_THRESHOLD	6	扩容拆分后树节点不多于 6 个时退回链表

下标怎么算

先做一次扰动，让高 16 位参与运算，再和 n - 1 按位与：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 下标：index = hash & (n - 1)，n 为数组长度

扩容时元素怎么迁移

扩容时容量翻倍。因为容量是 2 的幂，一个元素在新数组里只可能落在两个位置之一：原下标 j，或者 j + oldCap。判断依据是 hash & oldCap 是否为 0，不需要重新计算哈希。

一条链表因此被拆成"低位"和"高位"两条，各自保持原来的相对顺序。JDK 8 改用尾插法，避免了 JDK 7 头插法在并发扩容时可能形成环形链表的问题。不过 HashMap 本身仍然不是线程安全的，并发场景应使用 ConcurrentHashMap。

实践建议

能预估元素数量 n 时，把初始容量设为 n / 0.75 + 1，可以避免多次扩容。
JDK 19 起可以直接用 HashMap.newHashMap(n)，它会按负载因子算好容量。
作为键的类要正确实现 hashCode 和 equals，并且不要在放入后修改参与计算的字段。