拉链法导致的链表过深问题为什么用红黑树

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌拉链法导致的链表过深问题为什么用红黑树？

题目详细答案

在JDK 8中，HashMap采用红黑树来解决拉链法导致的链表过深问题，主要是为了提高在高冲突情况下的性能。

拉链法中的链表过深问题

在传统的拉链法中，当多个键的哈希值冲突时，这些键会被存储在同一个桶（bucket）中，形成一个链表。如果链表过长，查找、插入和删除操作的时间复杂度会退化为O(n)，其中n是链表中的元素个数。这种情况下，HashMap的性能会显著下降。

红黑树的优势

红黑树是一种自平衡的二叉搜索树，具有以下特性：

  1. 自平衡：红黑树通过颜色属性（红色和黑色）和一系列的旋转操作，保证树的高度近似平衡。其高度不会超过2 * log(n)，其中n是树中的节点数。
  2. 高效的查找、插入和删除：红黑树的查找、插入和删除操作的时间复杂度为O(log n)，远优于链表在最坏情况下的O(n)。

为什么选择红黑树

  1. 性能优化：在链表长度较短时，链表操作的性能是可以接受的。然而，当链表长度超过一定阈值（JDK 8中为8）时，链表操作的性能会显著下降。此时，将链表转换为红黑树，可以将操作的时间复杂度从O(n)降低到O(log n)，显著提高性能。
  2. 平衡性：红黑树通过自平衡机制，保证树的高度始终保持在一个较低的水平，避免了链表过长导致的性能问题。
  3. 空间效率：虽然红黑树比链表占用更多的空间（因为需要存储颜色和指针信息），但在链表长度较长时，性能的提升通常会超过空间开销的增加。

实现细节

在JDK 8的HashMap中，当链表长度超过阈值（8）时，会将链表转换为红黑树。

1
2
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);

treeifyBin方法将链表转换为红黑树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}
wechat
天生我才必有用