问题

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. 为什么 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);

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() 质量很差，会发生什么？