HashMap 底层原理全解｜从数组扩容到红黑树化

HashMap 是 Java 日常开发中使用频率最高的集合类之一，也是面试中的绝对高频考点。本文围绕 JDK 8 中 HashMap 的底层结构、hash 寻址、扩容机制、红黑树化条件以及 JDK 7 到 JDK 8 的演进展开，覆盖从 put 到 get 的完整链路。

底层三件套：数组 + 链表 + 红黑树

JDK 8 的 HashMap 底层由一个 Node[] table 数组构成，数组的每个位置称为一个“桶”（bucket）。根据哈希冲突的程度，桶内可能以不同结构存储数据：

反过来，当红黑树节点数被删到 ≤ 6 时，会退化为链表。6 和 8 之间留出 7 作为缓冲，防止在边界附近频繁转换造成性能抖动。

注意：链表长度达到 8 时并不会立即转树，还要满足数组长度 ≥ 64 的条件；若不满足，HashMap 会优先扩容。

定位下标分为两步：

① 扰动：

int h = key.hashCode();
int hash = h ^ (h >>> 16);

把 hashCode 的高 16 位与低 16 位做异或，让高位的特征也参与后续的取下标运算，减少碰撞。

② 按位与取下标：

int index = (n - 1) & hash;

其中 n 是数组长度。因为数组长度总是 2 的幂，n-1 的二进制低位全是 1，& 运算等价于 hash % n，但位运算更快。

哈希冲突无法完全避免：hashCode 有 2³² 种可能，而数组下标只有 n 个，必然存在多个 key 落入同一个桶的情况。

有两个核心原因：

原因一：位运算等价于取余

只有当 n 是 2 的幂时，(n - 1) & hash 才等价于 hash % n，结果均匀分布在 0 ~ n-1 之间。如果 n 不是 2 的幂，n-1 的二进制位中会出现 0，导致某些桶永远为空，分布严重不均。

原因二：扩容时定位成本极低

扩容时数组翻倍（16 → 32 → 64），每个元素的新下标只可能有两种情况：

也就是说，扩容时不需要对所有元素重新计算完整哈希，只需判断一个 bit 是 0 还是 1，JDK 8 利用这一点实现了高效的“高低位拆分”扩容。

默认初始容量：16
默认负载因子：0.75
触发扩容阈值：元素总数 ≥ 容量 × 负载因子
- 16 × 0.75 = 12，即元素达到 12 时触发第一次扩容
- 32 × 0.75 = 24 时触发第二次
- 以此类推

扩容时，数组长度翻倍（16 → 32），所有元素重新散列到新数组中（rehash）。这是一个 O(n) 的昂贵操作，但负载因子 0.75 在“内存浪费”和“查询效率”之间做了合理折中。

转换方向	触发条件
链表 → 红黑树	链表长度 ≥ 8 且数组长度 ≥ 64
红黑树 → 链表	树中节点数 ≤ 6

阈值 8 和 6 之间的缓冲（7）是为了避免在临界值附近反复转换，浪费性能。

get 方法的完整链路如下：

这里有两个分工明确的机制：

关键约束：equals 相同的两个对象，hashCode 必须相同。否则相同的 key 会被分到不同桶，导致 get 永远找不到。这也是为什么 HashMap 的 key 不应该使用可变字段——一旦 hashCode 变了，之前存入的数据就再也定位不到了。

维度	JDK 1.7	JDK 1.8	原因
底层结构	数组 + 链表	数组 + 链表 + 红黑树	极端情况下查询从 O(n) 降到 O(log n)，防哈希攻击
插入方式	头插法	尾插法	头插法在并发扩容时会产生“自环”，导致死循环 CPU 100%
扩容重散	全量重排	高低位拆分，仅判断新增 bit	更高效，利用 2 的幂特性
红黑树化	无	链长 ≥ 8 且数组 ≥ 64	防止链表过长导致性能退化

需要明确的是：无论是 1.7 还是 1.8，HashMap 都不是线程安全的。1.8 只是消除了“死循环”这个极端 bug，但多线程并发 put 仍然会出现数据覆盖、结构错乱等问题。真正需要并发场景时，应使用 ConcurrentHashMap。

理解 HashMap 的关键在于理清几个层次：