3.5 紅黑樹
3.5.1 樹形化操作
3.5.1.1 操作描述
參照源碼
3.5.1.2 源碼解析
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
//...
// 樹形化準備
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// 對于觸發(fā)了樹形化操作晶伦，但是桶容量還沒達到64的情況下優(yōu)先去做擴容處理孤个，擴容也會分拆鏈表
resize();
// 定位要做樹形下的桶位置晰绎，獲取桶位元素e
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
// 循環(huán)遍歷鏈表中的元素俏让，將其改造成為雙向鏈表結構，表頭元素為hd
do {
// 將e元素封裝成為樹節(jié)點TreeNode
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
// 執(zhí)行樹形化
hd.treeify(tab);
}
}
// 將Node節(jié)點封裝成樹節(jié)點
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
//...
// 樹形化操作
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;//代表根節(jié)點
// 此處循環(huán)將this賦值給x,this代表的是當前樹節(jié)點闸溃，這個類是HashMap的內(nèi)部類用于標識樹節(jié)點潘拱，
// this就是當前類的實例髓梅，也就是一個樹節(jié)點坯苹，但是是哪個樹節(jié)點，就要依靠之間的代碼上下文來判
// 斷了尚辑，看看調(diào)用該方法的地方有這樣的代碼：hd.treeify(tab);這就表示當前節(jié)點就是那額hd節(jié)
// 點北发，而這個hd節(jié)點就是之前改造好的雙向鏈表的表頭結點
// 這里循環(huán)的是雙向鏈表中的元素
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
// root == null的情況是鏈表頭結點的時候才會出現(xiàn)纹因，這時候將這個頭結點作為樹根節(jié)點
x.parent = null;//根節(jié)點無父節(jié)點
x.red = false;//黑色
root = x;//賦值
}
else {
// 這里只有非鏈表頭節(jié)點才能進來
K k = x.key;
int h = x.hash;
Class<?> kc = null;
// 此處循環(huán)的是已構建的紅黑樹的節(jié)點，從根節(jié)點開始琳拨，遍歷比較當前鏈表節(jié)點與當前紅黑樹節(jié)點的
// hash值瞭恰，dir用于保存比較結果，如果當前鏈表節(jié)點小狱庇，則dir為-1惊畏，否則為1恶耽，實際情況卻是，能
// 撥到同一個桶位的所有元素的hash值那是一樣的呀颜启，所以dir的值是無法依靠hash值比較得出結果
// 的偷俭，那么重點就靠最后一個條件判斷來得出結果了，
for (TreeNode<K,V> p = root;;) {
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);// 最后需要依靠這個方法來決定dir的值
TreeNode<K,V> xp = p;
// 根據(jù)dir的值來決定將當前鏈表節(jié)點保存到當前樹節(jié)點的左邊還是右邊缰盏，
// 或者當前鏈表節(jié)點需要與當前樹節(jié)點的左節(jié)點還是右節(jié)點接著比較
// 主要尋找子節(jié)點為null的情況涌萤，將節(jié)點保存到null位置
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
// dir<=0，將鏈表節(jié)點保存到當前樹節(jié)點的左邊子節(jié)點位置
xp.left = x;
else
// dir<=0口猜，將鏈表節(jié)點保存到當前樹節(jié)點的右邊子節(jié)點位置
xp.right = x;
// 一旦添加的一個新節(jié)點负溪，就要進行樹平衡操作，以此保證紅黑樹結構
// 樹的平衡操作依靠的就是其左右旋轉操作
root = balanceInsertion(root, x);
break;
}
}
}
}
// 最后將組裝好的樹的根節(jié)點保存到桶下標位
moveRootToFront(tab, root);
}
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
// 首先定位桶下標位
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
// 校驗當前桶下標位的值是否為根節(jié)點的值济炎，可能會存在不同的原因是樹的平衡操作將原本的根節(jié)點挪移了
// 如果相同川抡，那么不作任何處理，如果不同须尚，就需要替換桶位元素為樹根節(jié)點元素崖堤，然后改變雙向鏈表結構
// 將root根節(jié)點作為雙向鏈表表頭元素,為何要替換呢，因為在判斷桶位元素類型時會對鏈表進行遍歷耐床，如
// 果桶位置放的不是鏈表頭或者尾元素密幔，遍歷將變得非常麻煩
if (root != first) {
Node<K,V> rn;
tab[index] = root;
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
// 校驗鏈表和樹的結構
assert checkInvariants(root);
}
}
//...
}
//...
}
3.5.2 紅黑樹分拆操作
3.5.2.1 操作描述
很簡單，看源碼
3.5.2.2 源碼解析
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
//...
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
//...
// 將一顆大樹分拆為兩顆小樹咙咽，如果樹太小老玛，退化為單向鏈表
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
// this代表當前節(jié)點，也就是樹的根節(jié)點钧敞，桶位節(jié)點
// map代表當前集合
// tab代表新桶數(shù)組
// index代表當前節(jié)點的桶位下標
// bit為舊桶容量
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;// lc表示低位樹容量蜡豹，hc表示高位樹容量
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
// 分拆樹節(jié)點的依據(jù)，結果為0的一組（低位組）溉苛，結果不為0的一組（高位組）
if ((e.hash & bit) == 0) {
// 組裝低位組雙向鏈表
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
// 組裝高位組雙向鏈表
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
// 針對低位組進行樹形化處理镜廉，如果該組元素數(shù)量少于6個則退化為單向鏈表
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
// 針對高位組進行樹形化處理，如果該組元素少于6個則退化為單向鏈表
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
//...
}
//...
}
3.5.3 紅黑樹添加元素操作
3.5.3.1 操作描述
參照源碼
3.5.3.2 源碼解析
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
//...
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
//...
// 紅黑樹的添加元素愚战，map為當前HashMap娇唯，tab為當前桶數(shù)組，h為新增元素的key的hash值寂玲，k為新增元素的key,v為新增元素的value
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
// 當前節(jié)點是已定位的桶位元素塔插，其實就是樹結構的根節(jié)點元素
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
// dir代表當前樹節(jié)點與待添加節(jié)點的hash比較結果
// ph代表當前樹節(jié)點的hash值
// pk代表當前樹節(jié)點的key
// 由于一個桶位的所有元素hash值相等，所以最后得出結果需要依靠
int dir, ph; K pk;
if ((ph = p.hash) > h)
// 如果當前節(jié)點的hash值大拓哟，dir為-1
dir = -1;
else if (ph < h)
// 如果當前節(jié)點的hash值小想许，dir為1
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
// hash值相等的情況下，如果key也一樣直接返回當前節(jié)點，返回去之后會執(zhí)行value的替換操作
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
// 這個找到的q也是與待添加元素key相同的元素流纹，執(zhí)行替換
return q;
}
// 最終需要依靠這個方法來得出dir值的結果
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
// 根據(jù)dir的值來決定是當前節(jié)點的左側還是右側糜烹，如果該側右子節(jié)點則繼續(xù)循環(huán)尋找位置，否則直接將新元素添加到該側子節(jié)點位置
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);//封裝樹節(jié)點
if (dir <= 0)
// dir<=0漱凝，將新節(jié)點添加到當前節(jié)點左側
xp.left = x;
else
// 否則將新節(jié)點添加到當前節(jié)點右側
xp.right = x;
// 設置新節(jié)點的鏈表位置疮蹦，將其作為xp的下級節(jié)點
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
// 如果xp節(jié)點原本有下級節(jié)點xpn，則要將新節(jié)點插入到xp和xpn之間（指雙向鏈表中）
((TreeNode<K,V>)xpn).prev = x;
// 插入了新節(jié)點之后茸炒，要進行樹平衡操作愕乎，平衡操作完成，將根節(jié)點設置為桶位節(jié)點
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
// 一般我們在HashMap中保存的鍵值對的類型都是不變的壁公，這一般用泛型控制妆毕，
// 那么就意味著，兩個元素的key的類型時一樣的贮尖，所以才需要靠其hashCode來決定大小
// System.identityHashCode(parameter)是本地方法，用于獲取和hashCode一樣的結果趁怔，
// 這里的hashCode指的是默認的hashCode方法湿硝，與某些類重寫的無關
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;
}
//...
}
//...
}
3.5.4 紅黑樹添加元素平衡操作
3.5.4.1 操作描述
3.5.4.1.1 左旋操作描述
繞A節(jié)點左旋，等于將A的右子節(jié)點B甩上來替換自己的位置润努，而自己順勢下沉成為其左子節(jié)點关斜，這時你會發(fā)現(xiàn)，B有三個子節(jié)點铺浇，明顯結構不對痢畜，將B的原來的左子節(jié)點C轉移到下沉的A上，成為其右子節(jié)點鳍侣，旋轉結束
其實丁稀，要保證左子樹節(jié)點值小于其根節(jié)點，右子樹節(jié)點值大于其根節(jié)點倚聚，那么在替換AB節(jié)點之后线衫，C節(jié)點的值就出現(xiàn)了問題，只有將其挪到A節(jié)點右邊才能繼續(xù)保證上面的結構惑折。
首先我們知道B節(jié)點為A的右節(jié)點授账，那么B>A，而C為B的左節(jié)點惨驶，則C<B,而C又位于A的右子樹白热，則C>A,因此：A<C<B。要保證這個式子永遠成立粗卜，就必須依靠挪移節(jié)點來完成屋确。
現(xiàn)在B為最頂部節(jié)點且為最大值，那么A和C必須位于其左子樹，而C>A則乍恐，C必須位于A的右子樹评疗，再看看之前的情況，如果A為頂點節(jié)點茵烈，那么BC均應位于其右子樹百匆，而B>C，那么要么B為C的右節(jié)點呜投，要么C為B的左節(jié)點
3.5.4.1.2 右旋操作描述
繞A幾點右旋加匈，等于將A的左子節(jié)點B甩上來替換自己的位置，而自己順勢下沉成為其右子節(jié)點仑荐，這是你會發(fā)現(xiàn)雕拼，B有三個子節(jié)點，明顯結構不對粘招，將B的原來的右子節(jié)點C轉移到下沉的A上啥寇，成為其左子節(jié)點，旋轉結束
首先我們知道B為A的左子節(jié)點洒扎，所以B<A,再者C為B的右子節(jié)點辑甜，那么C>B，而C又位于A的左子樹袍冷，則C<A,最后：A>C>B磷醋。要保證這個結果成立，那么再B替換A的位置之后胡诗，A下沉為B的右子節(jié)點邓线，因為A>B,所以往右走，
這時C和A均位于B的右側煌恢，比較二者發(fā)現(xiàn)C<A骇陈，那么將C放到A的左側成為其左子節(jié)點
3.5.4.1.3 添加平衡操作描述
新增節(jié)點全部初始化為紅色節(jié)點，然后分以下幾種情況：
- 新增節(jié)點為根節(jié)點：顏色置黑症虑；
- 新增節(jié)點父節(jié)點為黑色節(jié)點或者父節(jié)點是根節(jié)點（原本為黑色）：不操作缩歪；
- 新增節(jié)點x的父節(jié)點為其父節(jié)點（x祖節(jié)點）的左子節(jié)點：
- x祖父節(jié)點的右子節(jié)點存在并為紅色（那么x祖父節(jié)點一定是黑色節(jié)點）：將x的祖父節(jié)點置為紅色，x的父節(jié)點和其兄弟節(jié)點置為黑色谍憔，然后以x的祖父節(jié)點為新的x執(zhí)行循環(huán)匪蝙；
- x祖父節(jié)點無右子節(jié)點或為黑色節(jié)點：
- 如果x是其父節(jié)點的右子節(jié)點：執(zhí)行以x父節(jié)點xp為基準的左旋操作，x被甩上來替換xp的位置习贫，并置黑逛球，原x祖父節(jié)點（現(xiàn)x節(jié)點父節(jié)點）置紅，然后以該祖父節(jié)點右旋苫昌，之后x節(jié)點再次被甩上來替換了祖父節(jié)點xpp的位置颤绕，然后以xp為新的x執(zhí)行循環(huán)
- 新增節(jié)點x的父節(jié)點為其父節(jié)點的右子節(jié)點：
- x祖父節(jié)點的左子節(jié)點存在并為紅色（那么x祖父節(jié)點一定為黑色節(jié)點）：將x的祖父節(jié)點置為紅色，x的父節(jié)點和其兄弟節(jié)點置為黑色，然后以x的祖父節(jié)點為新的x執(zhí)行循環(huán)奥务；
- x祖父節(jié)點無左子節(jié)點或為黑色節(jié)點：
- 如果x是其父節(jié)點的左子節(jié)點：執(zhí)行以x父節(jié)點xp為基準的右旋操作物独，x被甩上來替換xp的位置，并置黑氯葬，原x祖父節(jié)點（現(xiàn)x節(jié)點父節(jié)點）置紅挡篓，然后以該祖父節(jié)點右旋，之后x節(jié)點再次被甩上來替換了祖父節(jié)點xpp的位置帚称，然后以xp為新的x執(zhí)行循環(huán)
3.5.4.2 源碼解析
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
//...
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
//...
// 左旋操作官研，其中root為根節(jié)點，p為當前節(jié)點闯睹，r為p的右節(jié)點戏羽，rl為r的左節(jié)點，pp為p的父節(jié)點
// 左旋之后楼吃，r替換p的位置始花，rl挪到p的右節(jié)點
// 節(jié)點位置變換之后，既要改變其父節(jié)點的left/right值孩锡，也要改變當前節(jié)點中parent的值衙荐，
// 改變是雙向的，父子均有指向浮创，改變之后均要修改
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) {
// 首先將r節(jié)點的左子節(jié)點(rl)送給p當其右子節(jié)點
if ((rl = p.right = r.left) != null)
rl.parent = p;//變換rl的父節(jié)點為p,原來為r
if ((pp = r.parent = p.parent) == null)
// 原p節(jié)點為根節(jié)點的情況，r替換之后砌函，需要重新著色為黑色斩披，保證根節(jié)點為黑色
(root = r).red = false;
else if (pp.left == p)
// 原p節(jié)點為其父節(jié)點pp的左子節(jié)點的情況，r替換后讹俊，需要修改pp節(jié)點的left指向r節(jié)點
pp.left = r;
else
// 原p節(jié)點為其父節(jié)點pp的右子節(jié)點的情況垦沉，r替換后，需要修改pp節(jié)點的right指向r節(jié)點
pp.right = r;
//然后將p節(jié)點作為r節(jié)點的左子節(jié)點仍劈，即為p節(jié)點順勢下沉為r的左子節(jié)點
r.left = p;
p.parent = r;//變換p的父節(jié)點為r
}
return root;
}
// 右旋操作厕倍，嘿，那就是左旋的反向操作罷了
// root為根節(jié)點贩疙，p為當前節(jié)點讹弯，l為其左子節(jié)點，lr為l的右子節(jié)點这溅，pp為p的父節(jié)點
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) {
// 首先將l的右子節(jié)點lr挪給p
if ((lr = p.left = l.right) != null)
lr.parent = p;//變換lr的父節(jié)點為p,原來為l
if ((pp = l.parent = p.parent) == null)
// 如果p節(jié)點是根節(jié)點组民，替換為l之后，l便成為新的根節(jié)點悲靴，需要重新著色為黑色臭胜，保證紅黑樹結構
(root = l).red = false;
else if (pp.right == p)
// 如果原p節(jié)點是其父節(jié)點pp的右子節(jié)點，那么需要將其右子節(jié)點改成l
pp.right = l;
else
// 如果原p節(jié)點是其父節(jié)點pp的左子節(jié)點，那么需要將其左子節(jié)點改成l
pp.left = l;
// 最后將原p節(jié)點置為l節(jié)點的右子節(jié)點耸三，并修改p的父節(jié)點為l
l.right = p;
p.parent = l;
}
return root;
}
// 平衡操作,x為新增節(jié)點乱陡，root為根節(jié)點
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true;// 新增節(jié)點全部為紅色節(jié)點
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
if ((xp = x.parent) == null) {
// 1 x為根節(jié)點的情況，將其重新著色為黑色
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null)
// 2 如果x節(jié)點的父節(jié)點為黑色仪壮，又或者x的父節(jié)點是根節(jié)點憨颠，沒有影響，不操作
return root;
if (xp == (xppl = xpp.left)) {
// 3 如果x節(jié)點的父節(jié)點是其父節(jié)點（x的祖父節(jié)點）的左子節(jié)點
if ((xppr = xpp.right) != null && xppr.red) {
// 3-1 再如果x的祖父節(jié)點的右子節(jié)點存在且為紅色睛驳，則將這個節(jié)點和x的父節(jié)點統(tǒng)統(tǒng)改成黑色烙心，
// 再把x的祖父節(jié)點改成紅色，將x祖父節(jié)點作為新的x節(jié)點執(zhí)行循環(huán)
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
// 3-2 否則的情況
if (x == xp.right) {
// 3-2-1 如果x節(jié)點是其父節(jié)點的右子節(jié)點乏沸，則執(zhí)行以x父節(jié)點為基準的左旋操作淫茵，
// 左旋之后新增節(jié)點x替了其原父節(jié)點xp，將原xp節(jié)點當做現(xiàn)在的x節(jié)點蹬跃，原來的x
// 節(jié)點是現(xiàn)在x節(jié)點的父節(jié)點xp,原來的x節(jié)點的祖父節(jié)還是現(xiàn)在x的祖父節(jié)點
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {// xp為原來的x節(jié)點
// 將xp節(jié)點置為黑色
xp.red = false;
if (xpp != null) {// xpp還是之前的xpp
// 將xpp節(jié)點置為紅色匙瘪，然后執(zhí)行右旋,右旋可以將xpp節(jié)點用xp節(jié)點替換，紅黑交換
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
else {
// 4 如果x節(jié)點的父節(jié)點是其父節(jié)點（x的祖父節(jié)點）的右子節(jié)點
if (xppl != null && xppl.red) {
// 4-1 再如果x的祖父節(jié)點的左子節(jié)點存在并且為紅色蝶缀，則將該節(jié)點置為黑色丹喻，
// 將x的父節(jié)點置為黑色，祖父節(jié)點置為紅色翁都，然后把xpp祖父節(jié)點作為新的x節(jié)點
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
// 4-2 否則的情況
if (x == xp.left) {
// 4-2-1 如果x節(jié)點是其父節(jié)點的左子節(jié)點的情況碍论，先以x父節(jié)點進行右旋，
// 右旋之后原來的xp節(jié)點被新的x節(jié)點替換柄慰，原來的xp節(jié)點作為新xp節(jié)點的右子節(jié)點鳍悠，
// 現(xiàn)在看作為x,然后重新定義xpp，其實xpp位置不變
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
// 將現(xiàn)在的xp節(jié)點置為黑色
xp.red = false;
if (xpp != null) {
// 將祖父節(jié)點置為紅色坐搔。然后執(zhí)行左旋藏研，左旋之后，原來的xp節(jié)點接替了xpp節(jié)點的位置概行，xpp變成原來xp的左子節(jié)點
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
//...
}
//...
}
3.5.5 紅黑樹刪除元素操作
3.5.5.1 操作描述
紅黑樹的節(jié)點刪除操作主要分為這么三種：
- 待刪節(jié)點沒有子節(jié)點
- 待刪節(jié)點有一個子節(jié)點
- 待刪節(jié)點有兩個子節(jié)點
針對第一種情況蠢挡，真的好簡單，待刪節(jié)點即為葉子節(jié)點凳忙，直接刪除即可业踏；
針對第二種情況，也不難涧卵，將那個子節(jié)點替換待刪節(jié)點即可堡称；
至于第三種情況，那就麻煩了艺演，但通過變換却紧，可以將其轉化為第一種或者第二種情況：處理方式是桐臊，找到待刪節(jié)點的右子樹中的最左節(jié)點（或者左子樹中的最右節(jié)點），將其與待刪節(jié)點互換位置晓殊，然后就將情況轉換為第一種或者第二種了断凶。
針對第三種情況轉換方法的解析：為什么要找到待刪節(jié)點的右子樹最左節(jié)點呢，因為紅黑樹是二叉搜索樹巫俺，這個二叉搜索樹中滿足"左子節(jié)點<其父節(jié)點<其父節(jié)點的右子節(jié)點"的規(guī)則认烁，那么找到的右子樹的最左節(jié)點，就是整顆樹中大于待刪節(jié)點值的最小值節(jié)點了介汹，為了保證二叉搜索樹的搜索結構（也就是剛剛那個公式）却嗡，我們只能找最接近待刪節(jié)點值的節(jié)點值來接替它的位置，如此能保證二叉搜索的結構嘹承，但是可能會破壞紅黑樹的結構窗价，因為如果待刪節(jié)點為紅色，而替換節(jié)點為黑色的話叹卷，那豈不是在待刪節(jié)點分支多加了一個黑色節(jié)點嘛撼港，還有其他各種情況，種種骤竹，需要進行刪除節(jié)點后的樹平衡操作來保證紅黑樹的結構完整帝牡。
下面重點說說刪除后的平衡問題：
其實只要待刪節(jié)點是黑色節(jié)點，一旦刪除必然會導致分支中黑色節(jié)點缺一（紅黑樹不再平衡）蒙揣，具體情況又分為以下幾種：（基礎條件：待刪節(jié)點p為黑色靶溜，其只有一個子節(jié)點x，操作在待刪節(jié)點被刪除之后懒震，子節(jié)點替換其位置之后）
- 如果子節(jié)點x為紅色節(jié)點墨技，那么只需要將其置黑即可;
- 如果子節(jié)點x為黑色節(jié)點，為保證本分支黑色節(jié)點不會再變少挎狸，那么只能求助于其兄弟節(jié)點分支了：
- x為左子節(jié)點：
- x無兄弟節(jié)點xpr:以x的父節(jié)點xp為基準進行循環(huán)；
- x有兄弟節(jié)點xpr：
- xpr為紅色節(jié)點(那么xp必然為黑色節(jié)點)：將xp置紅断楷，xpr置黑锨匆，以xp為基準左旋；
解析：開始情況是x分支刪除了一個黑色節(jié)點冬筒，即x分支缺少一個黑色幾點恐锣，而x的兄弟節(jié)點xpr為紅色節(jié)點，xp為黑色節(jié)點舞痰，我們將xp和xpr顏色互換土榴，那么在xpr分支黑色節(jié)點數(shù)量是不變的（只是位置變了），然后我么以紅色的xp為基準執(zhí)行左旋,將黑色的xpr甩上去替換xp的位置响牛，xp作為xpr的左子節(jié)點玷禽，那么x端分支便多出了xpr這個黑色節(jié)點來補足不夠的數(shù)量赫段，而兄弟分支黑色節(jié)點數(shù)量還是不變的矢赁。 - xpr為黑色節(jié)點(那么xp顏色不明)：
- 兄弟節(jié)點的左子節(jié)點和右子節(jié)點全null或全黑或一黑一null：將兄弟節(jié)點置紅糯笙，然后以xp為基準進行循環(huán)；
- 兄弟節(jié)點的左子節(jié)點和右子節(jié)點全紅或一紅一null或一紅一黑：
- 兄弟節(jié)點的右子節(jié)點為黑色或null撩银，即兄弟節(jié)點的左子節(jié)點為紅色：將兄弟節(jié)點與其做自己節(jié)點交換顏色给涕，兄弟節(jié)點置紅，左子節(jié)點置黑额获，然后以兄弟節(jié)點為基準執(zhí)行右旋操作够庙，將其黑色的左子節(jié)點甩上去做自己的父節(jié)點，自己做其右子節(jié)點抄邀，然后將新的兄弟節(jié)點xpr(原來的xprl)的顏色置為與xp一致（不明耘眨，非黑即白），新的sr(即原來的xpr)置黑（這個置黑的原因是因為右旋操作之前執(zhí)行了顏色替換撤摸，兄弟節(jié)點右側分支少了一個黑色節(jié)點毅桃，右旋之后變?yōu)楹谏膕l補充了這個黑色節(jié)點，但是現(xiàn)在我們要用sl[新xpr]來替換xp節(jié)點[置為xp節(jié)點的顏色]准夷，那么右側分支原本用來補充之前缺少的黑色節(jié)點又消失了钥飞，所以將已知的紅色節(jié)點sr置為黑色來進行補充），xp置黑衫嵌，以xp左旋读宙，xpr被甩上來替換xp的位置，xp則是補充給x分支的黑色節(jié)點楔绞，xpr與以前的xp顏色一致结闸，所以兄弟分支黑色節(jié)點不變。
解析：新的sr(即原來的xpr)的原因是因為右旋操作之前執(zhí)行了顏色替換酒朵，兄弟節(jié)點右側分支少了一個黑色節(jié)點桦锄，右旋之后變?yōu)楹谏膕l補充了這個黑色節(jié)點，但是現(xiàn)在我們要用sl[新xpr]來替換xp節(jié)點[置為xp節(jié)點的顏色]蔫耽，那么右側分支原本用來補充之前缺少的黑色節(jié)點又消失了结耀，所以將已知的紅色節(jié)點sr置為黑色來進行補充）
- 兄弟節(jié)點的右子節(jié)點為黑色或null撩银，即兄弟節(jié)點的左子節(jié)點為紅色：將兄弟節(jié)點與其做自己節(jié)點交換顏色给涕，兄弟節(jié)點置紅，左子節(jié)點置黑额获，然后以兄弟節(jié)點為基準執(zhí)行右旋操作够庙，將其黑色的左子節(jié)點甩上去做自己的父節(jié)點，自己做其右子節(jié)點抄邀，然后將新的兄弟節(jié)點xpr(原來的xprl)的顏色置為與xp一致（不明耘眨，非黑即白），新的sr(即原來的xpr)置黑（這個置黑的原因是因為右旋操作之前執(zhí)行了顏色替換撤摸，兄弟節(jié)點右側分支少了一個黑色節(jié)點毅桃，右旋之后變?yōu)楹谏膕l補充了這個黑色節(jié)點，但是現(xiàn)在我們要用sl[新xpr]來替換xp節(jié)點[置為xp節(jié)點的顏色]准夷，那么右側分支原本用來補充之前缺少的黑色節(jié)點又消失了钥飞，所以將已知的紅色節(jié)點sr置為黑色來進行補充），xp置黑衫嵌，以xp左旋读宙，xpr被甩上來替換xp的位置，xp則是補充給x分支的黑色節(jié)點楔绞，xpr與以前的xp顏色一致结闸，所以兄弟分支黑色節(jié)點不變。
- xpr為紅色節(jié)點(那么xp必然為黑色節(jié)點)：將xp置紅断楷，xpr置黑锨匆，以xp為基準左旋；
- x為右子節(jié)點：與上面的情況正好對稱（不再介紹）
- x為左子節(jié)點：
貌似有點難...大家要看進去思考才能理解，光看沒用匙铡！
3.5.5.2 源碼解析
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
//...
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
//...
// 當前節(jié)點即為要刪除的節(jié)點图甜，map為當前集合，tab為當前桶數(shù)組
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n;
if (tab == null || (n = tab.length) == 0)
return;
// 定位待刪節(jié)點的桶位下標index
int index = (n - 1) & hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
if (pred == null)
// 如果當前節(jié)點是雙向鏈表頭節(jié)點/樹根節(jié)點,則將鏈表第二元素置為桶位元素鳖眼，即刪除該節(jié)點
tab[index] = first = succ;
else
// 如果當前節(jié)點不是雙向鏈表頭節(jié)點黑毅，則將其后置節(jié)點賦給其前置節(jié)點作為后置節(jié)點，即刪除該節(jié)點
pred.next = succ;
if (succ != null)
// 修改后置節(jié)點中prev指向新的前置元素節(jié)點
succ.prev = pred;
if (first == null)
return;
if (root.parent != null)
root = root.root();
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
// 退化為鏈表機構
tab[index] = first.untreeify(map); // too small
return;
}
//// 之前的操作是在雙向鏈表中刪除當前節(jié)點的痕跡钦讳，下面是在樹結構中刪除的操作
// p為待刪節(jié)點（即當前節(jié)點）矿瘦，pl為p的左子節(jié)點枕面，pr為p的右子節(jié)點，
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
if (pl != null && pr != null) {
// 當前節(jié)點同時擁有左右子節(jié)點的情況,sl表示當前節(jié)點的右子樹的最左節(jié)點
// 要刪除當前節(jié)點匪凡，需要找到與當前節(jié)點值最靠近的左右兩側的節(jié)點之一膊畴，這
// 里找的是右側的，即找的是整個樹中大于當前節(jié)點值的最小值節(jié)點病游，將找到
// 的節(jié)點與待刪節(jié)點互換唇跨，互換之后再刪除節(jié)點，如果原來的那個最左節(jié)點還
// 有右子節(jié)點衬衬，則將該右子節(jié)點替換其父節(jié)點（待刪節(jié)點）
TreeNode<K,V> s = pr, sl;
while ((sl = s.left) != null) // find successor
s = sl;// 找到右子樹的最左節(jié)點
boolean c = s.red; s.red = p.red; p.red = c; // swap colors 首先互換顏色
TreeNode<K,V> sr = s.right;// s為最左節(jié)點买猖，那么它不可能有左子節(jié)點，最多有右子節(jié)點
TreeNode<K,V> pp = p.parent;
if (s == pr) { // p was s's direct parent
// 如果找到的s即為待刪節(jié)點的直接右子節(jié)點（說明s無左子節(jié)點）滋尉，那么直接替換這兩個節(jié)點
p.parent = s;
s.right = p;
}
else {
// 否則的情況玉控，先找到s的父節(jié)點sp,將其設置為p的父節(jié)點，
TreeNode<K,V> sp = s.parent;
if ((p.parent = sp) != null) {
if (s == sp.left)
// 將p作為原來s的父節(jié)點的左子節(jié)點（即替換p和s的位置）
sp.left = p;
else
// TODO 這里是什么意思呢?找的就是sp的最左節(jié)點狮惜，這里怎么跑到右節(jié)點上去了呢高诺，雖然p是要刪除的節(jié)點
sp.right = p;
}
// 把p的右子節(jié)點pr置為s的右子節(jié)點
if ((s.right = pr) != null)
// 把s置為pr的父節(jié)點
pr.parent = s;
}
// 替換之后p是無左子節(jié)點的，（即原來的s是最左節(jié)點碾篡，無左子節(jié)點）
p.left = null;
// 把s的右子節(jié)點sr置為p的右子節(jié)點
if ((p.right = sr) != null)
// 把sr的父節(jié)點設置為p
sr.parent = p;
if ((s.left = pl) != null)
// 將p的左子節(jié)點置為s的左子節(jié)點
pl.parent = s;
// 把p的父節(jié)點設置為s的父節(jié)點
if ((s.parent = pp) == null)
// 如果p沒有父節(jié)點虱而，將s節(jié)點設置為根節(jié)點
root = s;
// 否則如果p是其父節(jié)點pp的左子節(jié)點
else if (p == pp.left)
// 現(xiàn)在將s設置為pp的左子節(jié)點
pp.left = s;
else
// 否則如果p是其父節(jié)點的右子節(jié)點，則將s設置為pp的右子節(jié)點
pp.right = s;
if (sr != null)
// 如果s存在右子節(jié)點开泽，則將其置為replacement,現(xiàn)在和待刪節(jié)點只有右子節(jié)點的情況一樣
replacement = sr;
else
// 否則將p置為replacement,至此第一種情況替換結束牡拇，現(xiàn)在和待刪節(jié)點沒子節(jié)點的情況一樣
replacement = p;
}
else if (pl != null)
// 待刪節(jié)點只有左子節(jié)點的情況，將其左子節(jié)點置為replacement
replacement = pl;
else if (pr != null)
// 當前節(jié)點只有右子節(jié)點的情況穆律，將其右子節(jié)點置為replacement
replacement = pr;
else
// 待刪節(jié)點沒有子節(jié)點的情況惠呼，直接將其設置為replacement
replacement = p;
if (replacement != p) {// 如果待刪節(jié)點有子節(jié)點replacement的情況
// 準備替換replacement節(jié)點和p節(jié)點
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)
// 待刪節(jié)點p為根節(jié)點的情況,將replacement設置為根節(jié)點即可
root = replacement;
else if (p == pp.left)
// p是作為其父節(jié)點pp的左子節(jié)點，則將replacement設置為pp的左子節(jié)點
pp.left = replacement;
else
// 否則p是作為其父節(jié)點pp的右子節(jié)點峦耘，則將replacement設置為pp的右子節(jié)點
pp.right = replacement;
// 最后將p節(jié)點的所有關系置空
p.left = p.right = p.parent = null;
}
// 如果待刪節(jié)點是紅色節(jié)點則不影響平衡剔蹋，無需執(zhí)行樹平衡操作，否則需要進行樹平衡操作
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
// 如果p節(jié)點沒有任何子節(jié)點的情況
if (replacement == p) { // detach
// 根據(jù)實際情況置空p節(jié)點的各屬性
TreeNode<K,V> pp = p.parent;
p.parent = null;
if (pp != null) {
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null;
}
}
if (movable)
// 如果可移動辅髓，那么將根節(jié)點設置為桶位節(jié)點
moveRootToFront(tab, r);
}
// 刪除節(jié)點后的平衡操作泣崩，root為根節(jié)點，x為上面提到的replacement節(jié)點利朵，該節(jié)點其實為替換p節(jié)點，為其子節(jié)點
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
TreeNode<K,V> x) {
for (TreeNode<K,V> xp, xpl, xpr;;) {
if (x == null || x == root)
// 如果x不存在或者其本來就是根節(jié)點猎莲，字節(jié)返回根節(jié)點
return root;
else if ((xp = x.parent) == null) {
// 如果x節(jié)點不存在父節(jié)點绍弟，那么則其為根節(jié)點，但是還未設置為root節(jié)點著洼，那么直接置黑色樟遣，并將其設置為root節(jié)點
x.red = false;
return x;
}
else if (x.red) {
// 如果x是紅色節(jié)點而叼，則將其置黑，因為如果x為紅色豹悬，那么其父節(jié)點p必然為黑色葵陵，
// 刪掉之后，會導致黑色節(jié)點減少瞻佛，正好x為紅色拿來補充黑色節(jié)點脱篙，使黑色節(jié)點數(shù)不變，
// 如果x是黑色伤柄，那么就會導致當前分支黑色節(jié)點減少绊困，需要使用其他方法進行平衡
x.red = false;
return root;
}
// 如果x為其父節(jié)點左子節(jié)點（刪除后的結果）
else if ((xpl = xp.left) == x) {
// 如果x存在兄弟節(jié)點（其父節(jié)點的右子節(jié)點），且為紅色适刀，那么xp必定為黑色
// 那么就表明x節(jié)點分支的黑色節(jié)點少了一個秤朗，也就是其兄弟節(jié)點多一個（其他所有分支都多一個），
if ((xpr = xp.right) != null && xpr.red) {
// 那么將兄弟節(jié)點置黑笔喉，父節(jié)點置紅取视，這是x分支還是少一個黑節(jié)點，兄弟分支黑節(jié)點不變
xpr.red = false;
xp.red = true;
// 再然后執(zhí)行xp節(jié)點的左旋常挚，將其右子節(jié)點（即x的兄弟節(jié)點）甩上去作谭，
// xp作為其左子節(jié)點，如此一來將兄弟節(jié)點這一黑色幾點變成兩份之共享待侵，
// 無形之中使得x分支黑色節(jié)點加1丢早，從而達到平衡
root = rotateLeft(root, xp);
xpr = (xp = x.parent) == null ? null : xp.right;
}
if (xpr == null)
x = xp;// 如果x沒有兄弟節(jié)點，那么循環(huán)以x的父節(jié)點為基準再次進行平衡
else {
// 否則秧倾，那就是x存在兄弟節(jié)點怨酝，且為黑色的情況，則其父節(jié)點顏色不明那先，x顏色不明
// sl為兄弟節(jié)點的左子節(jié)點农猬，sr為兄弟節(jié)點右子節(jié)點
TreeNode<K,V> sl = xpr.left, sr = xpr.right;
// 如果sr和sl中，全部為null,或者全部為黑色節(jié)點售淡，或者有一個為黑色節(jié)點斤葱，另一個是null
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
// 將兄弟節(jié)點置為紅色
xpr.red = true;
x = xp;// 為了循環(huán)
}
// 否則，就是sl和sr全為紅色或者一紅一null揖闸，或者一紅一黑
else {
// 如果sr為null(則sl必為紅色)弧呐，或者sr為黑色（則sl必為紅色）
if (sr == null || !sr.red) {
if (sl != null)
// 將sl置為黑色
sl.red = false;
// 兄弟節(jié)點置紅
xpr.red = true;
// 然后右旋兄弟節(jié)點凑耻，將其左子節(jié)點甩上去做自己的父節(jié)點，這時兄弟分支黑節(jié)點數(shù)量不變
root = rotateRight(root, xpr);
xpr = (xp = x.parent) == null ?
null : xp.right;// 更新xpr的指向,將其指向旋轉之后新的兄弟節(jié)點，即原來的sl(黑色)
}
if (xpr != null) {
// 將xp和xpr顏色弄一致盾舌，因為如果xp是黑色脊奋，左旋之后兄弟分支會少一個黑節(jié)點，
// 這樣xpr就會補充這個黑色，如果xp是紅色幔烛，那么xpr也是紅色，左旋之后xpr落座
// xp的位置囊蓝，還是原來的顏色饿悬，而左側確多出了xp這個黑色節(jié)點。
xpr.red = (xp == null) ? false : xp.red;
if ((sr = xpr.right) != null)
// 將sr置黑即把原來的xpr置黑
sr.red = false;
}
if (xp != null) {
// 將xp置黑
xp.red = false;
// 然后在執(zhí)行xp左旋聚霜，等于將sl甩到了xp的位置狡恬，
// 而且這個sl必然為黑色，是為了補充x分支缺少的那一個黑節(jié)點
root = rotateLeft(root, xp);
}
x = root;
}
}
}
// 否則如果x是其父節(jié)點的右子節(jié)點的話
else { // symmetric （對稱的）
if (xpl != null && xpl.red) {
xpl.red = false;
xp.red = true;
root = rotateRight(root, xp);
xpl = (xp = x.parent) == null ? null : xp.left;
}
if (xpl == null)
x = xp;
else {
TreeNode<K,V> sl = xpl.left, sr = xpl.right;
if ((sl == null || !sl.red) &&
(sr == null || !sr.red)) {
xpl.red = true;
x = xp;
}
else {
if (sl == null || !sl.red) {
if (sr != null)
sr.red = false;
xpl.red = true;
root = rotateLeft(root, xpl);
xpl = (xp = x.parent) == null ?
null : xp.left;
}
if (xpl != null) {
xpl.red = (xp == null) ? false : xp.red;
if ((sl = xpl.left) != null)
sl.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateRight(root, xp);
}
x = root;
}
}
}
}
}
//...
}
//...
}
四俯萎、總結
HashMap中涉及到了數(shù)組操作傲宜，單向鏈表操作，雙向鏈表操作夫啊，紅黑樹操作：
數(shù)組操作:
- HashMap中的數(shù)組指的就是桶數(shù)組函卒，用于承載鏈表（的頭結點）和紅黑樹（根節(jié)點）
- 數(shù)組的創(chuàng)建在第一次往集合中添加元素的時候進行，默認的數(shù)組長度為16撇眯，也可以手動指定报嵌，系統(tǒng)會自動計算一個大于等于給定容量的最小的2的次冪的容量值作為數(shù)組初始容量，數(shù)組的最大容量為不超過兩倍的Integer的最大限值熊榛。數(shù)組還有一個負載因子锚国，默認為0.75，這個值可算是一個時間空間的折中了玄坦，一般不會手動修改血筑，但也能手動指定，如果設置過大煎楣，查詢消耗增加豺总，如果設置過小，空間消耗增加择懂。
- 當向集合中添加一個新元素的時候喻喳，通過元素的key的hash算法結果來定位其在數(shù)組中的位置,這個hash算法要選擇的足夠好來使得元素能夠盡量平均的散布在數(shù)組的各個位置，而不是堆積在幾處困曙。
- 數(shù)組的容量是不可變的表伦，所以一旦原數(shù)組容量受限，一般是創(chuàng)建新的數(shù)組來替代慷丽，這叫數(shù)組的擴容蹦哼，擴容需要滿足一定的條件，HashMap中有一個閾值用于作為擴容的條件要糊，這個值是當前容量和負載因子的乘積纲熏，只要當前的集合的元素數(shù)量達到了閾值，就要執(zhí)行擴容操作，當然還有一種情況也要擴容赤套，那就是在單個數(shù)組位上的元素數(shù)量達到8個時，但數(shù)組容量未達到64個時珊膜，優(yōu)先執(zhí)行數(shù)組擴容容握。數(shù)組擴容后新數(shù)組為原數(shù)組的2倍容量。
單向鏈表操作：
- hashMap是依靠hash來存儲元素的车柠，hash存儲總是難以避免碰撞的出現(xiàn)剔氏，HashMap使用單向鏈表來保存發(fā)生碰撞的元素。新元素會保存到鏈表的尾部竹祷，如果新元素的key已經(jīng)存在谈跛，那么將會是一個更新操作，不會有新元素增加塑陵。
- 數(shù)組擴容的時候需要進行元素的遷移感憾，這里就是鏈表的遷移，鏈表遷移的時候會觸發(fā)鏈表分拆令花，將一個完整鏈表分拆成為兩個鏈表阻桅，我們成為低位鏈表和高位鏈表，低位鏈表的數(shù)組位置同舊數(shù)組兼都，而高位鏈表的數(shù)組位置為低位鏈表數(shù)組位+舊數(shù)組容量嫂沉。可見通過鏈表分拆也是可以降低鏈表中元素數(shù)量的扮碧。
- 在Jdk1.8以前的版本中在高并發(fā)的情況下趟章，HashMap數(shù)組擴容的時候可能會出現(xiàn)死循環(huán)，這是因為兩個線程同時進行擴容和元素遷移時慎王，由于再次對鏈表元素進行循環(huán)頭插法存儲元素蚓土，極可能就會導致出現(xiàn)了循環(huán)引用，Jdk1.8中已經(jīng)修復這一Bug柬祠，采用的是將頭插法改為尾插法北戏，而且遷移元素的方式也發(fā)生了變化，但是HashMap仍然是線程不安全的集合漫蛔，多線程環(huán)境中最好使用ConcurrentHashMap嗜愈。
雙向鏈表操作：
- hashMap中存在雙向鏈表，他是在單向鏈表元素達到8個莽龟，且數(shù)組容量達到64位之后執(zhí)行樹形化時轉換的蠕嫁，也就是說，HashMap中的紅黑樹同時也是一個雙向鏈表毯盈。這個雙向鏈表的作用是在某些特殊情況下（樹太小的時候）剃毒，在將紅黑樹退化為單向鏈表結構時使用的。正因為如此，在紅黑樹的增刪節(jié)點赘阀、平衡節(jié)點的時候還需要保證雙向鏈表的結構益缠。
紅黑樹操作：
- 這一部分可以算是hashMap中最最復雜難懂的東西了
- 紅黑樹的樹形化操作
- 紅黑樹的增加元素操作
- 紅黑樹的增加元素平衡操作
- 紅黑樹的樹分拆操作
- 紅黑樹的刪除元素操作
- 紅黑樹的刪除元素平衡操作
- 紅黑樹的退化單項鏈表操作，有兩處退化基公，一處是在擴容時幅慌，樹分拆之后，子樹內(nèi)元素容量少于6個時轰豆，執(zhí)行退化操作胰伍，還有就是在移除樹中元素之后，如果樹結構滿足某些條件則執(zhí)行退化操作
- 其實平衡的目的就是為了恢復被添加和移除元素操作破壞的紅黑樹結構罷了酸休，使用的手段無非變色和旋轉骂租。
