HashMap 源码设计
HashMap 是理解 Java 集合实现的核心入口。学习它时不要只记“数组 + 链表 + 红黑树”，更重要的是把 put 流程、扩容规则、哈希扰动、红黑树化、线程不安全原因，以及它和 ConcurrentHashMap 的差异串起来。
1. 底层结构
JDK 1.8 之后，HashMap 的底层结构是：
数组 + 链表 + 红黑树核心数组叫 table，数组中的每个位置叫一个桶。发生哈希冲突时，多个节点会挂在同一个桶下：
table[i] -> Node -> Node -> Node当链表过长时，会转成红黑树：
table[i] -> TreeNode这样可以把极端冲突下的查询复杂度从 O(n) 降到 O(log n)。
2. 核心字段
常见字段含义：
| 字段 | 含义 |
|---|---|
table | 底层数组 |
size | 当前键值对数量 |
threshold | 下一次扩容阈值 |
loadFactor | 负载因子，默认 0.75 |
modCount | 修改次数，用于 fail-fast |
扩容阈值通常是：
threshold = capacity * loadFactor默认负载因子是 0.75，这是时间和空间之间的折中：负载因子太小浪费空间，太大冲突变多。
3. 为什么容量必须是 2 的幂
HashMap 定位桶下标时不是直接取模，而是：
(n - 1) & hash当 n 是 2 的幂时，n - 1 的二进制低位全是 1，与运算等价于取模：
hash % n == (n - 1) & hash这样做有两个好处：
- 位运算比取模更快。
- 扩容时可以利用二进制新增位快速判断节点新位置。
如果容量不是 2 的幂，(n - 1) & hash 的分布会不均匀，冲突会变多。
4. hash() 扰动函数
JDK 1.8 的 HashMap 会对 key 的 hashCode() 做一次扰动：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}这样做是为了让高 16 位也参与到低位计算中。
因为桶下标计算只使用低位：
(n - 1) & hash如果很多 key 的低位相同，即使高位不同，也会落到同一个桶。高低位异或后，可以降低冲突概率。
5. put 流程
简化流程：
put(key, value)
-> 计算 hash
-> 如果 table 为空，先初始化
-> 根据 (n - 1) & hash 定位桶
-> 桶为空：直接插入新节点
-> 桶不为空：
-> key 相同：覆盖 value
-> 桶是链表：尾插法插入
-> 桶是红黑树：按红黑树规则插入
-> 如果链表长度超过阈值，尝试树化
-> size + 1
-> 如果 size 超过 threshold，扩容注意：JDK 1.8 链表插入使用尾插法，JDK 1.7 使用头插法。JDK 1.7 在并发扩容时可能出现链表成环问题。
6. 扩容机制
当元素数量超过阈值时触发扩容。扩容容量通常变成原来的 2 倍：
newCap = oldCap << 1扩容后，旧桶中的节点只会去两个位置之一：
原下标 i
i + oldCap判断依据是：
hash & oldCap如果结果为 0，节点仍在 i；如果结果不为 0，节点移动到 i + oldCap。
原因是容量翻倍后，参与下标计算的二进制位多了一位。只需要判断这新增的一位是 0 还是 1。
7. 链表转红黑树
链表转红黑树需要同时满足：
链表长度 >= 8
数组长度 >= 64如果链表长度达到 8，但数组长度还小于 64，HashMap 优先选择扩容，而不是树化。
这是因为数组较小时，冲突很可能是容量不足导致的，扩容能更有效地降低冲突。
红黑树退化回链表的阈值是 6。使用 8 和 6 两个不同阈值，是为了避免链表和红黑树之间频繁转换。
8. 为什么线程不安全
HashMap 没有任何同步控制，多线程同时写入时可能出现：
- 数据覆盖。
size统计不准确。- 扩容过程中数据丢失。
- JDK 1.7 并发扩容时链表可能成环。
- 迭代时并发修改会触发
ConcurrentModificationException。
所以多线程写场景应该使用 ConcurrentHashMap，或者在外部做同步控制。
9. HashMap、LinkedHashMap、TreeMap、ConcurrentHashMap
| 容器 | 底层结构 | 是否有序 | 是否线程安全 | 典型场景 |
|---|---|---|---|---|
HashMap | 数组 + 链表 + 红黑树 | 无序 | 否 | 普通 key-value 存储 |
LinkedHashMap | HashMap + 双向链表 | 插入顺序或访问顺序 | 否 | LRU、顺序遍历 |
TreeMap | 红黑树 | 按 key 排序 | 否 | 范围查询、排序 |
ConcurrentHashMap | 数组 + 链表 + 红黑树 | 无序 | 是 | 并发读写 |
10. 理解检查
为什么重写 equals 必须重写 hashCode？
因为 HashMap 先根据 hashCode 定位桶，再用 equals 判断 key 是否相等。如果两个对象 equals 相等但 hashCode 不同，它们可能落到不同桶，导致逻辑上相同的 key 被存成多份。
为什么负载因子默认是 0.75？
这是空间利用率和查询效率的折中。负载因子越大，空间越省，但冲突越多；负载因子越小，冲突越少，但数组空间浪费越多。
为什么链表长度到 8 才树化？
哈希分布正常时，链表很少变长。长度达到 8 已经是低概率事件，说明冲突比较严重。树化可以降低极端情况下的查询复杂度。
为什么数组长度小于 64 时不树化？
数组太小时，冲突通常来自容量不足。扩容比树化更划算。
11. 总结
HashMap 的核心是：用数组定位桶，用链表或红黑树处理冲突，用 2 的幂容量和扰动函数优化哈希分布，用扩容降低冲突概率。它追求的是单线程场景下的高性能，不提供并发安全。