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

前言

10年的海陽網(wǎng)站建設(shè)經(jīng)驗，針對設(shè)計、前端、開發(fā)、售后、文案、推廣等六對一服務(wù)，響應(yīng)快，48小時及時工作處理。全網(wǎng)營銷推廣的優(yōu)勢是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動調(diào)整海陽建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計，從而大程度地提升瀏覽體驗。創(chuàng)新互聯(lián)從事“海陽網(wǎng)站設(shè)計”,“海陽網(wǎng)站推廣”以來，每個客戶項目都認(rèn)真落實執(zhí)行。

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

01、故事的起因

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

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

紅黑樹查詢：其訪問性能近似于折半查找，時間復(fù)雜度 O(logn)；
鏈表查詢：這種情況下，需要遍歷全部元素才行，時間復(fù)雜度 O(n)；

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

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

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

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

1、每個節(jié)點要么是紅色，要么是黑色，但根節(jié)點永遠(yuǎn)是黑色的；
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)說到當(dāng)樹的結(jié)構(gòu)發(fā)生改變時，紅黑樹的條件可能被破壞，需要通過調(diào)整使得查找樹重新滿足紅黑樹的條件。

調(diào)整可以分為兩類：一類是顏色調(diào)整，即改變某個節(jié)點的顏色，這種比較簡單，直接將節(jié)點顏色進(jìn)行轉(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)定性。過程如下：

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

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

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

左旋方法 rotateLeft 如下：

/*
?*?左旋邏輯
?*/
static??TreeNode?rotateLeft(TreeNode?root,
?TreeNode?p)?{
			//root:表示根節(jié)點
			//p:表示要調(diào)整的節(jié)點
			//r:表示p的右節(jié)點
			//pp:表示p的parent節(jié)點
			//rl:表示p的右孩子的左孩子節(jié)點
?TreeNode?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)過程如下：

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

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

/*
?*?右旋邏輯
?*/
static??TreeNode?rotateRight(TreeNode?root,
?TreeNode?p)?{
			//root:表示根節(jié)點
			//p:表示要調(diào)整的節(jié)點
			//l:表示p的左節(jié)點
			//pp:表示p的parent節(jié)點
			//lr:表示p的左孩子的右孩子節(jié)點
?TreeNode?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)整過程圖解

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