//对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);
}
}
}
}
}