HashMap链表转红黑树源码解读

一、触发链表转红黑树的条件（以 Java 8 的 HashMap 为例）

1. 链表长度阈值：当链表长度达到 8 时TREEIFY_THRESHOLD = 8。

2. 哈希桶数量阈值：哈希表的容量（桶数量）需达到64MIN_TREEIFY_CAPACITY = 64。

   若仅链表长度达标，但桶数量不足 64，会优先进行扩容（resize）而非树化。

二、链表转红黑树的核心步骤

1. 节点类型转换：

   将链表节点（Node<K,V>）转换为树节点（TreeNode<K,V>），每个树节点保存父节点、左子节点、右子节点和颜色信息。

2. 构建红黑树：

   按插入顺序将链表节点依次插入红黑树，通过比较键的哈希值或键的自然顺序（需实现Comparable接口）确定插入位置。

3. 平衡调整：

   插入后若违反红黑树性质（如颜色冲突），通过左旋、右旋、颜色翻转进行调整，确保树的平衡性。

三、源码实现分析（Java 8 HashMap 的 treeifyBin 方法）

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 若哈希表容量不足64，优先扩容而非树化
    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;
        // 1. 将链表转换为树节点链表
        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);
        // 2. 将树节点链表转换为红黑树
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

// TreeNode的treeify方法：构建红黑树
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        // 若还没有根节点，当前节点即为根节点（黑色）
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        } else {
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            // 从根节点开始插入新节点
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                // 比较哈希值确定插入方向
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                // 哈希值相同，使用键的compareTo方法比较
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);

                TreeNode<K,V> xp = p;
                // 找到插入位置（叶子节点）
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    // 插入后调整红黑树平衡
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    // 确保根节点位于桶的第一个位置
    moveRootToFront(tab, root);
}

六、红黑树转回链表的条件 当树节点数量减少到 6 时（UNTREEIFY_THRESHOLD = 6），红黑树会转换回链表，避免频繁在树和链表之间切换。这一阈值比树化阈值小，形成一个差值缓冲区（8→6），防止临界值附近的频繁转换。

// 红黑树节点数量≤6时，调用untreeify转回链表
final Node<K,V> untreeify(HashMap<K,V> map) {
    Node<K,V> hd = null, tl = null;
    for (Node<K,V> q = this; q != null; q = q.next) {
        Node<K,V> p = map.replacementNode(q, null);
        if (tl == null)
            hd = p;
        else
            tl.next = p;
        tl = p;
    }
    return hd;
}