《Java8源码》图解HashMap链表转红黑树含红黑树插入节点、平衡、变色、左/右旋

一、前言

1、链表是什么时候转红黑树的？

1、在putVal()方法中如果链表长度大于阈值8；会进入到treeifyBin()方法中执行链表转红黑树操作；

2、HashMap中有个MIN_TREEIFY_CAPACITY变量 等于64，表示允许执行treeifyBin()链表转红黑树操作时HashMap数组的最小容量；如果数组容量容量小于64，则先执行扩容操作；

聊完了链表什么时候转红黑树，下面我们来看一下链表是怎么转红黑树的？

上面我们提到了treeifyBin()这个方法，链表转红黑树的逻辑也就在这个方法中。

二、源码分析

1、treeifyBin()

HashMap的putval()方法中调用treeifyBin()方法执行链表转红黑树操作；而treeifyBin()主要做两件事：

1、先根据hash计算出当前链表所在table数组中的位置，然后将其数据结构从单向链表Node转为双向链表TreeNode；
2、如果双向链表TreeNode的头节点hd不为null，则调用treeify()方法对TreeNode双向链表进行树型化操作；

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();
    // 如果新增的node 要插入的数组位置已经有node存在了，取消插入操作
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 步骤一：遍历链表中每个节点，将Node转化为TreeNode
        // hd指向头节点，tl指向尾节点
        TreeNode<K,V> hd = null, tl = null;
        do {
            // 将链表Node转换为红黑树TreeNode结构
            TreeNode<K,V> p = replacementTreeNode(e, null);
            // 以hd为头结点，将每个TreeNode用prev和next连接成新的TreeNode链表
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        // 步骤二：如果头结点hd不为null，则对TreeNode双向链表进行树型化操作
        if ((tab[index] = hd) != null)
            // 执行链表转红黑树的操作
            hd.treeify(tab);
    }
}

接着我们看一下真正将链表转成红黑树的地方：treeify()方法；

2、treeify()

treeify()方法中大体上分为三步：

1、遍历TreeNode双向链表，确定待插入节点x在其父节点的左边还是右边，然后将其插入节点到红黑树中；
2、插入节点之后树结构发生变化，需要通过变色和旋转操作维护红黑树的平衡；
3、因为调整了红黑树，root节点可能发生了变化，所以需要把最新的root节点放到双向链表的头部，并插⼊到table数组中。

final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    // 最开始的x表示TreeNode双向链表的头结点
    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;
            // p 表示parent节点
            for (TreeNode<K,V> p = root;;) {
                // dir表示x节点在parent节点的左侧还是右侧
                int dir, ph; // ph表示parent节点的hash值
                K pk = p.key; // pk表示parent节点的key值
                // x节点在parent节点的左侧
                if ((ph = p.hash) > h)
                    dir = -1;
                // x节点在parent节点的右侧
                else if (ph < h)
                    dir = 1;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);

                // 第二部分
                TreeNode<K,V> xp = p; // xp表示x的父节点
                // 如果p节点的左节点/右节点不为空，则令p = p.left/p.right，继续循环
                // 直到p.left/p.right为空
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    // 令待插入节点x的父节点为xp, 即p
                    x.parent = xp;
                    // 根据dir判断插入到xp的左子树(<0)还是右子树(>0)
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    // 往红黑树中插入节点后，进行树的平衡操作
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    // 将root节点插入到table数组中
    moveRootToFront(tab, root);
}

在往红黑树中插入一个节点之后，会调用balanceInsertion()方法进行树的平衡操作，我们来看一下红黑树是怎么进行平衡的？

3、balanceInsertion()

这里和TreeMap中插入节点之后进行的红黑树平衡操作fixAfterInsertion()类似。在文章：图解TreeMap的红黑树平衡操作fixAfterInsertion()，接着手撕红黑树添加节点中我们详细介绍；

对红黑树进行平衡操作时，主要分两部分：直接返回、变色旋转后返回；

第一部分：直接返回根节点：

1、如果待插入节点x没有parent节点，直接把x的节点变为黑色，并作为根节点返回；

2、如果x的父节点为黑色、或者没有祖父节点，则直接返回根节点root；

第二部分：根据x节点在父节点xp的左侧还是右侧、xp节点再其父节点xpp的左侧还是右侧进行旋转、变色；

1. 如果x的父节点xp是祖父节点xpp的左子节点：

0）若x的祖父节点xpp的右子节点xppr存在并且是红色，直接交换祖父节点和其子节点的颜色、并返回。
1）若x是其父节点xp的右子节点，交换x和xp的位置，然后对x进行左旋；

2）接着设置父节点xp为黑色、祖父节点xpp为红色，以xpp节点为轴右旋。

2. x的父节点xp是祖父节点的右子节点：

   这里和上面的类似，只是左旋变右旋、右旋变左旋；

0）若x的祖父节点xpp的左子节点xppl并在并且是红色，直接交换祖父节点和其子节点的颜色、并返回。
1）若x是其父节点xp的左子节点，交换x和xp的位置，然后对x进行右旋；

2）接着设置父节点xp为黑色、祖父节点xpp为红色，以xpp节点为轴左旋。

代码如下：

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                            TreeNode<K,V> x) {
    // 将待插入节点x的节点颜色置为红色
    x.red = true;
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
        // 1、如果x没有父节点，自己变为黑色节点、作为根节点返回
        if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
        // 2、如果x的父节点为黑色或者没有祖父节点，则直接返回root
        else if (!xp.red || (xpp = xp.parent) == null)
            return root;
        // 3、如果x的父节点xp是祖父节点的左子节点
        if (xp == (xppl = xpp.left)) {
            // 1）仅变色：
            //    如果xp和xppr都是红色节点，则把xppr、xp置为黑色、zpp置为红色。
            if ((xppr = xpp.right) != null && xppr.red) {
                xppr.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            // 2）旋转   变色：
            else {
                // （1）如果x 是其父节点xp的右子节点。令当前节点为其父节点，然后对当前节点x进行左旋
                if (x == xp.right) {
                    root = rotateLeft(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                // （2）如果x的父节点xp不为空
                if (xp != null) {
                    // 令xp的颜色为黑色
                    xp.red = false;
                    // 如果x的祖父节点xpp不为空
                    if (xpp != null) {
                        // 令xpp的颜色为红色
                        xpp.red = true;
                        // 对祖父节点xpp进行右旋
                        root = rotateRight(root, xpp);
                    }
                }
            }
        }
        // 4、x的父节点xp是祖父节点的右子节点
        else {
            // 逻辑和3、类似，只是单纯的左变右、右变左
            if (xppl != null && xppl.red) {
                xppl.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            else {
                if (x == xp.left) {
                    root = rotateRight(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                if (xp != null) {
                    xp.red = false;
                    if (xpp != null) {
                        xpp.red = true;
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}

可能上面一顿文字描述，不够直观，下面我们结合源代码图解分析；

上面第二部分的场景一：

x的父节点xp是祖父节点xpp的左子节点；

0）变色操作

若x的祖父节点xpp的左子节点xppl并在并且是红色，直接交换祖父节点和其子节点的颜色；

1、2）左旋 变色 右旋操作

（1）步骤一：将树节点左旋到同一侧；

（2）步骤二：父节点和祖父节点变色，以祖父节点xpp为轴右旋；

上面第二部分的场景二：

x的父节点xp是祖父节点xpp的右子节点；

0）变色操作

若x的祖父节点xpp的左子节点xppl并在并且是红色，直接交换祖父节点和其子节点的颜色；

1、2）右旋 变色 左旋操作

（1）步骤一：将树节点右旋到同一侧；

（2）步骤二：父节点和祖父节点变色，以祖父节点xpp为轴左旋；

4、rotateLeft()

左旋操作是将待旋转节点p的和其右子节点r交换位置和所有的节点关联关系，具体如下：

1、令当前旋转节点p的右子节点为其原右子节点r的左子节点rl（右儿子节点中的 左孙子节点）；rl节点的parent节点为p；

2、先令r的parent指向p的parent，然后再判断p节点的父节点pp的情况：

1）pp为空时，设置r为root节点，并将r的parent节点置为空；

2）p节点是父节点pp的左子节点时，pp的的左子节点变更为r；

3）p节点是父节点pp的右子节点时，pp的的右子节点变更为r；

3、最后将r的left指向p，p的parent指向r；

static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                      TreeNode<K,V> p) {
    TreeNode<K,V> r, pp, rl; // r为p的右子节点，pp为p的父节点，rl为r的左子节点
    // 如果p的右节点不为空
    if (p != null && (r = p.right) != null) {
        // rl赋值，并将p.right指向r.left
        if ((rl = p.right = r.left) != null)
            // rl的父节点为p
            rl.parent = p;
        // 1）当p节点没有父节点时，先令r的父节点为p的父节点
        if ((pp = r.parent = p.parent) == null)
            // 把p节点的右子节点r变为黑色，并作为root节点
            (root = r).red = false;
        // 2）p节点在其父节点pp的左子节点
        else if (pp.left == p)
            // 令pp节点的左子节点为r
            pp.left = r;
        // 3）p节点在其父节点的右子节点
        else
            // 令pp节点的右子节点为r
            pp.right = r;
        // 令r的左子节点为p
        r.left = p;
        // p的父节点为r
        p.parent = r;
    }
    return root;
}

结合源代码图解分析：

1）左旋操作的最终态：

2）细化每种情况

5、rotateRight()

右旋操作和左旋类似，只是左变右、右变左；本质上逻辑都是一样的；

static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                       TreeNode<K,V> p) {
    TreeNode<K,V> l, pp, lr; // l为p的左子节点，pp为p的父节点，lr为l的右子节点
    // 如果p的左节点不为空
    if (p != null && (l = p.left) != null) {
        // rl赋值，并将p.left指向r.right
        if ((lr = p.left = l.right) != null)
            // 设置lr的父节点为p
            lr.parent = p;
        // 1）将l的parent指向p的parent，如果p的父节点pp为空
        if ((pp = l.parent = p.parent) == null)
            // 将的l的颜色设置为黑色，并作为根节点root
            (root = l).red = false;
        // 2）p节点在其父节点pp的右子节点
        else if (pp.right == p)
            // 令pp节点的右子节点为l
            pp.right = l;
        // 3）p节点在其父节点pp的左子节点
        else
            // pp节点的左子节点为l
            pp.left = l;
        // 令l的右子节点为p
        l.right = p;
        // p的父节点为l
        p.parent = l;
    }
    return root;
}

结合源代码图解分析：

既然左旋的大家已经看懂了，右旋大家可以尝试一下自己画个图呀；锻炼一下自己的动手能力；

6、moveRootToFront()

在treeify()方法中调用balanceInsertion()对红黑树平衡完之后，最后会进入moveRootToFront()方法，将root节点放到整条双向链表的头部，并插⼊到table数组中。

注意这里说的双向链表是红黑树中的TreeNode。

static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
    int n;
    if (root != null && tab != null && (n = tab.length) > 0) {
        // 判断table数组中存储的元素是不是最新的root节点
        int index = (n - 1) & root.hash;
        TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
        // 如果不是
        if (root != first) {
            // 重塑双向链表的连接，把root放到整个链表的头位置，并将root插入到table数组中
            // A <--> root <--> C   变为   root <--> A <--> C
            Node<K,V> rn; // rn表示root的下一个节点
            tab[index] = root;
            TreeNode<K,V> rp = root.prev; // rp表示root的前一个节点
            if ((rn = root.next) != null)
                // rn的prev节点修改为rp
                ((TreeNode<K,V>)rn).prev = rp;
            if (rp != null)
                // rp的next节点修改为rn
                rp.next = rn;
            if (first != null)
                // 把root节点移动到first节点之前
                first.prev = root;
            root.next = first;
            // root的前一个节点置为空
            root.prev = null;
        }
        // 对整个红黑树结构执行check校验
        assert checkInvariants(root);
    }
}

重塑双向链表的连接，把root放到整个链表的头位置，并将root插入到table数组中；
将A <–> root(B) <–> C 变为 root(B) <–> A <–> C。

这篇好文章是转载于：学新通技术网