一文看懂 HashMap 中的紅黑樹實現(xiàn)原理

前言

本文咱們了解一下紅黑樹的設(shè)計，相比 jdk1.7 的 HashMap 而言，jdk1.8 最重要的就是引入了紅黑樹的設(shè)計，當沖突的鏈表長度超過 8 個的時候，鏈表結(jié)構(gòu)就會轉(zhuǎn)為紅黑樹結(jié)構(gòu)。

01、故事的起因

“JDK1.8 最重要的就是引入了紅黑樹的設(shè)計（當沖突的鏈表長度超過 8 個的時候），為什么要這樣設(shè)計呢？好處就是避免在最極端的情況下沖突鏈表變得很長很長，在查詢的時候，效率會非常慢。

• 紅黑樹查詢：其訪問性能近似于折半查找，時間復雜度 O(logn)；

• 鏈表查詢：這種情況下，需要遍歷全部元素才行，時間復雜度 O(n)；

本文主要是講解紅黑樹的實現(xiàn)，只有充分理解了紅黑樹，對于之前的分析才會更加理解。

“簡單的說，紅黑樹是一種近似平衡的二叉查找樹，其主要的優(yōu)點就是“平衡“，即左右子樹高度幾乎一致，以此來防止樹退化為鏈表，通過這種方式來保障查找的時間復雜度為 log(n)。

關(guān)于紅黑樹的內(nèi)容，網(wǎng)上給出的內(nèi)容非常多，主要有以下幾個特性：

• 1、每個節(jié)點要么是紅色，要么是黑色，但根節(jié)點永遠是黑色的；

• 2、每個紅色節(jié)點的兩個子節(jié)點一定都是黑色；

• 3、紅色節(jié)點不能連續(xù)（也即是，紅色節(jié)點的孩子和父親都不能是紅色）；

• 4、從任一節(jié)點到其子樹中每個葉子節(jié)點的路徑都包含相同數(shù)量的黑色節(jié)點；

• 5、所有的葉節(jié)點都是是黑色的（注意這里說葉子節(jié)點其實是上圖中的 NIL 節(jié)點）；

在樹的結(jié)構(gòu)發(fā)生改變時（插入或者刪除操作），往往會破壞上述條件 3 或條件 4，需要通過調(diào)整使得查找樹重新滿足紅黑樹的條件。

02、調(diào)整方式

“上面已經(jīng)說到當樹的結(jié)構(gòu)發(fā)生改變時，紅黑樹的條件可能被破壞，需要通過調(diào)整使得查找樹重新滿足紅黑樹的條件。

調(diào)整可以分為兩類：一類是顏色調(diào)整，即改變某個節(jié)點的顏色，這種比較簡單，直接將節(jié)點顏色進行轉(zhuǎn)換即可；另一類是結(jié)構(gòu)調(diào)整，改變檢索樹的結(jié)構(gòu)關(guān)系。結(jié)構(gòu)調(diào)整主要包含兩個基本操作：左旋（Rotate Left），右旋（RotateRight）。

2.1、左旋

左旋的過程是將 p 的右子樹繞 p 逆時針旋轉(zhuǎn)，使得 p 的右子樹成為 p 的父親，同時修改相關(guān)節(jié)點的引用，使左子樹的深度加 1，右子樹的深度減 1，通過這種做法來調(diào)整樹的穩(wěn)定性。過程如下：

以 jdk1.8 為例，打開 HashMap 的源碼部分，紅黑樹內(nèi)部類 TreeNode 屬性分析：

static?final?class?TreeNode<K,V>?extends?LinkedHashMap.Entry<K,V>?{
		//指向父節(jié)點的指針
		TreeNode<K,V>?parent;
		//指向左孩子的指針
?TreeNode<K,V>?left;
		//指向右孩子的指針
?TreeNode<K,V>?right;
		//前驅(qū)指針，跟next屬性相反的指向
?TreeNode<K,V>?prev;
		//是否為紅色節(jié)點
?boolean?red;
		......
}

左旋方法 rotateLeft 如下：

/*
?*?左旋邏輯
?*/
static?<K,V>?TreeNode<K,V>?rotateLeft(TreeNode<K,V>?root,
?TreeNode<K,V>?p)?{
			//root:表示根節(jié)點
			//p:表示要調(diào)整的節(jié)點
			//r:表示p的右節(jié)點
			//pp:表示p的parent節(jié)點
			//rl:表示p的右孩子的左孩子節(jié)點
?TreeNode<K,V>?r,?pp,?rl;
			//r判斷，如果r為空則旋轉(zhuǎn)沒有意義
?if?(p?!=?null?&&?(r?=?p.right)?!=?null)?{
				//多個等號的連接操作從右往左看，設(shè)置rl的父親為p
?if?((rl?=?p.right?=?r.left)?!=?null)
?rl.parent?=?p;
				//判斷p的父親，為空，為根節(jié)點，根節(jié)點的話就設(shè)置為黑色
?if?((pp?=?r.parent?=?p.parent)?==?null)
?(root?=?r).red?=?false;
				//判斷p節(jié)點是左兒子還是右兒子
?else?if?(pp.left?==?p)
?pp.left?=?r;
?else
?pp.right?=?r;
?r.left?=?p;
?p.parent?=?r;
?}
?return?root;
}

2.2、右旋

了解了左旋轉(zhuǎn)之后，相應(yīng)的就會有右旋，邏輯基本也是一樣，只是方向變了。右旋的過程是將 p 的左子樹繞 p 順時針旋轉(zhuǎn)，使得 p 的左子樹成為 p 的父親，同時修改相關(guān)節(jié)點的引用，使右子樹的深度加 1，左子樹的深度減 1，通過這種做法來調(diào)整樹的穩(wěn)定性。實現(xiàn)過程如下：

同樣的，右旋方法 rotateRight 如下：

/*
?*?右旋邏輯
?*/
static?<K,V>?TreeNode<K,V>?rotateRight(TreeNode<K,V>?root,
?TreeNode<K,V>?p)?{
			//root:表示根節(jié)點
			//p:表示要調(diào)整的節(jié)點
			//l:表示p的左節(jié)點
			//pp:表示p的parent節(jié)點
			//lr:表示p的左孩子的右孩子節(jié)點
?TreeNode<K,V>?l,?pp,?lr;
			//l判斷，如果l為空則旋轉(zhuǎn)沒有意義
?if?(p?!=?null?&&?(l?=?p.left)?!=?null)?{
				//多個等號的連接操作從右往左看，設(shè)置lr的父親為p
?if?((lr?=?p.left?=?l.right)?!=?null)
?lr.parent?=?p;
				//判斷p的父親，為空，為根節(jié)點，根節(jié)點的話就設(shè)置為黑色
?if?((pp?=?l.parent?=?p.parent)?==?null)
?(root?=?l).red?=?false;
				//判斷p節(jié)點是右兒子還是左兒子
?else?if?(pp.right?==?p)
?pp.right?=?l;
?else
?pp.left?=?l;
?l.right?=?p;
?p.parent?=?l;
?}
?return?root;
}

03、操作示例介紹

3.1、插入調(diào)整過程圖解

3.2、刪除調(diào)整過程圖解

3.3、查詢過程圖解

04、總結(jié)

至此，紅黑樹的實現(xiàn)就基本完成了，關(guān)于紅黑樹的結(jié)構(gòu)，有很多種情況，情況也比較復雜，但是整體調(diào)整流程，基本都是先調(diào)整結(jié)構(gòu)然后調(diào)整顏色，直到最后滿足紅黑樹特性要求為止。

讀者福利

加微信：haolagui521備注51CTO領(lǐng)取附送學習進階架構(gòu)資料、PDF書籍文檔、面試資料