Java源码阅读之红黑树在HashMap中的应用 - JDK1.8

阅读优秀的源码是提升编程技巧的重要手段之一。
如有不对的地方，欢迎指正~
转载请注明出处https://blog.lzoro.com。

前言

基于JDK1.8。

JDK1.8之前，HashMap并没有采用红黑树，所以哈希桶上的链表过长时，就会有效率问题。

JDK1.8，则在HashMap引入了红黑树，当链表长度超过指定阈值(默认为8)，则进行树化并提供相关操作(增删查等)，提高了操作效率。

之前阅读了HashMap的源码，但是由于篇幅关系，略过了链表树化后红黑树的相关操作，本着打破砂锅问到底的精神，来看下红黑树在HashMap中的应用。

打破沙锅问到底，是一个成语，拼音为：dǎ pò shā guō wèn dào dǐ，其 比喻追究事情的根底，其出处自 宋·黄庭坚《拙轩颂》。

红黑树

什么是红黑树？

是这样的吗（开个玩笑，不存在的）。

是这样的，这才对吧，有红有黑。

科普时间，it KePu's tims.

红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。
红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。

以上科普信息由度娘提供。

性质

红黑树不仅是二叉查找树，它还必须满足5个性质

• 1.节点非黑即红
• 2.根节点是黑色
• 3.每个叶节点（NIL节点，空节点）是黑色的
• 4.每个红色节点的两个子节点都是黑色(从每个叶子到根的所有路径上不能有两个连续的红色节点)
• 5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

满足了以上性质的二叉查找树的就是红黑树，如果是初次接触的话，是不是看完有点懵，不要慌，接着往下看。

红黑树的效率相对较高，所以它被用来存储相关数据，基本的操作有增加/删除/查找，在这些操作之后可能会破坏红黑树的性质，所以需要相关操作来维护以让红黑树符合上面的性质要求。

而这里提到的相关操作有

• 变色
• 左旋
• 右旋

左旋右旋

是不是对红黑树的任意操作之后，它都还能满足上面的提交的条件呢。

答案是No。

所以也就有了旋转的存在。

旋转跳跃，我闭着眼，尘嚣看不见 你沉醉了没。（请不要唱，快拉回你的心思）

嗯，旋转分为左旋和右旋。

左旋

将x的右子树绕x逆时针旋转，使得x的右子树成为x的父亲，并修改相关引用。

右旋

是将x的左子树绕x顺时针旋转，使得x的左子树成为x的父亲，并修改相关的引用。

是不是还是有点迷糊，那么再来两张动图帮助下理解~

懒人自有妙计，不过要有版权意识。
动图来源：https://blog.csdn.net/sun_tttt/article/details/65445754

是不是明白一些了~~

基本的关于红黑树概念介绍完毕，需要深入了解的小伙伴请移步搜索引擎。

接下来，坐好了，将车门焊死，准备发车了。

HashMap中的红黑树

先看下HashMap内部类TreeNode<K,V>的定义，它继承了LinkedHashMap.Entry<K,V>

类java.util.HashMap
第1791行起

/**
 * 二叉树实体. 继承 LinkedHashMap.Entry (顺序扩展节点)
 * 
 * linked node.
 */
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    //红黑树父节点(链)
    TreeNode<K,V> parent;  // red-black tree links
    //左节点
    TreeNode<K,V> left;
    //右节点
    TreeNode<K,V> right;
    //前置节点
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    //红黑标志
    boolean red;
    
    /**
     * 构造函数
     */
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }

    /**
     * 返回根节点
     */
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }
    
    //先略去部分功能代码
    ...    
}

在看相关的功能代码之前，先来看下HahsMap中红黑树左旋和右旋的实现

HashMap中的红黑树 - 左旋

/**
 * 红黑树左旋操作
 */
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                      TreeNode<K,V> p) {
    TreeNode<K,V> r, pp, rl;
    //p不为null且p的右子树不为null
    if (p != null && (r = p.right) != null) {
        //将r(p的右子树)的左子树变成p的右子树
        //有点拗口 o(╥﹏╥)o
        //下面会用一个图示来说明
        if ((rl = p.right = r.left) != null)
            //修改父节点引用，rl是r(p的右子树)的左子树
            rl.parent = p;
        //将r(p的右子树)的父节点变成p的父节点（左旋过程，将右子树变成自己的父节点）
        if ((pp = r.parent = p.parent) == null)
            //如果p节点的父节点为null，证明p是根节点（子树的根节点）
            //将r变成根节点（子树的根节点），并变成黑色（符合性质）
            (root = r).red = false;
        //如果存在父节点且p是该节点的左子树
        else if (pp.left == p)
            //将r(p的右子树)变成该节点的左子树
            pp.left = r;
        //如果存在父节点且p节点是该节点的右子树
        else
            //将r(p的右子树)变成该节点的右子树
            pp.right = r;
        //将r(p的左子树)变成p（左旋中，将左子树变成自己的父节点）
        r.left = p;
        //r变成p的父节点
        p.parent = r;
    }
    return root;
}

下面用图示来说明上面的步骤，会比较简单明了不拗口

一、p没有父节点（可以理解为p是根节点）

一、p有父节点

HashMap中的红黑树 - 右旋

/**
 * 红黑树右旋操作
 */
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                       TreeNode<K,V> p) {
    TreeNode<K,V> l, pp, lr;
    //p不为null且p的左子树不为null
    if (p != null && (l = p.left) != null) {
        //将l(p的左子树)的右子树变成p的左子树
        if ((lr = p.left = l.right) != null)
            //修改父节点引用，lr是l(p的左子树)的右子树
            lr.parent = p;
        //将l(p的右子树)的父节点变成p的父节点（右旋过程，将左子树变成自己的父节点）
        if ((pp = l.parent = p.parent) == null)
            //将l变成根节点（子树的根节点），并变成黑色（符合性质）
            (root = l).red = false;
        //如果存在父节点且p是该节点的右子树
        else if (pp.right == p)
            pp.right = l;
        //如果存在父节点且p是该节点的左子树
        else
            pp.left = l;
        //将l(p的右子树)变成p（右旋中，将右子树变成自己的父节点）
        l.right = p;
        p.parent = l;
    }
    return root;
}

类似的下面用图演示过程

一、p没有父节点（可以理解为p是根节点）

一、p有父节点

右旋

理解了HashMap中红黑树的左旋和右旋，下面看一下几个比较重要的方法

treeify

顾名思义：树化。当哈希桶中的链表长度超过阈值(默认8)的话，就会对链表进行树化，具体来看一下实现。

调用链如下

1、HashMap第643行treeifyBin(tab, hash);，判断阈值，超过则进行树化

2、HashMap第754行，treeifyBin实现，第771行调用TreeNode的树化实现

/**
 * 替换哈希桶中给定哈希索引的元素
 * 如果哈希桶太小，则resize
 */
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 {
            //这里的replacementTreeNode调用了TreeNode的构造函数进行构造
            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);
    }
}

3、HashMap第1897行，treeify实现

/**
 * 红黑树化
 * @return 树的根节点
 */
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节点的左右节点设置为null
        x.left = x.right = null;
        //判断当前红黑树是否有根节点
        if (root == null) {
            //如果没有根节点
            //当前节点的父节点设置为null
            x.parent = null;
            //设置颜色为黑色（根节点为黑色）
            x.red = false;
            //将x节点设置为根节点
            root = x;
        }
        //当前红黑树存在根节点
        else {
            //获取x节点的key
            K k = x.key;
            //获取x节点的hash
            int h = x.hash;
            //key的class
            Class<?> kc = null;
            //从根节点遍历，将x节点插入到红黑树中
            for (TreeNode<K,V> p = root;;) {
                //定义dir(方向),ph(节点hash)
                int dir, ph;
                //取出p节点的key
                K pk = p.key;
                //当p节点的hash大于x节点的hash时
                if ((ph = p.hash) > h)
                    //左侧
                    dir = -1;
                else if (ph < h)
                    //右侧
                    dir = 1;
                 
                //如果上面的if分支没走，则证明两个节点key的hash值相等，需要通过其他方式进行比较
                //如果当前节点(x)的key的类实现了comparable接口，且当前循环节点(p)是相同Class的实例
                //那么就通过comparable进行比较
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    //若还是相等，就通过tieBreakOrder比较     
                    dir = tieBreakOrder(k, pk);

                //先缓存p节点
                TreeNode<K,V> xp = p;
                //根据dir方向，来选择在左侧还是右侧插入
                //并判断是否为null
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    //选择的左/右子树为null
                    
                    //将原来的p节点(现xp)设置为x的父节点
                    x.parent = xp;
                    //如果dir 小于等于0
                    //将x节点放置在原p(现xp)节点的左侧
                    if (dir <= 0)
                        xp.left = x;
                    //如果dir 大于0
                    //将x节点放置在原p(现xp)节点的右侧
                        xp.right = x;
                    //调用balanceInsertion进行插入平衡
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    //确保哈希桶指定位置存储的节点是红黑树的根节点
    moveRootToFront(tab, root);
}

/**
 * 确保哈希桶指定位置存储的节点是红黑树的根节点
 */
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
    int n;
    if (root != null && tab != null && (n = tab.length) > 0) {
        //索引位置
        int index = (n - 1) & root.hash;
        TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
        //如果不是红黑树的根节点
        if (root != first) {
            Node<K,V> rn;
            //指向红黑树的根节点
            tab[index] = root;
            TreeNode<K,V> rp = root.prev;
            //整理节点顺序
            if ((rn = root.next) != null)
                ((TreeNode<K,V>)rn).prev = rp;
            if (rp != null)
                rp.next = rn;
            if (first != null)
                first.prev = root;
            root.next = first;
            root.prev = null;
        }
        //递归做一个恒定校验
        assert checkInvariants(root);
    }
}

4、HashMap第2206行，balanceInsertion实现

这个方法实现了红黑树插入节点后的平衡(为了满足平衡性)，方法的分支较多，如果没有很透彻理解红黑树的相关概念和操作，一时间会容易迷惑，下面代码对整体流程进行了注释，但是仍然比较晦涩，后面会带上图示，加深理解。

/**
 * 插入平衡
 */
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;;) {
        //取出x的父节点并判断是否为null
        if ((xp = x.parent) == null) {
            //x没有父节点
            x.red = false;//变色(黑色)
            return x;//x为根节点发那会
        }
        //如果x存在父节点且x的父节点为黑色或x的父父节点不存在
        else if (!xp.red || (xpp = xp.parent) == null)
            //返回root
            return root;
        //如果x的父节点是父父节点的左孩子
        if (xp == (xppl = xpp.left)) {
            //父父节点的右孩子不为null且为红色
            if ((xppr = xpp.right) != null && xppr.red) {
                xppr.red = false;//变色(黑)
                xp.red = false;//变色(黑)
                xpp.red = true;//变色(红)
                x = xpp;
            }
            else {
                //x是父节点的右孩子
                if (x == xp.right) {
                    //左旋
                    root = rotateLeft(root, x = xp);
                    //处理x的父父节点
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                //x的父节点存在
                if (xp != null) {
                    xp.red = false;//变色
                    //x的父父节点存在
                    if (xpp != null) {
                        xpp.red = true;//变色
                        //右旋
                        root = rotateRight(root, xpp);
                    }
                }
            }
        }
        //如果x的父节点是父父节点的右孩子
        else {
            //x的父父节点的左孩子存在且为红色
            if (xppl != null && xppl.red) {
                xppl.red = false;//变色(黑)
                xp.red = false;//变色(黑)
                xpp.red = true;//变色(红)
                x = xpp;
            }
            else {
                //如果x是父节点的左孩子
                if (x == xp.left) {
                    //右旋
                    root = rotateRight(root, x = xp);
                    //处理x的父父节点
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                //如果x的父节点存在
                if (xp != null) {
                    xp.red = false;//变色(黑)
                    //如果x的父父节点存在
                    if (xpp != null) {
                        xpp.red = true;//变色(红)
                        //左旋
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}

下面用图示，举个栗子~

栗子在这里

假如有如下一个链表，里面的数字代表hash值（先不考虑hash分布）

然后按照链表顺序取出节点进行红黑树插入，以及插入后平衡操作（左旋右旋/变色），来看一下整个过程

综合上面的描述和图示，大概可以把链表转红黑树的操作总结如下

1、将链表的首节点当做临时的红黑树根节点，左右孩子置为null
2、循环按顺序取出链表的节点，进行红黑树插入，和插入后平衡
    2.1、取出链表节点，经过hash比较，插入到红黑树合适的位置(保证平衡性)
    2.2、由于插入的节点会破坏红黑树的性质，所以需要进行插入后平衡
       2.2.1、新插入的节点置为红色
       2.2.2、父节点和父父节点的null判断和颜色判断
           2.2.2.1、判断新插入节点的父节点是否存在，不存在则返回
           2.2.2.1、如果父节点是黑色的，或者父父节点不存在着，则返回
       
       2.2.3、父节点是父父节点的左孩子还是右孩子判断
           2.2.3.1、是左孩子且兄弟节点存在并且是红色，则执行相应的变色，然后进行下一轮判断。
           2.2.3.2、是左孩子当兄弟节点不存在（或者是黑色），则执行相应的左旋/右旋。
           
           2.2.3.3、是右孩子且兄弟节点存在并且是红色，则执行相应的变色，然后进行下一轮判断。
           2.2.3.4、是右孩子当兄弟节点不存在（或者是黑色），则执行相应的左旋/右旋。
3、链表循环完毕后，确保哈希桶指定位置存储的是红黑树的根节点


嗯，没了。细节请看源码和图示，如果觉得迷糊，可以自己动手画画图，或者Debug。

untreeify

有了树化，肯定也有非树化。

有起有落，月缺月圆，凡事要有平衡。一本正经地胡说八道。

突然就斗起了表情。

没错，这个方法就是将红黑树退化成链表，俗称链表化。

入口有几个地方

• 节点删除时，红黑树的大小低于阈值，退化成链表。2035行tab[index] = first.untreeify(map); // too small
• 扩容/调整容量时，调用split方法

/**
 * 红黑树链表化
 */
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;
}

putTreeVal

嗯，没什么好说的，红黑树的节点插入。

对应上篇博客的链表节点插入，但相比链表来说会比较复杂。不过流程与之前提到过的树化当中的单一节点插入没有太大区别，也是从红黑树的根节点进行遍历，寻找合适的位置插入，并进行插入后的平衡(变色/左旋/右旋)，待插入平衡后，确保存储在哈希桶指定位置的节点是红黑树的根节点。

/**
 * 红黑树版本的节点插入
 */
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                               int h, K k, V v) {
    Class<?> kc = null;
    boolean searched = false;
    //取出根节点
    TreeNode<K,V> root = (parent != null) ? root() : this;
    //从根节点进行遍历，选择合适的位置插入节点(无边界遍历，需要内部跳出)
    for (TreeNode<K,V> p = root;;) {
        int dir, ph; K pk;
        //判断方向
        if ((ph = p.hash) > h)
            dir = -1;
        else if (ph < h)
            dir = 1;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            if (!searched) {
                TreeNode<K,V> q, ch;
                searched = true;
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                    return q;
            }
            dir = tieBreakOrder(k, pk);
        }
        //先缓存当前遍历的树节点
        TreeNode<K,V> xp = p;
        //判断该树节点下是否有子节点
        //如果没有，则根据之前判断的方向（左侧/右侧）进行插入
        //如果已有，则向下遍历继续上面的步骤，直到插入合适的位置
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            Node<K,V> xpn = xp.next;
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            xp.next = x;
            x.parent = x.prev = xp;
            if (xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            //插入到合适的位置和，可能破坏红黑树的性质，所以需要进行插入平衡
            //插入平衡后，需要确保哈希桶下标位置上存储的节点是红黑树的节点
            //这些在上面的树化过程都有提到，此处不再赘述
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

getTreeNode

红黑树中的节点查找。

对应链表的节点查找，在链表树化后，节点的查找就是红黑树实现的。查找的逻辑还是比较清晰的，因为红黑树是自平衡二叉查找树，节点左子树都比自己小，右子树都比自己大，所以根据给定的hash，可以确定从左子树还是右子树查找，然后循环进行定位，知道最终找到节点或者不存在该节点时，结束查找。

/**
 * 红黑树节点查找的入口方法
 */
final TreeNode<K,V> getTreeNode(int h, Object k) {
    return ((parent != null) ? root() : this).find(h, k, null);
}

/**
 * 根据给定的hash和key，从红黑树的根节点开始进行查找
 */
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this;
    do {
        int ph, dir; K pk;
        //取出左子树和右子树，根据hash和key进行查找
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        //根据hash大小决定取左子树还是右子树
        if ((ph = p.hash) > h)
            p = pl;
        else if (ph < h)
            p = pr;
        //如果在节点相等，就返回
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if (pl == null)
            p = pr;
        else if (pr == null)
            p = pl;
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&
                 (dir = compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr;
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        else
            p = pl;
    } while (p != null);
    return null;
}

removeTreeNode

移除红黑树节点。

对应链表节点的移除，红黑树版本的节点移除相比链表会复杂一些，因为涉及到维护红黑树的平衡性和相关性质。

/**
 * 移除给定节点, 调用该方法时要确保节点存在.
 * 因为无法交换存在叶子节点的内部节点内容，所以这会比典型的红黑树节点删除来得复杂
 * 遍历过程中"next"指针指向的继任节点是可访问的，所以我们交换了树的连接.
 * 如果当前树节点太少，则将二叉树替换成简单形式
 * (2-6节点测试触发，取决于树的结构)
 */
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                          boolean movable) {
    int n;
    //判断哈希桶
    if (tab == null || (n = tab.length) == 0)
        return;
    //下标
    int index = (n - 1) & hash;
    //取出指定下标的根节点
    TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
    //继任节点和前置节点
    TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
    //前置节点不存在，则证明要移除的节点是根节点
    if (pred == null)
        //将继任节点往前移
        tab[index] = first = succ;
    else
        //前置节点存在，则将继任节点连接到前置节点（移除本节点）
        pred.next = succ;
    //判断继任节点是否存在
    if (succ != null)
        //存在的话，修改前置引用
        succ.prev = pred;
    //这个时候first为null，则表示哈希桶指定位置可能只有一个节点
    if (first == null)
        //返回
        return;
    //获取根节点
    if (root.parent != null)
        root = root.root();
    //根节点不存在或者根节点的左子树/右子树不存在或者左左子树不存在
    //该判断是作为链表化的阈值
    if (root == null || root.right == null ||
        (rl = root.left) == null || rl.left == null) {
        //红黑树太小，进行链表化
        tab[index] = first.untreeify(map);  // too small
        return;
    }
    //取得要移除的节点，左子树，右子树
    TreeNode<K,V> p = this, pl = left, pr = right, replacement;
    //左右子树同时存在
    if (pl != null && pr != null) {
        TreeNode<K,V> s = pr, sl;
        //循环查找继任节点
        while ((sl = s.left) != null) // find successor
            s = sl;
        //交换p和s的颜色
        boolean c = s.red; s.red = p.red; p.red = c; // swap colors
        TreeNode<K,V> sr = s.right;
        TreeNode<K,V> pp = p.parent;
        //相等则证明p是s的直接父节点（只有一个层级）
        if (s == pr) { // p was s's direct parent
            //交换位置
            p.parent = s;
            s.right = p;
        }
        //如果是多个层级
        else {
            //取出s的父节点
            TreeNode<K,V> sp = s.parent;
            //下面操作仍然是交换p和s的位置
            if ((p.parent = sp) != null) {
                if (s == sp.left)
                    sp.left = p;
                else
                    sp.right = p;
            }
            if ((s.right = pr) != null)
                pr.parent = s;
        }
        //清空p的右子树引用
        p.left = null;
        //调整相关引用
        if ((p.right = sr) != null)
            sr.parent = p;
        if ((s.left = pl) != null)
            pl.parent = s;
        if ((s.parent = pp) == null)
            root = s;
        else if (p == pp.left)
            pp.left = s;
        else
            pp.right = s;
        //确定替换节点
        if (sr != null)
            replacement = sr;
        else
            replacement = p;
    }
    //只有左子树存在
    else if (pl != null)
        replacement = pl;
    //只有右子树存在
    else if (pr != null)
        replacement = pr;
    //左右子树都不存在
    else
        replacement = p;
    //判断替换的节点是不是自身
    if (replacement != p) {
        //不是自身的话，则执行相关替换操作
        TreeNode<K,V> pp = replacement.parent = p.parent;
        if (pp == null)
            root = replacement;
        else if (p == pp.left)
            pp.left = replacement;
        else
            pp.right = replacement;
        p.left = p.right = p.parent = null;
    }
    //判断p的颜色
    //如果p是红色节点，则将根节点赋值给r
    //如果p是黑色节点，则进行删除平衡(类似于插入平衡)
    //这里的r要存储红黑树的根节点
    TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
    //如果替换节点是自身的话
    if (replacement == p) {  // detach
        //进行分离操作
        TreeNode<K,V> pp = p.parent;
        p.parent = null;
        if (pp != null) {
            if (p == pp.left)
                pp.left = null;
            else if (p == pp.right)
                pp.right = null;
        }
    }
    if (movable)
        //确保哈希桶下标指定位置存储的是红黑树根节点
        moveRootToFront(tab, r);
}

split

只有在resize的时候被调用，作用是在哈希桶扩容/调整容量时，将红黑树拆分成两颗树，在红黑树太小时进行链表化等操作。

具体看源码注释。

/**
 * Splits nodes in a tree bin into lower and upper tree bins,
 * or untreeifies if now too small. Called only from resize;
 * see above discussion about split bits and indices.
 *
 * @param map the map
 * @param tab the table for recording bin heads
 * @param index the index of the table being split
 * @param bit the bit of hash to split on
 */
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    //拆分成两棵树
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    //遍历节点
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        //将e的next引用置空，目的是从e断开
        e.next = null;
        //将e的hash和bit(其实就是oldCap)相与（是不是很熟悉，其实跟链表的操作类似）
        //为0的放到lower树
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        //不为0放到upper树
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }
    //判断lower树是否为null
    if (loHead != null) {
        //判断是否需要链表化
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                loHead.treeify(tab);
        }
    }
    //判断upper树是否为null
    if (hiHead != null) {
    //判断是否需要链表化
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

到这里，关于HashMap中的红黑树相关内容基本上都介绍完毕了，篇幅有点长，没法面面俱到，呼~~（放松一下）。

后话

本来想着每个方法和每个操作流程都画图解释比较直观。

但是后面花现，画图，真的是他喵了太耗费精力了。

我花4，除了动图之外，其他的图都是我自己画的。对了，开头的那棵树除外。当然，表情包也不是。

其他图示留待后面时间充裕了补上吧。

溜了溜了，有帮助的话给格子点个赞呗。