在Java 8的HashMap中，何时会使用红黑树？

八股文_Java集合面试题 0 2

参考回答**

在 Java 8 的 HashMap 中，为了解决哈希冲突导致的性能问题，当单个哈希桶（bucket）中的元素数量超过一定阈值时（默认是 8），HashMap 会将链表结构转换为红黑树结构。

这种优化能够显著提升在高冲突场景下的操作效率，从 Java 8 开始被引入。

详细讲解与拓展

1. 红黑树的引入背景

在 Java 8 之前，HashMap 处理哈希冲突时使用的是 拉链法，即通过链表存储冲突的元素。然而，当大量键的哈希值落入同一个桶（发生哈希冲突）时，链表的长度会变得很长，使得链表操作（如查找、插入、删除）的时间复杂度从 O(1) 退化为 O(n)。

为了优化这一点，Java 8 引入了 红黑树：

当桶中的元素数量超过一定阈值（默认是 8），链表会被转换为红黑树。
红黑树的查找、插入、删除的时间复杂度为 O(log n)，大大提升了性能。

2. 转换规则

HashMap 在 Java 8 中的红黑树使用规则如下：

链表转换为红黑树的条件：

当单个桶中的元素个数超过 8 时（即链表长度超过 8），链表会转换为红黑树。

红黑树回退为链表的条件：

如果一个桶中元素的数量小于或等于 6 时，红黑树会退化为链表。
原因：在链表和红黑树之间保持一个性能平衡，避免红黑树的维护开销（如旋转和重新平衡）在小数据量时带来额外开销。

必须满足的前提：

转换为红黑树的条件是 HashMap 的底层数组长度（table）达到 64，即只有在哈希桶总数足够多时，才会进行转换。
如果数组长度小于 64，即使单个桶中的元素数量超过 8，也不会进行转换，而是优先扩容。

3. 红黑树的实现

红黑树是一种 自平衡的二叉搜索树，其核心特点是通过颜色（红色或黑色）来约束树的高度，从而保持平衡。
红黑树的插入、删除、查找的时间复杂度是 O(log n)。

在 HashMap 中，每个桶中的红黑树由以下规则管理：

红黑树的节点存储了哈希值、键值对、链表指针等信息。
红黑树中的节点可以动态调整颜色和位置，保持平衡性。

4. 红黑树在 `HashMap` 中的存储方式

HashMap 的桶（bucket）使用了一个链表和红黑树的混合结构。当冲突的元素较少时，使用链表存储；当冲突的元素较多时，切换为红黑树。

内部的转换逻辑：

如果桶内的元素少于等于 8 个，则使用链表存储。
如果桶内的元素超过 8 个，且数组长度大于等于 64，则将链表转换为红黑树。

5. 优化效果

时间复杂度对比：

在链表中：查找、插入、删除操作的时间复杂度为 O(n)。
在红黑树中：查找、插入、删除操作的时间复杂度为 O(log n)。

因此，红黑树的引入显著提升了 HashMap 在高冲突场景下的性能，特别是对于一些带有高重复性哈希值的键集合。

示例代码：验证红黑树的使用

以下代码展示了在 HashMap 中，链表转换为红黑树的场景：

import java.util.HashMap;
import java.lang.reflect.Field;

public class HashMapTreeifyExample {
    public static void main(String[] args) throws Exception {
        HashMap<Integer, String> map = new HashMap<>();

        // 插入大量哈希冲突的键
        for (int i = 0; i < 20; i++) {
            map.put(i * 16, "Value" + i); // 保证所有键的哈希值落入同一个桶
        }

        // 通过反射获取底层的 Node 数组
        Class<?> hashMapClass = HashMap.class;
        Field tableField = hashMapClass.getDeclaredField("table");
        tableField.setAccessible(true);
        Object[] table = (Object[]) tableField.get(map);

        for (Object bucket : table) {
            if (bucket != null) {
                // 打印桶的结构信息
                System.out.println(bucket.getClass().getName());
            }
        }
    }
}

输出示例（在 Java 8 中运行）：

java.util.HashMap$TreeNode

解释：

HashMap$TreeNode 表示当前桶中的链表已经转换为红黑树。
如果没有超过转换阈值，输出为 HashMap$Node，表示仍为链表结构。

6. 总结

红黑树的使用场景：
- 在 Java 8 的 HashMap 中，当某个桶中的元素个数超过 8，且数组长度（容量）大于等于 64 时，链表会转换为红黑树。
优化目的：
- 解决哈希冲突导致的链表性能退化问题，将操作时间复杂度从 O(n) 提升为 O(log n)。
红黑树的回退：
- 如果桶中元素减少到 6 个以下，红黑树会退化为链表。
限制条件：
- 数组长度小于 64 时，优先扩容，而不会转换为红黑树。