ConcurrentHashMap与红黑树实现分析Java8

上一篇：Java集合-ConcurrentHashMap工作原理和实现JDK8

本文学习知识点

1、二叉查找树，以及二叉树查找带来的问题。
2、平衡二叉树及好处。
3、红黑树的定义及构造。
4、ConcurrentHashMap中红黑树的构造。

在正式分析红黑树之前，有必要了解红黑树的发展过程，请读者耐心阅读。

二叉查找树

红黑树的起源得从二叉查找树（二叉排序树）说起。先来看二叉查找树的定义：

1、要么为一颗空树，要么就是一颗具有如下特性的二叉树。
2、左子节点的值必须小于等于父节点的值。
3、右子节点的值必须大于等于父节点的值。

每个节点都符合这个特性，所以易于查找，如下图：

二叉查找树-平衡

但二叉查找树会出现不平衡的情况，即左子树和右子树的深度相差很大，如果一颗二叉查找树，只有右子树，就演变成一个链表了，查找效率就变的很差，如下图：

不平衡的二叉查找树

对于查找而言，如果一棵二叉树的高度是N，那么最多可以在N步内完成查找。也就是说，树的高度要尽可能矮查找才会更快。考虑到查找的平均情况，叶子节点到根节点的距离不能差别太大，所以我们都希望二叉查找树是一颗矮胖树，而不是一条链路的二叉树。为了优化因深度的不稳定性对查找效率的影响，于是就出现了平衡二叉树。

时间复杂度
1.在一棵二叉查找树上，执行查找、插入、删除等操作，的时间复杂度为O（lgn）。因为，一棵由n个节点，随机构造的二叉查找树的高度为lgn，所以顺理成章，一般操作的执行时间为O（lgn）。至于n个节点的二叉树高度为lgn的证明，可参考算法导论第12章二叉查找树第12.4节。
2.但若是一棵具有n个节点的线性链，则此些操作最坏情况运行时间为O（n）。

平衡二叉树

定义：

1、要么为一颗空树，要么就是一颗具有如下特性的二叉树。
2、它的左子树和右子树都是平衡二叉树。
3、它的左子树和右子树的深度差的绝对值不超过1。

两颗平衡的二叉树

在构造平衡二插树时，失衡调整主要是通过旋转最小失衡子树来实现的。有必要弄清楚几个概念：

1、平衡因子：左子树的高度减去右子树的高度。由平衡二叉树的定义可知，平衡因子的取值只可能为0,1,-1.分别对应着左右子树等高，左子树比较高，右子树比较高。
2、最小失衡子树：在新插入的节点向上查找，以第一个平衡因子的绝对值超过1的节点为根的子树称为最小失衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树。

在图1中，例如插入节点5，那么2节点（左子树树高-右子树树高）的的平衡因子为-2。同理，3节点的平衡因子也为-2。此时同时存在了两棵不平衡子树，但按节点5往上查找，4节点的平衡因子为-1，3节点的平衡因子为-2，因此3节点是第一个最小的不平衡子树。所以我们将以3节点为中心，将最小不平衡树向左旋转，即可得到平衡二叉树，如图2。

调整过程

平衡二叉树失衡的全部调整过程和代码就不详述了，重点在于描述红黑树的调整过程。

红黑树

红黑树是一种特殊的二叉查找树，在满足二叉查找树的特性外，在每个节点上增加了存储颜色的标识，颜色要么是红色，要么是黑色，定义：

1、每个节点要么是黑色，要么是红色。
2、根节点是黑色。
3、所有叶子节点是黑色，即空节点（NIL）。
4、如果一个节点是红色的，则它的两个子节点必须是黑色的，也就是父子节点不能都为红色。
5、从一个节点到其所有叶子节点的所有路径上包含相同数目的黑节点。

注意：
(1) 特性3中的叶子节点，是只为空(NIL或null)的节点。
(2) 特性5，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。因此在最坏情况下，红黑树能保证时间复杂度为O( lgn )

红黑树示意图

树的旋转知识

当我们对红黑树进行插入和删除操作时，对树做了结构性修改，那么可能会违背红黑树的5条性质。

为了保持红黑树的性质，我们可以通过对树进行旋转，即修改树中某些节点的颜色及父子节点的指针结构，以维持红黑树的性质。
树的旋转，分为左旋和右旋，以下借助图来做形象的解释和介绍。

1、左旋

左旋

如上图所示：要对节点X进行左旋，其右子节点必定不能为NULL。左旋以X到Y之间的链为“支轴”进行，它使Y成为该孩子树新的根，而Y的左孩子β则成为X的右孩子。
再看个实例：

左旋实例

2、右旋

右旋和左旋类似，只看实例，理解一个就可以了：

右旋实例

左旋右旋总结
树的旋转，能保持不变的只有树的二叉查找性质，而原树的红黑性质则不能保持，在红黑树的数据插入和删除后，可利用旋转和颜色重涂来恢复树的红黑性质。

3、红黑树的插入

向一棵含有n个节点的红黑树插入一个新节点的操作可以在O（lgn）时间内完成。
在继续插入操作分析前，再来复习下红黑树的特性：

1、每个节点要么是黑色，要么是红色。
2、根节点是黑色。
3、所有叶子节点是黑色，即空节点（NIL）。
4、如果一个节点是红色的，则它的两个子节点必须是黑色的，也就是父子节点不能都为红色。
5、从一个节点到其所有叶子节点的所有路径上包含相同数目的黑节点

规则约定
（1）在红黑树中插入节点时，节点的初始颜色都是红色。因为这样可以在插入过程中尽量避免对树的结构进行调整（参考第5点性质）。
（2）初始插入按照二叉查找树的性质插入，即找到合适大小的节点，在其左边或右边插入子节点。

我们插入一个节点后，可能会使原树的哪些性质改变呢？
（1）由于是以二叉查找树的性质插入，因此节点的查找性质不会破坏。
（2）如果插入空树中，成为根节点，则性质2会被破坏，需要重新涂色。
（3）如果插入节点的父节点是红色，则性质4会被破坏，需要以插入的当前节点为中心进行旋转或重新涂色来恢复红黑树的性质。执行旋转或重新涂色后有可能红黑树仍然不满足性质，则需要将当前节点变换回溯到其父节点或祖父节点，以父节点或祖父节点为中心继续旋转或重新涂色，如此循环到根节点直到满足红黑树的性质。

恢复红黑树性质的策略
根据上面说到的性质改变，对应的恢复策略其实就简单很多。
（1）把出现违背红黑树性质的结点向上移（通过旋转操作或变换当前节点到父节点或祖父节点后再旋转达到向上移动的目的），如果能移到根结点，那么很容易就能通过直接修改根结点的颜色，或旋转根节点来恢复红黑树的性质。
（2）旋转或涂色处理可分5种情况进行处理。

情况1：空树中插入根节点。
情况2：插入节点的父节点是黑色。
情况3：当前节点的父节点是红色，且叔叔节点（祖父节点的另一个子节点）也是红色。
情况4：当前节点的父节点是红色，叔叔节点是黑色，当前节点是右子节点。
情况5：当前节点的父节点是红色，叔叔节点是黑色，当前节点是左子节点。

情况1：空树中插入根节点
违反：性质2
恢复策略：初始插入的节点均为红色，因此简单将红色重涂为黑色即可。

情况2：插入节点的父节点是黑色
违反：插入的红色节点，未违反任何性质。
恢复策略：什么也不做，无需调整。

情况3：当前节点的父节点是红色，且叔叔节点也是红色
违反：性质4
此时祖父节点一定存在，否则插入前就已不是红黑树。
与此同时，又分为父节点是祖父节点的左子还是右子，由于对称性，我们只要解开一个方向就可以了。在此，我们只考虑父节点为祖父左子的情况。
同时，还可以分为当前结点是其父结点的左子还是右子，但是处理方式是一样的。我们将此归为同一类。
恢复策略：将当前节点的父节点和叔叔节点涂黑，祖父结点涂红，把当前结点指向祖父节点，以祖父节点为中心重新开始新一轮的旋转或涂色。
以插入节点4为例，按照恢复策略，做如下图的涂色：

情况3——涂色

以插入节点4为当前节点，判断父节点和叔叔节点是否都为红色，如果为红色，则将祖父节点7的颜色改为红色，父节点5和叔叔节点8的颜色改为黑色。同时当前节点移动到祖父节点7。此时，当前节点7的父节点也为红色，出现父子节点都为红色的情况，且叔叔节点为黑色，因此适用于情况4：当前节点的父节点是红色，叔叔节点是黑色，当前节点是右子节点，那么按照情况4的恢复策略，进行新一轮的旋转或涂色，如下看情况4如何进行调整。

情况4：当前节点的父节点是红色，叔叔节点是黑色，当前节点是右子节点
违反：性质4
恢复策略：以当前节点的父节点作为新的当前节点，以新的当前节点为支撑，进行左旋操作。旋转操作后再按新的情况进行旋转或涂色。

情况4——左旋

这里作的操作为：当前节点由原来的7变换为其父节点2，以新的当前节点2，作左旋操作，如上图。操作完成后，发现父子节点仍都是红色，继续进行旋转或涂色。这里适用于情况5：当前节点的父节点是红色，叔叔节点是黑色，当前节点是左子节点来进行再次调整，请看下面的情况5如何进行调整。

情况5：当前节点的父节点是红色，叔叔节点是黑色，当前节点是左子节点
违反：性质4
恢复策略：父节点改变为黑色，祖父节点改变为红色，然后再以祖父节点为新的当前节点，做右旋操作。

情况5——涂色和旋转

此时，树已经满足红黑树的性质，如果仍不满足，则仍按照情况1——情况5的方式进行旋转和重新涂色。

红黑树的删除操作就不介绍了，涂色和旋转和这个类似。如何删除节点请看二叉查找树的删除即可。

为什么不用平衡二叉树作为底层实现

那是因为平衡二叉是高度平衡的树, 而每一次对树的修改, 都要 rebalance, 这里的开销会比红黑树大. 如果插入一个node引起了树的不平衡，平衡二叉树和红黑树都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时，最坏情况下，平衡二叉树需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而红黑树最多只需3次旋转，只需要O(1)的复杂度, 所以平衡二叉树需要rebalance的频率会更高，因此红黑树在大量插入和删除的场景下效率更高

ConcurrentHashMap二叉树的构造过程

前面讲了一大堆，终于来到ConcurrentHashMap二叉树的构造过程了，构造过程和前面讲的一样。我们先分析源码，然后以一个实际的例子进行分析。

在Java集合-ConcurrentHashMap工作原理和实现JDK8这篇文章中提到，链表的长度超过8时，会调用treeifyBin(tab , i)方法将链表结构转换为红黑树。
先复习下ConcurrentHashMap中节点的类型和继承关系：

ConcurrentHashMap几个核心内部类关系图

注意点：Node是链表中的元素，而TreeBin和TreeNode也继承自Node节点，也自然继承了next属性，同样拥有链表的性质，其实真正在存储时，红黑树仍然是以链表形式存储的，只是逻辑上TreeBin和TreeNode多了支持红黑树的root，first, parent，left，right，red属性，在附加的属性上进行逻辑上的引用和关联，也就构造成了一颗树。

所以理解了上面的红黑树其实也是一个链表，再来看源码就不难理解：

/**
 * Replaces all linked nodes in bin at given index unless table is
 * too small, in which case resizes instead.
 * @param tab table表
 * @param index 转换为红黑树的链表在table中的索引下标
 */
private final void treeifyBin(Node<K,V>[] tab, int index) {
    Node<K,V> b; int n, sc;
    if (tab != null) {
        // 一开始并非直接转换为红黑树，而是通过扩容table到2倍的方式，
        // 只有table的长度大于64之后，才会将超过8个元素的链表转红黑树
        if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
            tryPresize(n << 1);
        // b.hash >= 0即为普通的Node链表节点
        else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
            synchronized (b) {// 锁住链表头
                if (tabAt(tab, index) == b) {
                    TreeNode<K,V> hd = null, tl = null;
                    // 将原Node链表转换成以TreeBin节点为元素的链表
                    for (Node<K,V> e = b; e != null; e = e.next) {
                        TreeNode<K,V> p =
                            new TreeNode<K,V>(e.hash, e.key, e.val, null, null);
                        if ((p.prev = tl) == null)
                            hd = p;
                        else
                            tl.next = p;
                        tl = p;
                    }
                    // TreeBin的构造方法构造树，根据TreeBin链表构造
                    setTabAt(tab, index, new TreeBin<K,V>(hd));
                }
            }
        }
    }
}

从源码可以看出，一开始并非直接转换为红黑树，而是通过扩容table到2倍的方式，只有table的长度大于64之后，才会将超过8个元素的链表转红黑树。红黑树的构造过程是在TreeBin的构造方法中完成的。

红黑树的构造过程

假设待构造的红黑树TreeNode链表如下，节点中的数值代表元素的hash值：

源码如下：

/**
 * Creates bin with initial set of nodes headed by b.
 */
TreeBin(TreeNode<K,V> b) {
    super(TREEBIN, null, null, null);
    this.first = b;
    TreeNode<K,V> r = null;
    // 遍历TreeNode链表进行构造
    for (TreeNode<K,V> x = b, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        if (r == null) {
            x.parent = null;
            x.red = false;
            r = x;
        }
        else {
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            for (TreeNode<K,V> p = r;;) {
                // 执行插入，dir为比对节点hash值大小的标识,决定插入时在左还是在右
                int dir, ph;
                K pk = p.key;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);
                    TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    // 插入后，执行恢复操作：重新涂色或旋转
                    r = balanceInsertion(r, x);
                    break;
                }
            }
        }
    }
    this.root = r;
    assert checkInvariants(root);
}

源码中，balanceInsertion方法为恢复操作。所以根据上述源码和红黑树的恢复策略，依次遍历链表节点插入到红黑树中，我们构造如下：

（1）节点80。
第一个节点80，插入到空树中，设置为根节点，并为黑色：

链表中红色框节点表示已经完成插入红黑树

（2）节点60
节点60按二叉树插入后，未违反任何红黑树的性质，不做任何动作。

红黑树中虚线框为当前节点

（3）节点50
节点50插入后，违反了性质4，按照情况5：当前节点的父节点是红色，叔叔节点是黑色，当前节点是左子节点进行恢复。

节点50违反红黑树性质4

按照情况5的恢复策略调整如下：
把当前节点的父节点变为黑色，祖父节点变为红色，将祖父节点更新为当前节点，以新的当前节点为支点进行右旋操作。

先涂色后恢复

（4）节点70
节点70插入后，违反红黑树性质5，按照情况3：当前节点的父节点是红色，且叔叔节点也是红色进行调整。

节点70违反红黑树性质4

调整如下，需要经过两次涂色调整，将当前节点70的父节点和叔叔节点改为黑色，祖父节点改为红色。由于祖父节点为根节点，根节点只能为黑色，因此在此将根节点改为黑色，调整完成。

涂色和再涂色

（5）节点20
节点20插入后未违反任何特性，无需调整。

节点20插入后未违反任何特性，无需调整

（6）节点65
节点65插入后违反性质4，按照情况5：当前节点的父节点是红色，叔叔节点是黑色，当前节点是左子节点进行恢复。

节点65插入后违反性质4

恢复调整如下，需要经过两个步骤，当前节点65的父节点改为黑色，祖父节点改为红色，然后将祖父节点设为最新的当前节点。涂色后的新树违反了性质5，因此还要以最新的当前节点为支点进行右旋操作：

涂色和右旋

（7）节点40
节点40插入后，违反红黑树性质4:父子节点不能都为红色，插入后的红黑树见下图：

插入节点40后，违反红黑树性质4:父子节点不能都为红色

根据前文的调整策略，此处当前节点为红色，叔叔节点NIL为黑色，且当前节点为右子节点，按情况4进行调整恢复：
步骤一：以当前节点40的父节点20为新的当前节点（见下图1）；
步骤二：以图1中新的当前节点20为支点，左旋（见下图2）；

旋转完成后，发现当前节点20和父节点40都为红色，仍然违反了红黑树的性质4，需要继续回溯当前节点再次旋转或涂色。此时，当前节点是左子节点，按情况5进行调整恢复：
步骤一：将当前节点的父节点40重涂为黑色，祖父节点50重涂为红色（见下图3）；得到的红黑树发现不满足红黑树的性质5：从一个节点到其所有叶子节点的所有路径上包含相同数目的黑节点，继续执行步骤二的调整。
步骤二：以当前节点20的祖父节点50为新的当前节点，进行右旋（见下图5）；