01 概述

HashMap是Java程序員使用頻率最高的用于映射(鍵值對(duì))處理的數(shù)據(jù)類型。隨著JDK(Java Developmet Kit)版本的更新，JDK1.8對(duì)HashMap底層的實(shí)現(xiàn)進(jìn)行了優(yōu)化，例如引入紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)和擴(kuò)容的優(yōu)化等。本文主要分析一下HashMap中紅黑樹(shù)樹(shù)化的過(guò)程。

[[278900]]

02 紅黑樹(shù)(red black tree)

一個(gè)節(jié)點(diǎn)標(biāo)記為紅色或者黑色。 根是黑色的。 如果一個(gè)節(jié)點(diǎn)是紅色的，那么它的子節(jié)點(diǎn)必須是黑色的(這就是為什么叫紅黑樹(shù))。 一個(gè)節(jié)點(diǎn)到到一個(gè)null引用的每一條路徑必須包含相同數(shù)目的黑色節(jié)點(diǎn)(所以紅色節(jié)點(diǎn)不影響)。 其實(shí)RB Tree和著名的AVL Tree有很多相同的地方，困難的地方都在于將一個(gè)新項(xiàng)插入到樹(shù)中。了解AVL Tree的朋友應(yīng)該都知道為了維持樹(shù)的高度必須在插入一個(gè)新的項(xiàng)后必須在樹(shù)的結(jié)構(gòu)上進(jìn)行改變，這里主要是通過(guò)旋轉(zhuǎn)，當(dāng)然在RB Tree中原理也是如此。

03 兩種旋轉(zhuǎn)和一種典型的變換

旋轉(zhuǎn)的方向：

變換過(guò)程：

互相關(guān)聯(lián)：

單向關(guān)聯(lián)：

代表紅色的節(jié)點(diǎn)：

代表黑色的節(jié)點(diǎn)：

代表一個(gè)不會(huì)破壞紅黑樹(shù)結(jié)構(gòu)的部分，可能是節(jié)點(diǎn)，或者是一個(gè)子樹(shù)，總之不會(huì)破環(huán)當(dāng)前樹(shù)的結(jié)構(gòu)。這個(gè)部分會(huì)由于旋轉(zhuǎn)而連接到其他的節(jié)點(diǎn)后面，我們可以理解成由于重力原因它掉到了下面的節(jié)點(diǎn)上：

• 單旋轉(zhuǎn)變換。
• 雙旋轉(zhuǎn)變換(需要兩次反方向的單旋轉(zhuǎn))。
• 當(dāng)遇到兩個(gè)子幾點(diǎn)都為紅色的話執(zhí)行顏色變換，因?yàn)椴迦? 是紅色的會(huì)產(chǎn)生沖突。如果根節(jié)點(diǎn)兩邊的子節(jié)點(diǎn)都是紅色，兩個(gè)葉子節(jié)點(diǎn)變成黑色，根節(jié)點(diǎn)變成紅色，然后再將根節(jié)點(diǎn)變成黑色。

上面的圖中描述了紅黑樹(shù)中三種典型的變換，其實(shí)前兩種變換這正是AVL Tree中的兩種典型的變換。

04 幾個(gè)問(wèn)題

4.1 為什么要進(jìn)行旋轉(zhuǎn)?

由于P和X節(jié)點(diǎn)都為紅色節(jié)點(diǎn)這破環(huán)了紅節(jié)點(diǎn)下面的節(jié)點(diǎn)必須為黑色節(jié)點(diǎn)的規(guī)則。

4.2 新加入的節(jié)點(diǎn)總是紅色的，這是為什么呢?

因?yàn)楸徊迦肭暗臉?shù)結(jié)構(gòu)是構(gòu)建好的，一但我們進(jìn)行添加黑色的節(jié)點(diǎn)，無(wú)論添加在哪里都會(huì)破壞原有路徑上的黑色節(jié)點(diǎn)的數(shù)量平等關(guān)系，所以插入紅色節(jié)點(diǎn)是正確的選擇。

4.3 為什么要進(jìn)行顏色變換?

正如第一種旋轉(zhuǎn)新加入的節(jié)點(diǎn)X破壞了紅黑樹(shù)的結(jié)構(gòu)不得不進(jìn)行旋轉(zhuǎn)，后面的就是旋轉(zhuǎn)后的結(jié)果，旋轉(zhuǎn)后形成新的結(jié)構(gòu)，此時(shí)我們發(fā)現(xiàn)兩個(gè)子節(jié)點(diǎn)都是紅色的所以執(zhí)行第三個(gè)變換特性，顏色變換，因?yàn)槿绻庸?jié)點(diǎn)是紅色的那么我們?cè)谔砑拥臅r(shí)候只能添加黑色的節(jié)點(diǎn)，然而添加任何黑色葉子節(jié)點(diǎn)都會(huì)破壞樹(shù)的第四條性質(zhì)，所以要對(duì)其進(jìn)行變換。當(dāng)進(jìn)行變換后葉子節(jié)點(diǎn)是紅色的而且我們默認(rèn)添加的葉子節(jié)點(diǎn)是紅色的，所以添加到黑色節(jié)點(diǎn)后并不會(huì)破壞樹(shù)的第四條結(jié)構(gòu)，所以這種變換很有用。

第二種雙變換中在樹(shù)的內(nèi)部怎么出現(xiàn)的紅色的節(jié)點(diǎn)? 正是由于上面的顏色變換導(dǎo)致新顏色變換后的節(jié)點(diǎn)與他的父節(jié)點(diǎn)產(chǎn)生了顏色沖突。

與AVL樹(shù)相比? 比AVL樹(shù)相比優(yōu)點(diǎn)是不用在節(jié)點(diǎn)類中保存一個(gè)節(jié)點(diǎn)高度這個(gè)變量，節(jié)省了內(nèi)存。

而且紅黑樹(shù)一般不是以遞歸方式實(shí)現(xiàn)的而是以循環(huán)的形式實(shí)現(xiàn)。

一般的操作在最壞情形下花費(fèi)O(logN)時(shí)間。

05 好了有了這些基本的概念讓我們?nèi)タ匆幌翲ashMap中的代碼的實(shí)現(xiàn)

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) 
 { 
 Node<K, V>[] tab; 
 Node<K, V> p; 
 int n, i; 
 if ((tab = table) == null || (n = tab.length) == 0) 
 n = (tab = resize()).length; 
 if ((p = tab[i = (n - 1) & hash]) == null) 
 tab[i] = newNode(hash, key, value, null); 
 else 
 { 
 Node<K, V> e; 
 K k; 
 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) 
 e = p; 
 else if (p instanceof TreeNode) 
 // 如果當(dāng)前的bucket里面已經(jīng)是紅黑樹(shù)的話，執(zhí)行紅黑樹(shù)的添加操作 
 e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value); 
 else 
 { 
 for (int binCount = 0;; ++binCount) 
 { 
 if ((e = p.next) == null) 
 { 
 p.next = newNode(hash, key, value, null); 
 // TREEIFY_THRESHOLD = 8，判斷如果當(dāng)前bucket的位置鏈表長(zhǎng)度大于8的話就將此鏈表變成紅黑樹(shù)。 
 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 
 treeifyBin(tab, hash); 
 break; 
 } 
 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) 
 break; 
 p = e; 
 } 
 } 
 if (e != null) 
 { // existing mapping for key 
 V oldValue = e.value; 
 if (!onlyIfAbsent || oldValue == null) 
 e.value = value; 
 afterNodeAccess(e); 
 return oldValue; 
 } 
 } 
 ++modCount; 
 if (++size > threshold) 
 resize(); 
 afterNodeInsertion(evict); 
 return null; 
 } 

上面的方法通過(guò)hash計(jì)算插入的項(xiàng)的槽位，如果有是一樣的key則根據(jù)設(shè)置的參數(shù)是否執(zhí)行覆蓋，如果相應(yīng)槽位空的話直接插入，如果對(duì)應(yīng)的槽位有項(xiàng)則判斷是紅黑樹(shù)結(jié)構(gòu)還是鏈表結(jié)構(gòu)的槽位，鏈表的話則順著鏈表尋找如果找到一樣的key則根據(jù)參數(shù)選擇覆蓋，沒(méi)有找到則鏈接在鏈表最后面，鏈表項(xiàng)的數(shù)目大于8則對(duì)其進(jìn)行樹(shù)化，如果是紅黑樹(shù)結(jié)構(gòu)則按照樹(shù)的添加方式添加項(xiàng)。

讓我們看一下treeifyBin這個(gè)方法。

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()方法這里不過(guò)多介紹，感興趣的可以去看上面的鏈接。 
 resize(); 
 // 通過(guò)hash求出bucket的位置。 
 else if ((e = tab[index = (n - 1) & hash]) != null) 
 { 
 TreeNode<K, V> hd = null, tl = null; 
 do 
 { 
 // 將每個(gè)節(jié)點(diǎn)包裝成TreeNode。 
 TreeNode<K, V> p = replacementTreeNode(e, null); 
 if (tl == null) 
 hd = p; 
 else 
 { 
 // 將所有TreeNode連接在一起此時(shí)只是鏈表結(jié)構(gòu)。 
 p.prev = tl; 
 tl.next = p; 
 } 
 tl = p; 
 } while ((e = e.next) != null); 
 if ((tab[index] = hd) != null) 
 // 對(duì)TreeNode鏈表進(jìn)行樹(shù)化。 
 hd.treeify(tab); 
 } 
 } 

找個(gè)方法所做的事情就是將剛才九個(gè)項(xiàng)以鏈表的方式連接在一起，然后通過(guò)它構(gòu)建紅黑樹(shù)。

看代碼之前我們先了解一下TreeNode

static final class TreeNode<K, V> extends LinkedHashMap.Entry<K, V> 
 { 
 TreeNode<K, V> parent; // red-black tree links 
 TreeNode<K, V> left; 
 TreeNode<K, V> right; 
 TreeNode<K, V> prev; // needed to unlink next upon deletion 
 boolean red; 
 TreeNode(int hash, K key, V val, Node<K, V> next) 
 { 
 super(hash, key, val, next); 
 } 
  
 final void treeify(Node<K,V>[] tab) 
 { 
 // ...... 
 } 
  
 static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) 
 { 
 // ...... 
 } 
  
 static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) 
 { 
 // ...... 
 } 
  
 static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) 
 { 
 // ...... 
 } 
  
 // ......其余方法省略 
 } 

可以看出出真正的維護(hù)紅黑樹(shù)結(jié)構(gòu)的方法并沒(méi)有在HashMap中，全部都在TreeNode類內(nèi)部。

我們看一下treeify代碼

final void treeify(Node<K, V>[] tab) 
 { 
 TreeNode<K, V> root = null; 
 // 以for循環(huán)的方式遍歷剛才我們創(chuàng)建的鏈表。 
 for (TreeNode<K, V> x = this, next; x != null; x = next) 
 { 
 // next向前推進(jìn)。 
 next = (TreeNode<K, V>) x.next; 
 x.left = x.right = null; 
 // 為樹(shù)根節(jié)點(diǎn)賦值。 
 if (root == null) 
 { 
 x.parent = null; 
 x.red = false; 
 root = x; 
 } else 
 { 
 // x即為當(dāng)前訪問(wèn)鏈表中的項(xiàng)。 
 K k = x.key; 
 int h = x.hash; 
 Class<?> kc = null; 
 // 此時(shí)紅黑樹(shù)已經(jīng)有了根節(jié)點(diǎn)，上面獲取了當(dāng)前加入紅黑樹(shù)的項(xiàng)的key和hash值進(jìn)入核心循環(huán)。 
 // 這里從root開(kāi)始，是以一個(gè)自頂向下的方式遍歷添加。 
 // for循環(huán)沒(méi)有控制條件，由代碼內(nèi)break跳出循環(huán)。 
 for (TreeNode<K, V> p = root;;) 
 { 
 // dir：directory，比較添加項(xiàng)與當(dāng)前樹(shù)中訪問(wèn)節(jié)點(diǎn)的hash值判斷加入項(xiàng)的路徑，-1為左子樹(shù)，+1為右子樹(shù)。 
 // ph：parent hash。 
 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); 
 // xp：x parent。 
 TreeNode<K, V> xp = p; 
 // 找到符合x(chóng)添加條件的節(jié)點(diǎn)。 
 if ((p = (dir <= 0) ? p.left : p.right) == null) 
 { 
 x.parent = xp; 
 // 如果xp的hash值大于x的hash值，將x添加在xp的左邊。 
 if (dir <= 0) 
 xp.left = x; 
 // 反之添加在xp的右邊。 
 else 
 xp.right = x; 
 // 維護(hù)添加后紅黑樹(shù)的紅黑結(jié)構(gòu)。 
 root = balanceInsertion(root, x); 
  
 // 跳出循環(huán)當(dāng)前鏈表中的項(xiàng)成功的添加到了紅黑樹(shù)中。 
 break; 
 } 
 } 
 } 
 } 
 // Ensures that the given root is the first node of its bin，自己翻譯一下。 
 moveRootToFront(tab, root); 
 } 

第一次循環(huán)會(huì)將鏈表中的首節(jié)點(diǎn)作為紅黑樹(shù)的根，而后的循環(huán)會(huì)將鏈表中的的項(xiàng)通過(guò)比較hash值然后連接到相應(yīng)樹(shù)節(jié)點(diǎn)的左邊或者右邊，插入可能會(huì)破壞樹(shù)的結(jié)構(gòu)所以接著執(zhí)行balanceInsertion。

我們看balanceInsertion

static <K, V> TreeNode<K, V> balanceInsertion(TreeNode<K, V> root, TreeNode<K, V> x) 
 { 
 // 正如開(kāi)頭所說(shuō)，新加入樹(shù)節(jié)點(diǎn)默認(rèn)都是紅色的，不會(huì)破壞樹(shù)的結(jié)構(gòu)。 
 x.red = true; 
 // 這些變量名不是作者隨便定義的都是有意義的。 
 // xp：x parent，代表x的父節(jié)點(diǎn)。 
 // xpp：x parent parent，代表x的祖父節(jié)點(diǎn) 
 // xppl：x parent parent left，代表x的祖父的左節(jié)點(diǎn)。 
 // xppr：x parent parent right，代表x的祖父的右節(jié)點(diǎn)。 
 for (TreeNode<K, V> xp, xpp, xppl, xppr;;) 
 { 
 // 如果x的父節(jié)點(diǎn)為null說(shuō)明只有一個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)為根節(jié)點(diǎn)，根節(jié)點(diǎn)為黑色，red = false。 
 if ((xp = x.parent) == null) 
 { 
 x.red = false; 
 return x; 
 }  
 // 進(jìn)入else說(shuō)明不是根節(jié)點(diǎn)。 
 // 如果父節(jié)點(diǎn)是黑色，那么大吉大利（今晚吃雞），紅色的x節(jié)點(diǎn)可以直接添加到黑色節(jié)點(diǎn)后面，返回根就行了不需要任何多余的操作。 
 // 如果父節(jié)點(diǎn)是紅色的，但祖父節(jié)點(diǎn)為空的話也可以直接返回根此時(shí)父節(jié)點(diǎn)就是根節(jié)點(diǎn)，因?yàn)楦仨毷呛谏?，添加在后面沒(méi)有任何問(wèn)題。 
 else if (!xp.red || (xpp = xp.parent) == null) 
 return root; 
  
 // 一旦我們進(jìn)入到這里就說(shuō)明了兩件是情 
 // 1.x的父節(jié)點(diǎn)xp是紅色的，這樣就遇到兩個(gè)紅色節(jié)點(diǎn)相連的問(wèn)題，所以必須經(jīng)過(guò)旋轉(zhuǎn)變換。 
 // 2.x的祖父節(jié)點(diǎn)xpp不為空。 
  
 // 判斷如果父節(jié)點(diǎn)是否是祖父節(jié)點(diǎn)的左節(jié)點(diǎn) 
 if (xp == (xppl = xpp.left)) 
 { 
 // 父節(jié)點(diǎn)xp是祖父的左節(jié)點(diǎn)xppr 
 // 判斷祖父節(jié)點(diǎn)的右節(jié)點(diǎn)不為空并且是否是紅色的 
 // 此時(shí)xpp的左右節(jié)點(diǎn)都是紅的，所以直接進(jìn)行上面所說(shuō)的第三種變換，將兩個(gè)子節(jié)點(diǎn)變成黑色，將xpp變成紅色，然后將紅色節(jié)點(diǎn)x順利的添加到了xp的后面。 
 // 這里大家有疑問(wèn)為什么將x = xpp？ 
 // 這是由于將xpp變成紅色以后可能與xpp的父節(jié)點(diǎn)發(fā)生兩個(gè)相連紅色節(jié)點(diǎn)的沖突，這就又構(gòu)成了第二種旋轉(zhuǎn)變換，所以必須從底向上的進(jìn)行變換，直到根。 
 // 所以令x = xpp，然后進(jìn)行下下一層循環(huán)，接著往上走。 
 if ((xppr = xpp.right) != null && xppr.red) 
 { 
 xppr.red = false; 
 xp.red = false; 
 xpp.red = true; 
 x = xpp; 
 } 
 // 進(jìn)入到這個(gè)else里面說(shuō)明。 
 // 父節(jié)點(diǎn)xp是祖父的左節(jié)點(diǎn)xppr。 
 // 祖父節(jié)點(diǎn)xpp的右節(jié)點(diǎn)xppr是黑色節(jié)點(diǎn)或者為空，默認(rèn)規(guī)定空節(jié)點(diǎn)也是黑色的。 
 // 下面要判斷x是xp的左節(jié)點(diǎn)還是右節(jié)點(diǎn)。 
 else 
 { 
 // x是xp的右節(jié)點(diǎn)，此時(shí)的結(jié)構(gòu)是：xpp左->xp右->x。這明顯是第二中變換需要進(jìn)行兩次旋轉(zhuǎn)，這里先進(jìn)行一次旋轉(zhuǎn)。 
 // 下面是第一次旋轉(zhuǎn)。 
 if (x == xp.right) 
 { 
 root = rotateLeft(root, x = xp); 
 xpp = (xp = x.parent) == null ? null : xp.parent; 
 } 
 // 針對(duì)本身就是xpp左->xp左->x的結(jié)構(gòu)或者由于上面的旋轉(zhuǎn)造成的這種結(jié)構(gòu)進(jìn)行一次旋轉(zhuǎn)。 
 if (xp != null) 
 { 
 xp.red = false; 
 if (xpp != null) 
 { 
 xpp.red = true; 
 root = rotateRight(root, xpp); 
 } 
 } 
 } 
 }  
 // 這里的分析方式和前面的相對(duì)稱只不過(guò)全部在右測(cè)不再重復(fù)分析。 
 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); 
 } 
 } 
 } 
 } 
 } 
 } 

如果您的聯(lián)想能力很強(qiáng)的話估計(jì)到這里應(yīng)該已經(jīng)理解這集中變換的主要的關(guān)系。

下面簡(jiǎn)述一下前面的兩種種幸運(yùn)的情況

x本身為根節(jié)點(diǎn)返回x。 x的父節(jié)點(diǎn)為黑色或者x的父節(jié)點(diǎn)是根節(jié)點(diǎn)直接返回不需要變換。 如若上述兩個(gè)條件不滿足的話，就要進(jìn)行變換了，允許我再貼一點(diǎn)代碼......沒(méi)有代碼分析起來(lái)很困難。

06 顏色變換

if (xp == (xppl = xpp.left)) 
 { 
 if ((xppr = xpp.right) != null && xppr.red) 
 { 
 xppr.red = false; 
 xp.red = false; 
 xpp.red = true; 
 x = xpp; 
 } 
} 

這里是一個(gè)典型的一個(gè)黑色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是紅色的所以要進(jìn)行顏色變換，因?yàn)椴迦氲亩际羌t色節(jié)點(diǎn)，當(dāng)檢測(cè)到祖父節(jié)點(diǎn)的左右子節(jié)點(diǎn)都是紅色的時(shí)候兩個(gè)紅色就產(chǎn)生了沖突，所以先將節(jié)點(diǎn)進(jìn)行這種顏色變換，將祖父節(jié)點(diǎn)變成紅色，然后將祖父的兩個(gè)子節(jié)點(diǎn)變成黑色，這樣我們插入的紅色節(jié)點(diǎn)就不會(huì)違背紅黑樹(shù)的規(guī)則了。

這里有人會(huì)有疑問(wèn)，如果祖父節(jié)點(diǎn)是根節(jié)點(diǎn)呢，那樣的話祖父節(jié)點(diǎn)也會(huì)變成黑色，因?yàn)槊看窝h(huán)進(jìn)行插入平衡的操作當(dāng)進(jìn)行這種顏色變換之后都會(huì)將插入節(jié)點(diǎn)的引用指向祖父節(jié)點(diǎn)，當(dāng)進(jìn)行下一輪循環(huán)的時(shí)候會(huì)優(yōu)先檢測(cè)當(dāng)前節(jié)點(diǎn)是否是根節(jié)點(diǎn)，如果是根節(jié)點(diǎn)那就將顏色變成黑色，下面看圖：

當(dāng)將節(jié)點(diǎn)指向祖父節(jié)點(diǎn)進(jìn)行下一輪循環(huán)時(shí)：

07 兩個(gè)核心旋轉(zhuǎn)(左旋轉(zhuǎn)和右旋轉(zhuǎn))

// 一旦我們進(jìn)入到這里就說(shuō)明了兩件是情 
 // 1.x的父節(jié)點(diǎn)xp是紅色的，這樣就遇到兩個(gè)紅色節(jié)點(diǎn)相連的問(wèn)題，所以必須經(jīng)過(guò)旋轉(zhuǎn)變換。 
 // 2.x的祖父節(jié)點(diǎn)xpp不為空。 
  
 // 判斷如果父節(jié)點(diǎn)是否是祖父節(jié)點(diǎn)的左節(jié)點(diǎn) 
 if (xp == (xppl = xpp.left)) 
 { 
 if ((xppr = xpp.right) != null && xppr.red) 
 {// ...... 
 } 
 // 進(jìn)入到這個(gè)else里面說(shuō)明。 
 // 父節(jié)點(diǎn)xp是祖父的左節(jié)點(diǎn)xppr。 
 // 祖父節(jié)點(diǎn)xpp的右節(jié)點(diǎn)xppr是黑色節(jié)點(diǎn)或者為空，默認(rèn)規(guī)定空節(jié)點(diǎn)也是黑色的。 
 // 下面要判斷x是xp的左節(jié)點(diǎn)還是右節(jié)點(diǎn)。 
 else 
 { 
 // x是xp的右節(jié)點(diǎn)，此時(shí)的結(jié)構(gòu)是：xpp左->xp右->x。這明顯是第二中變換需要進(jìn)行兩次旋轉(zhuǎn)，這里先進(jìn)行一次旋轉(zhuǎn)。 
 // 下面是第一次旋轉(zhuǎn)。 
 if (x == xp.right) 
 { 
 root = rotateLeft(root, x = xp); 
 xpp = (xp = x.parent) == null ? null : xp.parent; 
 } 
 // 針對(duì)本身就是xpp左->xp左->x的結(jié)構(gòu)或者由于上面的旋轉(zhuǎn)造成的這種結(jié)構(gòu)進(jìn)行一次旋轉(zhuǎn)。 
 if (xp != null) 
 { 
 xp.red = false; 
 if (xpp != null) 
 { 
 xpp.red = true; 
 root = rotateRight(root, xpp); 
 } 
 } 
 } 
 }  

顏色變換完成后進(jìn)入下面的else塊

我們已知xp是xpp的左節(jié)點(diǎn)，首先判斷了x是xp的左節(jié)點(diǎn)還是右節(jié)點(diǎn)，如果是右節(jié)點(diǎn)的話構(gòu)成了下面的結(jié)構(gòu)。

這中結(jié)構(gòu)需要進(jìn)行雙旋轉(zhuǎn)，首先先進(jìn)行一次向左旋轉(zhuǎn)。

7.1 左旋轉(zhuǎn)

 1 static <K, V> TreeNode<K, V> rotateLeft(TreeNode<K, V> root, TreeNode<K, V> p) 
 2 { 
 3 // r：right，右節(jié)點(diǎn)。 
 4 // pp：parent parent，父節(jié)點(diǎn)的父節(jié)點(diǎn)。 
 5 // rl：right left，右節(jié)點(diǎn)的左節(jié)點(diǎn)。 
 6 TreeNode<K, V> r, pp, rl; 
 7 if (p != null && (r = p.right) != null) 
 8 { 
 9 if ((rl = p.right = r.left) != null) 
10 rl.parent = p; 
11 if ((pp = r.parent = p.parent) == null) 
12 (root = r).red = false; 
13 else if (pp.left == p) 
14 pp.left = r; 
15 else 
16 pp.right = r; 
17 r.left = p; 
18 p.parent = r; 
19 } 
20 return root; 
21 } 

1.剛進(jìn)入方法時(shí)，狀態(tài)如下圖。(RL可能是空的)

2.進(jìn)入了if塊后執(zhí)行到第10行后。

9 if ((rl = p.right = r.left) != null) 
10 rl.parent = p; 

此時(shí)如果9行的條件符合的話執(zhí)行10行RL指向P，如果RL為null的話，P的右節(jié)點(diǎn)指向null。

3.接著看11和12行代碼。

11 if ((pp = r.parent = p.parent) == null) 
12 (root = r).red = false; 

首先我們看11行if里面的賦值語(yǔ)句所造成的影響。

在if里面的表達(dá)式不管符不符合條件()內(nèi)的內(nèi)容都會(huì)執(zhí)行。

如果符合條件的話會(huì)執(zhí)行12行的代碼，變成了下面的結(jié)果。

由于PP為空所以只剩下這三個(gè)。

4.如果11行的條件為假的話，執(zhí)行完11行()內(nèi)的表達(dá)式后執(zhí)行13行

13 else if (pp.left == p) 
14 pp.left = r; 

滿足條件的話R和PP互相關(guān)聯(lián)。

5.由于進(jìn)入了13和14行所以不進(jìn)入15和16行的else語(yǔ)句。

15 else 
16 pp.right = r; 

6.看17和18行。

17 r.left = p; 
18 p.parent = r; 

最終執(zhí)行完了一個(gè)旋轉(zhuǎn)變成了我們開(kāi)始說(shuō)的第一種旋轉(zhuǎn)的形式，這個(gè)結(jié)構(gòu)還需要向右旋轉(zhuǎn)一次。

if (x == xp.right) 
 { 
 root = rotateLeft(root, x = xp); 
 xpp = (xp = x.parent) == null ? null : xp.parent; 
 } 
xpp = (xp = x.parent) == null ? null : xp.parent; 

執(zhí)行完上面的代碼，旋轉(zhuǎn)后調(diào)整x，xp，和xpp的關(guān)系得到下圖。

7.2 右旋轉(zhuǎn)

if (xp != null) 
{ 
xp.red = false; 
if (xpp != null) 
{ 
xpp.red = true; 
root = rotateLeft(root, xpp); 
} 
} 

1.首先讓XP變成黑色。

2.如果XPP不為空的話變成紅色。

由于我們?cè)趓otateLeft(root, xpp)，傳進(jìn)來(lái)的是XXP所以下面的的旋轉(zhuǎn)中實(shí)際上就是對(duì)XP和XXP執(zhí)行了一次與上面的方向相反其他完全相同的旋轉(zhuǎn)。

接著我們看向右旋轉(zhuǎn)的代碼

static <K, V> TreeNode<K, V> rotateRight(TreeNode<K, V> root, TreeNode<K, V> p) 
 { 
 // l：left，左節(jié)點(diǎn)。 
 // pp：parent parent，父節(jié)點(diǎn)的父節(jié)點(diǎn)。 
 // lr：left right，左節(jié)點(diǎn)的右節(jié)點(diǎn)。 
 TreeNode<K, V> l, pp, lr; 
 if (p != null && (l = p.left) != null) 
 { 
 if ((lr = p.left = l.right) != null) 
 lr.parent = p; 
 if ((pp = l.parent = p.parent) == null) 
 (root = l).red = false; 
 else if (pp.right == p) 
 pp.right = l; 
 else 
 pp.left = l; 
 l.right = p; 
 p.parent = l; 
 } 
 return root; 
 } 

3.剛進(jìn)來(lái)的時(shí)候結(jié)構(gòu)是這個(gè)樣子。

在這里的P就是剛才傳進(jìn)來(lái)的XPP。

4.這里我們認(rèn)為L(zhǎng)R是存在的，其實(shí)這個(gè)不影響主要的旋轉(zhuǎn)，為空就指向null唄，直接執(zhí)行完9和10行。

9 if ((lr = p.left = l.right) != null) 
0 lr.parent = p; 

5.在這里我們假使PP是存在的，直接執(zhí)行完11的表達(dá)式不再執(zhí)行12行。(不再分析不存在的情況)。

11 if ((pp = l.parent = p.parent) == null) 
12 (root = l).red = false; 

6.由于11行的條件不符合，現(xiàn)在直接執(zhí)行13行的表達(dá)式，不符合執(zhí)行15行else，執(zhí)行16行。

15 else 
16 pp.left = l; 

7.最后執(zhí)行層17和18行。

17 l.right = p; 
18 p.parent = l; 

最終完成兩次的旋轉(zhuǎn)。

08 疑問(wèn)?

大家可能覺(jué)得和剛才接不上其實(shí)是這樣的，剛才在右旋轉(zhuǎn)前的時(shí)候的圖像是這個(gè)樣的。

因?yàn)槲覀儌鬟M(jìn)來(lái)的是XPP，所以結(jié)合上一次的向左旋轉(zhuǎn)我們?cè)谙蛴倚D(zhuǎn)的時(shí)候看到全圖應(yīng)該是這個(gè)樣子的。(注：XPPP可能是XPP的左父節(jié)點(diǎn)也可能是右父節(jié)點(diǎn)這里不影響，而且可以是任意顏色)

現(xiàn)在知道為什么XPPP可以是任意顏色的了吧，因?yàn)樾D(zhuǎn)過(guò)后X是黑色的即便XPPP是紅色，此時(shí)我們又可以對(duì)兩個(gè)紅色的子節(jié)點(diǎn)進(jìn)行顏色變換了，變換后X和XPPP有發(fā)生了顏色沖突，接著進(jìn)行旋轉(zhuǎn)直到根。

static <K, V> TreeNode<K, V> balanceInsertion(TreeNode<K, V> root, TreeNode<K, V> x) 
 { 
 x.red = true; 
 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)) 
 { 
 // 插入位置父節(jié)點(diǎn)在祖父節(jié)點(diǎn)的左邊。 
 } 
 else 
 { 
 // 插入位置父節(jié)點(diǎn)在祖父節(jié)點(diǎn)的右邊。 
 } 
 } 
 } 

我們值分析了插入位置父節(jié)點(diǎn)在祖父節(jié)點(diǎn)的左邊的情況，并沒(méi)有分析另外一面的對(duì)稱情況，其實(shí)是一樣的因?yàn)檎{(diào)用的都是相同的方法。

以上就是在1.8中的HashMap新引進(jìn)的紅黑樹(shù)樹(shù)化的過(guò)程，與原來(lái)的鏈表相比當(dāng)同一個(gè)bucket上存儲(chǔ)很多entry的話樹(shù)形的查找結(jié)構(gòu)明顯要比鏈表線性的的效率要高。