Java 容器源码分析之ConcurrentHashMap(11)
- UID
- 1066743
|
Java 容器源码分析之ConcurrentHashMap(11)
二叉树结构:
4、加入节点60,如果root不为空,则通过比较节点hash值的大小将新节点插入到指定位置,实现如下:
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; }}其中x代表即将插入到红黑树的节点,p指向红黑树中当前遍历到的节点,从根节点开始递归遍历,x的插入过程如下:
1)、如果x的hash值小于p的hash值,则判断p的左节点是否为空,如果不为空,则把p指向其左节点,并继续和p进行比较,如果p的左节点为空,则把x指向的节点插入到该位置;
2)、如果x的hash值大于p的hash值,则判断p的右节点是否为空,如果不为空,则把p指向其右节点,并继续和p进行比较,如果p的右节点为空,则把x指向的节点插入到该位置;
3)、如果x的hash值和p的hash值相等,怎么办?
解决:首先判断节点中的key对象的类是否实现了Comparable接口,如果实现Comparable接口,则调用compareTo方法比较两者key的大小,但是如果key对象没有实现Comparable接口,或则compareTo方法返回了0,则继续调用tieBreakOrder方法计算dir值,tieBreakOrder方法实现如下:
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;}最终比较key对象的默认hashCode()方法的返回值,因为System.identityHashCode(a)调用的是对象a默认的hashCode();
插入节点60之后的二叉树:
5、当有新节点加入时,可能会破坏红黑树的特性,需要执行balanceInsertion()方法调整二叉树,使之重新满足特性,方法中的变量xp指向x的父节点,xpp指向xp父节点,xppl和xppr分别指向xpp的左右子节点,balanceInsertion()方法首先会把新加入的节点设置成红色。
①、加入节点60之后,此时xp指向节点80,其父节点为空,直接返回。
if ((xp = x.parent) == null) { x.red = false; return x;}else if (!xp.red || (xpp = xp.parent) == null) return root;调整之后的二叉树:
②、加入节点50,二叉树如下:
继续执行balanceInsertion()方法调整二叉树,此时节点50的父节点60是左儿子,走如下逻辑:
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); } } }}根据上述逻辑,把节点60设置成黑色,把节点80设置成红色,并对节点80执行右旋操作,右旋实现如下:
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) { 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;}右旋之后的红黑树如下:
③、加入节点70,二叉树如下:
继续执行balanceInsertion()方法调整二叉树,此时父节点80是个右儿子,节点70是左儿子,且叔节点50不为空,且是红色的,则执行如下逻辑:
if (xppl != null && xppl.red) { xppl.red = false; xp.red = false; xpp.red = true; x = xpp;}此时二叉树如下:
此时x指向xpp,即节点60,继续循环处理x,设置其颜色为黑色,最终二叉树如下:
④、加入节点20,二叉树变化如下:
因为节点20的父节点50是一个黑色的节点,不需要进行调整;
⑤、加入节点65,二叉树变化如下:
对节点80进行右旋操作。
⑥、加入节点40,二叉树变化如下:
1、对节点20执行左旋操作;
2、对节点50执行右旋操作;
最后加入节点10,二叉树变化如下:
重新对节点进行着色,到此为止,红黑树已经构造完成; |
|
|
|
|
|