文章目錄
- TreeNode結構
- HashMap1.8(插入)中的樹化
- treeify函式
- balanceInsertion函式
- 左旋右旋rotateLeft函式和rotateRight函式
- moveRootToFront函式
- checkInvariants函式
TreeNode結構
上一章我們陸續講解了二叉查找樹和紅黑樹理論知識，接著我們講一下代碼層面，下面是HashMap1.8中的TreeNode結構:
/**
* 用于Tree bins 的Entry， 擴展LinkedHashMap.Entry（進而擴展Node），因此可以用作常規節點或鏈接節點的擴展，
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 紅黑樹父節點
TreeNode<K,V> left; //左子節點
TreeNode<K,V> right; //右子節點
TreeNode<K,V> prev; // 洗掉后需要取消鏈接，指向前一個節點（原鏈表中的前一個節點）
boolean red; //紅黑樹精髓 red
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
} //省略后續代碼
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
TreeNode繼承了LinkedHashMap內部類LinkedHashMap.Entry，LinkedHashMap.Entry又繼承自HashMap.Node，這些欄位跟Entry，Node中的欄位一樣，是使用默認訪問權限的，所以子類可以直接使用父類的屬性，
這里提一點為什么在1.7中我們是沒有紅黑樹的，在1.8中要引入紅黑樹呢？？？
主要還是因為在1.7中hash沖突導致slot鏈化嚴重，影響get查詢效率，
本來散鏈表在最理想狀態的查詢效率是O(1)，但是在鏈化特別嚴重后會導致查詢退化為O(n)，
HashMap1.8(插入)中的樹化
在HashMap1.8中新增了鏈表樹化紅黑樹的代碼，但是要同時滿足兩個條件才會對鏈表進行樹化，
條件一:鏈表長度達到8
條件二:散串列陣列長度達到64
如果沒有同時滿足兩個條件的話只有鏈表長度達到8而陣列長度沒有達到64的話，只會觸發resize
進行擴容，
這里提一句，樹化以后還是可能轉回鏈表的，當長度小于6的時候就會轉回鏈表了，大于6就依然保持樹化結構，
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//省略部分代碼
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//當桶中元素個數超過閾值（8）時就進行樹化
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
//省略部分代碼
}
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)
resize(); //陣列大小在64以下的話會進行擴容不會去樹化
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
//將節點替換為TreeNode
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p; //hd指向頭結點
else {
/*這里其實是將單鏈表轉化成了雙向鏈表，tl是p的前驅，
每次回圈更新指向雙鏈表的最后一個元素，用來和p相連，
p是當前節點*/
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
//將鏈表進行樹化
hd.treeify(tab);
}
}
從上方中的代碼中可以看到，樹化操作是在put操作里面執行的，在putVal函式中有if判斷桶中元素個數是否超過8，符合條件呼叫treeifyBin函式，在treeifBin函式中是先if判斷了散串列陣列大小是否低于64，低于64不會進行樹化會去擴容，當符合我上文說的兩個條件鏈表大于8，陣列大于64的時候灰先將所有節點替換為TreeNode，然后再將單鏈表轉為雙鏈表，方便之后的遍歷和移動操作，而最終的操作，實際上是呼叫TreeNode的方法treeify進行的，
treeify函式
上面對putVal到treeifyBin函式做了分析，繼續往下走我們看treeify函式是如何進行樹化操作的
final void treeify(Node<K,V>[] tab) {
//樹的根節點
TreeNode<K,V> root = null;
//x是當前節點，next是后面往下遍歷的節點
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
//如果根節點為null，把當前節點設定為根節點
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
//這里回圈遍歷，進行二叉查找樹的插入
for (TreeNode<K,V> p = root;;) {
/*p指向遍歷中的根節點，x為待插入節點，k是x的key，h是x
的hash值，ph是p的hash值，dir用來指示x節點與p的比較，-1表示
比p小，1表示比p大，不存在相等情況，因為HashMap中是不存在
兩個key完全一致的情況，*/
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
/*如果hash值相等，
那么判斷k是否實作了comparable介面，
如果實作了comparable介面就使用compareTo進行進行比較，
如果仍舊相等或者沒有實作comparable介面，
則在tieBreakOrder中比較*/
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
/*這里進行左右子節點判定*/
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
/*上面有根據hash大小的判斷去給定dir的值，
這里拿dir的值來設定left和right*/
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x); //進行插入平衡處理
break;
}
}
}
}
moveRootToFront(tab, root); //確保給定節點是桶中的第一個元素
}
//這里不是為了整體排序，而是為了在插入中保持一致的順序
static int tieBreakOrder(Object a, Object b) {
int d;
//用兩者的類名進行比較，如果相同則使用物件默認的hashcode進行比較
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;
}
上面在treeify的代碼還是比較簡單的，我們可以看到，回圈遍歷當前樹，先會進行判斷是否有根節點，如果沒有的話現在插入的這個節點就作為根節點，如果存在的話，會去找到可以給該節點插入的位置，依次和遍歷節點比較hash值的大小，比它大則跟其右子樹節點比較，小則與其左子樹節點比較，依次遍歷，直到找到左子樹節點或者右子樹節點為null的位置進行插入，我在本章剛開始的時候講的二叉查找樹就提過這類樹的一個很重要的特點，左子樹節點的值小于根節點，右子樹節點的值大于根節點，
balanceInsertion函式
真正復雜一點的地方在于balanceInsertion函式，這個函式中，將紅黑樹進行插入
平衡處理(左旋,右旋和變色操作)，保證插入節點后仍保持紅黑樹的性質，
現在我們直接進入balanceInsertion的代碼
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true;
/*x:插入的節點，xp：父節點，xpp：祖父節點，
xppl:祖父左子節點（叔叔節點），xppr:祖父右子節點(叔叔節點)*/
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { //死回圈，直到找到根節點才結束，
//情景1：父節點為null，說明當前節點就是根節點，直接return
if ((xp = x.parent) == null) {
x.red = false; //染色為黑色（根節點規定為黑色）
return x;
}
//情景2：父節點是黑色節點或者祖父節點為null，插入后沒有影響黑色完美平衡，直接回傳
else if (!xp.red || (xpp = xp.parent) == null)
return root;
//情景3：插入的節點父節點和祖父節點都存在，并且其父節點是祖父節點的左節點,父節點為紅色,也有兩種情況（LR 或者 LL）
if (xp == (xppl = xpp.left)) {
//情景3-1：插入節點的叔叔節點存在且是紅色
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;//將叔叔節點染色成黑
xp.red = false; //將父節點染色成黑
xpp.red = true;//將祖父節點染色成紅
x = xpp; //最后將爺爺節點設定為當前節點進行下一輪操作
}
//情景3-2：插入節點的叔叔節點是黑色或不存在
else {
//情景3-2-1：當前插入節點是父節點的右子節點（LR的情景）
if (x == xp.right) {
root = rotateLeft(root, x = xp);//以父節點為旋轉節點進行左旋，變成LL的情景
xpp = (xp = x.parent) == null ? null : xp.parent;//設定祖父節點
}
//情景3-2-2：插入節點是其父節點的左子節點
/*左旋完了之后，就回到了LL的情景進行右旋(父節點是祖父節點的左子節點，當前節點是父節點的左子節點)，然后父節點又是紅色，當前插入節點也是紅色，違反了紅黑色的性質，紅色不能兩兩相連，所以接下來需要進行染色；*/
if (xp != null) {
xp.red = false; //將父節點染色為黑
if (xpp != null) {
xpp.red = true; //將祖父節點染色為紅
root = rotateRight(root, xpp); //然后再對祖父節點右旋，
}
}
}
}
//情景4：插入的節點父節點和祖父節點都存在，并且其父節點是祖父節點的右節點，父節點為紅色，也有兩種情況（RL 或者 RR）
else {
//情景4-1：插入節點的叔叔節點不為空且是紅色
if (xppl != null && xppl.red) {
xppl.red = false; //將叔叔節點染色成黑
xp.red = false; //將父節點染色成黑
xpp.red = true; //將祖父節點染色成紅
x = xpp; //并且祖父節點設定為當前節點進行下一輪操作
}
//情景4-2：插入節點的叔叔節點是黑色或不存在
else {
//情景4-2-1：插入節點是其父節點的左子節點(RL的情景)
if (x == xp.left) {
root = rotateRight(root, x = xp); 以父節點為旋轉節點進行右旋，變成RR的情景
xpp = (xp = x.parent) == null ? null : xp.parent; //設定祖父節點
}
//情景4-2-2：插入節點是其父節點的右子節點，這個時候已經變成了RR的情況，需要對祖父節點左旋來維持平衡
if (xp != null) {
xp.red = false; //將父節點染色為黑
if (xpp != null) {
xpp.red = true; //將祖父節點染色為紅
root = rotateLeft(root, xpp); //再對祖父節點進行左旋
}
}
}
}
}
}
從上面我寫的注釋來深入分析balanceInsertion函式后會發現插入的節點x可能存在有父節點xp，祖父節點xpp和叔叔節點xppr和xppl，這里是存在四種場景的，
場景1:父節點為null，直接return插入的節點x
場景2:父節點是黑色節點或者祖父節點為null的時候，balanceInsertion有root和x兩個引數，
在上層的treeify函式中已經對root節點插入了x這個子節點，所以在這里可以直接return root，
場景3:插入的節點父節點和祖父節點都存在，并且其父節點是祖父節點的左節點的時候，父節點為紅色,也有兩種情況（LR 或者 LL）
這個時候我們先去判定祖父節點的右節點是叔叔節點且是紅色在代碼中的判斷
//情景3-1：插入節點的叔叔節點存在且是紅色
if ((xppr = xpp.right) != null && xppr.red)
這個時候就會去變色，會去將叔叔節點xppr和父節點xp都變成黑色，然后祖父節點xpp變為紅色，
然后這里會進行x = xpp的賦值，講祖父節點設定為當前節點進行下一輪操作
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
//情景3-2：插入節點的叔叔節點是黑色或不存在
這個時候會存在兩個子情況
//情景3-2-1：當前插入節點是父節點的右子節點（LR的情景）
因為我們在上面判定過當前的父節點是祖父節點的左子節點，所以這個時候插入節點是父節點的右子節點的話對應的就是LR情況，
//情景3-2-2：插入節點是其父節點的左子節(LL的情景)
這里的判定因為上面已經判斷過了是父節點右子節點的情況，這里就只能是左子節點了，所以對應的是LL情景
場景4:插入的節點父節點和祖父節點都存在，并且其父節點是祖父節點的右節點，父節點為紅色，也有兩種情況（RR 或者 RL）
先去判定祖父節點的右節點是叔叔節點且是紅色在代碼中的判斷
//情景4-1：插入節點的叔叔節點不為空且是紅色
if ((xppr = xpp.right) != null && xppr.red)
這個時候就會去變色，會去將叔叔節點xppr和父節點xp都變成黑色，然后祖父節點xpp變為紅色，
然后這里會進行x = xpp的賦值，講祖父節點設定為當前節點進行下一輪操作
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
//情景4-2：插入節點的叔叔節點是黑色或不存在
這個時候會存在兩個子情況
//情景4-2-1：插入節點是其父節點的左子節點(RL的情景)
因為我們在上面判定過當前的父節點是祖父節點的右子節點，所以這個時候插入節點是父節點的左子節點的話對應的就是LR情況，
//情景4-2-2：插入節點是其父節點的右子節點，這個時候已經變成了RR的情況，需要對祖父節點左旋來維持平衡
這里的判定因為上面已經判斷過了是父節點左子節點的情況，這里就只能是右子節點了，所以對應的是RR情景
這里徹底分析了HashMap紅黑樹底層的平衡邏輯(變色+左旋右旋)，相信各位同學也理解了，對左旋右旋的情況 LL RR LR RL 還不太清晰的可以去看下本文開頭講解的二叉樹旋轉方面的知識點，
左旋右旋rotateLeft函式和rotateRight函式
接著我們繼續看一下TreeNode左旋和右旋的代碼 rotateLeft函式和rotateRight函式
/**
* 左旋
* @param root 當前根節點
* @param p 指定的旋轉節點
* @return 回傳根節點(平衡涉及左旋右旋會將根節點改變，所以需要回傳最新的根節點)
*/
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;
}
左旋示意圖：左旋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
/**
* 右旋
* @param root 當前根節點
* @param p 指定的旋轉節點
* @return 回傳根節點(平衡涉及左旋右旋會將根節點改變，所以需要回傳最新的根節點)
*/
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;
}
右旋示意圖：右旋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上面關于hashmap底層的樹化程序已經講得很詳細了，接著我們繼續把treeify函式中的 moveRootToFront函式講完，
moveRootToFront函式
/**
* 把給定節點設為陣列(鏈表)中的第一個節點
* 確保給出的根結點是箱中的第一個節點也就是直接位于table上，
* 原本的第一個節點若不是root則將root從鏈表中剪下放到第一個節點的前方
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeN1ode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;//根據root的hash值快速定位下標
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];//first指向鏈表第一個節點
if (root != first) { //root不是第一個節點，則將root放到第一個首節點位置
Node<K,V> rn;
tab[index] = root; //root放到table[index]位置
TreeNode<K,V> rp = root.prev; //rp=root的前一個結點
if ((rn = root.next) != null) //rn=root的后一個結點
((TreeNode<K,V>)rn).prev = rp; //rn的前指標指向root的前一個結點
if (rp != null)
rp.next = rn; rp的后指標指向root的后一個結點
if (first != null)
first.prev = root; //將原本的first放到root的后面
root.next = first;
root.prev = null;
}
/*這里是防御性編程，校驗更改后的結構是否滿足紅黑樹和雙鏈表的特性,
checkInvariants在遞回檢查整棵樹是否符合紅黑樹的性質,
若檢查不符會回傳false導致moveRootToFront拋出錯誤.
因為HashMap并沒有做并發安全處理，可能在并發場景中意外破壞了結構*/
assert checkInvariants(root); //assert后面的運算式為false時會拋出錯誤
}
}
這里的moveRootToFront函式是確保根結點被保存在了table陣列上面，如果不是的話，就將root從鏈表中取出，將他放到陣列對應的位置上，原本在陣列上的節點(該位置的鏈表首節點)鏈接到root的后面，
講到這一步了我們的put插入導致的樹化操作也快講完了，最后再把moveRootToFront中最后assert的checkInvariants函式在分析一下
checkInvariants函式
/**
* Recursive invariant check
* 從root開始遞回檢查紅黑樹的性質，僅在檢查root是否落在table上時呼叫
*/
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
tb = t.prev, tn = (TreeNode<K,V>)t.next;
if (tb != null && tb.next != t)
return false;//t的前一個結點的后續應為t
if (tn != null && tn.prev != t)
return false;//t的后一個結點的前驅應為t
if (tp != null && t != tp.left && t != tp.right)
return false;//t因為t父親的左兒子或右兒子
if (tl != null && (tl.parent != t || tl.hash > t.hash))
return false;//t的左兒子的hash值應小于t，父親應為t
if (tr != null && (tr.parent != t || tr.hash < t.hash))
return false;//t的右兒子的hash值應大于t，父親應為t
if (t.red && tl != null && tl.red && tr != null && tr.red)
return false;//t和t的兒子不能同時是紅色
if (tl != null && !checkInvariants(tl))
return false;//遞回檢查t的左兒子
if (tr != null && !checkInvariants(tr))
return false;//遞回檢查t的右兒子
return true;
}
講到這里相信同學們已經深刻了解了HashMap1.8底層是如何進行樹化，如果有同學想了解hashMap陣列+鏈表結構和1.7原始碼以及紅黑樹的，可以在我HashMap系列博客中了解，謝謝大家的觀看，希望能給各位同學帶來幫助，如果覺得博主寫的還可以的，可以點贊關注，😉
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/227843.html
標籤：java