//对treeMap的红黑树理解注解. 2017.02.16 by 何锦彬 JDK,1.7.51/** From CLR */ private void fixAfterInsertion(Entry<K, V> x) { //新加入红黑树的默认节点就是红色 x.color = RED; /** * 1. 如为根节点直接跳出 */ while (x != null && x != root && x.parent.color == RED) { if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { //如果X的父节点（P）是其父节点的父节点（G）的左节点 //即 下面这种情况 /** * G * P(RED) U */ //获取其叔(U)节点 Entry<K, V> y = rightOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { // 这种情况 /** * G * P(RED) U(RED) * X */ //如果叔节点是红色的（父节点有判断是红色）. 即是双红色，比较好办，通过改变颜色就行. 把P和U都设置成黑色然后,X加到P节点。 G节点当作新加入节点继续迭代 setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { //处理红父，黑叔的情况 if (x == rightOf(parentOf(x))) { // 这种情况 /** * G * P(RED) U(BLACK) * X */ //如果X是右边节点 x = parentOf(x); // 进行左旋 rotateLeft(x); } //左旋后，是这种情况了 /** * G * P(RED) U(BLACK) * X */ // 到这，X只能是左节点了，而且P是红色，U是黑色的情况 //把P和G改成黑色，以G为节点进行右旋 setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } else { //父节点在右边的 /** * G * U P(RED) */ //获取U Entry<K, V> y = leftOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { //红父红叔的情况 /** * G * U(RED) P(RED) */ setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); //把G当作新插入的节点继续进行迭代 x = parentOf(parentOf(x)); } else { //红父黑叔，并且是右父的情况 /** * G * U(RED) P(RED) */ if (x == leftOf(parentOf(x))) { x = parentOf(x); //以P为节点进行右旋 rotateRight(x); } //右旋后 /** * G * U(BLACK) P(RED) * X */ setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); //以G为节点进行左旋 rotateLeft(parentOf(parentOf(x))); } } } //红黑树的根节点始终是黑色 root.color = BLACK; }
2， HASHMAP的死链问题
//对HashMap死链理解的注解 . 2017.02.17 by 何锦彬 JDK,1.7.51
void transfer(Entry[] newTable, boolean rehash) { //获取新table的容量 int newCapacity = newTable.length; //迭代以前的数组 for (Entry<K,V> e : table) { //如果数组上有元素 while(null != e) { // 赋值next Entry<K,V> next = e.next; //获取e在新的table里的位置 if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); //把e指向当前的新数组里的第一个元素，这里会并发了，如果在这断点等待下个线程过来，就会死循环，尝试下 e.next = newTable[i]; //替代新数组的位置 newTable[i] = e; e = next; } } }
扩容前
[ 1 ] [ 2 ] [ 3 ] [ 空]
5 10
第一个线程扩容后，数组链表如下
[ 1 ] [ 10 ] [3] [] [] [] []
2
第二个线程又把从头把2指向10，然后2和10形成了个死循环
HashMap在 JDK8后 把数组链表变成了数组+链表+红黑树. 链表为O(n)，而红黑树为O(logN)
for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //JDK8 的hashmap，链表到了8就需要变成颗红黑树了 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; }
调整红黑树的方法其实和treeMap的一样了
如下：
//hashmap的红黑树平衡 static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) { x.red = true; //死循环加变量定义，总感觉JAVA很少这样写代码 哈 for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { //xp X父节点， XPP X的祖父节点， XPPL 祖父左节点 XXPR 祖父右节点 if ((xp = x.parent) == null) { x.red = false; return x; } // 如果父节点是黑色， 或者XP父节点是空，直接返回 else if (!xp.red || (xpp = xp.parent) == null) return root; // 下面的代码就和上面的很treeMap像了， if (xp == (xppl = xpp.left)) { // 第一种情况, 赋值xppl //父节点是左节点的情况,下面这种 /** * G * P(RED) U */ if ((xppr = xpp.right) != null && xppr.red) { //如果红叔的情况 // 这种情况 /** * G * P(RED) U(RED) * X */ //改变其颜色， xppr.red = false; xp.red = false; xpp.red = true; x = xpp; } else { // 黑叔的情况 // 这种情况 /** * G * P(RED) U(BLACK) */ if (x == xp.right) { //如果插入节点在右边 这种 // 这种情况 /** * G * P(RED) U(BLACK) * X */ //需要进行左旋 root = rotateLeft(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } //左旋后情况都是这种了 /** * G * P(RED) U(BLACK) * X */ // 到这，X只能是左节点了，而且P是红色，U是黑色的情况 if (xp != null) { //把P和G改成黑色，以G为节点进行右旋 xp.red = false; if (xpp != null) { xpp.red = true; root = rotateRight(root, xpp); } } } } else { //父节点在右边的 /** * G * U P(RED) */ //获取U if (xppl != null && xppl.red) { //红父红叔的情况 /** * G * U(RED) P(RED) */ xppl.red = false; xp.red = false; xpp.red = true; x = xpp; } else { if (x == xp.left) { //如果插入的X是右节点 /** * G * U(BLACK) P(RED) * X */ root = rotateRight(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } //右旋后 /** * G * U(BLACK) P(RED) * X */ if (xp != null) { xp.red = false; if (xpp != null) { xpp.red = true; root = rotateLeft(root, xpp); } } } } }
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。