JDK源码分析系列--HashMap.TreeNode

这篇可以看作是JDK源码分析系列—HashMap的下篇。java.util.HashMap.TreeNode是HashMap中非常重要的一个类，主要目的在于：当哈希冲突比较严重的时候，提升HashMap的查询效率。尽管实际用到的概率不高，却占了HashMap篇幅的1/4左右。因此在这写一篇单独分析。

红黑树

三种树对比

首先说二叉树，每个父节点都会最多生出两个子节点，其中，左子节点 < 父节点 < 右子节点，在最好的情况下，二叉树查询的时间复杂度是O(log n)，也就是树的层数。在最坏的情况下，即节点的添加顺序是严格递增或严格递减，那二叉树就会退化成链表，时间复杂度为O(n)。

为了解决二叉树偏向一边的情况，引入了平衡二叉树，要求从根节点到任意叶子节点的最短路径之差不大于1。这就保证了平衡二叉树的时间复杂度是O(log n)。但是这种状态是很难保持的，每次插入或移除一个节点，都可能导致性质被破坏，就需要通过自旋的方式来维持平衡。

为了高效的查询，同时不希望像平衡二叉树那样大的开销，于是引入了红黑树。红黑树是有红黑两种颜色的节点组成的二叉树，可以看做是一个不严格的平衡二叉树。

特点

红黑树包括五大特点：

每个节点要么是红色，要么是黑色；
根节点是黑色；
叶子节点是黑色；
红色节点的子节点必须是黑色；
从任意节点到任意叶子节点的最短路径上，走过的黑色节点数量都相同

在这样的规则约束下，从根节点到叶子节点的任意路径，节点数最少的情况是都为黑色节点，节点数最多的情况是每个黑色节点的子节点都为红色。由于根节点为黑色，所以后一种的节点数是前一种的两倍。

构造方法

TreeNode只有一个构造方法，内部最终调用的是HashMap.Node的构造方法，创建的是普通节点

1
2
3

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

成员变量

TreeNode

TreeNode新增五个成员变量

当前节点的父节点

1	TreeNode<K,V> parent;

当前节点的左子节点

1	TreeNode<K,V> left;

当前节点的右子节点

1	TreeNode<K,V> right;

当前节点的前驱节点

1	TreeNode<K,V> prev;

节点颜色，true红色，false黑色

1	boolean red;

Entry

从LinkedHashMap.Entry继承而来两个成员变量

当前节点的前一个节点

1	Entry<K,V> before;

当前节点的后一个节点

1	Entry<K,V> after;

Node

从HashMap.Node继承而来的四个成员变量

key的哈希值

1	final int hash;

key

1	final K key;

value

V value;

当前节点的后继节点

1	Node<K,V> next;

共有7个节点引用，分为三组：

prev，next一组，表示链表中的上下节点
before，after一组，表示插入顺序中的前后节点
parent，left，right一组，表示树中的父子节点

成员方法

TreeNode有15个成员方法，本文将按照HashMap的put，get，remove，resize的顺序来讲解

putTreeVal方法

在HashMap.putVal方法中，判断数组节点是TreeNode类型，则会调用putTreeVal方法，执行树节点的put逻辑

其中，调用方p是数组节点，this是当前hashMap对象，tab是节点数组，hash、key、value是新节点参数

1 2	if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

整体逻辑如下：

1.找到根节点。如果数组节点不是根节点，则沿着parent指针找到根节点

2.确定新节点在树中的位置，左边还是右边，或者节点已经存在

3.通过判断key的hash值，小于根节点则放在左子节点，大于根节点则放在右子节点

3.1如果hash值相同，而key又不同，则通过compareTo方法来判断大小

3.2如果通过compareTo无法判断大小，则通过find方法在子节点中找到相同的key

3.3如果还是找不到，则通过自定义的方式最终判断出大小

3.4如果判断是在左边，而左节点为null，则放到左子节点上

3.5如果判断是在右边，而右节点为null，则放到右子节点上

3.6如果子节点不为null，则将子节点作为父节点，继续判断，直到子节点为null

3.7由于find方法已执行过一遍（且没查到），所以后面循序不再执行find方法。

4.如果节点已存在，则直接返回

5.如果在左边，判断左子节点是否存在

5.1不存在，则直接放到左子节点，维护双向链表，调整树结构

5.2存在，则回到第二步，继续判断

6.右边同上

源码如下：

final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v) {
    // 表示k的类型
    Class<?> kc = null;
    // 控制只在第一次循环时调用find方法
    boolean searched = false;
    // 父节点为null，说明数组节点就是根节点；否则调用root方法来查找
    TreeNode<K,V> root = (parent != null) ? root() : this;
    
    // 循环只能从内部跳出；p指向根节点
    for (TreeNode<K,V> p = root;;) {
        // dir=-1表示放在左边，=1表示放在右边；p当前节点哈希值；p当前节点key
        int dir, ph; K pk;
        // 新节点哈希值小于当前节点哈希值，放在左边（不一定是左子节点）
        if ((ph = p.hash) > h)
            dir = -1;
        // 新节点哈希值大于当前节点哈希值，放在右边（不一定是右子节点）
        else if (ph < h)
            dir = 1;
        // 哈希值相等且key也相等，返回当前节点
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        // 哈希值相等但key不相等，需要通过别的方式判断出key的大小
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 // 如果k实现了Comparable，则通过compareTo方法来判断
                 (dir = compareComparables(kc, k, pk)) == 0) {
            // 如果没实现Comparable或者compareTo方法判断不了大小
            if (!searched) { // 第一次循环会进入这里
                TreeNode<K,V> q, ch;
                // 后面循序不需要再进
                searched = true;
                // 左子节点不为null，尝试从左边找到相同的key
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    // 右子节点不为null，尝试从右边找到相同的key
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                    // 找到则返回
                    return q;
            }
            // 找不到，实在没辙了，这个方法一定能判断出左右
            dir = tieBreakOrder(k, pk);
        }
        
        // xp指向当前节点
        TreeNode<K,V> xp = p;
        // p指向当前节点的子节点；如果dir对应方向的节点为null则继续，否则进入下一个循环
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            // xpn指向当前节点的next节点
            Node<K,V> xpn = xp.next;
            // x指向新节点，x指向xpn
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            if (dir <= 0)
                // 新节点作为当前节点的左子节点
                xp.left = x;
            else
                // 或者右子节点
                xp.right = x;
            // xp指向x，完成了xp→x→xpn
            xp.next = x;
            // x的父节点和上节点都指向xp
            x.parent = x.prev = xp;
            if (xpn != null)
                // xpn指向x，完成了xpn→x→xp，双向链表完成
                ((TreeNode<K,V>)xpn).prev = x;
            // 最后调整树结构，并将根节点移动到数组节点上
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

root方法

在putTreeVal中使用以下语句查找根节点：

1	TreeNode<K,V> root = (parent != null) ? root() : this;

其中，parent即数组节点的父节点，当parent为null时，数组节点就是根节点，否则要调用root方法找到根节点。

源码如下：

final TreeNode<K,V> root() {
    // 遍历，直到parent为null即为根节点
    for (TreeNode<K,V> r = this, p;;) {
        if ((p = r.parent) == null)
            return r;
        r = p;
    }
}

comparableClassFor和compareComparables是HashMap的成员方法，但是只在TreeNode中用到

HashMap.comparableClassFor方法

用于判断key的类型是否实现了Comparable接口

static Class<?> comparableClassFor(Object x) {
    // 实现Comparable接口
    if (x instanceof Comparable) {
        Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
        // String类型已实现了Comparable，直接返回class即可
        if ((c = x.getClass()) == String.class)
            return c;
        // 获得实现的接口列表
        if ((ts = c.getGenericInterfaces()) != null) {
            for (int i = 0; i < ts.length; ++i) {
                // t是参数化类型，也就是带有<>符号，
                if (((t = ts[i]) instanceof ParameterizedType) 
                    // t是Comparable类型
                    && ((p = (ParameterizedType)t).getRawType() == Comparable.class) 
                    // t的泛型不能为空
                    && (as = p.getActualTypeArguments()) != null 
                    // t的泛型个数为1且泛型类型就是x的类型
                    && as.length == 1 && as[0] == c)
                    // 返回x的类型
                    return c;
            }
        }
    }
    return null;
}

HashMap.compareComparables方法

调用compareTo方法来判断两个key的大小

/**
* kc	新节点的class对象
* k		新节点的key
* x		当前节点的key
*/
static int compareComparables(Class<?> kc, Object k, Object x) {
    // x为null或者x与k类型不同，返回0；否则调用compareTo判断大小
    return (x == null || x.getClass() != kc ? 0 : ((Comparable)k).compareTo(x));
}

这里注意下，x也就是树节点的key，是可能为null的。在HashMap中，key和value都能为null。在HashTable中，key和value都不能为null。

find方法

从根节点的左或者右子节点开始，递归查找，看是否存在相同的key，存在则返回该节点。

final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    // p最先是根节点的子节点
    TreeNode<K,V> p = this;
    do {
        // ph：p的哈希值；dir：表示在p左右；pk：p的key
        int ph, dir; K pk;
        // p的左子节点；p的右子节点；要找的那个节点
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        // h<ph，说明在左边
        if ((ph = p.hash) > h)
            // p指向左子节点，下一个循环
            p = pl;
        // h>ph，说明在右边
        else if (ph < h)
            // p指向右子节点，下一个循环
            p = pr;
        // k等于pk，说明p就是要找的节点，直接返回p
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        // 执行到这里，说明hash相同，key不同。尝试从不为null的一边继续找
        else if (pl == null)
            // 左子节点为null，p指向右子节点，下一个循环
            p = pr;
        else if (pr == null)
            // 右子节点为null，左子节点不为null，p指向左子节点，下一个循环
            p = pl;
        // 两边都不为null，尝试通过compareTo方法确定大小
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&
                 (dir = compareComparables(kc, k, pk)) != 0)
            // 大小已确定，p指向对应方向的子节点，下一个循环
            p = (dir < 0) ? pl : pr;
        // compareTo方法不能确定大小，递归调用右子节点的find方法
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        else
            // q为null，递归调用左子节点的find方法
            p = pl;
    } while (p != null); // 直到遍历结束
    return null;
}

tieBreakOrder方法

比较a和b，是用来打破平衡的终极方法。对于红黑树来说，用什么方法比较key的大小不重要，只要高效且多次比较结果一致即可

static int tieBreakOrder(Object a, Object b) {
    int d;
    if (a == null || b == null ||
        // 先用类名来比较
        (d = a.getClass().getName().compareTo(b.getClass().getName())) == 0)
        // 再用地址的哈希值排序
        d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
             -1 : 1);
    return d;
}

balanceInsertion方法

插入树节点后，通过 balanceInsertion 方法维持树结构的平衡

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;;) {
        // 父节点不存在，说明x就是根节点，设置成黑色，循环结束
        if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
        // 父节点是黑色，不影响平衡，循环结束（似乎并不存在后一种：父节点是根节点且为红色的情况）
        else if (!xp.red || (xpp = xp.parent) == null)
            return root;
        // 以下都是父节点为红色的情况，x的插入会导致平衡被打破，需要调整结构
        // 父节点为左子节点
        if (xp == (xppl = xpp.left)) {
            // 叔节点是红色
            if ((xppr = xpp.right) != null && xppr.red) {
                // 父节点和叔节点改为黑色，祖父节点改为红色
                xppr.red = false;
                xp.red = false;
                xpp.red = true;
                // 祖父节点改为当前节点，进入下一个循环
                x = xpp;
            } else { // 叔节点是黑色，只能通过旋转来处理
                // 对应左右情况
                if (x == xp.right) {
                    // 先左旋，对象是父节点
                    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);
                    }
                }
            }
        }
        else { // 父节点是右子节点
            // 叔节点是红色，同上
            if (xppl != null && xppl.red) {
                xppl.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            } else { // 叔节点是黑色，只能通过旋转来处理
                // 对应右左情况
                if (x == xp.left) {
                    // 先右旋，对象是父节点
                    root = rotateRight(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                // 不走上面，就是右右情况
                if (xp != null) {
                    // 互换父节点和祖父节点颜色
                    xp.red = false;
                    if (xpp != null) {
                        xpp.red = true;
                        // 左旋，对象是祖父节点
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}

对于新节点：

1.当父节点是黑色的，插入红色节点，不会有任何影响

2.当父节点是红色，插入红色节点会导致出现两个红节点，树结构被破坏

2.1如果叔节点也是红色，可以将父节点和叔节点都置为黑色，祖父节点置为红色，此时祖父节点往下的部分可以保持平衡。但是祖父节点改为红色可能导致往上的部分结构被破坏，因此需要继续递归处理

2.2如果叔节点为黑色，只能通过旋转保持平衡

2.2.1为右右情况，需要将左边的节点（即祖父节点）按下，右边节点（父节点）提上，交换二者颜色，记为左旋

2.2.2为左左情况，需要将右边的节点（即祖父节点）按下，左边节点（父节点）提上，交换二者颜色，记为右旋

2.2.3为左右情况，需要先左旋，将左边节点按下，右边节点提上，然后按左左情况处理

2.2.4为右左情况，需要先右旋，将右边节点按下，左边节点提上，然后按右右情况处理

规则总结如下：

父节点	叔节点	方向	规则
黑色	-	-	无
红色	红色	-	父节点和叔节点变成黑色，祖父节点变成红色，将祖父节点变成当前节点，递归处理
红色	黑色	右右	先左旋，再交换颜色
红色	黑色	左左	先右旋，再交换颜色
红色	黑色	左右	先左旋，再右旋，再交换颜色
红色	黑色	右左	先右旋，再左旋，再交换颜色

rotateLeft方法

左旋方法，在balanceInsertion中调用了两次，涉及到左右（<）和右右（\）的情况

左右：旋转对象xp是p的父节点

1	root = rotateLeft(root, x = xp);

右右：旋转对象xpp是p的祖父节点

1	root = rotateLeft(root, xpp);

主要作用是：按下p节点，使p作为r（p的右子节点）的左子节点，r作为p的父节点。pp作为r的父节点。rl作为p的右子节点

源码如下：

static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) {
    // r p的右子节点，pp p的父节点，rl r的左子节点
    TreeNode<K,V> r, pp, rl;
    // 只处理p和r都不为null的情况，即\（右右）或<（左右）
    if (p != null && (r = p.right) != null) {
        // p左旋（p从r的父节点变成r的左子节点），所以先把r的左子节点rl变成p的右子节点
        if ((rl = p.right = r.left) != null)
            // p变成rl的父节点
            rl.parent = p;
        // r变成p的父节点，要把p的父节点pp变成r的父节点
        if ((pp = r.parent = p.parent) == null)
            // pp为null，说明p是根节点，因此把r设置为根节点，变成黑色
            (root = r).red = false;
        // pp不为null，则把r变成pp的左子节点或右子节点
        else if (pp.left == p)
            pp.left = r;
        else
            pp.right = r;
        // p成为r的左子节点
        r.left = p;
        p.parent = r;
    }
    // 返回root
    return root;
}

rotateRight方法

右旋同理，在balanceInsertion中调用了两次，涉及到右左（>）和左左（/）的情况

右左：旋转对象p是父节点

1	root = rotateRight(root, x = xp);

左左：旋转对象p是祖父节点

1	root = rotateRight(root, xpp);

主要作用是：按下p节点，使p作为l（p的左子节点）的右子节点，l作为p的父节点。pp作为l的父节点。lr作为p的左子节点

源码如下：

static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) {
    // r p的左子节点，pp p的父节点，lr l的右子节点
    TreeNode<K,V> l, pp, lr;
    if (p != null && (l = p.left) != null) {
        if ((lr = p.left = l.right) != null)
            lr.parent = p;
        if ((pp = l.parent = p.parent) == null)
            (root = l).red = false;
        else if (pp.right == p)
            pp.right = l;
        else
            pp.left = l;
        l.right = p;
        p.parent = l;
    }
    return root;
}

moveRootToFront方法

当红黑树增加节点、移除节点或者树化后，根节点可能已经不是数组桶中的第一个节点

moveRootToFront 方法作用是：如果root节点不是数组节点，则将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;
            // root前后节点互相指向，也就是将root先从链表中移除
            if ((rn = root.next) != null)
                // rn指向rp
                ((TreeNode<K,V>)rn).prev = rp;
            if (rp != null)
                // rp指向rn
                rp.next = rn;
            // 将root移动到链表开头
            if (first != null)
                first.prev = root;
            root.next = first;
            root.prev = null;
        }
        // 检查红黑树结构是否正确
        assert checkInvariants(root);
    }
}

checkInvariants方法

用于验证红黑树结构是否正确。由于该方法调用时使用assert关键字，所以只有当启动时加上-ea参数才生效，默认不生效。

static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
    // t的父节点；t的左子节点；t的右子节点；t的前驱节点；t的后继节点
    TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
        tb = t.prev, tn = (TreeNode<K,V>)t.next;
    // 以下都满足，返回true；否则，返回false
    // 验证前驱节点的next指向t
    if (tb != null && tb.next != t)
        return false;
    // 验证后继节点的prev指向t
    if (tn != null && tn.prev != t)
        return false;
    // 验证父节点的left或right指向t
    if (tp != null && t != tp.left && t != tp.right)
        return false;
    // 验证tl的parent指向t且tl的hash大于t的hash
    if (tl != null && (tl.parent != t || tl.hash > t.hash))
        return false;
    // 验证tr的parent指向t且tr的hash小于t的hash
    if (tr != null && (tr.parent != t || tr.hash < t.hash))
        return false;
    // 验证t和子节点不能都为红色
    if (t.red && tl != null && tl.red && tr != null && tr.red)
        return false;
    // 从tl开始递归验证
    if (tl != null && !checkInvariants(tl))
        return false;
    // 从tr开始递归验证
    if (tr != null && !checkInvariants(tr))
        return false;
    return true;
}

getTreeNode方法

在HashMap.getNode方法中，判断数组节点是TreeNode类型，则会调用getTreeNode方法，执行树节点的get逻辑

其中，调用方node是数组节点，根据hash和查找

1 2	if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key);

先判断数组节点是不是根节点，如果不是，则通过root方法找到根节点。之后调用find方法，从根节点开始查找，找不到则返回null

final TreeNode<K,V> getTreeNode(int h, Object k) {
    // 先找到根节点，然后从根节点开始查找，找不到则返回null
    return ((parent != null) ? root() : this).find(h, k, null);
}

removeTreeNode方法

在HashMap.removeNode方法中，判断数组节点是TreeNode类型，则会调用removeTreeNode方法，执行树节点的remove逻辑

其中，调用方node是要删除的节点，this是当前hashMap对象，tab是节点数组，movable为true会执行moveRootToFront方法

1 2	if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);

removeTreeNode方法移除节点p按两部分进行：双向链表和红黑树。两部分互不影响

先处理双向链表

1.如果p是头节点，则将p的后继节点作为头节点

2.如果p是中间节点，则将p的前驱节点指向后继节点
再处理红黑树

1.如果节点数 <= 6，执行去树化操作，不再需要后续的红黑树处理

2.如果节点数 >6，按p是否存在子节点，分四种情况讨论

2.1没有子节点。这种情况最简单，直接移除p即可

2.2只有左子节点。移除p，用左子节点作为替换节点

2.3只有右子节点。移除p，用右子节点作为替换节点

2.4左右节点都有

2.4.1找到仅大于p的节点s（也就是p的右子节点的最左节点），交换s和p，分三步进行

2.4.1.1交换s和p的颜色

2.4.1.2将p的父节点、左子节点、右子节点作为s的父节点、左子节点、右子节点

2.4.1.3将s的父节点、右子节点作为p的父节点、右子节点（s没有左子节点）

2.4.2交换后，s节点的位置没有问题，p节点不符合要求，删除p节点即可

2.4.3如果p存在右子节点，则将右子节点作为替换节点

3.移除p后，替换节点有两种情况

3.1存在替换节点，连接替换节点和p的父节点

3.2不存在替换节点，使p的父节点的子节点指向null

4.p是黑色节点，则需要调整红黑树结构

5.将根节点移动到数组上

源码如下：

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;
    // first 数组节点；root 指向first；rl 根节点的左子节点
    TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
    // succ 待删除节点的后继节点；pred 待删除节点的前驱节点
    TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
    // pred为null，说明first是前驱节点
    if (pred == null)
        // 移除当前节点后，succ变成数组节点
        tab[index] = first = succ;
    else
        // 否则，使pred指向succ
        pred.next = succ;
    if (succ != null)
        // 使succ指向pred。至此，已将节点从链表中移除
        succ.prev = pred;
    if (first == null)
        return;
    
    // root.parent不为null，说明first不是根节点，需要重新查找
    if (root.parent != null)
        root = root.root();
    
    // 以下几种情况，节点数都不超过6，直接执行去树化操作，免得再去统计节点数
    // root == null，节点数0
    // root.right == null，节点数最多2
    // (rl = root.left) == null，节点数最多2
    // rl.left == null，节点数最多6
    if (root == null || root.right == null ||
        (rl = root.left) == null || rl.left == null) {
        tab[index] = first.untreeify(map);  // too small
        return;
    }
    
    // 以下是维护红黑树结构
    // p 待删除节点；pl 左子节点；pr 右子节点；replacement 在删除p后替代p的节点
    TreeNode<K,V> p = this, pl = left, pr = right, replacement;
    
    // 下面开始分四种情况讨论：左右子节点都存在，左不存在右存在，右存在左不存在，左右都不存在。
    // 其中，左右都存在的情况最为复杂
    if (pl != null && pr != null) {
        // s先指向pr；sl s的左子节点
        TreeNode<K,V> s = pr, sl;
        // 如果sl不为null，则将s指向sl。循环往复，直到sl为null，此时s指向pr子树的最左节点
        while ((sl = s.left) != null)
            s = sl;
        // 互换s和p的颜色，保证p所在位置节点颜色不变
        boolean c = s.red; s.red = p.red; p.red = c;
        // s的右子节点sr。由于s是pr的最左节点，所以s只有一个子节点
        TreeNode<K,V> sr = s.right;
        // p的父节点pp
        TreeNode<K,V> pp = p.parent;
        // 说明p是s的父节点，此时只需要互换父子关系
        if (s == pr) {
            p.parent = s;
            s.right = p;
        }
        // 说明p不是s的父节点
        else {
            // s的父节点sp
            TreeNode<K,V> sp = s.parent;
            // 将sp作为p的父节点
            if ((p.parent = sp) != null) {
                // 如果s是sp的左子节点，则将p作为sp的左子节点
                if (s == sp.left)
                    sp.left = p;
                else // 否则，将p作为sp的右子节点（这种情况不存在）
                    sp.right = p;
            }
            // 将pr作为s的右子节点
            if ((s.right = pr) != null)
                // 如果pr存在，则将s作为pr的父节点
                pr.parent = s;
        }
        
        // 因为s没有左子节点，所以使p的左子节点为空
        p.left = null;
        
        // 将sr作为p的右子节点
        if ((p.right = sr) != null)
            // 将p作为sr的父节点
            sr.parent = p;
        
        // 将pl作为s的左子节点
        if ((s.left = pl) != null)
            // 将s作为pl的父节点
            pl.parent = s;
        
        // 将pp作为s的父节点。如果pp为null，说明p是根节点，则将s作为根节点
        if ((s.parent = pp) == null)
            root = s;
        // p是左子节点，则将s作为pp的左子节点
        else if (p == pp.left)
            pp.left = s;
        else // p是右子节点，则将s作为pp的右子节点
            pp.right = s;
        
        // sr不为null，就用sr替换p
        if (sr != null)
            replacement = sr;
        else // 否则直接移除p就行
            replacement = p;
    }
    // 只有左子树存在的情况
    else if (pl != null)
        // 用左子树替换p
        replacement = pl;
    // 只有右子树存在的情况
    else if (pr != null)
        // 用右子树替换p
        replacement = pr;
    else
        // p没有子树，直接移除p就行
        replacement = p;
    
    // 移除p后，用replacement替换p
    if (replacement != p) {
        // p的父节点直接作为replacement的父节点，并赋值给pp
        TreeNode<K,V> pp = replacement.parent = p.parent;
        // 说明p是根节点，则将replacement作为根节点
        if (pp == null)
            root = replacement;
        // p是左子节点，则将replacement作为左子节点
        else if (p == pp.left)
            pp.left = replacement;
        else // 否则，将replacement作为右子节点
            pp.right = replacement;
        // 清空p的引用，便于垃圾回收
        p.left = p.right = p.parent = null;
    }
    
    // p是红色，移除不影响树结构；p是黑色，需要调整树结构。注意：p的颜色实际是之前s的颜色
    TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
    
    // 直接移除p
    if (replacement == p) {
        // p的父节点pp
        TreeNode<K,V> pp = p.parent;
        // 清空p的引用（只有一个父引用）
        p.parent = null;
        
        // 清除pp对p的引用
        if (pp != null) {
            if (p == pp.left)
                pp.left = null;
            else if (p == pp.right)
                pp.right = null;
        }
    }
    
    // 
    if (movable)
        moveRootToFront(tab, r);
}

balanceDeletion方法

balanceDeletion方法只在removeTreeNode方法中唯一调用。由上面的分析可知，调用者p一定为黑色节点，x为替代节点，有四种可能：p，pr，pl，sr。p被移除后，从x节点开始到任意叶子节点的黑色节点数，一定比从x的兄弟节点开始到叶子节点的黑色节点数少1。

balanceDeletion方法内是一个for循环，只能从内部跳出。循环体共分为五个if分支：

x节点为空或者x节点为根节点，返回根节点。
x的父节点为空，说明x节点就是根节点，将x节点置为黑色，返回x。
x节点不是根节点，且为红色，则将x节点置为黑色，就能保证x分支的黑色节点数符合要求，返回根节点。
x节点不是根节点，且为黑色，且为左子节点。
x节点不是根节点，且为黑色，且为右子节点。

其中，1、2、3都是方法的结束条件，在若干次循环后，总能进入1、2、3分支。4、5是对称分支，该分支会通过自旋的方式调整平衡，并最后会使x指向xp或者指向root，完成向1、2、3分支的靠拢。

由于x分支比兄弟分支黑色节点数少1，所以4、5平衡的方式有两种：

如果兄弟分支有红色节点，则将该节点旋转移动到x分支，并置为黑色，使x分支黑色节点数+1。
如果兄弟分支没有红色节点，则将黑色节点置为红色，使兄弟分支黑色节点数-1。但这样x分支又比堂兄弟分支数量少1，因此使x指向xp，继续下一个循环。

源码如下：

static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, TreeNode<K,V> x) {
    // xp x的父节点，xpl xp的左子节点，xpr x的右子节点
    for (TreeNode<K,V> xp, xpl, xpr;;)  {
        // 如果x节点为空或x节点为根节点，直接返回根节点
        if (x == null || x == root)
            return root;
        // 如果x的父节点为空，说明x节点就是根节点
        else if ((xp = x.parent) == null) {
            // 将x节点置为黑色，并返回
            x.red = false;
            return x;
        }
        // 如果x节点是红色
        else if (x.red) {
            // 则将x节点置为黑色，并返回根节点
            x.red = false;
            return root;
        }
        // 以下说明x节点为黑色
        // 其中，x为xp的左子节点
        else if ((xpl = xp.left) == x) {
            // xp的右子节点存在且为红色
            if ((xpr = xp.right) != null && xpr.red) {
                // 将xpr置为黑色
                xpr.red = false;
                // 将xp置为红色
                xp.red = true;
                // 对xp左旋，使xp成为xpr的左子节点
                root = rotateLeft(root, xp);
                // 使xpr重新指向xp的右子节点
                xpr = (xp = x.parent) == null ? null : xp.right;
            }
            // xpr为空，则使x指向xp，进入下一个循环
            if (xpr == null)
                x = xp;
            else { // 以下说明xpr不为空，可能为红色也可能为黑色
                // sl xp的右左节点，sr xp的右右节点
                TreeNode<K,V> sl = xpr.left, sr = xpr.right;
                // 即sr和sl没有一个红色
                if ((sr == null || !sr.red) &&
                    (sl == null || !sl.red)) {
                    // 将xpr置为红色
                    xpr.red = true;
                    // 使x指向xp，进入下一个循环
                    x = xp;
                }
                else { // 以下说明sr和sl至少有一个红色
                    // sr不存在或者sr是黑色，那么sl一定是红色
                    if (sr == null || !sr.red) {
                        // 将sl置为黑色
                        if (sl != null)
                            sl.red = false;
                        // xpr置为红色
                        xpr.red = true;
                        // 对xpr右旋，使xpr成为sl的右子节点
                        root = rotateRight(root, xpr);
                        // xpr重新成为xp的右子节点
                        xpr = (xp = x.parent) == null ?
                            null : xp.right;
                    }
                    if (xpr != null) {
                        // 使xpr和xp同色
                        xpr.red = (xp == null) ? false : xp.red;
                        // 使sr成为xpr的右子节点
                        if ((sr = xpr.right) != null)
                            // sr置为黑色
                            sr.red = false;
                    }
                    if (xp != null) {
                        // xp置为黑色
                        xp.red = false;
                        // 对xp左旋
                        root = rotateLeft(root, xp);
                    }
                    // x指向根节点，循环会在下一轮结束
                    x = root;
                }
            }
        }
        // 对称的情况，x为xp的右子节点
        else {
            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;
                }
            }
        }
    }
}

split方法

在HashMap.resize方法中，判断数组节点是树节点时，会调用红黑树的拆分方法split。

其中，调用方为数组节点，this是当前hashMap对象，newTab是扩容后的数组，j是e在旧数组上的位置，oldCap是旧数组长度。

1 2	else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

split与resize方法中拆分链表的逻辑类似

将红黑树所在链表按在新数组中的位置拆分成两条
低位链表放置在原来数组位置上，高位链表放置在数组右移oldCap位置上
如果链表长度<=6，则将红黑树结构转换成链表。否则重新维护红黑树结构

源码如下：

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    // 数组节点，也是红黑树的根节点和链表的头结点
    TreeNode<K,V> b = this;
    // 低位链表的头节点；低位链表的尾结点
    TreeNode<K,V> loHead = null, loTail = null;
    // 高位链表的头节点；高位链表的尾结点
    TreeNode<K,V> hiHead = null, hiTail = null;
    // 记录低位/高位链表的节点数，作为去树化的判断依据
    int lc = 0, hc = 0;
    // 遍历链表，按节点在新数组的位置将链表拆分
    // e初始为链表头结点
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        // next沿链表方向移动
        next = (TreeNode<K,V>)e.next;
        // 移除e的next指向
        e.next = null;
        // 节点位置不变
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                // 第一次进来，将e作为头结点
                loHead = e;
            else
                // 不是第一次，让尾结点的next指向e
                loTail.next = e;
            // e作为新的尾结点
            loTail = e;
            ++lc;
        }
        // 说明节点位置要移动bit长度
        else {
            if ((e.prev = hiTail) == null)
                // 第一次进来，将e作为头结点
                hiHead = e;
            else
                // 不是第一次，让尾结点的next指向e
                hiTail.next = e;
            // e作为新的尾结点
            hiTail = e;
            ++hc;
        }
    }
    // 存在低位链表
    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD)
            // 链表长度<=6，执行树转链表操作
            tab[index] = loHead.untreeify(map);
        else {
            // 链表长度>6，先将链表头结点放在数组原位置上
            tab[index] = loHead;
            if (hiHead != null)
                // 高位数组存在，说明发生了链表拆分，需要整理树结构
                loHead.treeify(tab);
        }
    }
    // 存在高位链表
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            // 区别在于链表移动bit位
            tab[index + bit] = hiHead.untreeify(map);
        else {
            // 区别在于链表移动bit位
            tab[index + bit] = hiHead;
            if (loHead != null)
                // 整理树结构
                hiHead.treeify(tab);
        }
    }
}

问题：红黑树拆分实质是对链表的拆分，原有的树结构去哪了？

对于长度<=6的链表，会调用untreeify方法创建新链表，并放置到数组上。原树结构的节点不再被引用，会被虚拟机回收；
对于长度>6的链表，会调用treeify方法重新梳理树结构，原有的树引用（parent, left, right）会被重置。

treeify方法

当链表转红黑树或红黑树拆分后，会执行treeify方法，根据链表维护红黑树结构。

其中，调用方loHead是链表头结点

1	loHead.treeify(tab);

源码如下：

final void treeify(Node<K,V>[] tab) {
    // 原根结点置为null
    TreeNode<K,V> root = null;
    // 从头结点开始，遍历链表，依次将节点插入到红黑树中
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        // 首次进入循环，将x设为根节点
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        }
        // 非首次进入循环，需要将x设为子节点
        else {
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            // 这个循环会从根节点开始，依次判断x应该放在左边或者右边，直到成功
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                // h < ph，表示要放在p的左边（不一定是左子节点）
                if ((ph = p.hash) > h)
                    dir = -1;
                // h > ph，表示要放在p的右边（不一定是右子节点）
                else if (ph < h)
                    dir = 1;
                // p = ph
                else if ((kc == null &&
                          // 优先用compareTo方法判断
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    // 不能用compareTo，或compareTo无法判断，则使用tieBreakOrder判断
                    dir = tieBreakOrder(k, pk);
                TreeNode<K,V> xp = p;
                
                // x应该在左边，且左子节点为空，则将x作为左子节点。否则让p指向左子节点，进入下一个循环
                // 或者x应该在右边，且右子节点为空，则将x作为右子节点。否则让p指向右子节点，进入下一个循环
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    // xp=p作为x的父节点
                    x.parent = xp;
                    // x作为xp的子节点
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    // 调整红黑树结构
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    // 将根节点作为数组节点
    moveRootToFront(tab, root);
}

untreeify方法

当树节点<=6时，会调用untreeify方法，执行红黑树转链表操作

其中，调用方loHead是链表头节点，会返回一个新链表

1	tab[index] = loHead.untreeify(map);

源码如下：

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) {
        // 创建新的节点p
        Node<K,V> p = map.replacementNode(q, null);
        if (tl == null)
            // hd指向头结点
            hd = p;
        else
            // 形成链表
            tl.next = p;
        // tl指向尾结点
        tl = p;
    }
    // 返回头节点
    return hd;
}

红黑树

三种树对比

特点

构造方法

成员变量

TreeNode

Entry

Node

成员方法

putTreeVal方法

root方法

HashMap.comparableClassFor方法

HashMap.compareComparables方法

find方法

tieBreakOrder方法

balanceInsertion方法

rotateLeft方法

rotateRight方法

moveRootToFront方法

checkInvariants方法

getTreeNode方法

removeTreeNode方法

balanceDeletion方法

split方法

treeify方法

untreeify方法

参考资料