閱讀優(yōu)秀的源碼是提升編程技巧的重要手段之一。
如有不對的地方巴帮，歡迎指正~
轉(zhuǎn)載請注明出處https://blog.lzoro.com晶密。
前言
基于JDK1.8。
JDK1.8之前秀鞭，HashMap并沒有采用紅黑樹宰睡，所以哈希桶上的鏈表過長時，就會有效率問題气筋。
JDK1.8拆内，則在HashMap引入了紅黑樹，當(dāng)鏈表長度超過指定閾值(默認(rèn)為8)宠默，則進(jìn)行樹化并提供相關(guān)操作(增刪查等)麸恍，提高了操作效率。
之前閱讀了HashMap的源碼搀矫，但是由于篇幅關(guān)系抹沪，略過了鏈表樹化后紅黑樹的相關(guān)操作，本著打破砂鍋問到底的精神瓤球，來看下紅黑樹在HashMap中的應(yīng)用融欧。
打破沙鍋問到底，是一個成語卦羡，拼音為：dǎ pò shā guō wèn dào dǐ噪馏，其 比喻追究事情的根底，其出處自 宋·黃庭堅《拙軒頌》绿饵。
紅黑樹
什么是紅黑樹欠肾？
是這樣的嗎（開個玩笑，不存在的）拟赊。
樹刺桃？
是這樣的，這才對吧吸祟，有紅有黑瑟慈。
紅黑樹
科普時間桃移，it KePu's tims.
紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹，是在計算機(jī)科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)葛碧，典型的用途是實現(xiàn)關(guān)聯(lián)數(shù)組借杰。
它是在1972年由Rudolf Bayer發(fā)明的，當(dāng)時被稱為平衡二叉B樹（symmetric binary B-trees）吹埠。后來第步，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改為如今的“紅黑樹”。
紅黑樹和AVL樹類似缘琅，都是在進(jìn)行插入和刪除操作時通過特定操作保持二叉查找樹的平衡粘都，從而獲得較高的查找性能。
它雖然是復(fù)雜的刷袍，但它的最壞情況運(yùn)行時間也是非常良好的翩隧，并且在實踐中是高效的： 它可以在O(log n)時間內(nèi)做查找，插入和刪除呻纹，這里的n 是樹中元素的數(shù)目堆生。
以上科普信息由度娘提供。
性質(zhì)
紅黑樹不僅是二叉查找樹雷酪，它還必須滿足5個性質(zhì)
- 1.節(jié)點非黑即紅
- 2.根節(jié)點是黑色
- 3.每個葉節(jié)點（NIL節(jié)點淑仆，空節(jié)點）是黑色的
- 4.每個紅色節(jié)點的兩個子節(jié)點都是黑色(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)
- 5.從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點
滿足了以上性質(zhì)的二叉查找樹的就是紅黑樹，如果是初次接觸的話哥力，是不是看完有點懵蔗怠，不要慌，接著往下看吩跋。
紅黑樹的效率相對較高寞射，所以它被用來存儲相關(guān)數(shù)據(jù)，基本的操作有增加/刪除/查找锌钮，在這些操作之后可能會破壞紅黑樹的性質(zhì)桥温，所以需要相關(guān)操作來維護(hù)以讓紅黑樹符合上面的性質(zhì)要求。
而這里提到的相關(guān)操作有
- 變色
- 左旋
- 右旋
左旋右旋
是不是對紅黑樹的任意操作之后梁丘，它都還能滿足上面的提交的條件呢侵浸。
答案是No。
所以也就有了旋轉(zhuǎn)的存在兰吟。
旋轉(zhuǎn)跳躍通惫，我閉著眼，塵囂看不見 你沉醉了沒混蔼。（請不要唱，快拉回你的心思）
旋轉(zhuǎn)跳躍
嗯珊燎，旋轉(zhuǎn)分為左旋和右旋惭嚣。
左旋
將x的右子樹繞x逆時針旋轉(zhuǎn)遵湖，使得x的右子樹成為x的父親，并修改相關(guān)引用晚吞。
左旋
右旋
是將x的左子樹繞x順時針旋轉(zhuǎn)延旧，使得x的左子樹成為x的父親，并修改相關(guān)的引用槽地。
右旋
是不是還是有點迷糊迁沫，那么再來兩張動圖幫助下理解~
左旋
右旋
懶人自有妙計，不過要有版權(quán)意識捌蚊。
動圖來源：https://blog.csdn.net/sun_tttt/article/details/65445754
是不是明白一些了~~
基本的關(guān)于紅黑樹概念介紹完畢集畅，需要深入了解的小伙伴請移步搜索引擎。
接下來缅糟，坐好了挺智，將車門焊死，準(zhǔn)備發(fā)車了窗宦。
發(fā)車
HashMap中的紅黑樹
先看下HashMap內(nèi)部類TreeNode<K,V>的定義赦颇，它繼承了LinkedHashMap.Entry<K,V>
類java.util.HashMap
第1791行起
/**
* 二叉樹實體. 繼承 LinkedHashMap.Entry (順序擴(kuò)展節(jié)點)
*
* linked node.
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
//紅黑樹父節(jié)點(鏈)
TreeNode<K,V> parent; // red-black tree links
//左節(jié)點
TreeNode<K,V> left;
//右節(jié)點
TreeNode<K,V> right;
//前置節(jié)點
TreeNode<K,V> prev; // needed to unlink next upon deletion
//紅黑標(biāo)志
boolean red;
/**
* 構(gòu)造函數(shù)
*/
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/**
* 返回根節(jié)點
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
//先略去部分功能代碼
...
}
在看相關(guān)的功能代碼之前，先來看下HahsMap中紅黑樹左旋和右旋的實現(xiàn)
HashMap中的紅黑樹 - 左旋
/**
* 紅黑樹左旋操作
*/
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
//p不為null且p的右子樹不為null
if (p != null && (r = p.right) != null) {
//將r(p的右子樹)的左子樹變成p的右子樹
//有點拗口 o(╥﹏╥)o
//下面會用一個圖示來說明
if ((rl = p.right = r.left) != null)
//修改父節(jié)點引用赴涵，rl是r(p的右子樹)的左子樹
rl.parent = p;
//將r(p的右子樹)的父節(jié)點變成p的父節(jié)點（左旋過程媒怯，將右子樹變成自己的父節(jié)點）
if ((pp = r.parent = p.parent) == null)
//如果p節(jié)點的父節(jié)點為null，證明p是根節(jié)點（子樹的根節(jié)點）
//將r變成根節(jié)點（子樹的根節(jié)點）髓窜，并變成黑色（符合性質(zhì)）
(root = r).red = false;
//如果存在父節(jié)點且p是該節(jié)點的左子樹
else if (pp.left == p)
//將r(p的右子樹)變成該節(jié)點的左子樹
pp.left = r;
//如果存在父節(jié)點且p節(jié)點是該節(jié)點的右子樹
else
//將r(p的右子樹)變成該節(jié)點的右子樹
pp.right = r;
//將r(p的左子樹)變成p（左旋中扇苞，將左子樹變成自己的父節(jié)點）
r.left = p;
//r變成p的父節(jié)點
p.parent = r;
}
return root;
}
下面用圖示來說明上面的步驟，會比較簡單明了不拗口
一纱烘、p沒有父節(jié)點（可以理解為p是根節(jié)點）
左旋演示1
一杨拐、p有父節(jié)點
左旋演示2
HashMap中的紅黑樹 - 右旋
/**
* 紅黑樹右旋操作
*/
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
//p不為null且p的左子樹不為null
if (p != null && (l = p.left) != null) {
//將l(p的左子樹)的右子樹變成p的左子樹
if ((lr = p.left = l.right) != null)
//修改父節(jié)點引用，lr是l(p的左子樹)的右子樹
lr.parent = p;
//將l(p的右子樹)的父節(jié)點變成p的父節(jié)點（右旋過程擂啥，將左子樹變成自己的父節(jié)點）
if ((pp = l.parent = p.parent) == null)
//將l變成根節(jié)點（子樹的根節(jié)點）哄陶，并變成黑色（符合性質(zhì)）
(root = l).red = false;
//如果存在父節(jié)點且p是該節(jié)點的右子樹
else if (pp.right == p)
pp.right = l;
//如果存在父節(jié)點且p是該節(jié)點的左子樹
else
pp.left = l;
//將l(p的右子樹)變成p（右旋中，將右子樹變成自己的父節(jié)點）
l.right = p;
p.parent = l;
}
return root;
}
類似的下面用圖演示過程
一哺壶、p沒有父節(jié)點（可以理解為p是根節(jié)點）
右旋演示1
一屋吨、p有父節(jié)點
右旋演示2
右旋
理解了HashMap中紅黑樹的左旋和右旋，下面看一下幾個比較重要的方法
treeify
顧名思義：樹化山宾。當(dāng)哈希桶中的鏈表長度超過閾值(默認(rèn)8)的話至扰，就會對鏈表進(jìn)行樹化，具體來看一下實現(xiàn)资锰。
調(diào)用鏈如下
1敢课、HashMap第643行treeifyBin(tab, hash);，判斷閾值，超過則進(jìn)行樹化
2直秆、HashMap第754行濒募，treeifyBin實現(xiàn)，第771行調(diào)用TreeNode的樹化實現(xiàn)
/**
* 替換哈希桶中給定哈希索引的元素
* 如果哈希桶太小圾结，則resize
*/
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)
//調(diào)整擴(kuò)容
resize();
//在哈希桶中獲取指定位置的元素
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
//替換成樹節(jié)點
do {
//這里的replacementTreeNode調(diào)用了TreeNode的構(gòu)造函數(shù)進(jìn)行構(gòu)造
TreeNode<K,V> p = replacementTreeNode(e, null);
//維護(hù)順序
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
//修改哈希桶中對應(yīng)下標(biāo)的指向為樹的頭結(jié)點
if ((tab[index] = hd) != null)
//執(zhí)行紅黑樹化
hd.treeify(tab);
}
}
3、HashMap第1897行晌姚，treeify實現(xiàn)
/**
* 紅黑樹化
* @return 樹的根節(jié)點
*/
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
//循環(huán)整理
for (TreeNode<K,V> x = this, next; x != null; x = next) {
//取出下一個鏈表節(jié)點
next = (TreeNode<K,V>)x.next;
//將x節(jié)點的左右節(jié)點設(shè)置為null
x.left = x.right = null;
//判斷當(dāng)前紅黑樹是否有根節(jié)點
if (root == null) {
//如果沒有根節(jié)點
//當(dāng)前節(jié)點的父節(jié)點設(shè)置為null
x.parent = null;
//設(shè)置顏色為黑色（根節(jié)點為黑色）
x.red = false;
//將x節(jié)點設(shè)置為根節(jié)點
root = x;
}
//當(dāng)前紅黑樹存在根節(jié)點
else {
//獲取x節(jié)點的key
K k = x.key;
//獲取x節(jié)點的hash
int h = x.hash;
//key的class
Class<?> kc = null;
//從根節(jié)點遍歷歇竟，將x節(jié)點插入到紅黑樹中
for (TreeNode<K,V> p = root;;) {
//定義dir(方向),ph(節(jié)點hash)
int dir, ph;
//取出p節(jié)點的key
K pk = p.key;
//當(dāng)p節(jié)點的hash大于x節(jié)點的hash時
if ((ph = p.hash) > h)
//左側(cè)
dir = -1;
else if (ph < h)
//右側(cè)
dir = 1;
//如果上面的if分支沒走途蒋，則證明兩個節(jié)點key的hash值相等，需要通過其他方式進(jìn)行比較
//如果當(dāng)前節(jié)點(x)的key的類實現(xiàn)了comparable接口号坡，且當(dāng)前循環(huán)節(jié)點(p)是相同Class的實例
//那么就通過comparable進(jìn)行比較
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
//若還是相等宽堆，就通過tieBreakOrder比較
dir = tieBreakOrder(k, pk);
//先緩存p節(jié)點
TreeNode<K,V> xp = p;
//根據(jù)dir方向腌紧，來選擇在左側(cè)還是右側(cè)插入
//并判斷是否為null
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//選擇的左/右子樹為null
//將原來的p節(jié)點(現(xiàn)xp)設(shè)置為x的父節(jié)點
x.parent = xp;
//如果dir 小于等于0
//將x節(jié)點放置在原p(現(xiàn)xp)節(jié)點的左側(cè)
if (dir <= 0)
xp.left = x;
//如果dir 大于0
//將x節(jié)點放置在原p(現(xiàn)xp)節(jié)點的右側(cè)
xp.right = x;
//調(diào)用balanceInsertion進(jìn)行插入平衡
root = balanceInsertion(root, x);
break;
}
}
}
}
//確保哈希桶指定位置存儲的節(jié)點是紅黑樹的根節(jié)點
moveRootToFront(tab, root);
}
/**
* 確保哈希桶指定位置存儲的節(jié)點是紅黑樹的根節(jié)點
*/
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é)點
if (root != first) {
Node<K,V> rn;
//指向紅黑樹的根節(jié)點
tab[index] = root;
TreeNode<K,V> rp = root.prev;
//整理節(jié)點順序
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);
}
}
4、HashMap第2206行畜隶，balanceInsertion實現(xiàn)
這個方法實現(xiàn)了紅黑樹插入節(jié)點后的平衡(為了滿足平衡性)壁肋，方法的分支較多，如果沒有很透徹理解紅黑樹的相關(guān)概念和操作籽慢，一時間會容易迷惑浸遗，下面代碼對整體流程進(jìn)行了注釋，但是仍然比較晦澀箱亿，后面會帶上圖示跛锌，加深理解。
/**
* 插入平衡
*/
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
//將x節(jié)點設(shè)為紅色（新插入節(jié)點一開始為紅色）
x.red = true;
//一個沒有邊界的循環(huán)(需要內(nèi)部跳出)
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//取出x的父節(jié)點并判斷是否為null
if ((xp = x.parent) == null) {
//x沒有父節(jié)點
x.red = false;//變色(黑色)
return x;//x為根節(jié)點發(fā)那會
}
//如果x存在父節(jié)點且x的父節(jié)點為黑色或x的父父節(jié)點不存在
else if (!xp.red || (xpp = xp.parent) == null)
//返回root
return root;
//如果x的父節(jié)點是父父節(jié)點的左孩子
if (xp == (xppl = xpp.left)) {
//父父節(jié)點的右孩子不為null且為紅色
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;//變色(黑)
xp.red = false;//變色(黑)
xpp.red = true;//變色(紅)
x = xpp;
}
else {
//x是父節(jié)點的右孩子
if (x == xp.right) {
//左旋
root = rotateLeft(root, x = xp);
//處理x的父父節(jié)點
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//x的父節(jié)點存在
if (xp != null) {
xp.red = false;//變色
//x的父父節(jié)點存在
if (xpp != null) {
xpp.red = true;//變色
//右旋
root = rotateRight(root, xpp);
}
}
}
}
//如果x的父節(jié)點是父父節(jié)點的右孩子
else {
//x的父父節(jié)點的左孩子存在且為紅色
if (xppl != null && xppl.red) {
xppl.red = false;//變色(黑)
xp.red = false;//變色(黑)
xpp.red = true;//變色(紅)
x = xpp;
}
else {
//如果x是父節(jié)點的左孩子
if (x == xp.left) {
//右旋
root = rotateRight(root, x = xp);
//處理x的父父節(jié)點
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//如果x的父節(jié)點存在
if (xp != null) {
xp.red = false;//變色(黑)
//如果x的父父節(jié)點存在
if (xpp != null) {
xpp.red = true;//變色(紅)
//左旋
root = rotateLeft(root, xpp);
}
}
}
}
}
}
下面用圖示届惋，舉個栗子~
栗子在這里
舉個栗子
假如有如下一個鏈表髓帽，里面的數(shù)字代表hash值（先不考慮hash分布）
鏈表
然后按照鏈表順序取出節(jié)點進(jìn)行紅黑樹插入，以及插入后平衡操作（左旋右旋/變色）脑豹，來看一下整個過程
插入節(jié)點過程1
插入節(jié)點過程2
綜合上面的描述和圖示郑藏，大概可以把鏈表轉(zhuǎn)紅黑樹的操作總結(jié)如下
1、將鏈表的首節(jié)點當(dāng)做臨時的紅黑樹根節(jié)點瘩欺，左右孩子置為null
2必盖、循環(huán)按順序取出鏈表的節(jié)點拌牲，進(jìn)行紅黑樹插入，和插入后平衡
2.1筑悴、取出鏈表節(jié)點们拙，經(jīng)過hash比較阁吝，插入到紅黑樹合適的位置(保證平衡性)
2.2突勇、由于插入的節(jié)點會破壞紅黑樹的性質(zhì)坷虑，所以需要進(jìn)行插入后平衡
2.2.1定躏、新插入的節(jié)點置為紅色
2.2.2痊远、父節(jié)點和父父節(jié)點的null判斷和顏色判斷
2.2.2.1碧聪、判斷新插入節(jié)點的父節(jié)點是否存在逞姿，不存在則返回
2.2.2.1、如果父節(jié)點是黑色的谒养，或者父父節(jié)點不存在著蝴光，則返回
2.2.3蔑祟、父節(jié)點是父父節(jié)點的左孩子還是右孩子判斷
2.2.3.1疆虚、是左孩子且兄弟節(jié)點存在并且是紅色罢屈，則執(zhí)行相應(yīng)的變色缠捌，然后進(jìn)行下一輪判斷曼月。
2.2.3.2、是左孩子當(dāng)兄弟節(jié)點不存在（或者是黑色）聪姿，則執(zhí)行相應(yīng)的左旋/右旋末购。
2.2.3.3招盲、是右孩子且兄弟節(jié)點存在并且是紅色，則執(zhí)行相應(yīng)的變色讳推，然后進(jìn)行下一輪判斷银觅。
2.2.3.4镊绪、是右孩子當(dāng)兄弟節(jié)點不存在（或者是黑色）蝴韭，則執(zhí)行相應(yīng)的左旋/右旋榄鉴。
3剃诅、鏈表循環(huán)完畢后矛辕，確保哈希桶指定位置存儲的是紅黑樹的根節(jié)點
嗯如筛，沒了。細(xì)節(jié)請看源碼和圖示擦剑，如果覺得迷糊惠勒，可以自己動手畫畫圖纠屋，或者Debug售担。
untreeify
有了樹化族铆，肯定也有非樹化哥攘。
有起有落，月缺月圓栅葡，凡事要有平衡妥畏。一本正經(jīng)地胡說八道醉蚁。
舉個栗子
突然就斗起了表情网棍。
沒錯氏身，這個方法就是將紅黑樹退化成鏈表蛋欣，俗稱鏈表化陷虎。
入口有幾個地方
- 節(jié)點刪除時，紅黑樹的大小低于閾值凿掂，退化成鏈表庄萎。2035行
tab[index] = first.untreeify(map); // too small - 擴(kuò)容/調(diào)整容量時惨恭，調(diào)用
split方法
/**
* 紅黑樹鏈表化
*/
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
//循環(huán)免都，將紅黑樹轉(zhuǎn)成鏈表
for (Node<K,V> q = this; q != null; q = q.next) {
//構(gòu)造一個普通鏈表節(jié)點
Node<K,V> p = map.replacementNode(q, null);
//維護(hù)順序
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
putTreeVal
嗯脓规，沒什么好說的侨舆，紅黑樹的節(jié)點插入挨下。
對應(yīng)上篇博客的鏈表節(jié)點插入臭笆，但相比鏈表來說會比較復(fù)雜愁铺。不過流程與之前提到過的樹化當(dāng)中的單一節(jié)點插入沒有太大區(qū)別茵乱，也是從紅黑樹的根節(jié)點進(jìn)行遍歷获黔，尋找合適的位置插入，并進(jìn)行插入后的平衡(變色/左旋/右旋)腋舌，待插入平衡后，確保存儲在哈希桶指定位置的節(jié)點是紅黑樹的根節(jié)點授艰。
/**
* 紅黑樹版本的節(jié)點插入
*/
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é)點
TreeNode<K,V> root = (parent != null) ? root() : this;
//從根節(jié)點進(jìn)行遍歷，選擇合適的位置插入節(jié)點(無邊界遍歷谷朝，需要內(nèi)部跳出)
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
//判斷方向
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
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))
return q;
}
dir = tieBreakOrder(k, pk);
}
//先緩存當(dāng)前遍歷的樹節(jié)點
TreeNode<K,V> xp = p;
//判斷該樹節(jié)點下是否有子節(jié)點
//如果沒有，則根據(jù)之前判斷的方向（左側(cè)/右側(cè)）進(jìn)行插入
//如果已有专钉，則向下遍歷繼續(xù)上面的步驟站叼，直到插入合適的位置
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);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
//插入到合適的位置和大年，可能破壞紅黑樹的性質(zhì)翔试，所以需要進(jìn)行插入平衡
//插入平衡后垦缅，需要確保哈希桶下標(biāo)位置上存儲的節(jié)點是紅黑樹的節(jié)點
//這些在上面的樹化過程都有提到壁涎，此處不再贅述
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
getTreeNode
紅黑樹中的節(jié)點查找。
對應(yīng)鏈表的節(jié)點查找竟坛，在鏈表樹化后担汤，節(jié)點的查找就是紅黑樹實現(xiàn)的。查找的邏輯還是比較清晰的洼冻，因為紅黑樹是自平衡二叉查找樹崭歧，節(jié)點左子樹都比自己小，右子樹都比自己大撞牢，所以根據(jù)給定的hash率碾，可以確定從左子樹還是右子樹查找，然后循環(huán)進(jìn)行定位普泡，知道最終找到節(jié)點或者不存在該節(jié)點時播掷，結(jié)束查找。
/**
* 紅黑樹節(jié)點查找的入口方法
*/
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
/**
* 根據(jù)給定的hash和key勘究，從紅黑樹的根節(jié)點開始進(jìn)行查找
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
//取出左子樹和右子樹，根據(jù)hash和key進(jìn)行查找
TreeNode<K,V> pl = p.left, pr = p.right, q;
//根據(jù)hash大小決定取左子樹還是右子樹
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
//如果在節(jié)點相等呵燕，就返回
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
removeTreeNode
移除紅黑樹節(jié)點让虐。
對應(yīng)鏈表節(jié)點的移除辩稽，紅黑樹版本的節(jié)點移除相比鏈表會復(fù)雜一些喷众，因為涉及到維護(hù)紅黑樹的平衡性和相關(guān)性質(zhì)般眉。
/**
* 移除給定節(jié)點, 調(diào)用該方法時要確保節(jié)點存在.
* 因為無法交換存在葉子節(jié)點的內(nèi)部節(jié)點內(nèi)容埠对，所以這會比典型的紅黑樹節(jié)點刪除來得復(fù)雜
* 遍歷過程中"next"指針指向的繼任節(jié)點是可訪問的稍计，所以我們交換了樹的連接.
* 如果當(dāng)前樹節(jié)點太少，則將二叉樹替換成簡單形式
* (2-6節(jié)點測試觸發(fā)，取決于樹的結(jié)構(gòu))
*/
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n;
//判斷哈希桶
if (tab == null || (n = tab.length) == 0)
return;
//下標(biāo)
int index = (n - 1) & hash;
//取出指定下標(biāo)的根節(jié)點
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
//繼任節(jié)點和前置節(jié)點
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
//前置節(jié)點不存在徒扶，則證明要移除的節(jié)點是根節(jié)點
if (pred == null)
//將繼任節(jié)點往前移
tab[index] = first = succ;
else
//前置節(jié)點存在，則將繼任節(jié)點連接到前置節(jié)點（移除本節(jié)點）
pred.next = succ;
//判斷繼任節(jié)點是否存在
if (succ != null)
//存在的話漾狼，修改前置引用
succ.prev = pred;
//這個時候first為null，則表示哈希桶指定位置可能只有一個節(jié)點
if (first == null)
//返回
return;
//獲取根節(jié)點
if (root.parent != null)
root = root.root();
//根節(jié)點不存在或者根節(jié)點的左子樹/右子樹不存在或者左左子樹不存在
//該判斷是作為鏈表化的閾值
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
//紅黑樹太小，進(jìn)行鏈表化
tab[index] = first.untreeify(map); // too small
return;
}
//取得要移除的節(jié)點察藐，左子樹譬猫，右子樹
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
//左右子樹同時存在
if (pl != null && pr != null) {
TreeNode<K,V> s = pr, sl;
//循環(huán)查找繼任節(jié)點
while ((sl = s.left) != null) // find successor
s = sl;
//交換p和s的顏色
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
//相等則證明p是s的直接父節(jié)點（只有一個層級）
if (s == pr) { // p was s's direct parent
//交換位置
p.parent = s;
s.right = p;
}
//如果是多個層級
else {
//取出s的父節(jié)點
TreeNode<K,V> sp = s.parent;
//下面操作仍然是交換p和s的位置
if ((p.parent = sp) != null) {
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if ((s.right = pr) != null)
pr.parent = s;
}
//清空p的右子樹引用
p.left = null;
//調(diào)整相關(guān)引用
if ((p.right = sr) != null)
sr.parent = p;
if ((s.left = pl) != null)
pl.parent = s;
if ((s.parent = pp) == null)
root = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
//確定替換節(jié)點
if (sr != null)
replacement = sr;
else
replacement = p;
}
//只有左子樹存在
else if (pl != null)
replacement = pl;
//只有右子樹存在
else if (pr != null)
replacement = pr;
//左右子樹都不存在
else
replacement = p;
//判斷替換的節(jié)點是不是自身
if (replacement != p) {
//不是自身的話益愈，則執(zhí)行相關(guān)替換操作
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)
root = replacement;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
p.left = p.right = p.parent = null;
}
//判斷p的顏色
//如果p是紅色節(jié)點靠汁，則將根節(jié)點賦值給r
//如果p是黑色節(jié)點成洗，則進(jìn)行刪除平衡(類似于插入平衡)
//這里的r要存儲紅黑樹的根節(jié)點
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
//如果替換節(jié)點是自身的話
if (replacement == p) { // detach
//進(jìn)行分離操作
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)
//確保哈希桶下標(biāo)指定位置存儲的是紅黑樹根節(jié)點
moveRootToFront(tab, r);
}
split
只有在resize的時候被調(diào)用，作用是在哈希桶擴(kuò)容/調(diào)整容量時青团，將紅黑樹拆分成兩顆樹，在紅黑樹太小時進(jìn)行鏈表化等操作。
具體看源碼注釋末早。
/**
* Splits nodes in a tree bin into lower and upper tree bins,
* or untreeifies if now too small. Called only from resize;
* see above discussion about split bits and indices.
*
* @param map the map
* @param tab the table for recording bin heads
* @param index the index of the table being split
* @param bit the bit of hash to split on
*/
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int 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;
//遍歷節(jié)點
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
//將e的next引用置空捆憎，目的是從e斷開
e.next = null;
//將e的hash和bit(其實就是oldCap)相與（是不是很熟悉础拨，其實跟鏈表的操作類似）
//為0的放到lower樹
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
//不為0放到upper樹
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
//判斷l(xiāng)ower樹是否為null
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);
}
}
//判斷upper樹是否為null
if (hiHead != null) {
//判斷是否需要鏈表化
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
到這里谅年，關(guān)于HashMap中的紅黑樹相關(guān)內(nèi)容基本上都介紹完畢了圣猎，篇幅有點長士葫，沒法面面俱到，呼~~（放松一下）送悔。
后話
本來想著每個方法和每個操作流程都畫圖解釋比較直觀慢显。
但是后面花現(xiàn)，畫圖欠啤，真的是他喵了太耗費精力了荚藻。
我花4，除了動圖之外洁段，其他的圖都是我自己畫的出皇。對了关划，開頭的那棵樹除外。當(dāng)然，表情包也不是刻获。
其他圖示留待后面時間充裕了補(bǔ)上吧。
溜了溜了盛泡，有幫助的話給格子點個贊唄奋早。
