HashMap 几乎是每个 Java 工程师每天都在用的容器，但真正能讲清楚它扩容时为什么不需要重新计算哈希、链表什么时候变红黑树、为什么多线程下会丢数据甚至 CPU 飙到 100% 的人并不多。这篇文章从源码层面把这几件事拆开。

场景：一个看似无害的 Map

设想一个高并发缓存：多个线程往同一个 HashMap 里 put，没有加锁，因为"读多写少，偶尔写一下应该没事"。线上跑了几周突然有一台机器 CPU 飙满，线程 dump 显示一堆线程卡在 HashMap.get。这就是经典的 HashMap 并发死循环（JDK 7）或数据错乱（JDK 8）。要理解为什么，得先看它的内部结构。

机制一：哈希扰动与寻址

HashMap 底层是一个 Node[] 数组（table），每个槽位（bucket）挂一条链表或一棵红黑树。定位槽位的核心是这段代码：

1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

为什么要 h ^ (h >>> 16)？因为最终定位下标用的是 (n - 1) & hash，而 n（数组容量）是 2 的幂，n - 1 的高位全是 0。如果直接用原始 hashCode，高 16 位完全参与不了运算，碰撞率会显著升高。把高 16 位异或到低 16 位，相当于让高位也"搅拌"进来，这就是所谓的扰动函数。用 & 而不是取模，是因为对 2 的幂取模等价于按位与，而位运算快得多——这也是容量必须是 2 的幂的根本原因。

机制二：扩容时的高低位拆分

当元素数量超过 容量 * 负载因子（默认 0.75）时触发扩容（resize），容量翻倍。JDK 8 在这里做了一个很漂亮的优化：扩容时不需要重新计算每个 key 的 hash。

关键在于：容量从 n 变成 2n，下标计算从 (n-1) & hash 变成 (2n-1) & hash。两者唯一的区别是参与运算的多了一个 bit——即 hash 在 n 这个二进制位上是 0 还是 1：

1
2
原容量 16:  (16-1) = 01111
新容量 32:  (32-1) = 11111   多看的就是 10000 这一位

所以一条链表里的节点，扩容后只会被拆成两条：那一位是 0 的留在原下标 j（低位链表 lo），是 1 的搬到 j + oldCap（高位链表 hi）。源码大致如下：

1
2
3
4
5
6
7
8
9
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;
}

这避免了重算 hash，而且因为是顺序遍历追加，JDK 8 扩容后链表内部相对顺序保持不变。这一点很重要：正是它修复了 JDK 7 头插法导致的死循环。JDK 7 用头插法（rehash 时反转链表），在并发扩容下两个线程可能把链表节点的 next 指针搅成环，后续 get 走到这个环就无限循环，表现为 CPU 100%。

机制三：树化与退化

当某个 bucket 的链表长度达到 TREEIFY_THRESHOLD（8），并且 table 容量达到 MIN_TREEIFY_CAPACITY（64）时，链表转为红黑树；如果容量不足 64，则优先扩容而不是树化。反过来，当树节点数降到 UNTREEIFY_THRESHOLD（6）以下时退化回链表。

为什么阈值是 8？这不是拍脑袋。在哈希分布良好（接近泊松分布）的情况下，单个 bucket 里出现 8 个元素的概率极低（量级约百万分之一）。换句话说，链表正常情况下根本不该长到 8。一旦达到 8，往往意味着要么哈希函数很差，要么遭遇了哈希碰撞攻击。树化是一个兜底：把单 bucket 的查找从 O(n) 降到 O(log n)，防止退化成线性表被恶意构造慢查询打垮。

设置 6 和 8 两个不同阈值（而非都用 7）是为了避免在临界点反复树化/退化（抖动），留出一个缓冲区间。

工程权衡：容量、负载因子与内存

  • 初始容量：如果你知道大致要放多少元素，应预设容量。new HashMap<>(expectedSize / 0.75 + 1) 可以避免多次扩容。注意构造函数传入的容量会被 tableSizeFor 向上取整到 2 的幂。常见误区是写 new HashMap<>(64) 以为放 64 个不扩容，实际放到 64 * 0.75 = 48 个就触发扩容了。
  • 负载因子：0.75 是时间与空间的折中。调高（如 0.9）省内存但碰撞增多、查询变慢；调低（如 0.5）查询快但浪费空间。绝大多数场景不要动它。
  • 扩容代价：扩容是 O(n) 的全表搬迁，且会产生新数组、旧数组待回收，瞬时内存接近翻倍。大 Map 频繁扩容会造成 GC 压力和延迟毛刺。

线上踩坑清单

  1. 并发 put 不要用 HashMap。JDK 8 虽然消除了死循环，但并发扩容仍可能丢数据、覆盖元素、size 计数错乱。需要并发就用 ConcurrentHashMap。
  2. key 的 hashCode/equals 必须稳定。如果把可变对象当 key，put 之后改了字段导致 hashCode 变化，这个 entry 就再也找不到了（定位到了错误的 bucket）。
  3. 迭代时修改抛 ConcurrentModificationException。modCount 在迭代器创建时被快照，结构性修改（put 新 key、remove）会使其失配，触发 fail-fast。要在迭代中删除，用 Iterator.remove()。
  4. 依赖遍历顺序是危险的。HashMap 不保证顺序，且扩容会改变 bucket 分布。需要顺序用 LinkedHashMap。

小结

HashMap 的精妙之处集中在几个数字背后的工程考量：容量是 2 的幂以便位运算寻址，扰动函数让高位参与，扩容靠 hash & oldCap 一位之差完成高低位拆分而免去重算，树化是抵御哈希碰撞退化的兜底。理解这些机制，不仅能在面试时讲清楚，更能在真实系统里避开并发死循环和无谓的扩容抖动。