# 问题

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)]
1
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);
1
2

# 4. JDK 1.7 和 JDK 1.8 处理哈希冲突的区别

版本 哈希冲突处理 查找复杂度 扩容机制
JDK 1.7 链地址法(数组 + 链表) O(n)(链表) 头插法,可能导致死循环
JDK 1.8 链地址法(数组 + 链表 + 红黑树) O(n) → O(log n)(红黑树) 尾插法,避免死循环

# 5. HashMap 的常见问题

常见误区

  1. 误以为 HashMap 100% 不会哈希冲突

    • 即使 hashCode() 质量很好,哈希冲突仍然不可避免(n-1 & hash 可能映射到相同 bucket)。
    • **优化:**自定义对象需要重写 hashCode(),确保哈希分布均匀。
  2. 误以为红黑树一定比链表快

    • 红黑树的查找复杂度是 O(log n),但如果数据量小(≤ 8),链表的顺序查找 O(n) 反而更快。
  3. 误认为 JDK 1.8 彻底解决了哈希冲突

    • 仍然依赖 hashCode() 质量,如果 key 分布不均衡,可能依然导致某些 bucket 过度拥挤。

# 深入追问

🔹 为什么 JDK 1.8 选择 8 作为树化的阈值?
🔹 HashMap 扩容时,红黑树如何处理?
🔹 为什么 treeify 需要 table 长度 >= 64?
🔹 高并发场景下,红黑树转换会不会有性能抖动?

# 相关面试题

红黑树的特点是什么?
ConcurrentHashMap 如何解决哈希冲突?
如何优化 HashMap 的 hash 函数,使其减少冲突?
如果 hashCode() 质量很差,会发生什么?