【Java集合】HashMap系列（三）——TreeNode内部类源码分析_java hashmap集合split()

目录

一、TreeNode的类定义和数据结构

1.1 类定义

1.2 属性

1.3 TreeNode的方法

二、构造方法

三、HashMap扩容操作

3.1 split()

3.2 untreeify()

3.3 treeify()

3.3.1 comparableClassFor()

3.3.2 compareComparables()

3.4 tieBreakOrder()

3.5 balanceInsertion()

3.5.1 rotateLeft()

3.5.2 rotateRight()

3.6 moveRootToFront()

3.7 checkInvariants()

四、HashMap添加操作

4.1 putTreeVal()

4.2 root()

4.3 find()

4.4 untreeify()、treeify()、treeifyBin()总结

4.4.1 treeifyBin()和treeify()

4.4.2 untreeify()

五、HashMap查找操作

5.1 getTreeNode()

六、HashMap删除操作

6.1 removeTreeNode()

6.1.1 removeTreeNode()方法图解

6.1.2 removeTreeNode()方法源码

6.1.3 为什么 sr 是 replacement 的首选，p 为备选？

6.2 balanceDeletion()

6.2.1 balanceDeletion()方法源码

6.2.2 balanceDeletion()方法流程详解

6.2.2 总结

---

前面的文章已经讲解过HashMap源码分析以及红黑树的基础知识，今天这篇文章就讲解之前HashMap源码中中未讲解的红黑树操作部分。TreeNode是HashMap的内部类，TreeNode类也是HashMap中最核心的类。从链表变成红黑树，从红黑树转成链表，以及旋转等，都是在这个类中实现。接下来，就以HashMap.TreeNode来说明红黑树的源码操作。

一、TreeNode的类定义和数据结构

1.1 类定义

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>

继承LinkedHashMap.Entry，追溯源头可以到HashMap.Node，下面图展示了对应的结构关系：

1.2 属性

/**
* 父节点
*/
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可以使用的属性并不只有这么多，因为它还继承了别的类，比如LinkedHashMap.Entry<K,V>。这个类包括了before属性和after属性，分别代表节点的上一个节点和下一个节点，也就组成了一个双向链表结构。因为TreeNode继承了LinkedHashMap.Entry<K,V>这个类，所以它也是可以使用这两个属性的。

LinkedHashMap.Entry<K,V>又继承了HashMap.Node<K,V>，TreeNode也就可以使用HashMap.Node<K,V>中的成员属性。

TreeNode类其实就通过这些继承关系既实现了红黑树结构，也维持了一个双向链表结构结构。通过TreeNode自身属性left、right、parent、red四个属性实现了红黑树结构，通过自身属性prev和继承HashMap.Node<K,V>的next属性来实现了双向链表的结构。

treeifyBin()方法只是把Node链表转成了TreeNode双向链表（prev、next是双向链表的指针）。 treeify()方法才会把TreeNode链表转成TreeNode树，用left、right连接。

现在我们对其成员变量进行汇总：

由此可见，HashMap中的TreeNode的大小大约是Node节点的二倍，TreeNode中增加了很多属性，这会造成TreeNode的空间开销要比Node大很多。因此不是一上来就转换为红黑树。而是需要链表的长度大于8而且size大于64时才会将Node链表转换为TreeNode红黑树。

1.3 TreeNode的方法

// 返回根节点TreeNode
TreeNode<K,V> root();
 
// 确保根节点是bin桶（数组tab的其中一个元素）中的第一个节点,如果不是，则进行操作，将根节点放到tab数组上
void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root);
 
// 从当前节点开始使用给定的hash和key查找到对应的节点，只会查询遍历以当前节点为根节点的局部树结构的节点。
TreeNode<K,V> find(int h, Object k, Class<?> kc);
 
// 根据key和key的hash 查找对应的树节点，找不到返回null
TreeNode<K,V> getTreeNode(int h, Object k);
 
// 比较两个对象的大小，-1：a<=b；1：a>b
int tieBreakOrder(Object a, Object b);
 
// 链表转红黑树
void treeify(Node<K,V>[] tab);
 
// 将树转换为链表结构，将TreeNode转化为Node
Node<K,V> untreeify(HashMap<K,V> map);
 
// 向红黑树插入 or 更新数据（键值对），遍历红黑树，找到与新数据key相同的节点，新数据value替换旧数据的value，找不到相同的key则创建新节点并插入
TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v);
 
// 红黑树的节点移除，还要根据movable判断删除时是否移动其他节点。movable - 如果为false，则在删除时不移动其他节点
void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,boolean movable);
 
// 红黑树拆分
void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit);
 
// 左旋操作
TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p);
 
// 右旋操作
TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p);
 
// 插入节点之后进行平衡调整，x为新添加的节点，root为树的根节点，返回根节点
TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x);
 
// 删除节点后自平衡操作，x是删除节点的替换节点
TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,TreeNode<K,V> x);
 
// 对整棵树进行红黑树一致性的检查 目前仅在检查root是否落在table上时调用，满足红黑树的特性以及节点指向的正确性
boolean checkInvariants(TreeNode<K,V> t);

以上为TreeNode的所有方法，但是在后面讲解方法源码的时候并不会按照TreeNode源码的方法顺序，而是按照HashMap在各种操作中的调用顺序来进行讲解，这样将TreeNode和HashMap结合起来讲解，更有助于理解HashMap的执行流程和原理。

二、构造方法

/**
* 构造方法直接调用的父类方法
* 最终还是HashMap.Node的构造方法，调用代码下面也列出来了
*/
TreeNode(int hash, K key, V val, Node<K,V> next) {
    super(hash, key, val, next);
}
 
/**
* TreeNode父类LinkedHashMap.Entry<K,V>的构造方法
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    // LinkedHashMap.Entry<K,V>的构造方法调用的还是父类的构造方法
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}
 
/**
* LinkedHashMap.Entry<K,V>父类HashMap.Node<K,V>的构造方法
*/
Node(int hash, K key, V value, Node<K,V> next) {
    this.hash = hash;
    this.key = key;
    this.value = value;
    this.next = next;
}
 

 TreeNode的构造方法，最终还是调用的Node的构造方法。

三、HashMap扩容操作

HashMap中的resize()扩容方法会触发一系列的TreeNode类的方法，依次为：split()、untreeify()、treeify()、tieBreakOrder()、balanceInsertion()、moveRootToFront()、checkInvariants()

调用开始位置：

final Node<K,V>[] resize() {
    ......
    // 判断当前的e是不是红黑树
    else if (e instanceof TreeNode)
        // 拆分树，重新更新HashMap扩容后红黑树中元素的位置
        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
    ......
}

3.1 split()

拆分操作，随着元素的插入，hashMap还会扩容，红黑树和链表因为扩容的原因导致原本在一个数组元素下的Node节点分为高低位两部分，低位树即当前原位置，高位树则在新扩容的tab上（原位置index + 扩容大小）。这一块难点就是 低位红黑树和高位红黑树的处理，至于(e.hash & bit) == 0 这个问题在之前的HashMap源码讲解的文章中已经解释过了，这里的原理和对链表进行高低位处理时的相同。

/**
* 将红黑中的节点拆分为较高位红黑树和低位红黑树，或者如果树现在太小，则取消树化
*
* @param index 当前红黑树所在数组位置
* @param bit 当前数组容量，也就是二倍扩容后要增加的容量大小
* @param map 这里将HashMap<K,V> map传入进来是为了调用HashMap类中的replacementNode()方法，用来实现TreeNode转为Node的操作。
* @param tab HashMap中的数组
*/
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    // 获得调用此方法的节点b，这个节点是存储在数组桶中的TreeNode节点，也就是红黑树的根节点
    TreeNode<K,V> b = this;
    // 重新链接到 lo 和 hi 列表，保留顺序
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null; // 低位树存储索引位置为:“原索引位置”的节点  loHead为链表头节点，loTail为链表尾节点
    TreeNode<K,V> hiHead = null, hiTail = null; // 高位树存储索引位置为:“原索引+oldCap”的节点   hiHead为链表头节点，hiTail为链表尾节点
    // lc 低位红黑树的节点数，hc 高位红黑树的节点数
    int lc = 0, hc = 0;
    // 从节点b开始，遍历整个红黑树节点。这里遍历红黑树是采用链表遍历的方法，因为TreeNode在维护节点的红黑树结构的同时，也维护了链表结构，所以既可以通过红黑树结构遍历，也可以通过链表结构遍历
    // 这个循环操作是将所有的节点遍历一篇，判断出哪些节点需要留在原位置，哪些节点需要升到高位，所以这里只需要通过链表方式把所有节点都遍历一遍就可以了。
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        // next赋值为e的下个节点
        next = (TreeNode<K,V>)e.next; 
        // 得到e的next后，将e的next指向null 以便垃圾收集器回收
        e.next = null;
        // 注意此处&运算的数组容量没有-1
        // 那么数组的容量值二进制表达必定为：1000...，所以此处计算只有两个结果，1或者0
        // 0：TreeNode在新数组的位置是原位置，将节点放入低位树；1：原位置加上旧数组容量值的位置，将节点放入高位树。
        if ((e.hash & bit) == 0) {
            // 将loTail节点变成e节点的前节点，
            // 若loTail节点不存在，代表该节点为第一个节点
            if ((e.prev = loTail) == null)
                //将e节点赋值给loHead节点，loHead指向第一个节点
                loHead = e;
            else
                //存在则将e节点赋值给loTail的后节点
                loTail.next = e;
            //将e节点赋值给loTail节点
            loTail = e;
            //计算低位红黑树的节点数
            ++lc;
        }
        // 以下操作和上方操作一样
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }
    // 如果低位红黑树存在
    if (loHead != null) {
        // 如果低位红黑树节点数量小于等于红黑树瓦解阈值6，
        if (lc <= UNTREEIFY_THRESHOLD)
            // 将低位红黑树转为链表，并将头节点放到原位置的桶中
            tab[index] = loHead.untreeify(map);
        else {
            // 否则将低位红黑树根节点放到数组上
            tab[index] = loHead;
            // 高位树不存在则说明原先的节点都在当前红黑树上。则就不需要变化了
            if (hiHead != null) // (else is already treeified) 
                // 如果高位红黑树存在，则将低位红黑树重新树化，
                // 虽然当前已经是红黑树了，但是节点改变了，所以要重新进行一遍树化，梳理节点
                loHead.treeify(tab);
        }
    }
    
    //以下操作与上方操作一样
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            // 将高位红黑树转为链表，并将根节点放到新位置的桶中
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                // 如果低位红黑树存在，则将高位红黑树重新树化，
                hiHead.treeify(tab);
        }
    }
}
 

 以上对红黑树的处理 涉及到 树化 和 反树化 ，也就是链表和红黑树的互相转换，下面我们来看一下反树化和树化代码。

3.2 untreeify()

将红黑树节点转为链表节点（反树化）, 当节点<=6个时会被触发。

/**
 * 将红黑树节点转为链表节点, 当节点<=6个时会被触发
 * @param map 这里将HashMap<K,V> map传入进来是为了调用HashMap类中的replacementNode()方法，来构建Node节点进而生成链表。
 */
final Node<K,V> untreeify(HashMap<K,V> map) {
    // hd指向头节点, tl指向尾节点
    Node<K,V> hd = null, tl = null; 
    // 从调用该方法的节点, 即链表（当前这个链表的节点都是TreeNode红黑树节点）的头节点开始遍历, 将所有TreeNode节点全转为Node链表节点
    for (Node<K,V> q = this; q != null; q = q.next) {
        // 调用HashMap的replacementNode()方法，将树节点构建成链表节点
        Node<K,V> p = map.replacementNode(q, null);
        // 如果tl为null, 则代表当前节点为第一个节点, 将hd指向p
        if (tl == null)
            hd = p;
        // 否则, 将尾节点的next指向当前节点p，也就是进行链表追加
        else
            tl.next = p;
        
        // 每次循环q都会后移一个，同理p也就是后移之后构建出来的链表节点
        tl = p; // 将tl节点指向链表节点p, 即尾节点
    }
    // 返回转换后的链表的头节点
    return hd;
}
// 构建链表节点
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
    return new Node<>(p.hash, p.key, p.value, next);
}

3.3 treeify()

以当前调用该方法的TreeNode为初始节点，遍历处理链表（使用TreeNode的链表结构）上的每个节点来进行树化，把遍历到的链表上的节点重新插入到新构建的红黑树结构中，每次插入树节点都要进行平衡处理，保证红黑树的平衡。这样就完成了重新的树化操作。根据这个方法的执行过程也可以看成是将链表结构转换为红黑树结构的方法。

/**
 * 红黑树树化操作
 * @param tab 在后续需要调用moveRootToFront方法将构建好的红黑树节点的根节点放置在tab数组的桶中
 */
final void treeify(Node<K,V>[] tab) {
    // 定义红黑树的根节点
    TreeNode<K,V> root = null; 
    // 遍历链表（使用TreeNode红黑树的链表结构来进行遍历），x指向当前节点、next指向下一个节点。初始化将x指向调用treeify()方法的TreeNode节点
    // 整个树化流程就是将需要重新树化的红黑树结构以它的链表形态进行遍历，将遍历到的每一个节点插入到新构建好的红黑树结构中，这里就会进行一个遍历红黑树的操作，每次插入一个节点就重新对新构建好的红黑树进行平衡处理。
    // 下面我们将遍历链表结构的当前节点x叫做链表节点，将后面遍历红黑树结构时的当前节点p成为红黑树节点，但需要注意它俩其实都是TreeNode节点，x节点所在的链表也只是使用了红黑树结构的链表形式，其本身也是一个红黑树
    for (TreeNode<K,V> x = this, next; x != null; x = next) { 
        // 下一个链表节点
        next = (TreeNode<K,V>)x.next; 
        // 设置当前链表节点的左右子节点为空，清空以前的红黑树结构，准备构建新的红黑树结构
        x.left = x.right = null; 
        // 如果新构建的红黑树还没有根节点，则将调用treeify()的节点设置为根节点
        if (root == null) {
            // 当前节点的父节点设为空
            x.parent = null; 
            // 当前节点的红色属性设为false（把当前节点设为黑色）
            x.red = false;
            // 根节点指向到当前节点（当前节点设置为根节点），将该链表节点插入到新构建红黑树的根节点位置
            root = x; 
        }
        // 如果已经存在根节点了，说明非第一次操作，则将x节点添加到root节点的子树上
        else {
            // 取得当前遍历到链表节点的key 
            K k = x.key; 
            // 取得当前遍历到链表节点的hash值
            int h = x.hash; 
            // 定义key所属的Class
            Class<?> kc = null; 
            // 从已经构建好的红黑树的根节点开始遍历，这里采用的是红黑树结构的遍历，此遍历没有设置边界，只能从内部跳出
            // p表示当前遍历到的节点，我们在这里可以将其称作红黑树节点，外面一层循环的x节点我们可以称其为链表节点，方便后续操作的区分
            for (TreeNode<K,V> p = root;;) { 
                // GOTO1
                // dir 表示方向（左右）、ph表示当前红黑树节点的hash值
                int dir, ph; 
                // pk表示当前树节点的key
                K pk = p.key; 
                // 如果当前树节点hash值 大于 当前链表节点的hash值
                if ((ph = p.hash) > h) 
                    // 表示当前链表节点会放到当前树节点的左侧
                    dir = -1; 
                else if (ph < h)
                    // 右侧
                    dir = 1; 
 
                /*
                * 如果两个节点的key的hash值相等，那么还要通过其他方式再进行比较
                * 下面这个if分支就是先判断kc是否等于null，注意它的后面是且运算符，所以当判断kc等于null的时候还要继续向下判断，kc==null说明kc还没有被赋值。
                * 然后再去调用comparableClassFor方法来判断当前节点的key是否实现了comparable接口，如果返回的是null说明没有实现，如果实现了，就会返回Key的class类型，这里对kc进行了赋值。
                * kc==null&&(kc = comparableClassFor(k)) == null是一个与运算组合，然后它门后面就是一个或运算，也就是如果kc没有被赋值并且调用comparableClassFor返回是null，也就是这个与运算表达式结果是true，那么整个或运算结果就是true，也不会继续执行后面的代码了，直接进入到if分支内部，因为如果是null说明它没有实现comparable接口，也就不能使用compareComparables方法来判断大小了，需要进入到if分支使用tieBreakOrder()来判断大小。
                * 但是如果返回不是null，说明key实现了comparable接口，可以使用compareComparables方法来比较大小，则会继续执行后面的代码。
                * 当确定了key实现了comparalble接口以后，就可以执行后面调用compareComparables方法的代码，来进行大小的判断，并且将判断大小的结果赋值给dir，只要dir！=0，说明compareComparables成功判断出了两个数据的大小关系，就不用进入if分支内使用tieBreakOrder来进行大小的比较了，
                * 但是如果返回的结果是0，说明compareComparables也没能比较出两者大小（比较的两个对象使用compareComparables方法比较也相等或者两者Class类型不一致或者要比较的有一方为null这个方法就会返回0），还是需要tieBreakOrder来比较。
                */
                else if ((kc == null && (kc = comparableClassFor(k)) == null) ||
                            (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);
 
                // 保存当前树节点
                TreeNode<K,V> xp = p; 
 
                /*
                 * 如果dir 小于等于0 ： 当前链表节点一定放置在当前树节点的左侧，但不一定是该树节点的左孩子，也可能是左孩子的右孩子 或者 更深层次的节点。
                 * 如果dir 大于0 ： 当前链表节点一定放置在当前树节点的右侧，但不一定是该树节点的右孩子，也可能是右孩子的左孩子 或者 更深层次的节点。
                 * 如果当前树节点不是叶子节点，那么最终会以当前树节点的左孩子或者右孩子 为 起始节点  再从GOTO1 处开始 重新寻找自己（当前链表节点）的位置
                 * 如果当前树节点就是叶子节点，那么根据dir的值，就可以把当前链表节点挂载到当前树节点的左或者右侧了。每一个链表节点最后都会被插入到红黑树的叶子节点下
                 * 挂载之后，还需要重新把树进行平衡。平衡之后，就可以针对下一个链表节点进行处理了。
                 */
                // if判断力的语句是先根据dir的值来将p.left或p.right赋值给p，然后再判断p是不是null
                // 如果p是null，说明它是叶子节点，直接将x链表节点插入到p的左子节点或右子节点即可
                // 如果不是null，说明不是叶子节点，则以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;
                }
            }
        }
    }
 
    // 把所有的链表节点都遍历完之后，最终构造出来的树可能经历多个平衡操作，根节点目前到底是链表的哪一个节点是不确定的
    // 因为我们要基于树来做查找，确保给定的根节点是其 tab 中的节点（存放在数组桶的节点）。
    moveRootToFront(tab, root); 
}

这个方法中在判断链表节点和树节点时，如果链表节点的hash值小于树节点的hash值的时候，链表节点就会作为树节点的左节点；hash值大于树结点的hash值的时候就作为树节点的右节点。如果发现它俩的key和hash值相等，这时还是会先尝试看是否能够通过Comparable进行比较一下两个对象，要想看看是否能基于Comparable进行比较的话，首先要看该元素键是否实现了Comparable接口，此时就需要用到comparableClassFor方法来获取该元素键的Class，然后再通过compareComparables方法来比较两个对象的大小。这里就是用了HashMap的两个方法comparableClassFor()和compareComparables()，TreeNode是HashMap的内部类，可以直接调用HashMap的方法。

如果两者不具有compare的资格，或者compare之后仍然没有比较出大小。那么最后就要通过tieBreakOrder方法再比较一次。

3.3.1 comparableClassFor()

/**
 * Returns x's Class if it is of the form "class C implements
 * Comparable<C>", else null.
 * 如果对象x的类是C，如果C实现了Comparable<C>接口，那么返回C，否则返回null。这个方法的作用就是查看对象x是否实现了Comparable接口
 */
static Class<?> comparableClassFor(Object x) {
    if (x instanceof Comparable) {
        Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
        // 如果x是个字符串对象，直接返回String.class
        if ((c = x.getClass()) == String.class) 
            // 返回String.class
            return c; 
        /*
         * 为什么如果x是个字符串就直接返回c了呢 ? 因为String  实现了 Comparable 接口，可参考如下String类的定义
         * public final class String implements java.io.Serializable, Comparable<String>, CharSequence
         */ 
 
        // 如果 c 不是字符串类，获取c直接实现的接口（如果是泛型接口则附带泛型信息）    
        if ((ts = c.getGenericInterfaces()) != null) {
            // 遍历接口数组
            for (int i = 0; i < ts.length; ++i) { 
                // 如果当前接口t是个泛型接口 
                // 如果该泛型接口t的原始类型p 是 Comparable 接口
                // 如果该Comparable接口p只定义了一个泛型参数
                // 如果这一个泛型参数的类型就是c，那么返回c
                if (((t = ts[i]) instanceof ParameterizedType) &&
                    ((p = (ParameterizedType)t).getRawType() ==
                        Comparable.class) &&
                    (as = p.getActualTypeArguments()) != null &&
                    as.length == 1 && as[0] == c) // type arg is c
                    return c;
            }
            // 上面for循环的目的就是为了看看x的class是否 implements  Comparable<x的class>
        }
    }
    // 如果c并没有实现 Comparable<c> 那么返回空
    return null; 
}

 

3.3.2 compareComparables()

/**
  * Returns k.compareTo(x) if x matches kc (k's screened comparable
  * class), else 0.
  * 如果x的类型是kc，返回k.compareTo(x)的比较结果
  * 如果x为空，或者类型不是kc，返回0
  * @param kc 对象k的Class类型
  * @param k  标准对象k
  * @param x  比较对象x
  */
@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
static int compareComparables(Class<?> kc, Object k, Object x) {
    return (x == null || x.getClass() != kc ? 0 :
            ((Comparable)k).compareTo(x));
}

3.4 tieBreakOrder()

比较两个对象的大小，返回值只能大于0或小于0，不能为0，因为需要插入节点是放在左子树还是右子树，这里在两个对象都不为空时，先使用compareTo的方法比较两个对象的类名按字符串规则比较，如果类名比较不出来或者为空则调用native方法System.identityHashCode()去比较key的hashcode值，相等时返回-1，否则返回1

/**
 * 比较a和b的大小，-1：a<=b；1：a>b
 */
static int tieBreakOrder(Object a, Object b) {
    int d;
    //对象a和b都不为null则进行比较
    if (a == null || b == null ||
        (d = a.getClass().getName().
         compareTo(b.getClass().getName())) == 0)
        //如果通过compareTo方法不能解决，则通过native的System.identityHashCode方法
        d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
             -1 : 1);
    return d;
}

 

3.5 balanceInsertion()

这里先简单说一下红黑树的平衡调整。红黑树是一种自平衡二叉树，拥有优秀的查询和插入/删除性能，广泛应用于关联数组。

对比 AVL 树，AVL 要求每个节点的左右子树的高度之差的绝对值（平衡因子）最多为 1，而红黑树通过适当的放低该条件（红黑树限制从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，结果是这个树大致上是平衡的），以此来减少插入/删除时的平衡调整耗时，从而获取更好的性能，而这虽然会导致红黑树的查询会比 AVL 稍慢，但相比插入/删除时获取的时间，这个付出在大多数情况下显然是值得的。

在 HashMap 中的应用：HashMap 在进行插入和删除时有可能会触发红黑树的插入平衡调整（balanceInsertion 方法）或删除平衡调整（balanceDeletion 方法），调整的方式主要有以下手段：左旋转（rotateLeft 方法）、右旋转（rotateRight 方法）、改变节点颜色（x.red = false、x.red = true），进行调整的原因是为了维持红黑树的数据结构。

红黑树的插入平衡，通过左旋、右旋和改变节点颜色来保证当前树符合红黑树的要求。在插入节点之后进行平衡调整，x为新添加的节点，root为树的根节点，返回根节点。

注释中写的各种章节，是这篇文章中对应的情况【数据结构】史上最好理解的红黑树讲解，让你彻底搞懂红黑树_小七mod的博客-CSDN博客_红黑树csdnhttps://blog.csdn.net/cy973071263/article/details/122543826?spm=1001.2014.3001.5501

/**
 * 调用该方法，是因为在红黑树插入新节点之后，可能会出现红黑树的失衡，需要重新进行平衡
 * @param root 当前根节点
 * @param x 新插入的节点
 * 
 * @return 返回重新平衡后的根节点
 */
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x) {
    // 新插入的节点标为红色                                                    
    x.red = true; 
 
    /*
     * 这一步即定义了变量，又开起了循环，循环没有控制条件，只能从内部跳出
     * xp：当前节点的父节点、xpp：祖父节点、xppl：左叔父节点、xppr：右叔父节点
     */
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { 
 
        // 如果父节点为空、说明当前节点就是根节点，那么把当前节点标为黑色，返回当前节点
        if ((xp = x.parent) == null) { 
            x.red = false;
            // 当前节点x即为红黑树的根节点
            return x;
        }
 
        // 父节点不为空
        // 如果父节点为黑色，则无需处理即可维持红黑树性质，直接返回根节点。
        // 后面这一段(xpp = xp.parent) == null根本就不可能出现这种情况，这里这样写只是为了对xpp祖父节点进行的复制，进而继续后面的操作。并不会真的出现(xpp = xp.parent) == null的情况导致直接返回根节点
        else if (!xp.red || (xpp = xp.parent) == null) // 6.2.1.1节
            return root;
        // 如果执行到这里，说明新插入节点的父节点是红色。之前讲过，父节点为红色一共有8种情况，全部都需要进行处理才能维持红黑树性质
        // 如果父节点是祖父节点的左孩子 
        if (xp == (xppl = xpp.left)) { 
            // 如果右叔父不为空 并且为红色，即上溢LL插入情况和上溢LR情况
            if ((xppr = xpp.right) != null && xppr.red) { // 上溢LL是6.2.4节，上溢LR是6.2.6节，这两种的修复方法一样
                // 右叔父置为黑色
                xppr.red = false; 
                // 父节点置为黑色
                xp.red = false; 
                // 祖父节点置为红色
                xpp.red = true; 
                // 运行到这里之后，就又会进行下一轮的循环了，将祖父节点当做处理的起始节点（当成新的插入节点处理）
                x = xpp; 
            }
            else { // 如果右叔父为空或者为黑色，即右叔父节点不为红色
                // 如果插入节点是父节点的右孩子，即LR插入情况，该情况的修复需要插入节点的父节点左旋，祖父节点右旋  
                if (x == xp.right) { // 6.2.3节
                    // 父节点左旋，并且将当前节点设置为原父节点，见下文左旋方法解析
                    root = rotateLeft(root, x = xp);
                    // 获取祖父节点（相对于新的x节点的祖父节点）。这个是为了后面需要将祖父节点进行右旋转，所以要获取一下祖父节点。
                    // 但是这里可能会比较绕，那就是这个时候x已经表示的不是原来的插入节点了，而是变成了插入节点的原父节点，这里实际上找的是旋转之后的插入节点的原父节点现在的祖父节点（这里的xp = x.parent指向的实际是插入节点，此时插入节点已经变成了其原父节点的父节点，两者颠倒了一下位置）
                    // 但旋转过后现在原父节点已经下降了一层了，所以向上走两代其实找到的还是原来的那个相对于插入节点的祖父节点，旋转并没有影响到祖父节点那一层的变化，所以这里是没有问题的。结合自旋图例更容易理解。
                    xpp = (xp = x.parent) == null ? null : xp.parent; 
                }
                // 如果插入节点是父节点的左节点，上面的if分支是不会执行的，只会执行下面的if分支。如果只执行下面的分支，说明是LL插入情况，修复方法是将祖父节点右旋。 6.2.2节
                // 如果执行了上面的if分支，还要执行下面的if分支，说明是LR插入情况
                // 如果父节点不为空，将祖父节点右旋来完成修复
                if (xp != null) { 
                    // 父节点置为黑色。此时的xp就是最开始的插入节点，只是因为自旋的原因换了位置。最开始插入节点x的父节点进行左旋，调用左旋方法的时候将插入节点x赋值给了原父节点，在经过左旋之后，原父节点下降了一层，原插入节点上升了一层，原插入节点成了原父节点的父节点，所以更新过的xp的父节点其实就是最开始的插入节点原x节点，想要将插入节点变成黑色，就需要把xp设置为黑色
                    xp.red = false; 
                    // 祖父节点不为空
                    if (xpp != null) { 
                        // 祖父节点置为红色
                        xpp.red = true;
                        // 祖父节点右旋，见下文右旋方法解析
                        root = rotateRight(root, xpp);  
                    }
                }
            }
        }
        else { // 如果父节点是祖父节点的右孩子
            // 如果左叔父节点是红色，即为上溢的RR插入情况和上溢的RL插入情况
            if (xppl != null && xppl.red) { // 上溢RR是6.2.5节，上溢RL是6.2.7节，这两种的修复方法一样
                // 左叔父节点置为 黑色
                xppl.red = false; 
                // 父节点置为黑色
                xp.red = false; 
                // 祖父节点置为红色
                xpp.red = true; 
                // 运行到这里之后，就又会进行下一轮的循环了，将祖父节点当做处理的起始节点 
                x = xpp; 
            }
            else { // 如果左叔叔为空或者是黑色，即左叔父节点不为红色
                // 如果插入节点是父节点的左孩子，即RL插入情况，该情况的修复需要插入节点的父节点右旋，祖父节点左旋  
                if (x == xp.left) { // 6.2.3节
                    // 针对父节点做右旋，见下文右旋方法解析
                    root = rotateRight(root, x = xp); 
                    // 获取祖父节点，这个是为了后面需要将祖父节点进行左旋转，所以要获取一下祖父节点。
                    xpp = (xp = x.parent) == null ? null : xp.parent; 
                }
                // 如果插入节点是父节点的右节点，上面的if分支是不会执行的，只会执行下面的if分支。如果只执行下面的分支，说明是RR插入情况，修复方法是将祖父节点左旋。 6.2.2节
                // 如果执行了上面的if分支，还要执行下面的if分支，说明是RL插入情况
                // 如果父节点不为空 
                if (xp != null) { 
                    // 父节点置为黑色。此时的xp就是最开始的插入节点，只是因为自旋的原因换了位置。
                    xp.red = false; 
                    // 如果祖父节点不为空
                    if (xpp != null) { 
                        // 爷爷节点置为红色
                        xpp.red = true; 
                        // 针对祖父节点做左旋
                        root = rotateLeft(root, xpp); 
                    }
                }
            }
        }
    }
}

 

3.5.1 rotateLeft()

 

// p：图示中的 E， r：图示中的 S，  rl:图示最开始S节点的左子节点，只有这个节点做了位置的较大改动，从S的子节点变成了E的子节点
// E节点由上层转移到了下层，S节点由下层转移到了上层
/**
 * 节点左旋
 * root 根节点
 * p 要左旋的节点
 */
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                              TreeNode<K,V> p) {
    // r：要左旋节点的右子节点  pp：要左旋节点的父节点  rl：要左旋节点的右孩子的左子节点
    TreeNode<K,V> r, pp, rl;
    // 要左旋的节点 以及 要左旋的节点的右孩子 不为空。此时将要左旋节点的右孩子赋值给r
    if (p != null && (r = p.right) != null) { 
        // 下面要重新设置要左旋节点的右子节点的左子节点的位置，因为旋转过程中只有这个节点有较大的位置变动，以图为例它的父节点由S变成了E
        // 要左旋的节点的右孩子的左节点 赋给 要左旋的节点的右孩子。此时将要左旋节点的右孩子的左子节点赋值给rl
        if ((rl = p.right = r.left) != null) 
            // 设置rl和要左旋的节点的父子关系【之前只是爹认了孩子，孩子还没有答应，这一步孩子也认了爹】
            rl.parent = p; 
        // 下面就是要重新设置左旋节点父节点的新子节点，因为左旋节点已经被旋转到了下一层，左旋节点原来的位置被旋转上来一个新的元素，需要重新设置父子关系
 
        // 将要左旋的节点的右孩子的父节点 指向 要左旋的节点的父节点，相当于右孩子提升了一层。此时将要左旋节点的父节点赋值给pp
        // 此时如果父节点为空，说明r已经是顶层节点了，应该作为root并且标为黑色
        if ((pp = r.parent = p.parent) == null) 
            (root = r).red = false;
        // 如果父节点不为空 并且 要左旋的节点是个左孩子
        else if (pp.left == p) 
            // 设置r和父节点的父子关系【之前只是孩子认了爹，爹还没有答应，这一步爹也认了孩子】
            pp.left = r; 
        else // 要左旋的节点是个右孩子
            pp.right = r; 
        // 重新设置左旋节点和左旋节点的右子节点的父子关系，因为此时左旋节点被旋转到了下一层，左旋节点的右子节点旋转到了上一层，两者的父子关系进行了对调
        // 要左旋的节点 作为 它的右孩子的左节点  【爹认孩子】
        r.left = p; 
        // 要左旋的节点的右孩子 作为 它的父节点  【孩子认爹】
        p.parent = r; 
    }
    // 返回根节点
    return root; 
}

 

3.5.2 rotateRight()

// p：图示中的 S，l：图示中的 E，lr：图示最开始E节点的右子节点，只有这个节点做了位置的较大改动，从E的子节点变成了S的子节点
// E节点由下层转移到了上层，S节点由上层转移到了下层
/**
 * 节点右旋
 * root 根节点
 * p 要右旋的节点
 */
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                               TreeNode<K,V> p) {
    // l：要右旋节点的左子节点  pp：要右旋节点的父节点  lr：要右旋的节点的左孩子的右节点
    TreeNode<K,V> l, pp, lr;
    // 要右旋的节点不为空 以及 要右旋的节点的左孩子不为空。此时将要右旋节点的左子节点赋值给l
    if (p != null && (l = p.left) != null) {
        // 下面要重新设置要右旋节点的左子节点的右子节点的位置，因为旋转过程中只有这个节点有较大的位置变动，以图为例它的父节点由E变成了S
        // 要右旋的节点的左孩子的右节点 赋给 要右旋节点的左孩子。此时将要右旋的节点的左孩子的右节点赋值给lr 
        if ((lr = p.left = l.right) != null) 
            // 设置lr和要右旋的节点的父子关系【之前只是爹认了孩子，孩子还没有答应，这一步孩子也认了爹】
            lr.parent = p; 
        // 下面就是要重新设置右旋节点父节点的新子节点，因为右旋节点已经被旋转到了下一层，右旋节点原来的位置被旋转上来一个新的元素，需要重新设置父子关系
 
        // 将要右旋的节点的左孩子的父节点 指向 要右旋的节点的父节点，相当于左孩子提升了一层。此时将要右旋节点的父节点赋值给pp
        // 此时如果父节点为空， 说明l已经是顶层节点了，应该作为root 并且标为黑色
        if ((pp = l.parent = p.parent) == null) 
            (root = l).red = false;
        // 如果父节点不为空 并且 要右旋的节点是个右孩子
        else if (pp.right == p) 
            // 设置l和父节点的父子关系【之前只是孩子认了爹，爹还没有答应，这一步爹也认了孩子】
            pp.right = l; 
        else // 要右旋的节点是个左孩子
            // 同上
            pp.left = l; 
        
        // 下面要重新设置右旋节点和右旋节点的左子节点的父子关系，因为此时右旋节点被旋转到了下一层，右旋节点的左子节点旋转到了上一层，两者的父子关系进行了对调
        
        // 要右旋的节点 作为 他左孩子的右节点   【爹认孩子】
        l.right = p; 
        // 要右旋的节点的父节点 指向 他的左孩子 【孩子认爹】
        p.parent = l; 
    }
    // 返回根节点
    return root;
}
 

3.6 moveRootToFront()

当我们删除或者增加红黑树节点的时候，root节点在双链表中的位置可能会变动，为了保证每次红黑树的根节点都在链表的第一个位置（也就是红黑树根节点需要在数组桶中），在操作完成之后需要moveRootToFront方法来进行调整，将root节点移动到数组桶中。

TreeNode<K,V> extends LinkedHashMap.Entry<K,V>因为TreeNode继承了Entry。所以它除了它自己几个属性 parent 、left、 right、 prev、 red、之外，还有继承过来的属性hash、key、value 、next。因为有prev和next属性，所以它底层其实是双结构的，维护着红黑树和双向链表两种结构。所以当每次调整好红黑树之后，root节点的位置可能会变动，红黑树的位置关系改变了，但是双向链表的关系没有变，那这个时候我们就要重新维护root在双向链表中的关系了，这里注意下，重新维护时不是修改红黑树结构而是修改的链表结构的prev和next属性，进而将table的桶指向新的root节点（移动双向链表中的元素并不会影响红黑树，同样移动红黑树也不会影响双向链表）。

/**
 * 将root放到头节点(链表结构的头节点，也就是将root节点放到数组桶中)的位置, 原头节点（原来在数组桶中的节点）放在root的next节点上，即保证树的根节点一定也要成为链表的头节点
 * 把红黑树的根节点放置在数组桶中
 */
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
    // 当前数组tab的长度
    int n;
    if (root != null && tab != null && (n = tab.length) > 0) {
        // 找到当前树所在的bin桶位置（即数组tab的位置）
        int index = (n - 1) & root.hash;
        // 将tab[index]的树节点记录下来为first
        TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
        // 判断当前root和该root应该在的数组桶位置上的元素是不是同一个，如果不是，说明root没有落在tab数组上，则将root调整放置在tab数组上
        if (root != first) {
            Node<K,V> rn;
            // 这里即替换掉tab[index]指向的原有节点，可以理解成现在指向root节点
            tab[index] = root;
            // rp为root指向的前一个节点
            TreeNode<K,V> rp = root.prev;
            // rn为root的后一个节点
            // 将root前后节点关联
            if ((rn = root.next) != null)
                // root节点的next节点的prev前驱节点指向root节点的prev节点，相当于把root从链表中摘除
                ((TreeNode<K,V>)rn).prev = rp;
            if (rp != null)
                // root节点的prev节点的next后继节点指向root节点的next节点
                rp.next = rn;
            // first 和 root 节点进行关联，first的前一个节点为root
            if (first != null)
                // 操作与root前后节点关联相同，将first的前一个节点指向root，相当于root目前位于链表的首位
                first.prev = root;
            // 修改root的链表属性，原来的链表头节点现在作为root的下一个节点，变成了第二个节点
            root.next = first;
            // root节点的前驱节点置为空，头节点没有前驱节点
            root.prev = null;
        }
        
        /*
         * 检查红黑树一致性，这一步是防御性的编程
         * 校验TreeNode对象是否满足红黑树和双链表的特性
         * 如果这个方法校验不通过：可能是因为用户编程失误，破坏了结构（例如：并发场景下）；也可能是TreeNode的实现有问题（这个是理论上的以防万一）；
         */ 
        assert checkInvariants(root);
    }
}

 

3.7 checkInvariants()

对整棵树进行红黑树一致性的检查，目前仅在检查root是否落在table上时调用。校验是否满足红黑树的特性以及双向链表的特性。

/**
 * Recursive invariant check
 */
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
    TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
        tb = t.prev, tn = (TreeNode<K,V>)t.next;
    //t的前一个节点的next指针应该指向t
    if (tb != null && tb.next != t)
        return false;
    //t的后一个节点的prev指针应该指向t
    if (tn != null && tn.prev != t)
        return false;
    //t的父节点的左子节点或者右子节点应该为t
    if (tp != null && t != tp.left && t != tp.right)
        return false;
    //t的左子节点的父节点应该为t且t的左子节点的has值小于t的哈希值
    if (tl != null && (tl.parent != t || tl.hash > t.hash))
        return false;
    //t的右子节点的父节点应该为t且t的右子节点的hash值应该大于t的hash值
    if (tr != null && (tr.parent != t || tr.hash < t.hash))
        return false;
    //t和t的子节点不能同时为红
    if (t.red && tl != null && tl.red && tr != null && tr.red)
        return false;
    //如果t的左子节点存在，那么左子节点递归检查
    if (tl != null && !checkInvariants(tl))
        return false;
    //如果t的右子节点存在，那么右子节点递归检查
    if (tr != null && !checkInvariants(tr))
        return false;
    return true;
}

 这是一个递归函数。整个执行过程类似于二叉树，叶子节点返回的bool值给上一层，以此类推，一直到了root。

返回上一层后，if (tl != null && !checkInvariants(tl))和if (tr != null && !checkInvariants(tr))会分别判断两个底层返回来的bool值，如果返回的bool值都是true，那么将执行终点return true。

四、HashMap添加操作

HashMap中的putVal()添加元素方法会触发一系列的TreeNode类的方法，依次为：putTreeVal()、root()、find()

调用开始位置：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    ......
    // 若p节点是红黑树，则直接在树中插入或者更新键值对
    else if (p instanceof TreeNode){
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    }
    ......
    // 插入节点后，判断是否需要链表转红黑树，
    // 链表元素数大于8才转，因为这里是从第二个节点开始的，所以 TREEIFY_THRESHOLD - 1 = 7 ，又因为binCount是从0开始的，所以用的是>=号。
    // 例如bigCount=7，表示循环了进行了7次，加上原来的那个头节点，表示该链表原先有8个节点，然后新元素又进行了尾插入，此时该链表就有9个元素了，所以此时就得树化操作
    if (binCount >= TREEIFY_THRESHOLD - 1)
        treeifyBin(tab, hash); // 树化操作
    ......
}

4.1 putTreeVal()

向红黑树插入 or 更新数据（键值对），遍历红黑树，如果找到与新数据key相同的节点，则直接返回该节点；如果找不到相同的key，则创建新节点并插入，然后重新平衡红黑树。

putTreeVal的两种情况：

1. key已经存在这个红黑树中当中了，就直接放回对应的那个节点；
2. 从红黑树的root节点开始遍历，定位到要插入的叶子节点，插入新节点；

putTreeVal除了要维护红黑树的平衡外，还需要维护节点之间的前后关系，也就是同时在维护双向链表关系。

/**
    红黑树的put操作，红黑树插入会同时维护原来的链表属性, 即原来的next属性
    @param map:当前调用该方法的对象实例，也就是当前map
    @param tab：当前map里的数组，
    @param h:新数据的key计算出来的hash，
    @param k：新数据的key，
    @param v：新数据的value 
    @return 成功插入返回null，如果找到在红黑树中有key相同的节点，则直接将该节点返回
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) {
    // 新数据的key的Class类型
    Class<?> kc = null;
    // 是否调用find方法进行查找，默认没调用
    boolean searched = false;
    // 查找根节点, 索引位置的头节点并不一定为红黑树的根节点，所以需要通过调用root()方法来遍历红黑树结构进而找到根节点
    // 此处的this就是调用该方法的TreeNode实例，
    TreeNode<K,V> root = (parent != null) ? root() : this;
    // 将根节点赋值给p节点，从根节点开始遍历红黑树，从内部终止遍历
    for (TreeNode<K,V> p = root;;) {
        // dir：表示向哪个子树查找，-1左，1右； p：当前节点，ph：当前树节点的hash，pk：当前树节点的key
        int dir, ph; K pk;
        // 将当前节点p的hash赋值给ph，
        // 并且新数据的hash小于当前树节点的hash，则向p的左子树查找
        if ((ph = p.hash) > h)
            // dir赋值为-1
            dir = -1;
        // 否则向p的右子树查找
        else if (ph < h)
            // dir赋值为1
            dir = 1;
        // 当前树节点的key等于新数据的key，直接返回当前节点
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        /**
         * 如果kc为null，说明当前kc还没有被赋值，需要继续执行后面的代码对kc进行赋值，因为它的后面是与运算符，如果kc已经被赋值了，说明已经执行过后面的语句了，就不用再执行后面comparableClassFor和compareComparables了
         * kc==null&&(kc = comparableClassFor(k)) == null是同一个与运算表达式，继续执行后面comparableClassFor来判断key是不是实现了comparable接口，如果返回null，说明key没有实现comparable接口，也就无法使用compareComparables来比较大小了。整个与运算表达式结果为true，也就直接进入到if分支内部了，因为它们的后面是或运算
         * 如果实现了comparable接口接口，则继续调用compareComparables来比较大小，如果返回值不为0，则说明通过compareComparables比较出了大小，将比较结果直接赋值给dir，也就不用执行if分支内部的语句来比较大小了。
         * 如果返回值为0，说明compareComparables方法也没有比较出两者的大小关系，则需要继续进入到if分支内部去用别的方法继续进行比较。
         */
        else if ((kc == null && (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            // 还没有调用find方法进行查找
            if (!searched) {
                TreeNode<K,V> q, ch;
                // 改为已经调用find方法进行查找了，
                searched = true;
                // 从p节点的左节点和右节点分别调用find方法进行查找, 如果查找到目标节点则并终止循环，返回q；
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                    // 找到了相同key的节点，直接返回该节点
                    return q;
            }
            // 使用定义的一套规则来比较p节点的key和新数据的key大小, 用来决定向左还是向右查找
            dir = tieBreakOrder(k, pk);// dir<0 则代表 k<pk，则向p左边查找；反之亦然
        }
        // x表示新插入元素构建出来的树节点
        // xp赋值为x的父节点，中间变量，用于下面给x的父节点赋值
        TreeNode<K,V> xp = p;
        // dir<=0则向p左边查找，否则向p右边查找，如果为null,说明已经到达了叶子节点，红黑树插入新节点都会插入到叶子结点的位置，遍历到了null则代表该位置即为新插入节点x的应该插入的位置，进入if分支内进行插入操作
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            // 走进来代表已经找到x要插入的位置，只需将x放到该位置即可
            Node<K,V> xpn = xp.next;
            // 创建新的节点, 其中x的next节点为xpn, 即将x节点插入xp与xpn之间
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            // 调整x、xp、xpn之间的属性关系
            if (dir <= 0) // 如果时dir <= 0, 则代表x节点为xp的左节点
                xp.left = x;
            else // 如果时dir> 0, 则代表x节点为xp的右节点
                xp.right = x;
            // 将xp的next节点设置为x
            xp.next = x; 
            // 将x的parent和prev节点设置为xp
            x.parent = x.prev = xp; 
            // 如果xpn不为空,则将xpn的prev节点设置为x节点,与上文的x节点的next节点对应
            if (xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            // 进行红黑树的插入平衡调整，调用了balanceInsertion和moveRootToFront
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

4.2 root()

查找红黑树的根节点。向上层遍历，通过判断有没有父节点来找出根节点

final TreeNode<K,V> root() {
    for (TreeNode<K,V> r = this, p;;) {
        // 当节点没有父节点的时候，该节点即为根节点
        if ((p = r.parent) == null)
            return r;
        // 当前遍历到的节点设置为其父节点，实现向上层遍历
        r = p;
    }
}

4.3 find()

从调用此方法的节点开始查找, 对左右子树进行递归遍历，通过hash值和key找到对应的节点。查找过程是比较hash，判断往左找还是往右找，特殊情况就是一边为空，那就只往另一边找，比较key是否相等，递归遍历直到找到相等的key时，就代表找到了。

/**
 * 从调用此方法的节点开始查找, 通过hash值和key找到对应的节点
 * 此方法是红黑树节点的查找, 红黑树是特殊的自平衡二叉查找树
 * 平衡二叉查找树的特点：左节点<根节点<右节点
 * 
 * @return 找到了返回找到的节点，没找到返回Null
 */
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    // 1.将p节点赋值为调用此方法的节点，即为红黑树根节点
    TreeNode<K,V> p = this;
    // 2.从p节点开始向下遍历
    do {
        // ph p的hash，pk p的key
        int ph, dir; K pk;
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        // 3.如果传入的hash值小于p节点的hash值，则往p节点的左边遍历
        if ((ph = p.hash) > h)
            p = pl;
        // 4.如果传入的hash值大于p节点的hash值，则往p节点的右边遍历
        else if (ph < h)
            p = pr;
        // 5.如果传入的hash值和key值等于p节点的hash值和key值,则p节点为目标节点,返回p节点
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        // 6.p节点的左节点为空则将向右遍历
        else if (pl == null)    
            p = pr;
        // 7.p节点的右节点为空则向左遍历
        else if (pr == null)    
            p = pl;
        // 8.如何k的hash值等于pk的hash值，但是k和pk不相等，则将继续用其他的方法对p节点与k进行比较
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) && // 8.1 kc不为空代表k实现了Comparable
                 (dir = compareComparables(kc, k, pk)) != 0)// 8.2 k<pk则dir<0, k>pk则dir>0
            // 8.3 k<pk则向左遍历(p赋值为p的左节点), 否则向右遍历
            p = (dir < 0) ? pl : pr;
        // 9.代码走到此处, 代表key所属类没有实现Comparable, 向p的右边遍历查找，继续递归调用find()
        else if ((q = pr.find(h, k, kc)) != null) 
            return q;
        // 10.代码走到此处代表上一步的向右边没找到“pr.find(h, k, kc)”为空, 因此向左遍历
        else
            p = pl;
    } while (p != null);
    // 没找到
    return null;
}

 

4.4 untreeify()、treeify()、treeifyBin()总结

上一章节讲了untreeify()和treeify()两个TreeNode类的方法，在HashMap源码讲解的文章里讲了HashMap类的treeifyBin()方法。下面将这三个方法拿到一起对比总结一下。

4.4.1 treeifyBin()和treeify()

在向一个HashMap中添加数值时，算法会根据已经计算过的节点数binCount来控制是否需要将链表转化为红黑树，如果着实需要，那么会将当前hash值映射的桶进行树化。在本节最开始也贴出了，插入数据时进行树化需要调用treeifyBin()方法，然后treeifyBin()方法再去调用treeify()方法。

在树化的过程中使用的这两个方法，其中，treeifyBin()是将链接的链表线索化，即为每个二叉树的节点添加前驱和后继节点，形成线索，也就是维护了双向链表的结构，并且将节点都转换成红黑树节点。在完成线索化后，算法会调用treeify函数将已经线索化的链表转化为红黑树。

除了这两个方法之外，还有replacementTreeNode()和newTreeNode()两个方法用来完成Node节点和TreeNode节点之间的相互转化。由于TreeNode没有表达next的语义，所以虽然TreeNode继承自Node，但在算法中调用replacementTreeNode()时，形参next被赋予null。在Node转向TreeNode后，next语义由left，right两个字段表达。

treeifyBin小结：

1. 判断是否真的需要转换红黑树，如果数组长度小于MIN_TREEIFY_CAPACITY 将会对HashMap进行扩容，不会去进行树化。
2. 如果符合转换的条件。将指定链表上的节点转换成树形节点，并且构造成双链表，为调用treeify()转换成红黑树结构做准备。

treeify小结：

该方法的主要作用就是，将链表的元素一个一个的插入到树中，构造出符合红黑树特性的结构，来将链表结构真正转换为红黑树结构。真正构建红黑树结构就是在这个方法内实现的。

4.4.2 untreeify()

这个方法就相对简单很多，就是将红黑树转变为链表，具体的实现就是使用红黑树节点的链表结构进行遍历，将所有的TreeNode节点都转换为Node节点，只是对节点的类型进行了转换，并没有修改红黑树和链表的结构。

五、HashMap查找操作

HashMap中的getNode()查找元素方法会触发一系列的TreeNode类的方法，依次为：getTreeNode()、root()、find()

调用开始位置：

final Node<K,V> getNode(int hash, Object key) {
    ......
    // 第一个节点不是要找的元素，
    // 取出来第二个节点，并且第二个节点不为null，说明还没走到该节点链的最后
    if ((e = first.next) != null) {
        // 如果第一个节点是红黑树类型
        if (first instanceof TreeNode){
            // 调用红黑树的查找目标节点方法getTreeNode
            return ((TreeNode<K,V>)first).getTreeNode(hash, key);
        }
        ......
    }
    ......
}

 

5.1 getTreeNode()

在红黑树中根据key和key的hash 查找对应的树节点，找不到返回null，这里要先找到根节点，然后从根节点再去查找树节点。root 和 find 方法之前已经讲解过了。

final TreeNode<K,V> getTreeNode(int h, Object k) {
    // 如果当前调用该方法的红黑树节点还有父级节点，说明该红黑树节点不是根节点，所以需要调用 root() 方法找到根节点，
    // 如果当前调用该方法的红黑树节点没有父级节点，说明该红黑树节点就是根节点，
    // 找到根节点后，根节点调用find方法去查找目标节点
    return ((parent != null) ? root() : this).find(h, k, null);
}

六、HashMap删除操作

HashMap中的removeNode()删除元素方法会触发一系列的TreeNode类的方法，依次为：removeTreeNode()、untreeify()、balanceDeletion()、rotateLeft()、rotateRight()

调用开始位置：

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    ......        
    // 找到目标节点了
    if (node != null && (!matchValue || (v = node.value) == value ||
                            (value != null && value.equals(v)))) {
        // 如果目标节点是红黑树
        if (node instanceof TreeNode){
            // 调用红黑树的删除节点方法
            ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
        }
        ......
    }
    ......
}

6.1 removeTreeNode()

6.1.1 removeTreeNode()方法图解

本图解忽略红黑树的颜色，请注意。下面的图解是代码中的最复杂的情况（p既有左子树也有右子树的情况，代码中的情况12），即流程最长的那个，p 节点不为根节点，p 节点有左右节点，s 节点不为 pr 节点，s 节点有右节点。

另外，第一次调整和第二次调整的是根据代码而设定的，将第一次和第二次调整合起来看会更容易理解（看第一和第三张图）。如下：

• 第一次调整 + 第二次调整：将 p 节点和 s 节点进行了位置调换，选出要替换掉 p 节点的 replacement
  • 这个操作关键点就是找到与p节点进行位置对调的s节点。将p节点与s节点对调，是为了在删除p节点后，能够更加简单方便地维护二叉搜索树结构。那么什么样的位置能让删除p后，能更加简单的进行后续处理呢，也就是我们该如何选定s节点。其实很容易就能想到，当要删除的节点p只有一棵子树甚至没有子树的时候，我们对后续的操作越方便。所以在选择s节点的时候，就按照让p的子树越少越好的原则来选，在removeTreeNode中选择s节点的标准就是选择刚刚大于p节点的节点，因为这个节点必定没有左子树了，如果有左子树的话它也不会是刚刚大于p节点的节点，这样也就满足了该位置最多只有一颗子树的条件。这一步的具体讲解见代码12.1-12.3
  • 第二个关键操作就是寻找replacement节点，用来替换掉p节点。removeTreeNode的规则就是取s和p交换位置前s的右子节点sr作为要用来替代p节点的replacement节点（如果sr为空的话就不用找代替节点了）。p和s交换位置之后，sr就是p的唯一子树的根节点，直接将sr替换到p的原位置即可，不需要做其他操作就能维持二叉搜索树结构。
• 第三次调整：将 replacement 节点覆盖掉 p 节点。可见第三张和第四张图的变化。

6.1.2 removeTreeNode()方法源码

删除树节点操作，谁调用该方法就删除谁，并且在删除完后进行红黑树平衡操作。

还要根据movable判断删除节点后是否移动其他节点，即删除完成之后，需否需要执行moveRootToFront()方法，将红黑树根节点root放到数组桶中。movable参数在remove()方法调用时默认是true。

该方法在HashMap里removeNode方法中使用，被要删除的节点调用的。该删除操作相当于将链表结构和红黑树结构节点之间的关联重新梳理，修正两部分，第一部分是链表的关系修正，第二部分是树的关系修正，然后自平衡操作即可。

/**
 * 红黑树的节点移除
 * @param movable 如果为false，则在删除后不移动其他节点，不用执行moveRootToFront()方法。
 */
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                          boolean movable) {
    // --- 链表的处理start ---
    int n;
    // 1.table为空或者length为0直接返回
    if (tab == null || (n = tab.length) == 0)
        return;
    // 2.根据调用者的hash计算出索引的位置，也就是 根据将要被移除的node节点的hash进行计算
    int index = (n - 1) & hash;
    // 3.first：当前index位置的节点，root：当前index位置的节点，作为根节点，rl：root的左节点
    TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
    // 4.succ：目标节点(也就是this节点，调用removeTreeNode方法要删除掉的节点)node.next节点，pred：目标节点node.prev节点
    TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
    // 下面的5-7步的操作就是在链表结构上对node目标节点进行删除
    // 5.如果pred节点为空，则代表目标节点node为头节点，
    if (pred == null){
        // 则将table索引位置和first都指向succ节点(node.next节点)
        tab[index] = first = succ;
    }
    // 6.否则将pred的next属性指向succ节点(node.next节点)
    else{
        // 这块有一点点饶，主要是因为他这个变量搞得，其实等同于 node.prev.next = node.next;
        // 原来是 pred.next = node -> node.next = succ
        // 现在是 pred.next = node.next = succ，跳过了node，也就相当于把node删除了（前驱节点与后继节点相连，跳过node节点）
        pred.next = succ;
    }
    // 7.如果succ节点(node.next节点)不为空，
    if (succ != null){
        // 则将succ.prev(node.next.prev)节点设置为pred(node.prev), 与前面对应（后继节点与前驱节点相连，跳过node节点）
        // 等同于 node.next.prev = node.prev
        succ.prev = pred;
    }
    // 8.如果first节点为null，则代表该索引位置没有节点则直接返回
    // 这个if其实可以放在上方第3点后面，第4点前面，因为直接判断索引位置就是null，压根不用在找下个节点
    if (first == null){
        return;
    }
    // 9.如果root的父节点不为空，说明该节点并不是真正的红黑树根节点，需要重新查找根节点
    if (root.parent != null){
        // 从该root节点开始去查找根节点，得到根节点之后，将root指向真正的红黑树根节点
        root = root.root();
    }
    // 10.通过root节点来判断此红黑树是否太小, 如果是太小了则调用untreeify方法转为链表节点并返回
    // (转链表后就无需再进行下面的红黑树处理)
    // 太小的判定依据：根节点为null，或者根的右节点为null，或者根的左节点为null，或者根的左节点的左节点为null
    // 这里并没有遍历整个红黑树去统计节点数是否小于等于阈值6，而是直接判断这几种情况，来决定要不要转换为链表，因为这几种情况一般就涵盖了节点数小于6的情况，这样执行效率也会变高
    if (root == null || root.right == null ||
        (rl = root.left) == null || rl.left == null) {
        tab[index] = first.untreeify(map);  // too small
        return;
    }
    // --- 链表的处理end ---
    // --- 红黑树的处理start ---
    // 11.p：目标节点node，pl：p的左节点，pr：p的右节点，replacement：用来替换掉被删除节点的节点
    TreeNode<K,V> p = this, pl = left, pr = right, replacement;
    // 12.如果p的左和右节点都不为空时。这种情况是最复杂的
    if (pl != null && pr != null) {
        // 12.1-12.3操作就是用来定位节点p和节点s，为第一次调整做准备
        /**
         * 这里说明一下p和s的作用
         * p就是目标节点，也就是我们要删除的节点，这个没什么可说的。
         * 但是p节点不能直接在原位置将其删除，因为如果P有左右子树的话，将p删除后应该对其子树进行移动处理，需要在其中选出合适的节点放置在p原有的位置来代替p，并且重新维护搜索二叉树结构。毕竟删除后p的原有位置不能是空的，需要有新的节点来顶替上。
         * 如果直接在p的原位置删除的话，后续的处理操作有很大的难度，从两颗子树中找到合适的节点来代替p原有的位置是一件很麻烦的事情，因为有很多个可选择的节点，这个选择标准不好把控，而且就算是选出来也需要进行一些列的操作来维护二叉搜索树结构（需要照顾到两棵子树的结构）。所以最好是将p移动到一个对后续操作更加简单位的位置上
         * s节点就是要在删除p前，应该将p移动到的位置，将p与s节点进行位置交换，后续的处理就会更加简单
         * 那么什么样的位置能让删除p后，能更加简单的进行后续处理呢，也就是我们该如何选定s节点？
         * 其实很容易就能想到，当要删除的节点p只有一棵子树甚至没有子树的时候，我们对后续的操作越方便。想想看如果p没有子树，那么删除了p之后，也不需要做其他操作来维护二叉搜索树结构了，只需要后续进行红黑树平衡操作即可，如果p只有一棵子树，那也很简单，直接将这颗子树的根节点替换到p的原有位置即可维持二叉搜索树结构
         * 所以在选择s节点的时候，就按照让p的子树越少越好的原则来选
         * 在removeTreeNode中选择s节点的标准就是选择刚刚大于p节点的节点，因为这个节点必定没有左子树了，如果有左子树的话它也不会是刚刚大于p节点的节点，这样也就满足了该位置最多只有一颗子树的条件。
         * 并且s节点如果刚刚大于p节点，那么将s和p节点交换位置，其他的节点都不需要变换位置，因为s是刚刚大于p节点的节点，所以将s放到p的位置，能让他继续保持和p节点一样的与pp、pl、pr等其他节点相同的位置关系。虽然交换后s和p的位置关系有问题（s应该是大于p的，交换之后p却成了s的左子树节点），但是后续删除p节点即可。具体的变化可以对比第一次调整前和第二次调整后的两张图片
         * 
         */
        // 12.1 将s指向pr(p的右节点)，这是为了保证查找s节点是找到的节点都是比p大的    sl：s的左节点
        TreeNode<K,V> s = pr, sl;
        // 12.2 从p节点的右子节点开始，向左一直查找，跳出循环时，s为没有左节点的节点。这也就保证了最后定位到的s节点是刚刚比p大的节点
        while ((sl = s.left) != null){
            s = sl;
        }
        // 12.3 交换p节点和s节点的颜色
        boolean c = s.red; s.red = p.red; p.red = c;
        // s的右节点
        TreeNode<K,V> sr = s.right; 
        // p的父节点
        TreeNode<K,V> pp = p.parent; 
        // --- 第一次调整和第二次调整：将p节点和s节点进行了位置调换，并且选出要替换掉 p 节点的 replacement ---
        // 12.4 第一次调整：将 p 节点和 s 节点进行了位置调换
        // 如果p的右节点即为s节点，则将p和s交换位置，原先是s.parent = p；p.right = s；
        if (s == pr) {
            p.parent = s;
            s.right = p;
        }
        else {
            // 将sp指向s的父节点
            TreeNode<K,V> sp = s.parent;
            // 将sp作为p的父节点
            if ((p.parent = sp) != null) {
                // 如果s节点为sp的左节点，则将sp的左节点指向p，此时sp的的左节点s变成了p节点
                if (s == sp.left){
                    sp.left = p;
                }
                // 否则s节点为sp的右节点，则将sp的右节点指向p，此时sp的的右节点s变成了p节点
                else{
                    sp.right = p;
                }
                // 完成了p和s的交换位置
            }
            // s的右节点指向p的右节点
            if ((s.right = pr) != null)
                // 如果pr不为空，则将pr的父节点指向s，此时p的右节点变成了s的右节点
                pr.parent = s;
        }
        // 12.5 第二次调整：将第一次调整后独立出来的节点再次插入新构造出来的红黑树结构的对应位置，并且选出要替换掉 p 节点的 replacement
        // 12.5.1 将第一次调整后独立出来的节点再次插入新构造出来的红黑树结构的对应位置
        // 将p的左节点赋值为空，pl已经保存了该节点
        p.left = null;
        // 将p节点的右节点指向sr，如果sr不为空，则将sr的父节点指向p节点，此时s的右节点变成了p的右节点
        if ((p.right = sr) != null)
            sr.parent = p;
        // 将s节点的左节点赋值为pl，如果pl不为空，则将pl的父节点指向s节点，此时p的左节点变成了s的左节点
        if ((s.left = pl) != null)
            pl.parent = s;
        // 将s的父节点赋值为p的父节点pp
        // 如果pp为空，则p节点为root节点, 交换后s成为新的root节点
        if ((s.parent = pp) == null)
            root = s;
        // 如果p不为root节点, 并且p是pp的左节点，则将pp的左节点赋值为s节点
        else if (p == pp.left)
            pp.left = s;
        // 如果p不为root节点, 并且p是pp的右节点，则将pp的右节点赋值为s节点
        else
            pp.right = s;
        // 12.5.2 寻找replacement节点，用来替换掉p节点。removeTreeNode的规则就是取s和p交换位置前s的右子节点sr作为要用来替代p节点的replacement节点,如果sr节点为null，则直接将p删除即可
        // 12.5.2.1 如果sr不为空，则replacement节点为sr，因为s没有左节点，所以使用s的右节点来替换p的位置
        if (sr != null)
            replacement = sr;
        // 12.5.2.1 如果sr为空，则s为叶子节点，replacement为p本身，只需要将p节点直接去除即可
        else
            replacement = p;
    }
    // 13.承接12点的判断，如果p的左节点不为空，右节点为空，replacement节点为p的左节点，原理上面也讲过了，因为只有一颗子树，直接将子树的根节点替换到p的位置即可，不需要重新维护二叉搜索树结构
    else if (pl != null)
        replacement = pl;
    // 14.如果p的右节点不为空,左节点为空，replacement节点为p的右节点，原理同上
    else if (pr != null)
        replacement = pr;
    // 15.如果p的左右节点都为空, 即p为叶子节点, replacement节点为p节点本身，直接将p删除即可
    else
        replacement = p;
    // 16.第三次调整：使用replacement节点替换掉p节点的位置，将p节点移除
    // 16.1 如果p节点不是叶子节点（上面只有当p没有子树的时候，才会将replacement指向p），则将p删除后需要再将replacement节点替换到p的位置
    if (replacement != p) { 
        // 16.1.1 将p节点的父节点（此时p的父节点是已经交换完位置后p的父节点，也就是第三张图中的sp节点）赋值给replacement节点的父节点, 同时赋值给pp节点
        TreeNode<K,V> pp = replacement.parent = p.parent;
        // 16.1.2 如果p没有父节点, 即p为root节点，则将root节点赋值为replacement节点即可
        if (pp == null)
            root = replacement;
        // 16.1.3 如果p不是root节点, 并且p为pp（第三张图的sp节点）的左节点，则将pp的左节点赋值为替换节点replacement
        else if (p == pp.left)
            pp.left = replacement;
        // 16.1.4 如果p不是root节点, 并且p为pp的右节点，则将pp的右节点赋值为替换节点replacement
        else
            pp.right = replacement;
        // 16.1.5 p节点的位置已经被完整的替换为replacement, 将p节点清空, 以便垃圾收集器回收
        p.left = p.right = p.parent = null;
    }
    // 16.2 完成了p节点的删除并将替代节点放置到p的位置后，判断如果p节点不为红色，则进行红黑树删除平衡调整(如果删除的节点是红色则不会破坏红黑树的平衡无需调整，在红黑树的文章中讲过)
    TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
    // 16.3 如果p节点为叶子节点（即无子树）, 则简单的将p节点去除即可，无需做其他操作
    if (replacement == p) {
        TreeNode<K,V> pp = p.parent;
        // 16.3.1 将p的parent属性设置为空
        p.parent = null;
        if (pp != null) {
            // 16.3.2 如果p节点为父节点的左节点，则将父节点的左节点赋值为空
            if (p == pp.left)
                pp.left = null;
            // 16.3.3 如果p节点为父节点的右节点，则将父节点的右节点赋值为空
            else if (p == pp.right)
                pp.right = null;
        }
    }
    // 根据movable判断删除节点后是否要将红黑树根节点root放到数组桶中
    if (movable)
        // 18.将root节点移到数组桶中
        moveRootToFront(tab, r);   
    // --- 红黑树的处理end ---
}

 

6.1.3 为什么 sr 是 replacement 的首选，p 为备选？

首先我们看 sr 是什么？从代码中可以看到 sr 第一次被赋值时，是在 s 节点进行了向左穷遍历结束后，因此此时 s 节点是没有左节点的，sr 即为 s 节点的右节点。而从上面的第一次调整和第二次调整我们知道，p 节点已经跟 s 节点进行了位置调换，所以此时 sr 其实是 p 节点的右节点，并且 p 节点没有左节点，因此要移除 p 节点，只需要将 p 节点的右节点 sr 覆盖掉 p 节点即可，因此 sr 是 replacement 的首选，而如果 sr 为空，则代表 p 节点为叶子节点，此时将 p 节点直接移除即可。

6.2 balanceDeletion()

6.2.1 balanceDeletion()方法源码

红黑树的删除平衡调整，第一个输入参数是整棵红黑树的根节点，第二个输入参数是待删除节点或删除节点的替代节点。代码注释的标号对应着下一节流程讲解的步骤。

在removeTreeNode()方法中调用这个方法的时候已经完成了对节点的删除，并且已经将替代节点放到了删除节点的位置。传入的参数是已删除节点的替代节点，在方法中只需要做平衡处理即可。

/**
 * 红黑树的删除平衡调整
 * @param root 整棵红黑树的根节点
 * @param x 待删除节点或删除节点的替代节点，在removeTreeNode方法中调用时传入的就是replacement删除节点的代替节点
 * 
 * @return 返回重新平衡后的根节点
 */
static <K, V> TreeNode<K, V> balanceDeletion(TreeNode<K, V> root, TreeNode<K, V> x) {
    // x 当前要删除的节点
    // xp x节点的父节点
    // xpl xp节点的左节点
    // xpr xp节点的右节点
    TreeNode<K, V> xp, xpl, xpr;
    // 循环操作，平衡局部之后继续判断调整。注意，传进来的x节点子树的黑节点数，肯定是比x的兄弟节点子树的黑节点数少1
    for (; ; ) {
        // 前三个分支就是处理结束的返回条件
        // 如果x节点为空，或x节点是根节点  ①
        if (x == null || x == root) {
            // 直接返回根节点
            return root;
        // 当xp节点为空时，说明x为根节点（这个分支说明是循环后更新x后，使得x指向了root）。这个if分支也完成了对xp的赋值  ②
        } else if ((xp = x.parent) == null) {
            // 将x节点设置为黑色，并返回x节点
            x.red = false;
            return x;
        // 如果x不是root(有父节点)，且x为红色，直接把x变成黑色，让x子树的黑节点+1。多次循环可到达此分支  ③
        } else if (x.red) {
            // 将x的颜色设置为黑色
            x.red = false;
            return root;
        } 
        // 接下来两个分支，x必为黑色，只是区分x为左子节点还是右子节点  ④
        // 如果x是xp的左孩子。此分支也完成了对xpl的赋值
        else if ((xpl = xp.left) == x) {
            // 如果x节点为xpl节点
            if ((xpr = xp.right) != null && xpr.red) {
                // 如果xpr节点不为空，且xpr节点是红色的
                // 将xpr设置为黑色，xp设置为红色
                xpr.red = false;
                xp.red = true;
                // 左旋
                root = rotateLeft(root, xp);
                // 重新将xp节点指向x节点的父节点，并将xpr节点指向xp的右节点
                xpr = (xp = x.parent) == null ? null : xp.right;
            } // 如果xpl为黑色，则不会进入到上面的if分支中
            // 若xpr节点不存在，即x的兄弟为空
            if (xpr == null) {
                // 则将x节点指向xp节点向上调整，继续以x父节点调整平衡
                x = xp;
            } else {
                // sl xpr节点的左节点
                // sr xpr节点的右节点
                TreeNode<K, V> sl = xpr.left, sr = xpr.right;
                if ((sr == null || !sr.red) &&
                        (sl == null || !sl.red)) {
                    // 若sr节点为空或者sr节点是黑色的，且sl节点为空或者sl节点是黑色的
                    // 将xpr节点变成红色
                    xpr.red = true;
                    // 则将x节点指向xp节点向上调整
                    x = xp;
                } else {
                    // sr和sl中存在一个红节点
                    if (sr == null || !sr.red) {
                        // 此处说明sl是红节点,将sl节点设置为黑色
                        sl.red = false;
                        // 将xpr节点设置为红色
                        xpr.red = true;
                        // 右旋
                        root = rotateRight(root, xpr);
                        // 将xpr节点重新指向xp节点的右节点
                        xpr = (xp = x.parent) == null ? null : xp.right;
                    }
                    if (xpr != null) {
                        // 如果xpr节点不为空,让xpr节点与xp节点同色
                        xpr.red = (xp == null) ? false : xp.red;
                        // 当sr节点不为空，将其变成黑色
                        if ((sr = xpr.right) != null) {
                            sr.red = false;
                        }
                    }
                    // 存在xp节点
                    if (xp != null) {
                        // 将xp节点设置为黑色
                        xp.red = false;
                        // 进行左旋
                        root = rotateLeft(root, xp);
                    }
                    // 将x节点指向root进行下一次循环时跳出
                    x = root;
                }
            }
        }
        // 和上边分支的操作是对称的
        // 如果x是xp的右孩子。此分支也完成了对xpl的赋值
        else {
            // 当x节点是右节点  1.1
            if (xpl != null && xpl.red) {
                // 当xpl节点存在且为红色
                // 将xpl变为黑色，xp变为红色
                xpl.red = false;
                xp.red = true;
                // 右旋
                root = rotateRight(root, xpl);
                // 将xpl节点重新指向xp节点的左节点
                xpl = (xp = x.parent) == null ? null : xp.left;
            } // 如果xpl为黑色，则不会进入到上面的if分支中  1.2
            // 经过上面if，不管它有没有执行，x的兄弟xpl肯定为黑色节点了  2.1
            if (xpl == null) {
                // 如果xpl节点不存在，则xp节点没有子节点了
                // 将x节点指向xp节点向上调整
                x = xp;
            // 2.2
            } else {
                // sl xpl节点的左节点
                // sr xpl节点的右节点
                TreeNode<K, V> sl = xpl.left, sr = xpl.right;
                // 这种情况说明xpl的孩子里没有红色节点  2.2.1
                if ((sl == null || !sl.red) && (sr == null || !sr.red)) {
                    // 若sr节点为空或者sr节点是黑色的，且sl节点为空或者sl节点是黑色的
                    // 将xpl节点变成红色
                    xpl.red = true;
                    // 则将x节点指向xp节点向上调整
                    x = xp;
                // 这种情况说明xpl的孩子里有红色节点  2.2.2
                } else {
                   // 如果sr为红色，则走此分支；sr其他情况则不会  2.2.2.1.1和2.2.2.2.1
                    if (sl == null || !sl.red) {
                        // 此处说明sr是红节点,将sr节点设置为黑色
                        sr.red = false;
                        // 将xpr节点设置为红色
                        xpl.red = true;
                        // 左旋
                        root = rotateLeft(root, xpl);
                        // 将xpl节点重新指向xp节点的左节点
                        xpl = (xp = x.parent) == null ? null : xp.left;
                    }
                    // 如果xpl节点存在  2.2.2.1.2和2.2.2.2.2
                    if (xpl != null) {
                        // xpl最终会旋转到之前xp的位置，并保持xp的颜色
                        xpl.red = (xp == null) ? false : xp.red;
                        // 如果sl节点存在
                        if ((sl = xpl.left) != null) {
                            //将sl节点变为黑色
                            sl.red = false;
                        }
                    }
                    // 如果xp节点存在    2.2.2.1.3和2.2.2.2.3
                    if (xp != null) {
                        // 将xp节点设置为黑色
                        xp.red = false;
                        // 右旋
                        root = rotateRight(root, xp);
                    }
                    // 将x节点指向root进行下一次循环时跳出
                    x = root;
                }
            }
        }
    }
}
 

6.2.2 balanceDeletion()方法流程详解

提前说明一下，当说到“x节点子树的黑节点数n”是指：从x节点到它的子树的任意一个叶子节点的路径上的黑色节点个数都等于n。

整个函数是一个循环过程，可能会经过若干次循环。不管是刚调用此函数的第一次循环，或者是以后的循环，每次循环体刚开始时，x节点子树的黑节点数，肯定是比x的兄弟节点子树的黑节点数少1，这是由removeTreeNode函数来做保证的（在removeTreeNode中调用balanceDeletion方法时，如果删除的是红色节点是不需要调用balanceDeletion来做平衡处理的，只有删除黑色节点才需要，因为只有删除黑色节点才会导致左右的黑色节点树不一致。所以由于删掉了一个黑色节点，所以替代节点x的黑节点数少1）。既然知道了x的黑节点数，比x的兄弟节点的黑节点数少1，那么就需要通过调整来维持红黑树平衡。

①-③分支都是方法的结束返回条件:

①

if (x == null || x == root)分支，如果x是root，则直接返回root。上一次循环执行了x = root后，会进入此分支。此分支是balanceDeletion()方法的结束条件。

②

else if ((xp = x.parent) == null)分支，x的父节点xp为null，但xp为null说明x为root，但这样的话则只会进入上面的if (x == null || x == root)分支了，所以我认为此分支不可能进入。此分支是balanceDeletion()方法的结束条件。

③

else if (x.red)分支，说明x不是root节点，且x为红色。这好办，直接把x变成黑色，让x的黑节点数+1。这样x的黑节点数就和x的兄弟节点的黑节点数一样了，也就到达了平衡。此分支是balanceDeletion()方法的结束条件。

④

接下来的两个分支，说明x不是root节点，且x为黑色，所以调整过程要稍微复杂一点了。但这两个分支是完全对称的，一个是x节点为其父节点的左节点，一个是x节点为其父节点的右节点。这里只讲解else if ((xpl = xp.left) == x)的else分支。

接下来这个大图是整个函数的else if ((xpl = xp.left) == x)的else分支的所有过程，每个过程都有标号以方便讲解。节点除标明为黑色或者红色外，灰色则代表不清楚此节点的颜色。建议读者对照着大图、源码和本博客同时进行查阅。

下面全部是进入到else if ((xpl = xp.left) == x)的else分支的流程，会对内部的每一个分支进行讲解。进入到这个分支时，x一定是xp的右孩子，并且x一定是黑色。

1.1

if (xpl != null && xpl.red) {
    xpl.red = false;
    xp.red = true;
    root = rotateRight(root, xp);
    xpl = (xp = x.parent) == null ? null : xp.left;
}

if (xpl != null && xpl.red)这个分支可能执行，可能不执行。

如果xpl为红色，那么则会进入此if (xpl != null && xpl.red)分支，如下图所示。如果xpl为红色，那么xp和xpl的孩子的颜色都必为黑色节点。而之前说过，刚开始时x的黑节点数，比x的兄弟节点的黑节点数少1，我们假设x的黑节点数为n，那么xpl作为它的兄弟节点，xpl的黑节点数则为n+1，由于xpl是红色的不属于黑色节点，那么可推理出xpl的两个孩子的黑节点数也为n+1。

xpl.red = false;
xp.red = true;

将xpl置为黑色，xp置为红色。这是xpl和x的黑色节点数差1，就需要将x那一侧的增加一个黑色节点，所以将xpl和xp交换颜色，然后对xp右旋，这样就可以把黑色的xpl移到上一层去

root = rotateRight(root, xp);

进行右旋，将xpl移到了上一层，完成了一层的平衡，现在就差x那一层的黑色节点数还没左右一致，步骤1的操作就算是完成了，对x这一层的平衡会在步骤2中进行。

xpl = (xp = x.parent) == null ? null : xp.left;

根据xp的父节点是否为null，来更新xpl的指向

总结：

如果xpl为红色，且执行完if (xpl != null && xpl.red)分支后，如上图所示。调整后，x的兄弟节点变成了一个黑色节点。对比（1）和（4）发现，通过旋转操作后，使得x和一个黑节点数为n+1的黑色节点成为了兄弟。

1.2

如果xpl为黑色，那么则不会进入此if (xpl != null && xpl.red)分支，如下图所示。xpl的黑节点数为n+1，比x多1。

这种情况的最终结果就是这样：

对比1.1（xpl为红色）和1.2（xpl为黑色）两种情况：

对比xpl为红色和xpl为黑色的两种情况的最终结果，如下图所示，可以发现两种情况最终结果的共同点是：x的兄弟节点必为黑色，但此时兄弟节点的黑节点数多1，所以还需要调整。而两种情况的差异点是：xp的颜色。这也是后面要执行xpl.red = (xp == null) ? false : xp.red（把xp的颜色赋给xpl）的原因。

2.1

if (xpl == null)
    x = xp;

如果xpl为null，那么则不会进入此if (xpl != null && xpl.red)分支，会进入到这个if (xpl == null)分支，如下图所示。但是xpl为null的情况应该是不可能存在的，因为初始状态xp的左孩子的黑节点必须比右孩子的黑节点多1才可以，下面这种情况并不符合，所以这种情况不可能出现。

2.2

else {
    TreeNode<K,V> sl = xpl.left, sr = xpl.right;
    if ((sl == null || !sl.red) &&
        (sr == null || !sr.red)) {
        xpl.red = true;
        x = xp;
    }
    else {
        if (sl == null || !sl.red) {
            if (sr != null)
                sr.red = false;
            xpl.red = true;
            root = rotateLeft(root, xpl);
            xpl = (xp = x.parent) == null ?
                null : xp.left;
        }
        if (xpl != null) {
            xpl.red = (xp == null) ? false : xp.red;
            if ((sl = xpl.left) != null)
                sl.red = false;
        }
        if (xp != null) {
            xp.red = false;
            root = rotateRight(root, xp);
        }
        x = root;
    }
}

接下来讲解if (xpl == null)的else分支里的逻辑（根据上一条分析，所以是认为不可能进入if (xpl == null)分支的），在大图中是虚线以下的过程。

虚线下的过程，只能操作到x节点，xp节点（x的父节点），xpl节点（x的兄弟节点），sl节点（x的兄弟节点的左孩子）和sr节点（x的兄弟节点的右孩子），即只能操作这上下三层节点。这也是为什么虚线上的过程最后总会调整为xpl节点为黑色节点的情况，因为这样的话，xpl节点的两个孩子sl和sr的黑节点数就为n，而x节点本身的黑节点数也为n。只有找到了黑节点数都为n的节点们后，才方便进行调整，那之后就根据各种情况来再平衡就好了。

if (xpl == null)的else分支的初始状态如下图（注意，此初始状态是从过程( 4 )而来的，所以虚线下的过程都是过程( 4 )接下来的过程。这里就不再画出从过程( 6 )而来的初始状态了）。由于xpl的黑节点数为n+1，则它自身为黑色，所以推理出，它的左右孩子的黑节点则为n。

很有必要说明一下if ((sl == null || !sl.red) && (sr == null || !sr.red))分支和它的else分支的各种情况，如下图所示，它的else分支里，sl和sr中必有一个节点是红色的。而且在else分支里，当sr为红色时，必然还会进入if (sl == null || !sl.red)子分支。

2.2.1

if ((sl == null || !sl.red) &&
        (sr == null || !sr.red)) {
    xpl.red = true;
    x = xp;
}

如果进入了if ((sl == null || !sl.red) && (sr == null || !sr.red))分支，如下图所示。那么说明“sl为null或sl为黑色”和“sr为null或sr为黑色”这两件事都必须同时成立，如图过程( 8 )。这个时候，x的兄弟节点的两个孩子都是黑色节点，这样的话根本没有操作空间使得x和x的兄弟节点平衡（但凡x的兄弟节点的两个孩子有一个红色节点，也不至于这样）。

所以在if ((sl == null || !sl.red) && (sr == null || !sr.red))分支内，将xpl设为红色，这样xpl和它的兄弟节点平衡了（黑节点数一样），但由于这里是通过让xpl的黑节点数少1来使得平衡的，且xp的颜色我们又没有变过（这里考虑了虚线上的两种情况的差异点，即xp刚开始的颜色可能是红色，也可能是黑色），所以不管xp的初始颜色是什么，xp必然比xp的兄弟节点的黑节点数少1，所以还是不平衡的，就将x指向xp，然后继续循环。如果xp初始为黑色，那么xp的黑节点数为n+1，xp的兄弟节点的黑节点数为n+2。如果xp初始为红色，就如过程（9）所示，xp的黑色节点数为n，xp的兄弟节点的黑色节点数为n+1。

下图即为该分支的转化过程，xpl设置为红色，并且将x指向xp

2.2.2

else {
    if (sl == null || !sl.red) {
        if (sr != null)
            sr.red = false;
        xpl.red = true;
        root = rotateLeft(root, xpl);
        xpl = (xp = x.parent) == null ?
            null : xp.left;
    }
    if (xpl != null) {
        xpl.red = (xp == null) ? false : xp.red;
        if ((sl = xpl.left) != null)
            sl.red = false;
    }
    if (xp != null) {
        xp.red = false;
        root = rotateRight(root, xp);
    }
    x = root;
}
 

如果进入了if ((sl == null || !sl.red) && (sr == null || !sr.red))的else分支，如下图所示。那么说明“sl为null或sl为黑色”和“sr为null或sr为黑色”这两件事不会同时都成立。观察逻辑可以发现，else分支里可以分为两种情况：

1. 如果sl为黑色，那么sr为红色。即(sl == null || !sl.red) 成立，(sr == null || !sr.red)不成立，如图（10）
2. 如果sl为红色，此时不管sr的颜色是什么都会进入else分支。即(sl == null || !sl.red)不成立，如图（17）

其实这两种情况的共同点就是sr和sl中至少有一个是红色节点。

2.2.2.1  情况一

情况一是“sl为黑色，sr为红色”，这种情况(sl == null || !sl.red) 成立，(sr == null || !sr.red)不成立，对应上面说的第一种情况。

如下图所示，为这种情况的开始过程和结束过程。发现过程( 16 )时，整个树已经平衡了，结束后会将x指向root（x = root），下次循环就会直接退出了。且过程( 10 ) 里xp这个位置，对应到过程( 16 )里则变成了xpl这个节点，且过程( 10 )里xp的颜色还可能为黑色，那么过程( 16 )的xpl会和过程( 10 )里xp的颜色一致（虚线下的三行过程都保证了这一点）。这是通过将xp的颜色赋给xpl（xpl.red = (xp == null) ? false : xp.red），再右旋xp（rotateRight(root, xp)）来保证的，这样，就把虚线上的差异点考虑在内了。

下面是这个情况的具体执行过程

2.2.2.1.1

if (sl == null || !sl.red) {
    if (sr != null)
        sr.red = false;
    xpl.red = true;
    root = rotateLeft(root, xpl);
    xpl = (xp = x.parent) == null ? null : xp.left;
}

“sl为黑色，sr为红色”，这种情况会进入到if (sl == null || !sl.red) 分支。

开始状态

if (sr != null)
    sr.red = false;
xpl.red = true;
root = rotateLeft(root, xpl);

将sr置为黑色，xpl置为红色，将xpl左旋

左旋之后的结果

xpl = (xp = x.parent) == null ? null : xp.left;

根据x的父节点xp是否为null来更新xpl的指向，如果xp不为null，则将xpl指向xp的左子节点

2.2.2.1.2

if (xpl != null) {
    xpl.red = (xp == null) ? false : xp.red;
    if ((sl = xpl.left) != null)
        sl.red = false;
}

 进入到if (xpl != null)分支，如果xp不为空，则将xpl的颜色设置为和xp的颜色一样，然后在if ((sl = xpl.left) != null)判断中更新sl的指向，以前sl指向的是旧的xpl的左子节点，经过步骤（13）xpl的位置更新了，所以需要重新更新sl的位置，然后如果sl不为null，则将sl节点染成黑色

2.2.2.1.3

if (xp != null) {
    xp.red = false;
    root = rotateRight(root, xp);
}

进入到if (xp != null)分支，如果xp不为null，则将xp置为黑色，然后将xp进行右旋

这是情况一经过处理之后的结果

 最后x = root;结束处理，这样在下一轮循环时就会直接返回。

2.2.2.2  情况二

情况二是“sl为红色”，这种情况(sl == null || !sl.red) 不成立，对应上面说的第二种情况。

如下图所示，为这种情况的开始过程和结束过程。发现过程( 20 )时，整个树已经平衡了，结束后会将x指向root（x = root），下次循环就会直接退出了。同样的，过程( 17 )里xp这个位置对应过过程( 20 )里会保持相同位置的节点颜色一致。

下面是这个情况的具体执行过程

2.2.2.2.1

if (sl == null || !sl.red) {
    if (sr != null)
        sr.red = false;
    xpl.red = true;
    root = rotateLeft(root, xpl);
    xpl = (xp = x.parent) == null ? null : xp.left;
}

因为这种情况sl为红色，所以不可能进入到这个if分支

开始状态

 2.2.2.2.2

if (xpl != null) {
    xpl.red = (xp == null) ? false : xp.red;
    if ((sl = xpl.left) != null)
        sl.red = false;
}

进入到if (xpl != null)分支，如果xp不为空，则将xpl的颜色设置为和xp的颜色一样，然后在if ((sl = xpl.left) != null)判断中更新sl的指向，但是因为这种情况并没有进入if (sl == null || !sl.red) 分支，所以xpl的位置并没有改变，最后如果sl不为null，则将sl节点染成黑色

 2.2.2.2.3

if (xp != null) {
    xp.red = false;
    root = rotateRight(root, xp);
}

进入到if (xp != null)分支，如果xp不为null，则将xp置为黑色，然后将xp进行右旋

 这是情况二经过处理之后的结果

最后x = root;结束处理，这样在下一轮循环时就会直接返回。

2.2.2.3 情况一和情况二对比

虚线下的第二行过程（过程( 10 )到过程( 16 )）和第三行过程（过程( 17 )到过程( 20 )），除了开始过程和结束过程外，中间过程里图中只给那些调整过程中黑节点数不变的节点标注出来了黑节点数，其他没有标注出来的节点只需要在结束过程里进行确认就好了。

之所以虚线下的第二行过程和第三行过程要进行区分，是因为sr是否为红色，需要进行的调整操作是不一样的。比如过程过程( 10 )如果走的是第三行过程的流程，如下图所示，最终会造成sl和xp这两个兄弟节点不是平衡的。

6.2.2 总结

• 和balanceInsertion一样，此balanceDeletion方法同样只处理三层树的结构。
• 每次循环体里，除非进入那些直接return的终点，那么循环体开始时，x节点总是比x节点的兄弟节点的黑节点数少1的。
• 虚线下的过程，其主要技巧（指的是虚线下第二行和第三行。第一行是先让自己和兄弟平衡，但却是通过不是让自己加1，而是让兄弟减1，所以还需要x往上移动，往更高层借红色节点）是通过借用颜色为红色的兄弟节点的左右孩子，只要有一个孩子是红色的，就可以借用。而借用其实就是，通过旋转操作把红色节点弄到自己的子树里，然后通过红色变黑色，让自己子树的黑节点数加1，从达到平衡。
• 大图中，到达虚线时的过程，x的兄弟节点总会是黑色的。根据前提“x节点总是比x节点的兄弟节点的黑节点数少1”，而兄弟节点又是黑色，可以推理出“x的兄弟节点的两个孩子的黑节点数，和x节点一样大”，找到了一样大的节点，之后才好处理。

  ---

    相关文章：【Java集合】HashMap系列（一）——底层数据结构分析
                    【Java集合】HashMap系列（二）——底层源码分析
                    【Java集合】一文快速了解HashMap底层原理
                    【数据结构】史上最好理解的红黑树讲解，让你彻底搞懂红黑树