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

缺乏、安全感 2023-10-02 16:55 75阅读 0赞

## 一、前言 ##

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

> 1、在putVal()方法中如果链表长度`大于阈值8`；会进入到`treeifyBin()`方法中执行链表转红黑树操作；  
> ![在这里插入图片描述][39431fd4af794b2ebc7270aba1836efa.png]  
> 2、HashMap中有个`MIN_TREEIFY_CAPACITY`变量 等于64，表示允许执行`treeifyBin()`链表转红黑树操作时HashMap数组的最小容量；如果数组容量容量小于64，则先执行扩容操作；  
> ![在这里插入图片描述][286326ac79254cada1f777747fbbcd1f.png]

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

上面我们提到了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()，接着手撕红黑树添加节点][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节点为轴右旋`。
> 
> 1.  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并在并且是红色，直接交换祖父节点和其子节点的颜色；  
![在这里插入图片描述][43b33a9d95764765be52c658c60bd159.png]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qWg546W5p-S_size_20_color_FFFFFF_t_70_g_se_x_16]

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

（1）步骤一：将树节点左旋到同一侧；  
![在这里插入图片描述][f76c4d1b9dec4c5abd6903efe7fe0f45.png]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qWg546W5p-S_size_20_color_FFFFFF_t_70_g_se_x_16 1]

（2）步骤二：父节点和祖父节点变色，以祖父节点xpp为轴右旋；  
![在这里插入图片描述][cd29bb6f45cc489c945f84f81f62065e.png]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qWg546W5p-S_size_20_color_FFFFFF_t_70_g_se_x_16 2]

#### 上面第二部分的场景二： ####

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

##### 0）变色操作 #####

若x的祖父节点xpp的左子节点xppl并在并且是红色，直接交换祖父节点和其子节点的颜色；  
![在这里插入图片描述][a37562bb27e24b259a4e0deac94847fd.png]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qWg546W5p-S_size_20_color_FFFFFF_t_70_g_se_x_16 3]

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

（1）步骤一：将树节点右旋到同一侧；  
![在这里插入图片描述][dd8877b4d80048c3b9d7a223c269410b.png]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qWg546W5p-S_size_20_color_FFFFFF_t_70_g_se_x_16 4]

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

![在这里插入图片描述][daf2381d7aef4700965498f58b553914.png]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qWg546W5p-S_size_20_color_FFFFFF_t_70_g_se_x_16 5]

### 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）左旋操作的最终态： #####

![在这里插入图片描述][e2cf21891ee241fab0f0946fe07f79b1.png]

##### 2）细化每种情况 #####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qWg546W5p-S_size_20_color_FFFFFF_t_70_g_se_x_16 6]

### 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。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qWg546W5p-S_size_20_color_FFFFFF_t_70_g_se_x_16 7]

[39431fd4af794b2ebc7270aba1836efa.png]: https://img-blog.csdnimg.cn/39431fd4af794b2ebc7270aba1836efa.png
[286326ac79254cada1f777747fbbcd1f.png]: https://img-blog.csdnimg.cn/286326ac79254cada1f777747fbbcd1f.png
[TreeMap_fixAfterInsertion]: https://blog.csdn.net/Saintmm/article/details/121461176
[43b33a9d95764765be52c658c60bd159.png]: https://img-blog.csdnimg.cn/43b33a9d95764765be52c658c60bd159.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qWg546W5p-S_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/0b6399e11b894a529f73e5b640fb28fd.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5qWg546W5p-S,size_20,color_FFFFFF,t_70,g_se,x_16
[f76c4d1b9dec4c5abd6903efe7fe0f45.png]: https://img-blog.csdnimg.cn/f76c4d1b9dec4c5abd6903efe7fe0f45.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qWg546W5p-S_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/ce2da8f122e14e6fbd7b8de9d7eab5a1.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5qWg546W5p-S,size_20,color_FFFFFF,t_70,g_se,x_16
[cd29bb6f45cc489c945f84f81f62065e.png]: https://img-blog.csdnimg.cn/cd29bb6f45cc489c945f84f81f62065e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qWg546W5p-S_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/028ab093fe214d0dab743f412e7f9c00.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5qWg546W5p-S,size_20,color_FFFFFF,t_70,g_se,x_16
[a37562bb27e24b259a4e0deac94847fd.png]: https://img-blog.csdnimg.cn/a37562bb27e24b259a4e0deac94847fd.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qWg546W5p-S_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/3a512d2329bd43f692397426030477fd.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5qWg546W5p-S,size_20,color_FFFFFF,t_70,g_se,x_16
[dd8877b4d80048c3b9d7a223c269410b.png]: https://img-blog.csdnimg.cn/dd8877b4d80048c3b9d7a223c269410b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qWg546W5p-S_size_20_color_FFFFFF_t_70_g_se_x_16 4]: https://img-blog.csdnimg.cn/bce00e364ba64166881c66ba4b1579e3.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5qWg546W5p-S,size_20,color_FFFFFF,t_70,g_se,x_16
[daf2381d7aef4700965498f58b553914.png]: https://img-blog.csdnimg.cn/daf2381d7aef4700965498f58b553914.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qWg546W5p-S_size_20_color_FFFFFF_t_70_g_se_x_16 5]: https://img-blog.csdnimg.cn/716cfb36890f4f2b826da937b4f1fa6c.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5qWg546W5p-S,size_20,color_FFFFFF,t_70,g_se,x_16
[e2cf21891ee241fab0f0946fe07f79b1.png]: https://img-blog.csdnimg.cn/e2cf21891ee241fab0f0946fe07f79b1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qWg546W5p-S_size_20_color_FFFFFF_t_70_g_se_x_16 6]: https://img-blog.csdnimg.cn/fbc97e3b52a54f4f861426722cad01e7.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5qWg546W5p-S,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qWg546W5p-S_size_20_color_FFFFFF_t_70_g_se_x_16 7]: https://img-blog.csdnimg.cn/15f61a181d584fe6bfcf781300f25ea2.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5qWg546W5p-S,size_20,color_FFFFFF,t_70,g_se,x_16