HashMap 为什么这么设计

读完这一节，你能做到

1. 说清 HashMap 的底层结构与各阈值。
2. 解释 hash 扰动与 (n-1) & hash 的作用。
3. 说清扩容、树化、退化三个机制的触发条件。
4. 判断 HashMap 在并发下会出什么问题。

一、底层结构

JDK 8 的 HashMap 是"数组 + 链表 + 红黑树"：

Node[] table
  └─ 每个桶：链表（长度 < 8）或红黑树（长度 ≥ 8 且容量 ≥ 64）

几个关键常量：

常量	默认值	含义
初始容量	16	必须是 2 的幂
负载因子	0.75	空间与冲突的折中
树化阈值	8	链表转红黑树
退化阈值	6	红黑树转回链表
最小树化容量	64	容量不足时先扩容而不是树化

为什么容量必须是 2 的幂？因为索引计算用 (n - 1) & hash 代替取模，位运算更快，且 2 的幂能让低位充分参与。

二、hash 扰动

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

把高 16 位异或到低 16 位，是为了让高位也参与索引计算。否则当容量较小时，只有低位起作用，高位信息被浪费，冲突会变多。

索引计算：index = (n - 1) & hash。当 n 是 2 的幂时，等价于 hash % n，但更快。

三、扩容与 rehash

当元素数量超过 capacity × loadFactor 时触发扩容，容量翻倍。JDK 8 的 rehash 有一个巧妙的优化：

旧索引 = hash & (oldCap - 1)
新索引 = hash & (newCap - 1)

由于 newCap = oldCap × 2，新索引只有两种可能：原索引，或原索引 + oldCap。判断依据是 hash & oldCap 是否为 0。这样不需要重新计算 hash，只需把链表拆成两条。

扩容是高成本操作，已知数据量时预设容量可以避免多次扩容。预设公式：expectedSize / 0.75 + 1，再向上取 2 的幂。

四、树化与退化

链表长度达到 8 且容量 ≥ 64 时转红黑树；红黑树节点减少到 6 时退化回链表。

为什么是 8？在理想的哈希分布下，链表长度达到 8 的概率极低（泊松分布，约千万分之六）。设成 8 是为了在极端冲突时兜底，而不是常态。

为什么不直接树化？红黑树节点占用的内存约为链表节点的两倍，且维护成本更高。阈值 8/6 之间留出缓冲，避免频繁转换。

红黑树的代价与收益

收益：极端冲突下，查找从 O(n) 降到 O(log n)，避免哈希攻击导致链表退化成线性。

代价：节点更大、插入删除需要旋转与变色、实现复杂。正常分布下链表很短，红黑树几乎不会被用到。

所以它是“兜底”而不是“常态”：阈值为 8，且容量不足 64 时优先扩容，而不是过早树化。

为什么 JDK 8 引入红黑树

JDK 7 在极端冲突下，链表查找退化为 O(n)，构造大量同哈希的 key 可以拖垮服务（哈希碰撞攻击）。红黑树把最坏情况压到 O(log n)，同时保留链表在低冲突下的低开销。

代价是复杂度与内存，所以用“阈值 + 容量”双条件限制，避免小表过早树化。

五、并发下的问题

HashMap 不是线程安全的，并发写入会出现：

• JDK 7 的死循环：头插法扩容时链表可能形成环，导致 CPU 100%。
• JDK 8 的数据覆盖：尾插法避免了环，但并发 put 仍可能丢失更新。
• size 不准：并发下计数错误。

解决方式：

方案	特点
Collections.synchronizedMap	全表锁，性能差
Hashtable	全表锁，已过时
ConcurrentHashMap	分段/CAS + synchronized 桶锁，推荐

ConcurrentHashMap 在 JDK 8 用 CAS + synchronized 锁单个桶，扩容时多线程协助迁移，读操作基本无锁。

HashMap 的遍历与性能

• 遍历顺序与桶的顺序、链表顺序有关，不稳定。
• 遍历时修改结构会 fail-fast，抛 ConcurrentModificationException。
• 大量扩容会导致性能抖动，能预估容量就预估。
• 哈希分布差（比如 key 都是 2 的幂）会让冲突集中，必要时换哈希策略。

六、常见坑

1. 用可变对象作为 key，字段变化后找不到。
2. 预设容量时没有按 0.75 折算，仍会扩容。
3. 认为树化阈值是 8 就一定树化（容量不足 64 时先扩容）。
4. 在并发场景用 HashMap 存共享数据。
5. 重写 equals 不重写 hashCode，导致桶定位错误。

七、动手任务：自写 → AI 写 → 对比 → 取舍

四步不跳：① 自己写（限时，关掉补全）→ ② 让 AI 写同一题 → ③ 逐条比对 → ④ 说出保留谁的写法。 完整动作与记录模板见《AI 协作与代码评审》。

① 自己写

1. 用反射打印 HashMap 的 table 长度与某个桶的链表长度。
2. 构造 8 个哈希冲突的 key，观察树化后的结构。
3. 对比预设容量与默认容量在 100 万次 put 下的耗时。

② 让 AI 写同一题

把第 1 题（手写一个简化版 HashMap）交给 AI，补一句 说明扩容与哈希冲突的处理，以及并发下的表现。

③ 对比要盯的点

• 默认容量、负载因子、树化阈值与退化阈值，它写的数字对吗？（16 / 0.75 / 8 / 6）
• 它有没有把“JDK 8 改尾插修掉了死循环”和“仍然线程安全”混为一谈？
• hash() 里的高位异或扰动它实现了吗？漏了就是退化性能。

④ 一句话取舍

它说“HashMap 线程不安全”时，能举出一个具体的失效场景吗？

八、自测

1. HashMap 的底层结构是什么？
2. 容量为什么必须是 2 的幂？
3. hash 扰动解决了什么问题？
4. 扩容时新索引如何计算？
5. JDK 7 与 JDK 8 的并发问题有什么不同？

参考答案要点：数组+链表+红黑树；位运算取模；高位参与；原索引或加 oldCap；死循环 vs 覆盖。

附录：高频追问

问：为什么负载因子是 0.75？ 空间与冲突的折中。太小浪费空间，太大冲突变多；0.75 在泊松分布下冲突概率较低。

问：为什么链表转红黑树的阈值是 8？ 正常分布下几乎不会达到 8；设 8 是为了极端冲突兜底，同时避免频繁转换。

问：为什么退化阈值是 6 而不是 8？ 留出缓冲，避免在 7/8 之间反复转换。

问：HashMap 的 key 可以为 null 吗？ 可以，null 的 hash 固定为 0，放在 0 号桶；ConcurrentHashMap 不允许。

问：HashMap 线程不安全的表现？ JDK 7 扩容成环导致死循环；JDK 8 并发 put 丢数据、size 不准。

问：ConcurrentHashMap 为什么高效？ 锁粒度到桶，读基本无锁，扩容支持多线程协助迁移。

问：LinkedHashMap 怎么实现 LRU？ 构造时 accessOrder=true，重写 removeEldestEntry 在超过容量时移除最久未访问的节点。

问：HashMap 的遍历顺序稳定吗？ 不稳定，随扩容与哈希分布变化；需要顺序用 LinkedHashMap 或 TreeMap。

问：为什么 JDK 8 改成尾插法？ 避免扩容时链表成环，同时保持插入顺序的相对稳定。

问：HashMap 扩容一定翻倍吗？ 是，容量始终为 2 的幂，翻倍保证位运算索引成立。

一个容量估算例子

预计存 1,000 个元素，按 0.75 负载因子，需要容量 ≥ 1333；向上取 2 的幂为 2048。直接 new HashMap<>(2048) 可以避免多次扩容。先算容量，再建表；容量估算是最便宜的优化。先算后建。

配套题目

★ 越多越该先背；点题目可看完整答案与深入版。

• ★★★★★ ConcurrentHashMap 是怎么保证线程安全的？
• ★★★★☆ ArrayList 和 LinkedList 该怎么选？
• ★★★☆☆ HashSet 和 TreeSet 有什么区别？
• ★★★★★ 线程池的核心参数有哪些？为什么不推荐用 Executors 创建？