學完了紅黑樹的性質，再來看hashMap源碼就舒服多了，紅黑樹插入後自平衡的情景有很多種，在上一篇紅黑色的部落格中都有提到，還有就是左旋右旋的實作，這裡就不再多說了，直接來撸源碼。
/**
* 插入平衡（分多鐘情況，左旋，右旋）
* @param root 目前根節點
* @param x 目前要插入的節點
* @return 傳回根節點(平衡涉及左旋右旋會将根節點改變，是以需要傳回最新的根節點)
*/
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x) {
x.red = true; //首先将要插入的節點染色成紅色，不要問為什麼不是黑色，因為黑色會破壞黑高(黑色完美平衡)，還是不知道到先去學一下紅黑樹的性 //質再來看
//xp:x的父節點,xpp:x的爺爺節點，xppl:爺爺節點的左子節點，xppr:爺爺節點的右子節點
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { //死循環，直到找到根節點才結束。
if ((xp = x.parent) == null) { //如果目前插入節點的父節點為空，那麼說明目前節點就是根節點，
x.red = false; //染色為黑色（根節點規定為黑色）
return x;
}
else if (!xp.red || (xpp = xp.parent) == null) //如果爸爸節點為黑色或者爺爺節點為空（插入後不影響黑色完美平衡，直接傳回）
return root;
if (xp == (xppl = xpp.left)) { //目前插入節點的父節點為紅色，并且是爺爺節點的左子節點（有兩種情況：LL或者LR）
if ((xppr = xpp.right) != null && xppr.red) { //叔叔節點存在并且為紅色
xppr.red = false; //将爸爸節點和叔叔節點染色成黑
xp.red = false;
xpp.red = true; //将爺爺節點染色成紅
x = xpp; //最後将爺爺節點設定為目前節點進行下一輪操作
}
else { //叔叔節點不存在或者為黑色
if (x == xp.right) { // 目前插入節點是父節點的右子節點（LR的情景）
root = rotateLeft(root, x = xp); //以爸爸節點為旋轉節點進行左旋
xpp = (xp = x.parent) == null ? null : xp.parent; //設定爺爺節點
}
if (xp != null) { //左旋完了之後，就回到了LL的情景(爸爸節點是爺爺節點的左子節點，目前節點是爸爸節點的左子節點)，然後爸爸節點又是紅色，目前插入節點也是紅色，違反了紅黑色的性質，紅色不能兩兩相連，是以接下來需要進行染色；
xp.red = false; //将爸爸節點染色為黑
if (xpp != null) {
xpp.red = true; //将爺爺節點染色為紅，然後在對爺爺節點右旋。
root = rotateRight(root, xpp);
}
}
}
}
else { //爸爸節點是爺爺節點的右子節點，爸爸節點為紅色，也有兩種情況（RR 或者 RL）
if (xppl != null && xppl.red) { //叔叔節點不為空并且為紅色
xppl.red = false; //需要将爸爸節點和叔叔節點染色成黑
xp.red = false;
xpp.red = true; //将爺爺節點染色成紅
x = xpp; //并且爺爺節點設定為目前節點進行下一輪操作
}
else { //叔叔節點不存在或者為黑色
if (x == xp.left) { //目前插入節點是爸爸節點的左子節點(RL的情景)
root = rotateRight(root, x = xp); //先将爸爸節點右旋變成的RR的情景
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) { //這個時候已經變成了RR的情況，需要染色在意爺爺節點左旋來維持平衡
xp.red = false; //将爸爸節點染色為黑
if (xpp != null) {
xpp.red = true; //将爺爺節點染色成紅
root = rotateLeft(root, xpp); //在對爺爺節點左旋
}
}
}
}
}
}
/**
* 左旋
* @param root 目前根節點
* @param p 指定的旋轉節點
* @return 傳回根節點(平衡涉及左旋右旋會将根節點改變，是以需要傳回最新的根節點)
* 左旋示意圖：左旋p節點
pp pp
| |
p r
/ \ ----> / \
l r p rr
/ \ / \
rl rr l rl
左旋做了幾件事？
* 1、将rl設定為p的右子節點，将rl的父節點設定為p
* 2、将r的父節點設定pp,将pp的左子節點或者右子節點設定為r
* 3、将r的左子節點設定為p,将p的父節點設定為r
*/
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,TreeNode<K,V> p) {
// r：旋轉節點的右子節點； pp:旋轉節點的父節點， rl:旋轉節點的右子節點的左子節點
TreeNode<K,V> r, pp, rl;
if (p != null && (r = p.right) != null) { //旋轉節點非空并且旋轉節點的右子節點非空
if ((rl = p.right = r.left) != null) //将p節點的右子節點設定為右子節點的左子節點
rl.parent = p; //将rl的父節點設定為p
if ((pp = r.parent = p.parent) == null)//将r的爸爸節點設定為p的爸爸節點，如果是空的話
(root = r).red = false;//染色成黑
else if (pp.left == p) //判斷父節點是爺爺節點的左子節點還是右子節點
pp.left = r; //如果是左子節點，那麼就把爺爺節點的左子節點設定為r
else
pp.right = r; //如果是右子節點，就把爺爺節點的右子節點設定為r
r.left = p; //最後将r的左子節點設定為p
p.parent = r; //将p的爸爸節點設定為r
}
return root;
}
/**
* 右旋
* @param root 目前根節點
* @param p 指定的旋轉節點
* @return 傳回根節點(平衡涉及左旋右旋會将根節點改變，是以需要傳回最新的根節點)
* 右旋示意圖：右旋p節點
pp pp
| |
p l
/ \ ----> / \
l r ll p
/ \ / \
ll lr lr r
* 右旋都做了幾件事？
* 1.将lr設定為p節點的左子節點，将lr的父節點設定為p
* 2.将l的父節點設定為pp,将pp的左子節點或者右子節點設定為l
* 3.将l的右子節點設定為p,将p的父節點設定為l
*/
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,TreeNode<K,V> p) {
//l:p節點的左子節點 pp:p節點的爸爸節點 lr:p節點的左子節點的右子節點
TreeNode<K,V> l, pp, lr;
if (p != null && (l = p.left) != null) { //旋轉節點p非空并且p節點的左子節點非空
if ((lr = p.left = l.right) != null) //将p節點的左子節點設定為左子節點的右子節點
lr.parent = p; //然後将p節點的左子節點的右子節點的父節點設定為p
if ((pp = l.parent = p.parent) == null) //将p節點的左子節點的父節點設定為p的父節點，如果為空的話，說明l就是根節點了
(root = l).red = false; //染色成黑
else if (pp.right == p) //判斷p節點是pp節點的左子節點還是右子節點，
pp.right = l; //如果p節點是pp節點的右子節點的話，将爸爸節點pp的右子節點設定為l
else //如果p節點是pp節點的左子節點的話，将爸爸節點pp的左子節點設定為l
pp.left = l;
l.right = p; //最後将l節點的右子節點設定為p
p.parent = l; //将p節點的父節點設定為l
}
return root;
}
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)