絮叨

學(xué)校短學(xué)期剛結(jié)束了，離學(xué)校開學(xué)還有很多天，一直呆在寢室玩游戲豈不是浪費(fèi)了大好時(shí)光，于是心血來潮想看看HashMap的源碼。雖然我沒有經(jīng)歷過面試，但是JAVA程序員都知道，HashMap是面試官必問的知識(shí)點(diǎn)，而我現(xiàn)在只停留在對(duì)HashMap的基本使用層面，因此我覺得有必要深入了解一下HashMap的底層原理。在HashMap中，我覺得最難的應(yīng)該是紅黑樹了吧，我結(jié)合代碼和畫圖軟件研究了兩天，終于總結(jié)出規(guī)律，現(xiàn)在分享給大家

一、紅黑樹的特點(diǎn)

下面是紅黑樹的5條性質(zhì)，現(xiàn)在大家要對(duì)這些性質(zhì)有印象，后面我會(huì)結(jié)合圖解的形式，多次提到這些性質(zhì)來幫助大家記憶

• 每個(gè)節(jié)點(diǎn)要么是紅的，要么是黑色的
• 跟節(jié)點(diǎn)一定是黑色的
• 葉子節(jié)點(diǎn)一定是黑色的（葉節(jié)點(diǎn)一般不畫，在末尾節(jié)點(diǎn)上，沒有內(nèi)容）
• 紅節(jié)點(diǎn)下的兩個(gè)子節(jié)點(diǎn)一定是黑色的
• 任意一條從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑中黑色節(jié)點(diǎn)的個(gè)數(shù)相等

紅黑樹插入節(jié)點(diǎn)后，若導(dǎo)致紅黑樹不平衡（整棵樹不滿足上面5條性質(zhì)中的任意一條），就會(huì)進(jìn)行變色、旋轉(zhuǎn)操作，直到紅黑樹平衡，而學(xué)習(xí)紅黑樹的難點(diǎn)正是這些變色、旋轉(zhuǎn)的規(guī)則

二、紅黑樹的優(yōu)點(diǎn)

談到紅黑樹的優(yōu)點(diǎn)，就不得不拿出AVL樹來進(jìn)行比較。

AVL樹是完全平衡的樹，根的最大深度和最小深度相差不大于1，查找效率比較高，而紅黑樹不是完全平衡樹，查找效率略低于AVL樹

紅黑樹的插入和刪除操作比AVL樹快很多，因?yàn)榧t黑樹保證插入刪除時(shí)最多需要旋轉(zhuǎn)三次就可以達(dá)到平衡，而AVL樹每次插入刪除會(huì)進(jìn)行大量的平衡度計(jì)算，開銷很大

因此，紅黑樹犧牲了一點(diǎn)點(diǎn)查找效率，使它有更快的插入刪除操作，綜合來說，紅黑樹性能高于AVL樹

三、紅黑樹插入如何平衡

3.1 紅黑樹插入基本規(guī)則

1. 新插入的節(jié)點(diǎn)是紅的
2. 父節(jié)點(diǎn)是黑的，或者父節(jié)點(diǎn)是根節(jié)點(diǎn)，直接插入
3. 父節(jié)點(diǎn)是紅的，需要變色、旋轉(zhuǎn)（也就是出現(xiàn)兩個(gè)連在一起的紅節(jié)點(diǎn)失去平衡）
4. 如果一次平衡后出現(xiàn)祖父節(jié)點(diǎn)和祖父節(jié)點(diǎn)的父親是紅的，那么把祖父節(jié)點(diǎn)當(dāng)做新節(jié)點(diǎn)，繼續(xù)變色翻轉(zhuǎn)，知道整體平衡（遞歸思想）

3.2 紅黑樹變色規(guī)則

在基本規(guī)則中提到，出現(xiàn)兩個(gè)連續(xù)的紅節(jié)點(diǎn)需要變色，旋轉(zhuǎn)，所以我們暫且先不管要不要旋轉(zhuǎn)，先來看看紅黑樹的變色規(guī)則是怎么樣的吧

3.2.1 新節(jié)點(diǎn)沒有叔叔節(jié)點(diǎn)，或者叔叔節(jié)點(diǎn)是黑的

這種情況只要把父節(jié)點(diǎn)變黑，祖父節(jié)點(diǎn)變紅就ok了

這種情況不但要把父節(jié)點(diǎn)變黑，祖父節(jié)點(diǎn)變紅，還要考慮祖父節(jié)點(diǎn)是否是根節(jié)點(diǎn)，在紅黑樹插入基本規(guī)則第二條中寫到，根節(jié)點(diǎn)一定是黑的，所以如果祖父節(jié)點(diǎn)是根節(jié)點(diǎn)，需要再次變色把根節(jié)點(diǎn)顏色變黑

3.2.2 新節(jié)點(diǎn)的叔叔節(jié)點(diǎn)是紅的

這種情況把叔叔節(jié)點(diǎn)和父節(jié)點(diǎn)顏色變黑，祖父節(jié)點(diǎn)變紅，變完之后還要考慮祖父節(jié)點(diǎn)是否是根節(jié)點(diǎn)，根據(jù)情況再次變色

3.2.3 小結(jié)

1. 因?yàn)樾鹿?jié)點(diǎn)是紅色的，所以當(dāng)父節(jié)點(diǎn)是紅色時(shí)，出現(xiàn)了連續(xù)的紅節(jié)點(diǎn)，導(dǎo)致不平衡，要進(jìn)行變色
2. 要變色的情況下，叔叔節(jié)點(diǎn)和父節(jié)點(diǎn)一定要變黑，叔叔節(jié)點(diǎn)沒有就不考慮它，祖父節(jié)點(diǎn)要變紅
3. 祖父節(jié)點(diǎn)變紅以后，需要考慮它是否是根節(jié)點(diǎn)，如果是根節(jié)點(diǎn)，根節(jié)點(diǎn)要變黑

3.3 紅黑樹旋轉(zhuǎn)規(guī)則

在上一節(jié)我們搞明白了紅黑樹是如何變色的，現(xiàn)在來看看紅黑樹的旋轉(zhuǎn)規(guī)則，在這一環(huán)節(jié)，變色的過程就不再具體描述了，我只描述紅黑樹如何旋轉(zhuǎn)

紅黑樹旋轉(zhuǎn)有四種情況：

1. 左旋
2. 右旋
3. 先左旋，再右旋
4. 先右旋，再左旋

左旋和右旋其實(shí)是差不多的，只是方向換了，如果看完左旋你能想到右旋是如何進(jìn)行的，那么說明我寫的還是很通俗易懂的

3.3.1 左旋

首先有兩種情況下會(huì)進(jìn)行左旋操作

• 新節(jié)點(diǎn)、父節(jié)點(diǎn)都在右
• 父節(jié)點(diǎn)在左，新節(jié)點(diǎn)在右

第二種情況比較復(fù)雜，等我寫完左旋和右旋操作后，再來考慮這種情況，因?yàn)樗婕暗阶笮陀倚齼刹讲僮?/p>

這里先來看一下新節(jié)點(diǎn)、父節(jié)點(diǎn)都在右的情況下是如何左旋的

圖解1

這種情況下左旋的節(jié)點(diǎn)都是祖父節(jié)點(diǎn)，祖父節(jié)往左轉(zhuǎn)成為了父節(jié)點(diǎn)左孩子（因?yàn)樵谧筮呑匀欢怀蔀樽蠛⒆永玻?/p>

圖解2

這種情況稍微有點(diǎn)復(fù)雜，也是祖父節(jié)點(diǎn)往左旋轉(zhuǎn)，成為父節(jié)點(diǎn)的左孩子

可是原來父節(jié)點(diǎn)是有左孩子的（也就是兄弟節(jié)點(diǎn)），那么這個(gè)兄弟節(jié)點(diǎn)就成了祖父節(jié)點(diǎn)的右孩子（可以這么想，祖父節(jié)點(diǎn)左旋轉(zhuǎn)后，兄弟節(jié)點(diǎn)在右邊，因此成了他的右孩子）。

還有一點(diǎn)是原來祖父節(jié)點(diǎn)是有父親的（這里我們叫做祖先節(jié)點(diǎn)），如果祖先節(jié)點(diǎn)的左孩子是祖父節(jié)點(diǎn)，那么旋轉(zhuǎn)后祖先節(jié)點(diǎn)的左孩子變成了父節(jié)點(diǎn)；如果祖先節(jié)點(diǎn)的右孩子是祖父節(jié)點(diǎn)，那么旋轉(zhuǎn)后祖先節(jié)點(diǎn)的右孩子變成了父節(jié)點(diǎn)（可以這么想，父節(jié)點(diǎn)移到了祖父節(jié)點(diǎn)的位置）

3.3.2 右旋

這里也有兩種情況下會(huì)進(jìn)行右旋操作

• 新節(jié)點(diǎn)、父節(jié)點(diǎn)都在左
• 父節(jié)點(diǎn)在右，新節(jié)點(diǎn)在左

右旋的操作根左旋很相似，只是方向換了一下，我這里就不再詳細(xì)的解釋了，大家看圖自己領(lǐng)悟，最好是把左旋看明白，在自己想想對(duì)應(yīng)的情況下右旋應(yīng)該怎么操作，想到了再和我下面的圖對(duì)照一下看是否正確

圖解1

圖解2

3.3.3 先左旋，再右旋

這種情況比較復(fù)雜，不多逼逼，直接上圖

如何理解？

可以看到，新節(jié)點(diǎn)、父節(jié)點(diǎn)、祖父節(jié)點(diǎn)不在同一條直線上，從圖中可以看出這種情況的操作思想是先把這三個(gè)節(jié)點(diǎn)旋轉(zhuǎn)到一條直線上，再應(yīng)用我們上面所講的左旋和右旋，來達(dá)到平衡，所以就有兩步旋轉(zhuǎn)操作了

第一步旋轉(zhuǎn)

第一步旋轉(zhuǎn)的旋轉(zhuǎn)節(jié)點(diǎn)和上面小節(jié)的節(jié)點(diǎn)不一樣，上面小節(jié)里旋轉(zhuǎn)的是祖父節(jié)點(diǎn)，而這里旋轉(zhuǎn)的是父節(jié)點(diǎn)（父節(jié)點(diǎn)左旋下來，子節(jié)點(diǎn)左旋上去）

第二步旋轉(zhuǎn)

第二步旋轉(zhuǎn)就是上面講到的右旋，自己慢慢體會(huì)

如何記憶？

這里我們?cè)趺纯吹膱D就想到先左旋還是先右旋呢，教你一個(gè)方法，看父節(jié)點(diǎn)在哪邊，父節(jié)點(diǎn)在左邊，左旋，父節(jié)點(diǎn)在右邊，右旋，這樣是不是就很簡單了呢

變色過程

之前變色過程都是在第一步做的，但這種情況是在第二步做的，所以我們看到這種圖時(shí)就要這樣想，左旋+變色+右旋，這樣就很容易記住了

3.3.4 先右旋，再左旋

這種情況也是和先左旋再右旋差不多的，只是方向變了一下，這里不過多贅述，大家看圖慢慢體會(huì)

3.3.5 小節(jié)

1. 當(dāng)祖父節(jié)點(diǎn)、父節(jié)點(diǎn)、新節(jié)點(diǎn)在一條直線上，發(fā)生左旋和右旋，父節(jié)點(diǎn)和子節(jié)點(diǎn)在左，右旋；父節(jié)點(diǎn)和子節(jié)點(diǎn)在右，左旋
2. 當(dāng)祖父節(jié)點(diǎn)、父節(jié)點(diǎn)、新節(jié)點(diǎn)不在一條直線上，先旋轉(zhuǎn)父節(jié)點(diǎn)，使它與子節(jié)點(diǎn)都在左或都在右，再變色，再旋轉(zhuǎn)。父在左，左旋+變色+右旋，父在右，右旋+變色+左旋

四 紅黑樹左旋規(guī)則詳細(xì)總結(jié)

五 紅黑樹插入規(guī)則詳細(xì)總結(jié)

六、心得體會(huì)

HashMap的源碼在1.7和1.8兩個(gè)版本變化很大，建議大家如果看的話先看1.7的源碼，再看1.8的源碼。說實(shí)話，剛開始我1.7的源碼都看不懂，后來找了個(gè)講jdk1.7中HashMap源碼視頻，講的很不錯(cuò)，看完視頻后，再自己看一遍源碼，就很有感覺了。之后看1.8源碼我沒有看過視頻，自己就能看懂了

所以說實(shí)話，對(duì)于紅黑樹的平衡規(guī)則我沒有參考其他任何人寫的文章，我也嘗試看看別人寫的關(guān)于紅黑樹的文章，但是我還是覺得這些節(jié)點(diǎn)變色旋轉(zhuǎn)過程太復(fù)雜，要通過文章看懂并且記住很有難度，所以我選擇了看源碼自己總結(jié)規(guī)律

后來把這些過程全部搞懂了，并且也記下了，是通過理解+技巧結(jié)合記下的，這個(gè)技巧在我這個(gè)文章中也要提到，不是死記硬背的

最后一定要像我一樣把自己學(xué)到的記錄下來，方便自己看，也分享給需要的人看，這是一舉兩得的事情。

七、寫給讀者的話

接下來，我會(huì)總結(jié)HashMap紅黑樹刪除時(shí)的平衡規(guī)則，到時(shí)候也會(huì)分享出來，希望大家多多關(guān)注哦

如何文章中哪里有錯(cuò)誤，或者有疑問，大家一定要在評(píng)論區(qū)寫下來，我會(huì)及時(shí)答復(fù)大家和修改錯(cuò)誤的，謝謝啦

作者：myboy
鏈接：https://juejin.im/post/6876350595305996301
來源：掘金
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。