ConcurrentHashMap基礎
1，ConcurrentHashMap維護了一個Node數組（JDK1.8），儲存了各節點連結清單的頭節點。
2，當連結清單長度超過8時，ConcurrentHashMap會考慮把連結清單轉為紅黑樹，但不一定真的轉。
3，當連結清單長度超過8，但Node數組長度小于64時，優先考慮數組擴容。如果Node數組長度大于64，則把連結清單轉為紅黑樹。
紅黑樹基礎
紅黑樹是一種近似平衡的二叉查找樹，它并非絕對平衡，但是可以保證任何一個節點的左右子樹的高度差不會超過二者中較低的那個的一倍。
紅黑樹有這樣的特點：
1，每個節點要麼是紅色，要麼是黑色。
2，根節點必須是黑色。葉子節點必須是黑色NULL節點。
3，紅色節點不能連續。
4，對于每個節點，從該點至葉子節點的任何路徑，都含有相同個數的黑色節點。
5，能夠以O(log2(N))的時間複雜度進行搜尋、插入、删除操作。此外,任何不平衡都會在3次旋轉之内解決。
ConcurrentHashMap在insert元素時如何平衡紅黑樹
ConcurrentHashMap在insert元素後，會調用balanceInsertion()方法來讓紅黑樹重新恢複平衡。
balanceInsertion()方法來自ConcurrentHashMap的内部類TreeBin，這個類保有紅黑樹根節點引用，也記錄了鎖狀态。
下面看一下balanceInsertion()方法的代碼，然後總結一下大概的邏輯：
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, //root是根節點
TreeNode<K,V> x) { //x是要插入的節點
x.red = true; //節點插入時預設為紅色
/* 變量說明:
* xp:父節點
* xpp:祖父節點
* xppl:祖父節點的左子節點
* xppr:祖父節點的右子節點
*/
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
if ((xp = x.parent) == null) { //父節點是null，說明目前節點是根節點，設為黑色，并傳回
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null) //父節點是黑色，或者祖父節點為空，可以直接插入并傳回
return root;
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); //以祖父節點為中心右旋
}
}
}
}
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); //以祖父節點為中心左旋
}
}
}
}
}
}
總結一下的話，大概是這樣的：
循環開始
if 是根節點：直接置黑，傳回
if 父節點為黑色或祖父節點為空：直接插入，傳回
if 父節點為紅
if 父節點為祖父節點的左子節點
if 叔父節點存在且為紅：直接變色（父節點和叔父節點變黑，祖父節點變紅），下一循環将處理祖父節點
else if 目前節點為右節點（此為内側插入）：左旋（後面右旋），下一循環将處理父節點
else 目前節點為左節點（此為外側插入）或前面左旋了：先變色（父節點變黑，祖父節點變紅），然後右旋
else 父節點為祖父節點的右子節點
if 叔父節點存在且為紅：直接變色，父節點和叔父節點變黑，祖父節點變紅，下一循環将處理祖父節點
else if 目前節點為左節點（此為内側插入）：右旋（後面左旋），下一循環将處理父節點
else 目前節點為右節點（此為外側插入）或前面左旋了：先變色（父節點變黑，祖父節點變紅），然後左旋
循環的出口：目前節點為根節點，或父節點為黑色，或祖父節點為空
一個例子
如果我們要依次往紅黑樹中插入12，1，9，2，圖示如下：
注意：本文的圖中都沒畫出葉子節點
關于左旋的邏輯
1，目前節點X是右子節點時才需要左旋
2，父節點也是紅色時才需要左旋
3，左旋後，父節點成為X的左子節點，X的左子節點成為父節點的右子節點
畫個圖來看就是這樣的：
從圖上看，邏輯并不複雜，左旋也就是逆時針旋轉的含義也很形象，但是代碼寫出來就讓人眼花缭亂，因為代碼要考慮各處null的判斷，而且要完成父子關系的雙向指向，即顯式指定A的左(或右)子節點是B，且B的父節點是A。
方法代碼是這樣的：
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
if (p != null && (r = p.right) != null) { //1 r是p的右子節點，如果r是null就不用左旋了
if ((rl = p.right = r.left) != null) //2 rl是r的左子節點，把p的右子節點設為rl，如果rl不是null，說明r存在非葉子左子節點
rl.parent = p; //把p設為rl的父節點
if ((pp = r.parent = p.parent) == null) //3-1 pp是p的父節點，把pp設為r的父節點，如果pp是null，表示p是root
(root = r).red = false; //把r設為root，改成黑色
else if (pp.left == p) //3-2 如果pp不是null，而且p是pp的左子節點
pp.left = r; //把r設為pp的左子節點
else //3-3 如果pp不是null，而且p是pp的右子節點
pp.right = r; //把r設為pp的右子節點
r.left = p; //4 把p設為r的左子節點
p.parent = r; //5 把r設為p的父節點
}
return root; //傳回root，有可能是最開始的root，也有可能是頂替了原root（也就是p）的r
}
關于右旋的邏輯
1，目前節點X是左子節點時才需要右旋
2，父節點也是紅色時才需要右旋
3，右旋後，父節點成為X的右子節點，X的右子節點成為父節點的左子節點
畫個圖來看就是這樣的：
方法代碼是這樣的：
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) { //1 l是p的左子節點，如果l是null就不用右旋了
if ((lr = p.left = l.right) != null) //2 lr是l的右子節點，把p的左子節點設為lr，如果lr不是null，說明l存在非葉子右子節點
lr.parent = p; //把p設為lr的父節點
if ((pp = l.parent = p.parent) == null) //3-1 pp是p的父節點，把pp設為l的父節點，如果pp是null，表示p是root
(root = l).red = false; //把l設為root，改成黑色
else if (pp.right == p) //3-2 如果pp不是null，而且p是pp的右子節點
pp.right = l; //把l設為pp的右子節點
else //3-3 如果pp不是null，而且p是pp的左子節點
pp.left = l; //把l設為pp的左子節點
l.right = p; //4 把p設為l的右子節點
p.parent = l; //5 把l設為p的父節點
}
return root; //傳回root，有可能是最開始的root，也有可能是頂替了原root（也就是p）的l
}
本文結束