# 问题
4. HashMap 如何处理哈希冲突?为什么 1.8 之后引入红黑树?
# 标准答案
HashMap 主要通过 链地址法(Separate Chaining)+ 红黑树 处理哈希冲突。JDK 1.8 之前,所有冲突的 key 都存储在链表中,查找时间复杂度为 O(n)。JDK 1.8 之后,引入了 红黑树(Red-Black Tree),当链表长度超过 8 时,会转换为红黑树,将查找复杂度降低到 O(log n),大幅提升了性能。
# 答案解析
# 1. HashMap 的哈希冲突处理机制
HashMap 使用数组(table)存储 key-value,key 经过 hash()
计算索引 (n - 1) & hash
后映射到数组的某个 bucket。但由于 hashCode()
可能不同 key 计算出相同的索引,发生哈希冲突(Hash Collision)。
JDK 1.8 之前,HashMap 采用链地址法,即在相同 bucket 位置用 链表 存储冲突 key。JDK 1.8 后,在链表长度超过 8 时,自动转换为红黑树,提升查询性能。
存储结构变化(JDK 1.8 之前 vs. 之后):
JDK 1.7 (链表结构)
[0] -> (key1, value1) -> (key2, value2) -> (key3, value3) -> NULL [O(n)]
JDK 1.8 (链表 + 红黑树)
[0] -> (key1, value1) -> (红黑树: key2, key3, key4...) [O(log n)]
2
3
4
5
# 2. 为什么 JDK 1.8 引入红黑树?
1. 链表查找性能低下(O(n))
- 在极端情况下(如
hashCode()
质量差,所有 key 映射到相同 bucket),链表长度接近n
,查找get()
退化为 O(n),影响性能。
2. 红黑树查找更快(O(log n))
- 红黑树是一种 自平衡二叉搜索树(Balanced Binary Search Tree),插入、删除、查找的复杂度均为 O(log n),可极大提升冲突严重情况下的查询速度。
3. 为什么使用红黑树而不是 AVL?
- AVL 树严格平衡,插入/删除时旋转较多,成本更高。
- 红黑树在适当范围内平衡,插入/删除代价较低,查询速度仍然稳定在 O(log n)。
# 3. 红黑树的转换规则
- 链表 → 红黑树(Treeify):当某个 bucket 的链表长度 超过 8,并且 table 长度大于 64 时,转换为红黑树。
- 红黑树 → 链表(Untreeify):当 bucket 发生扩容,导致元素减少,链表长度降到 6 以下时,红黑树会退化回链表,减少额外的空间开销。
示例:
if (binCount >= TREEIFY_THRESHOLD - 1) // TREEIFY_THRESHOLD = 8
treeifyBin(tab, hash);
2
# 4. JDK 1.7 和 JDK 1.8 处理哈希冲突的区别
版本 | 哈希冲突处理 | 查找复杂度 | 扩容机制 |
---|---|---|---|
JDK 1.7 | 链地址法(数组 + 链表) | O(n)(链表) | 头插法,可能导致死循环 |
JDK 1.8 | 链地址法(数组 + 链表 + 红黑树) | O(n) → O(log n)(红黑树) | 尾插法,避免死循环 |
# 5. HashMap 的常见问题
❌ 常见误区
误以为 HashMap 100% 不会哈希冲突
- 即使
hashCode()
质量很好,哈希冲突仍然不可避免(n-1 & hash
可能映射到相同 bucket)。 - **优化:**自定义对象需要重写
hashCode()
,确保哈希分布均匀。
- 即使
误以为红黑树一定比链表快
- 红黑树的查找复杂度是 O(log n),但如果数据量小(
≤ 8
),链表的顺序查找 O(n) 反而更快。
- 红黑树的查找复杂度是 O(log n),但如果数据量小(
误认为 JDK 1.8 彻底解决了哈希冲突
- 仍然依赖
hashCode()
质量,如果 key 分布不均衡,可能依然导致某些 bucket 过度拥挤。
- 仍然依赖
# 深入追问
🔹 为什么 JDK 1.8 选择 8 作为树化的阈值?
🔹 HashMap 扩容时,红黑树如何处理?
🔹 为什么 treeify 需要 table 长度 >= 64?
🔹 高并发场景下,红黑树转换会不会有性能抖动?
# 相关面试题
• 红黑树的特点是什么?
• ConcurrentHashMap 如何解决哈希冲突?
• 如何优化 HashMap 的 hash 函数,使其减少冲突?
• 如果 hashCode()
质量很差,会发生什么?