在Java 8的HashMap中，为什么链表长度达到8时才转换为红黑树？这个数字8有何特殊含义？

八股文_Java集合面试题 0 2

参考回答**

在 Java 8 中，HashMap 的实现进行了优化，当单个桶中的链表长度达到 8 时，会将链表转换为红黑树。这是为了提高查询和操作的性能，避免退化为线性时间复杂度（O(n)）。这个阈值 8 是经过仔细权衡和设计选择的。

原因分析：为什么选择 8？

时间复杂度的平衡：
- 在链表中，查找、插入和删除的时间复杂度是 O(n)（n 是链表长度）。
- 红黑树的操作复杂度是 O(log n)。
- 当链表长度较小时（比如小于 8），链表的操作性能优于红黑树，因为链表结构简单，没有树的旋转、节点维护等额外开销。
- 当链表长度超过 8 时，红黑树的 O(log n) 性能优于链表的 O(n)，因此选择 8 作为转换阈值。
存储和性能的权衡：
- 红黑树相比链表需要更多的内存（节点需要存储额外的父节点、左子节点和右子节点的引用）。
- 链表虽然简单，但当长度超过一定范围时，性能会急剧下降。
- 经过大量实验和性能测试，8 是一个合理的折中点，既能保证性能，又不会过多增加内存开销。
哈希冲突的概率分布：
- 在一个理想的哈希分布中，哈希冲突（多个键映射到同一个桶）的概率符合泊松分布。
- 如果桶中元素数量平均分布，当链表长度达到 8 时，已经属于极端情况，只有很小的概率会发生。
- 因此，这个阈值在实际场景中很少被触发。
避免过早转换：
- 如果设置阈值过低（例如 4 或更小），红黑树的额外内存开销可能得不偿失，因为低负载因子的情况下，链表的性能足够好。
- 如果设置阈值过高（例如 16 或更大），链表长度过长时性能会急剧下降，影响操作效率。

详细讲解与拓展

1. 转换过程：从链表到红黑树

当单个桶中元素的数量达到 8 时，链表会转换为红黑树：
- 链表插入新元素时检查长度：如果链表长度达到 8，就进行转换。
- 红黑树的优点：树的查找时间复杂度是 O(log n)，性能大幅提升。
- 链表的删除优化：当树中节点数量减少到 6 以下时，红黑树会退化回链表（节省内存开销）。

2. 源码解析

HashMap 的转换逻辑位于 java.util.HashMap 类的 Node<K, V> 和 TreeNode<K, V> 相关代码中。

转换的关键代码：TreeifyBin 方法

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
        resize();
    } else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        tab[index] = hd;
        if (hd != null)
            hd.treeify(tab);
    }
}

treeifyBin：当链表长度超过 8 时，将桶中的链表转换为红黑树。
MIN_TREEIFY_CAPACITY：在转换之前，会检查数组容量，如果容量小于 64，则会先扩容，而不是直接转换为红黑树。

3. 为什么不是其他数字？

性能测试的结果：
- 经过实验，8 是一个最优的折中值：既不会过早增加内存开销，也能在性能开始下降之前转换为红黑树。
- 如果选择更小的值（如 4），虽然能提前优化性能，但内存开销会显著增加。
- 如果选择更大的值（如 16），性能可能因为链表长度过长而大幅下降。
理论支持：泊松分布：
- 在哈希表中，桶中元素数量符合泊松分布。假设负载因子为 0.75，计算链表长度达到 8 的概率：
- 链表长度 = k，概率公式为：P(k) = (e^(-λ) * λ^k) / k!，其中 λ 是平均哈希冲突的元素数量。
- 当链表长度 >= 8 的概率非常小，转换阈值设为 8 足以覆盖大多数场景。

4. 红黑树的成本

时间复杂度：
- 链表的查找时间复杂度是 O(n)，而红黑树是 O(log n)。
- 在链表长度较小时，操作性能差异不明显，但随着链表长度增加，链表性能会迅速下降。
内存开销：
- 链表的节点只需要一个数据引用和一个指向下一个节点的引用。
- 红黑树的节点需要额外存储父节点、左子节点和右子节点的引用，以及颜色信息。

因此，红黑树在长度较短时的性能优势不足以抵消额外的内存开销，只有当长度较长（≥8）时才值得转换。

5. 扩展：为什么在长度减少到 6 时退化为链表？

红黑树的维护操作（如插入、删除）需要平衡树结构，操作复杂度较高。
当节点数量较少时，红黑树的额外开销大于链表的开销。
因此，当树中元素数量减少到 6 时，HashMap 会将红黑树退化回链表，以节省内存和计算资源。

总结

链表长度达到 8 时转换为红黑树：
- 8 是基于性能、内存和概率分布权衡后的最优选择。
- 超过 8 后，链表性能（O(n)）变差，而红黑树（O(log n)）性能提升。
转换策略的意义：
- 提升查询和操作性能，避免最坏情况下的线性复杂度。
- 在保持高效操作的同时，尽可能降低内存开销。
实践中的影响：
- 在大多数实际应用中，链表长度达到 8 是极少见的情况。
- Java 8 的这种优化使 HashMap 在高负载因子和高冲突率的情况下表现更好。