聊聊java中的哪些Map：（二）HashMap中的TreeNo

[toc]
本文是上一篇聊聊java中的哪些Map：（一）HashMap(1.8)源码分析
中对于treeNode的补充。主要涉及各种红黑树操作。当然本文的重点还是在treeNode源码。

1 类结构及其成员变量

TreeNode则是hashMap树化之后，组成树的基本节点。需要注意的是，TreeNode继承了LiknedHashMap.Entry
，LinkedHashMap.Entry又继承了Node。这个地方确实比较绕。

/**
 * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
 * extends Node) so can be used as extension of either regular or
 * 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);
    }

    /**
     * Returns root of tree containing this node.
     */
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }

... ...
}

其他方法先不介绍，我们可以看到，这个类中，由于是一颗红黑树，因此添加了parent、left、right、prev指针。
我们再看看其父类：

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

其父类扩展了 before、after指针。而在链表中使用的是next指针。
其结构如下图：

image.png

TreeNode类也是HashMap中最核心的类。从链表变成红黑树，从红黑树转成链表，以及旋转等，都是在这个类中实现。

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

变量	类型	说明
hash	int	用于存储Node节点本身的hashcode
key	泛型K	传入的Key
value	泛型V	传入的value
next	Node<K,V>	组成链表的指针，指向下一个节点
before	Entry<K,V>	组成LinkedHashMap链表的指针，指向前一个
after	Entry<K,V>	组成LinkedHashMap链表的指针，指向后一个
parent	TreeNode<K,V>	组成红黑树的指针，指向父节点
left	TreeNode<K,V>	组成红黑树的指针，指向左子节点
right	TreeNode<K,V>	组成红黑树的指针，指向右子节点
prev	TreeNode<K,V>	组成红黑树的指针，指向上一个节点
red	boolean	标记红黑树是否为红，true表示红，false表示黑

由此可见，在前文的注释中说到，HashMap中的TreeNode的大小大约是Node节点的二倍，由此我们不难看出，TreeNode中增加了很多属性，这会造成TreeNode的空间开销要比Node大很多。因此不是一上来就转换为红黑树。而是需要链表的长度大于8而且size大于64。

2 构造方法

TreeNode的构造方法最终是调用其父类的构造方法。

TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
}
    
Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
}

Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
}

最终还是使用的是Node中的构造方法。这个构造方法只是将key、value、next以及hash进行了赋值。

3 重要的方法

TreeNode由于涉及到红黑树的旋转、和链表的转换等各种操作，因此存在许多非常重要的方法，下面逐一介绍。

3.1 root

该方法的目的是从任一当前节点，找到红黑树的root。

/**
     * Returns root of tree containing this node.
     */
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }

实际上这个实现非常简单，就是根据parent指针进行判断，如果有节点parent为null，则即是root节点。反之则继续遍历。

3.2 moveRootToFront

这个方法是确保红黑树的根节点是table种引用的哪个节点。这是因为红黑树在增加元素的过程种，会由于转等操作而造成root节点的更换。当root节点发生改变的时候，应该将table种对应槽位的指针指向这个root节点。

 /**
 * Ensures that the given root is the first node of its bin.
 */
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
    int n;
    if (root != null && tab != null && (n = tab.length) > 0) {
        //找到当前节点hash之后对应的table中的索引位置，注意这个方法
        int index = (n - 1) & root.hash;
        //将table[index]对应的节点记录为first
        TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
        //根据first和root是否相等来判断root是否在数组上，如果不在则执行如下逻辑：
        if (root != first) {
            Node<K,V> rn;
            //将table中的位置指向root
            tab[index] = root;
            //rp为root指向的前一个节点
            TreeNode<K,V> rp = root.prev;
            //将root的前后节点关联
            if ((rn = root.next) != null)
                ((TreeNode<K,V>)rn).prev = rp;
            if (rp != null)
                rp.next = rn;
            //first的前一个节点为root
            if (first != null)
                first.prev = root;
            root.next = first;
            root.prev = null;
        }
        //对红黑树的一致性进行检查
        assert checkInvariants(root);
    }
}

需要注意的是，这个方法并没有修改红黑树，仅仅只是将table中对应位置的指针指向了这个节点。
在这个地方，我们需要注意的是index = (n - 1) & root.hash。这是一个快速根据hashcode计算当前table索引的方法。这个计算效率比通过取余数运算快很多。
当且仅当b=2^n的时候，如下公式成立：

//当b为2的n次幂的时候
a % b = a & ( b - 1 ) 

如下，在n=16的时候，计算189和205的余数。

image.png

这种计算方法的性能会大大高于%。

3.3 checkInvariants

既然在上个方法中提到了checkInvariants，那么我们来看看checkInvariants的源代码：

/**
 * 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;
}

此方法的目的在于对整颗红黑树的一致性进行检查，目前仅在检查root节点是否在table上的时候进行调用，用以保证红黑树的特性以及节点指向的正确性。

3.4 find

从当前节点开始，使用给定的hash和key查找对应的节点，只会对以当前节点为根的节点进行判断。红黑树对左右子树进行递归遍历，直到key相等。

/**
 * Finds the node starting at root p with the given hash and key.
 * The kc argument caches comparableClassFor(key) upon first use
 * comparing keys.
 */
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this;
    do {
        int ph, dir; K pk;
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        // ph为p的hash值，如果查找节点的哈希值小于ph，则搜索左子树
        if ((ph = p.hash) > h)
            p = pl;
        //反之，查找节点的hash值大于ph则搜索右子树
        else if (ph < h)
            p = pr;
        //如果hash相等同时key相等则说明要找的节点就是p
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        //如果hash值相等key不等则寻找左右非空的一侧
        else if (pl == null)
            p = pr;
        else if (pr == null)
            p = pl;
        //左右两边都不为空，则判断kc是否为Comparable的实现类，即按key的值进行比较，k<pk则向左子树移动，否则向右子树移动
        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);
    //如果没有找到则返回null
    return null;
}

这是树化之后的TreeNode的搜索过程。

3.5 tieBreakOrder

这个方法的目的是在于比较两个对象的大小，返回值只能大于0或者小于0。

/**
 * Tie-breaking utility for ordering insertions when equal
 * hashCodes and non-comparable. We don't require a total
 * order, just a consistent insertion rule to maintain
 * equivalence across rebalancings. Tie-breaking further than
 * necessary simplifies testing a bit.
 */
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;
}

首先根据compareTo方法进行比较，如果相等则通过System.identityHashCode方法，如果还是相等则返回-1。否则返回1。

3.6 treeify

遍历整个链表，将链表变成红黑树。

/**
 * Forms tree of the nodes linked from this node.
 */
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    //定义树的根节点
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        //next为指向下一个节点的指针
        //x为当前的TreeNode节点
        next = (TreeNode<K,V>)x.next;
        //在使用之前将当前节点左右都置空
        x.left = x.right = null;
        //判断root是否赋值，如果没有则将root指向x，并改为黑色节点，修改其parent为null
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
        //此时root不为空，说明非第一次操作，则将x节点添加到root之后的树下面
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            //需要x节点的key和哈希值用于比较
            for (TreeNode<K,V> p = root;;) {
               //定义p指向root
                int dir, ph;
                K pk = p.key;
                //先判断p的hash值与x比较，类似于比较器得到一个结果为 -1 或者1
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                //如果hash相等则通过比较器比较，比较值、字符串等
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);
                    //如果还得不到结果，调用上面的tieBreakOrder比较方法
                TreeNode<K,V> xp = p;
                //dir是比较的结果，根据dir的值判断对左右子树分别进行处理，如果左右为空则直接插入，反之则遍历对应的子树，此时在for循环内，这个操作会持续到为null
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    //插入之后，再调用balanceInsertion 以确保红黑树的特性
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    //上述操作可能会由于红黑树的转置而root节点发生变化，调用这个方法将root节点放在table中
    moveRootToFront(tab, root);
}

需要注意的是，这个树化操作中全部是对TreeNde节点的操作，一个HashMap最开始的节点为Node而不是TreeNode，究竟是何时将Node对象变成了TreeNode，还是说，一开始创建的时候就是TreeNode对象，这个代码中还没看出来。我们继续看后面的代码。

3.7 untreeify

这个方法是将树化的红黑树转换为链表的操作。

/**
 * Returns a list of non-TreeNodes replacing those linked from
 * this node.
 */
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) {
        //q表示当前的TreeNode节点，p则表示将q转换为Node的节点，顺着q原有的next指针遍历
        Node<K,V> p = map.replacementNode(q, null);
        //当tl为空的时候，将hd指向p，那么hd实际上就是根节点。
        if (tl == null)
            hd = p;
        else
            tl.next = p;
        //tl指向p用于链表操作，只有第一次的时候tl为null
        tl = p;
    }
    return hd;
}

// For conversion from TreeNodes to plain nodes
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
    //将TreeNode重新替换为Node
    return new Node<>(p.hash, p.key, p.value, next);
}

将TreeNode变成链表的过程实际上是利用了之前的next指针，再链表树化的过程中可以肯定的是原有的next指针继续有效。因为TreeNode前面学过，其构造函数也是需要传入next指针的。
这样可以理解为，实际上将树变成链表非常简单，因为next指针已经存在，现在只需要将TreeNode替换为Node之后，重新将next指针建立好即可。
这个循环中的链表指针修改算法非常巧妙，tl是上一次循环的p，那么再当次循环中，将上次的next指针指向了当前的节点，因为每次都需要重建Node节点。这个将上次节点暂存的方法也是我们在刷leetcode的时候值得借鉴的地方。

3.8 putTreeVal

将K、V插入到红黑树中。
首先要根据当前的key在红黑树上寻址，看能否找到对应的节点，如果应该插入的节点为空，则插入，之后重新平衡红黑树。

/**
 * Tree version of putVal.
 */
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的parent指针不为空则调用root)()方法找到根节点。
    TreeNode<K,V> root = (parent != null) ? root() : this;
    //循环遍历
    for (TreeNode<K,V> p = root;;) {
        int dir, ph; K pk;
        //p首先指向root，之后和h判断，确定要插入左子树还是右子树。
        if ((ph = p.hash) > h)
            dir = -1;
        else if (ph < h)
            dir = 1;
        //如果k与当前的节点相等 则返回当前节点跳出循环
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        //如果不等则通过compare方法
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            //设置一个searched标识，这样只用搜索一次，以p为根进行搜索。
            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;
                //平衡红黑树并重新移动root节点
                moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

该方法实际上是将K和V插入红黑树中。判断该插入的位置是否为空，是否应该插入，如果插入之后还需要重新平衡和重置root节点。

3.9 removeTreeNode

将当前节点从红黑树上移除。这个操作比普通的红黑树操作更加复杂，因为还需要考虑当size下降到6的时候将红黑树转为链表。

/**
 * Removes the given node, that must be present before this call.
 * This is messier than typical red-black deletion code because we
 * cannot swap the contents of an interior node with a leaf
 * successor that is pinned by "next" pointers that are accessible
 * independently during traversal. So instead we swap the tree
 * linkages. If the current tree appears to have too few nodes,
 * the bin is converted back to a plain bin. (The test triggers
 * somewhere between 2 and 6 nodes, depending on tree structure).
 */
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                          boolean movable) {
    int n;
   //判断非空
    if (tab == null || (n = tab.length) == 0)
        return;
    //计算当前节点对应的table中的index
    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;
    //succ指向后一个节点，pred指向前一个节点，如果pred为空则说明当前节点为根节点，将succ的位置放置到tab中
    if (pred == null)
        tab[index] = first = succ;
    else
        //反之则pred的下一个节点为succ
        pred.next = succ;
    if (succ != null)
        succ.prev = pred;
    if (first == null)
        return;
    //计算root节点
    if (root.parent != null)
        root = root.root();
    if (root == null
        || (movable
            && (root.right == null
                || (rl = root.left) == null
                || rl.left == null))) {
        tab[index] = first.untreeify(map);  // too small
        //根据红黑树的特点，当根节点中的左右子树存在一个为空的情况则说明size比较少，转换为链表。
        return;
    }
    //以上情况都是对可能是链表的情况进行修正，以下则是对应该是树的情况进行修正
    TreeNode<K,V> p = this, pl = left, pr = right, replacement;
     //如果删除的节点对应的左右都不为空则对应红黑树的4种情况进行处理
    if (pl != null && pr != null) {
        TreeNode<K,V> s = pr, sl;
        while ((sl = s.left) != null) // find successor
         //s指向后继节点
            s = sl;
         //交换后继节点和删除节点的颜色，之后在后继节点上操作
        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;
        //改变节点的指向 交换值
        if (s == pr) { // p was s's direct parent
            p.parent = s;
            s.right = p;
        }
        else {
            TreeNode<K,V> sp = s.parent;
            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.left = null;
        //调整p和s交换之后的指向关系
        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;
    }

    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;
        }
    }
    //调整root使其在数组上
    if (movable)
        moveRootToFront(tab, r);
}

3.10 split

拆分操作，随着元素的插入，hashMap还会扩容，由于扩容，将原有的节点对应的红黑树就会被分成高低位俩部分。因为每次扩容都是向上位移。这个后面会在resize方法里面具体讲解。由于每次都是通过取模计算出来的index位置。因此当table扩大一倍之后，原有的节点的元素肯定会分成俩部分。

/**
 * 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;
    //按next链表顺序遍历节点 将节点分为高低树
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        //这个区分高低位的方法非常有特点，后面详细讨论
        if ((e.hash & bit) == 0) {
         //低位处理 添加到低位的链表上
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
         //高位处理 添加到高位的链表上
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }
    //低位树处理，判断是否触发了非树化阈值
    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);
        }
    }
    //高位数处理 同样要判断是否触发了非树化阈值
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            //链表处理
            tab[index + bit] = hiHead.untreeify(map);
        else {
            //树化处理
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

上面提到了这个地方对整个map中每个槽位的元素进行resize之后，会拆分为两部分，一部分为低位树，一部分为高位树。
我们知道，hashmap扩容是采用位运算来实现的。直接向左移动1位。那么扩容之后，分成的两部分，低位还是原来的索引位置index，高位则是原来的索引位置加上原来的长度index+size。
这个区分高低位的算法非常巧妙：

if ((e.hash & bit) == 0)

这里bit是原有的size大小。
我们用之前的例子进行说明，扩容之后为32 n=31计算如下：

image.png

我们可以看出，实际上就是在原来的基础上增加了1位，所以高位的索引位置很容易就得出了是13+16=29。之后，这两个数字就是在增加的这位上的反应不一样导致会分配到不同的索引。因此实际上我们只用关注这个新增加的位即可：
size位16：

image.png

新增加的位和全部数据计算之后要么为0，要么不为0，等于16。考虑到代码的通用性，实际上不管怎么扩容，只要为0就说明保持低位不变。否则就将该节点放到高位。
看完整个过程，忽然明白hashMap为什么初始大小为16。因为只要为16，这个两个位移计算就非常方便。这使得hashMap就很高效。

3.11 rotateRight

右旋操作。与左旋操作一样，在balanceInsertion方法中被调用。其目的是为了保证红黑树的特征。

static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                       TreeNode<K,V> p) {
    TreeNode<K,V> l, pp, lr;
    //p为当前需要旋转的节点，其不能为空，l为其左子节点
    if (p != null && (l = p.left) != null) {
    p的左子节点变为l的右子节点，lr指向这个节点，如果不为空则将这个节点的父节点改为p
        if ((lr = p.left = l.right) != null)
            lr.parent = p;
        //p的父节点变为l的父节点，pp指向这个节点，如果不为空，r改为black
        if ((pp = l.parent = p.parent) == null)
            (root = l).red = false;
        else if (pp.right == p)
            pp.right = l;
        else
            pp.left = l;
        //p的父节点和l左子节点重新赋值
        l.right = p;
        p.parent = l;
    }
    return root;
}

可能根据代码无法理解是如何旋转的，我们从下图来看整个旋转过程。
以E为顶点开始旋转：

image.png

第一步，将M的left指向E的right

image.png

第二步，将E的right指向M

image.png

操作完之后就完成了红黑树的右旋：

image.png

。

3.12 rotateLeft

左旋操作。与右旋操作类似。是右旋操作的逆向过程。

// Red-black tree methods, all adapted from CLR

static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                      TreeNode<K,V> p) {
    TreeNode<K,V> r, pp, rl;
    //p为当前需要旋转的节点，其不能为空，r为其右子节点
    if (p != null && (r = p.right) != null) {
        r的左子节点变为p的右子节点，rl指向这个节点，如果不为空则将这个节点的父节点改为p
        if ((rl = p.right = r.left) != null)
            rl.parent = p;
        //p的父节点变为r的父节点，pp指向这个节点，如果不为空，r改为black
        if ((pp = r.parent = p.parent) == null)
            (root = r).red = false;
        //反之p为pp的左子节点的话，将r改为pp的左子节点
        else if (pp.left == p)
            pp.left = r;
        else
            pp.right = r;
        //r的父节点和左子节点重新赋值
        r.left = p;
        p.parent = r;
    }
    返回root
    return root;
}

上述过程是右旋的一个逆过程。

3.13 balanceInsertion

在插入新节点之后进行平衡检查，x为插入的新节点，返回root节点。

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                            TreeNode<K,V> x) {
    //插入节点默认为红色                     
    x.red = true;
    //遍历之后对红黑树进行调整
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
        //如果其父节点为空，则说明其为根，直接改为黑色返回
        if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
        //父节点为黑色或者x的祖父节点为空则符合红黑树为红的第二种情况，直接返回
        else if (!xp.red || (xpp = xp.parent) == null)
            return root;
        //如下情况都为红
        //x的父节点为x祖父节点的左儿子，插入情况下三四种情况需要区分左还是右
        if (xp == (xppl = xpp.left)) {
            if ((xppr = xpp.right) != null && xppr.red) {
                // x的叔叔修改为黑色
                xppr.red = false;
                 // x的父节点修改为黑色
                xp.red = false;
                 // x的祖父节点修改为红色
                xpp.red = true;
                //x指向x的祖父节点，以祖父节点循环继续向上调整
                x = xpp;
            }
            else {
            // x的叔叔是黑色且x是右儿子，相当于在树的“内部”                    //符合插入节点第四种情况的第一种状态
                if (x == xp.right) {
                // 以x父节点进行左旋
                    root = rotateLeft(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                // 这里处理第二种状态，相当于在树的“外部”
                if (xp != null) {
                    xp.red = false;
                    if (xpp != null) {
                        xpp.red = true;
                        root = rotateRight(root, xpp);
                    }
                }
            }
        }
        // x的父节点为x祖父节点的右儿子
            // 下面跟上边类似，对称关系
        else {
         
            if (xppl != null && xppl.red) {
                xppl.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            else {
                if (x == xp.left) {
                //// 以x父节点进行右旋
                    root = rotateRight(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                if (xp != null) {
                    xp.red = false; 
                    //x的父节点改为黑色，x的祖父节点改为红色后对x的祖父节点进行左旋转
                    if (xpp != null) {
                        xpp.red = true;
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}

以上即是在插入节点之后对红黑树的平衡操作。

3.14 balanceDeletion

同理，删除节点之后也会进行平衡操作。此时的x是是节点删除之后的替换节点。

static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                           TreeNode<K,V> x) {
    // 循环操作
    for (TreeNode<K,V> xp, xpl, xpr;;) {
    //如果此时x为空，则x指向root节点，直接返回
        if (x == null || x == root)
            return root;
        // 删除后x父节点为空，说明x为根节点，x置为黑色，红黑树平衡
        // 参考红黑树删除文章中的3种情况中的第一种情况，整棵树的根节点需要将根节点置黑
        else if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
        else if (x.red) {
            x.red = false;
            return root;
        }
        // 区分x为左子节点还是右子节点
        else if ((xpl = xp.left) == x) {
            if ((xpr = xp.right) != null && xpr.red) {
                xpr.red = false;
                xp.red = true;
                root = rotateLeft(root, xp);
                xpr = (xp = x.parent) == null ? null : xp.right;
            }
            if (xpr == null)
                x = xp;
            else {
                TreeNode<K,V> sl = xpr.left, sr = xpr.right;
                if ((sr == null || !sr.red) &&
                    (sl == null || !sl.red)) {
                    xpr.red = true;
                    x = xp;
                }
                else {
                    if (sr == null || !sr.red) {
                        if (sl != null)
                            sl.red = false;
                        xpr.red = true;
                        root = rotateRight(root, xpr);
                        xpr = (xp = x.parent) == null ?
                            null : xp.right;
                    }
                    if (xpr != null) {
                        xpr.red = (xp == null) ? false : xp.red;
                        if ((sr = xpr.right) != null)
                            sr.red = false;
                    }
                    if (xp != null) {
                        xp.red = false;
                        root = rotateLeft(root, xp);
                    }
                    x = root;
                }
            }
        }
        else { // symmetric
            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)
                x = xp;
            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;
                }
            }
        }
    }
}

上述大部分内容与插入后的平衡操作类似。都是一个对称操作。

4 总结

TreeNode是HashMap中的核心内部类，实现了HashMap从链表变成红黑树和从红黑树变成链表的所有操作。另外为了保持红黑树的特性，在插入、删除的的时候都会进行平衡检查。从而保持了红黑树的特性。
另外对于HashMap关于位运算的部分非常巧妙。通过&实现了位运算的索引、以及扩容后高低位区分操作。