原文出处 http://cmsblogs.com/ 『chenssy'
在【死磕 Java 并发】—–J.U.C 之 Java 并发容器:ConcurrentHashMap 一文中详细阐述了 ConcurrentHashMap 的实现过程,其中有提到在 put 操作时,如果发现链表结构中的元素超过了 TREEIFY_THRESHOLD(默认为 8),则会把链表转换为红黑树,已便于提高查询效率。代码如下:
- if (binCount >= TREEIFY_THRESHOLD)
- treeifyBin(tab, i);
下面博主将详细分析整个过程,并用一个链表转换为红黑树的过程为案例来分析。博文从如下几个方法进行分析阐述:
先看红黑树的基本概念:红黑树是一课特殊的平衡二叉树,主要用它存储有序的数据,提供高效的数据检索,时间复杂度为 O(lgn)。红黑树每个节点都有一个标识位表示颜色,红色或黑色,具备五种特性:
请牢记这五个特性,它在维护红黑树时选的格外重要
红黑树结构图如下:
对于红黑树而言,它主要包括三个步骤:左旋、右旋、着色。所有不符合上面五个特性的 "红黑树" 都可以通过这三个步骤调整为正规的红黑树。
当对红黑树进行插入和删除操作时可能会破坏红黑树的特性。为了继续保持红黑树的性质,则需要通过对红黑树进行旋转和重新着色处理,其中旋转包括左旋、右旋。
左旋
左旋示意图如下:
左旋处理过程比较简单,将 E 的右孩子 S 调整为 E 的父节点、S 节点的左孩子作为调整后 E 节点的右孩子。
右旋
由于链表转换为红黑树只有添加操作,加上篇幅有限所以这里就只介绍红黑树的插入操作,关于红黑树的详细情况,烦请各位 Google。
在分析过程中,我们已下面一颗简单的树为案例,根节点 G、有两个子节点 P、U,我们新增的节点为 N
红黑树默认插入的节点为红色,因为如果为黑色,则一定会破坏红黑树的规则 5(从一个节点到该节点的子孙节点的所有路径包含相同个数的黑色节点)。尽管默认的节点为红色,插入之后也会导致红黑树失衡。红黑树插入操作导致其失衡的主要原因在于插入的当前节点与其父节点的颜色冲突导致(红红,违背规则 4:如果一个节点为红色,那么它的子节点一定是黑色)。
要解决这类冲突就靠上面三个操作:左旋、右旋、重新着色。由于是红红冲突,那么其祖父节点一定存在且为黑色,但是叔父节点 U 颜色不确定,根据叔父节点的颜色则可以做相应的调整。
1 叔父 U 节点是红色
如果叔父节点为红色,那么处理过程则变得比较简单了:更换 G 与 P、U 节点的颜色,下图(一)。
当然这样变色可能会导致另外一个问题了,就是父节点 G 与其父节点 GG 颜色冲突(上图二),那么这里需要将 G 节点当做新增节点进行递归处理。
2 叔父 U 节点为黑叔
如果当前节点的叔父节点 U 为黑色,则需要根据当前节点 N 与其父节点 P 的位置决定,分为四种情况:
情况 1、2 称之为外侧插入、情况 3、4 是内侧插入,之所以这样区分是因为他们的处理方式是相对的。
2.1 外侧插入
以 N 是 P 的右子节点、P 是 G 的右子节点为例,这种情况的处理方式为:以 P 为支点进行左旋,然后交换 P 和 G 的颜色(P 设置为黑色,G 设置为红色),如下:
左外侧的情况(N 是 P 的左子节点,P 是 G 的左子节点)和上面的处理方式一样,先右旋,然后重新着色。
2.2 内侧插入
以 N 是 P 的左子节点,P 是 G 的右子节点情况为例。内侧插入的情况稍微复杂些,经过一次旋转、着色是无法调整为红黑树的,处理方法如下:先进行一次右旋,再进行一次左旋,然后重新着色,即可完成调整。注意这里两次右旋都是以新增节点 N 为支点不是 P。这里将 N 节点的两个 NIL 节点命名为 X、L。如下:
至于左内侧则处理逻辑如下:先进行右旋,然后左旋,最后着色。
ConcurrentHashMap 的链表转换为红黑树过程就是一个红黑树增加节点的过程。在 put 过程中,如果发现链表结构中的元素超过了 TREEIFY_THRESHOLD(默认为 8),则会把链表转换为红黑树:
- if (binCount >= TREEIFY_THRESHOLD)
- treeifyBin(tab, i);
treeifyBin 主要的功能就是把链表所有的节点 Node 转换为 TreeNode 节点,如下:
- private final void treeifyBin(Node < K, V > [] tab, int index) {
- Node < K,
- V > b;
- int n,
- sc;
- if (tab != null) {
- if ((n = tab.length) < MIN_TREEIFY_CAPACITY) tryPresize(n << 1);
- else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
- synchronized(b) {
- if (tabAt(tab, index) == b) {
- TreeNode < K,
- V > hd = null,
- tl = null;
- 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;
- }
- setTabAt(tab, index, new TreeBin < K, V > (hd));
- }
- }
- }
- }
- }
先判断当前 Node 的数组长度是否小于 MIN_TREEIFY_CAPACITY(64),如果小于则调用 tryPresize 扩容处理以缓解单个链表元素过大的性能问题。否则则将 Node 节点的链表转换为 TreeNode 的节点链表,构建完成之后调用 setTabAt() 构建红黑树。TreeNode 继承 Node,如下:
- static final class TreeNode < K,
- V > extends Node < 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, TreeNode < K, V > parent) {
- super(hash, key, val, next);
- this.parent = parent;
- }......
- }
我们以下面一个链表作为案例,结合源代码来分析 ConcurrentHashMap 创建红黑树的过程:
12
12 作为跟节点,直接为将红编程黑即可,对应源码:
- next = (TreeNode<K,V>)x.next;
- x.left = x.right = null;
- if (r == null) {
- x.parent = null;
- x.red = false;
- r = x;
- }
(【注】:为了方便起见,这里省略 NIL 节点,后面也一样)
1
此时根节点 root 不为空,则插入节点时需要找到合适的插入位置,源码如下:
- K k = x.key;
- int h = x.hash;
- Class<?> kc = null;
- for (TreeNode<K,V> p = r;;) {
- 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;
- }
- }
从上面可以看到起处理逻辑如下:
- 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;
- }
tieBreakOrder() 方法最终还是通过调用 System.identityHashCode() 方法来比较。
确定插入位置后,插入,由于插入的节点有可能会打破红黑树的结构,所以插入后调用 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.parent == null,为跟节点,置黑即可
- if ((xp = x.parent) == null) {
- x.red = false;
- return x;
- }
- // x 父节点为黑色,或者x 的祖父节点为空,直接插入返回
- else if (!xp.red || (xpp = xp.parent) == null)
- return root;
- /*
- * x 的 父节点为红色
- * ---------------------
- * x 的 父节点 为 其祖父节点的左子节点
- */
- if (xp == (xppl = xpp.left)) {
- /*
- * x的叔父节点存在,且为红色,颜色交换即可
- * x的父节点、叔父节点变为黑色,祖父节点变为红色
- */
- if ((xppr = xpp.right) != null && xppr.red) {
- xppr.red = false;
- xp.red = false;
- xpp.red = true;
- x = xpp;
- }
- else {
- /*
- * x 为 其父节点的右子节点,则为内侧插入
- * 则先左旋,然后右旋
- */
- if (x == xp.right) {
- // 左旋
- root = rotateLeft(root, x = xp);
- // 左旋之后x则会变成xp的父节点
- xpp = (xp = x.parent) == null ? null : xp.parent;
- }
- /**
- * 这里有两部分。
- * 第一部分:x 原本就是其父节点的左子节点,则为外侧插入,右旋即可
- * 第二部分:内侧插入后,先进行左旋,然后右旋
- */
- 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,其父节点为黑色,即:
- else if (!xp.red || (xpp = xp.parent) == null)
- return root;
直接插入:
9
9 作为 1 的右子节点插入,但是存在红红冲突,此时 9 的并没有叔父节点。9 的父节点 1 为 12 的左子节点,9 为其父节点 1 的右子节点,所以处理逻辑是先左旋,然后右旋,对应代码如下:
- 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);
- }
- }
图例变化如下:
2
节点 2 作为 1 的右子节点插入,红红冲突,切其叔父节点为红色,直接变色即可,:
- if ((xppr = xpp.right) != null && xppr.red) {
- xppr.red = false;
- xp.red = false;
- xpp.red = true;
- x = xpp;
- }
对应图例为:
0
节点 0 作为 1 的左子节点插入,由于其父节点为黑色,不会插入后不会打破红黑树结构,直接插入即可:
11
节点 11 作为 12 的左子节点,其父节点 12 为黑色,和 0 一样道理,直接插入:
7
节点 7 作为 2 右子节点插入,红红冲突,其叔父节点 0 为红色,变色即可:
19
节点 19 作为节点 12 的右子节点,直接插入:
至此,整个过程已经完成了,最终结果如下:
来源: http://blog.csdn.net/chenssy/article/details/73749297