HashMap 底层原理详解：从数组到红黑树的进化

面试官：“说说 HashMap 的底层实现？”
你：“数组+链表+红黑树，1.7 用头插，1.8 改尾插，长度超 8 且数组超 64 变树，低于 6 退链表……”
面试官：“好，下一个问题。”

HashMap 确实是 Java 后端面试的“老熟人”，但很多人只背了结论，稍一追问就卡壳。本文从源码角度，把 HashMap 的底层数据结构、哈希冲突、树化、扩容机制彻底讲透，顺便揭开几个容易混淆的细节。

---

一、HashMap 的整体结构：数组 + 链表 + 红黑树

无论 JDK 1.7 还是 1.8，HashMap 的主干都是一个 Node 数组（1.7 叫 Entry 数组）。每个数组元素称为一个 桶（bucket），用来存放键值对。

• JDK 1.7：数组 + 链表。发生哈希冲突时，新节点采用 头插法 插入链表。
• JDK 1.8：数组 + 链表 + 红黑树。当链表长度过长时，会转换为红黑树，提升查询性能；同时将头插法改为 尾插法，解决了多线程下扩容死循环的问题（但依然线程不安全）。

简单记：数组存头节点，冲突拉链，太长变树，满了扩容。

---

二、哈希冲突与拉链法

哈希冲突是指：两个不同的 key，通过 hash() 计算后得到了相同的数组下标。

HashMap 的解决办法是 拉链法：每个数组槽位其实是一个链表的头节点，冲突的节点都挂在同一个链表上。

// 1.8 中 Node 的结构
static class Node<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

当 put 一个键值对时：

1. 计算 hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)（扰动函数，让高位参与运算，降低冲突）
2. 计算数组下标 i = (n - 1) & hash
3. 如果 tab[i] 为空，直接新建节点放进去；
4. 如果不为空，遍历链表，找到相同 key 则覆盖 value，否则在链表尾部插入新节点（1.8 尾插）。

---

三、链表 → 红黑树：什么时候触发？

很多人背“链表长度 ≥ 8 就转红黑树”，但少了一个关键条件：数组长度必须 ≥ 64。

源码中的 treeifyBin 方法：

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY = 64)
    resize();  // 扩容，而不是树化
else if ((e = tab[index = (n - 1) & hash]) != null)
    treeifyBin(tab, hash);  // 真正转为红黑树

为什么需要两个条件？

• 如果数组很小（比如默认初始容量 16），链表长度达到 8 时，优先扩容一倍（容量变为 32、64…）。扩容后，原来冲突的节点会被重新散列到不同的桶中，链表自然变短，没必要树化。
• 只有当数组已经较大（≥64），且某个桶中冲突依然严重，才认为这是“恶意 hash 或极端场景”，此时树化可以避免查询退化为 O(n)。

为什么阈值是 8？

这是基于泊松分布的概率统计：在理想随机 hash 下，同一个桶内链表长度达到 8 的概率已经小于千万分之一。所以 8 是一个“非常不寻常”的信号，值得用红黑树来优化。

---

四、红黑树 → 链表：什么时候退化？

树化之后，如果因为删除或扩容导致节点数减少，红黑树会退化为链表，阈值是 6。

为什么不是 8 → 8 和 6 之间留了一个 缓冲（7）：

• 如果频繁在阈值边界插入/删除，会导致反复树化、链化，性能损耗严重。
• 设置为 6，意味着节点数降到 6 及以下才退化，避免震荡。

---

五、加载因子 0.75 与扩容机制

1. 默认加载因子为什么是 0.75？

加载因子 loadFactor = 0.75，表示当数组中的元素个数（总键值对数量）超过 数组容量 * 0.75 时，就触发扩容。

这是一个 时间和空间的权衡：

• 加载因子越大（比如 0.9），空间利用率高，但哈希冲突概率增加，查询变慢。
• 加载因子越小（比如 0.5），冲突少，查询快，但频繁扩容浪费内存。

0.75 是 JDK 工程师经过大量测试得出的经验值，兼顾了二者。

2. 扩容过程（resize）

扩容时，新数组容量为原来的 2 倍，然后遍历所有旧桶中的节点，重新计算下标并迁移。

• 在 1.7 中，迁移时采用头插法，导致链表顺序反转，多线程下可能形成环形链表。
• 在 1.8 中，重新计算下标时利用一个巧妙的优化：节点的新下标要么是原下标，要么是 原下标 + 旧容量，并且迁移时保持原有顺序（尾插），避免了死循环问题。

3. 扩容时机的误区

很多人以为“数组占用达到 75% 才扩容”，其实不是。
判断依据是总键值对数量（size） > 阈值（threshold = 容量 * 负载因子），而不是看数组里有多少个非空桶。

举例：容量 16，负载因子 0.75 → 阈值 12。即使 16 个桶中只有 1 个桶挂了 12 个节点，也会触发扩容（因为总 size = 12）。

---

六、几个容易忽略的细节

1. hash 扰动函数为什么要右移 16 位？

因为计算数组下标时只用了 hash 的低位（(n-1) & hash，n 通常较小）。如果不让高位参与，当容量较小时，很多不同高位的数据会冲突。

右移 16 位再异或，相当于把高 16 位“混入”低 16 位，让 hash 分布更均匀。

2. HashMap 的 key 可以为 null

null 的 hash 固定为 0，永远存放在数组的 0 号桶中。

3. 红黑树在 HashMap 中是“阉割版”

真正的红黑树需要实现左旋、右旋、变色等复杂逻辑，但 HashMap 中的 TreeNode 只实现了部分特性，且不要求严格的黑平衡，只保证近似平衡。因为 HashMap 的核心是哈希表，树只是“应急方案”。

---

七、HashMap 是线程安全的吗？

不是。 多线程环境下：

• 1.7 中扩容可能造成 环形链表，导致 get() 死循环。
• 1.8 中虽然修复了死循环，但仍然存在 数据覆盖 问题（两个线程同时 put 时，一个线程的值可能被覆盖）。

如果需要线程安全，可以用 ConcurrentHashMap（推荐）或 Collections.synchronizedMap（性能较差）。

---

八、面试高频追问

Q：为什么树化阈值是 8，退化阈值是 6，差 2 有什么意义？
A：避免频繁转换带来的性能开销。如果都是 8，删除一个变 7 就退化，再插入一个又树化，产生抖动。

Q：初始化容量是 100，实际容量是多少？
A：HashMap 会通过 tableSizeFor 方法找到大于等于 100 的最小 2 的幂次方，即 128。因为容量必须为 2 的幂，方便取模运算 (n-1) & hash。

Q：为什么容量必须是 2 的幂？
A：因为 hash % n 的运算效率低于 (n-1) & hash，后者要求 n 为 2 的幂时，n-1 的二进制全是 1，与运算相当于取模。

---

总结

特性	JDK 1.7	JDK 1.8
数据结构	数组 + 链表	数组 + 链表 + 红黑树
插入方式	头插法	尾插法
扩容死循环	存在	已修复
树化条件	无	链表长度≥8 且数组≥64
退化条件	无	节点数≤6

理解 HashMap 的关键在于：它本质上是一个 动态扩容的散列表，用链表解决冲突，在极端冲突时升级为红黑树，通过合理的加载因子和 2 的幂容量来平衡时空效率。

背下口诀不难，但只有理解了这些设计背后的权衡，面试时才能从容应对“为什么是 0.75”“为什么树化阈值是 8”这类追问。

希望这篇文章能帮你彻底拿下 HashMap 考点，欢迎留言讨论。