一文帶你速通 HashMap 底層核心數(shù)據(jù)結(jié)構(gòu)紅黑樹(shù)
一、什么是紅黑樹(shù)
在權(quán)威書籍中，對(duì)于紅黑樹(shù)的解釋是這樣的:
- 每個(gè)節(jié)點(diǎn)或者紅色，或者是黑色。
- 根節(jié)點(diǎn)為黑色。
- 每一個(gè)葉子節(jié)點(diǎn)都是黑色。
- 如果一個(gè)節(jié)點(diǎn)是紅色，那么他的孩子節(jié)點(diǎn)都是黑色。
- 從任意一個(gè)節(jié)點(diǎn)，經(jīng)過(guò)的黑色節(jié)點(diǎn)是一樣的。
在《算法4》一書中認(rèn)為紅黑樹(shù)和2-3樹(shù)是等價(jià)的。
二、2-3樹(shù)詳解
2-3樹(shù)的2節(jié)點(diǎn)和3節(jié)點(diǎn)
很多人認(rèn)為紅黑樹(shù)是2-3樹(shù)的另一種實(shí)現(xiàn)，所以在正式的介紹紅黑樹(shù)之前，我們不妨了解2-3樹(shù)，先來(lái)說(shuō)說(shuō)2-3樹(shù)的2節(jié)點(diǎn)，其性質(zhì)如下：
- 滿足二分搜索樹(shù)的基本性質(zhì)。(左節(jié)點(diǎn)小于節(jié)點(diǎn)，右節(jié)點(diǎn)大于節(jié)點(diǎn))
- 節(jié)點(diǎn)分為2節(jié)點(diǎn)和3節(jié)點(diǎn)，2節(jié)點(diǎn)即可以掛兩個(gè)子節(jié)點(diǎn)。3節(jié)點(diǎn)即可掛3節(jié)點(diǎn)。
如下圖所示，這就是典型的2-3樹(shù)的2節(jié)點(diǎn),可以看到2節(jié)點(diǎn)即父節(jié)點(diǎn)存放一個(gè)元素的節(jié)點(diǎn)，這種節(jié)點(diǎn)只能掛兩個(gè)元素。
同理我們?cè)俳o出3節(jié)點(diǎn)的圖例，可以看出3節(jié)點(diǎn)的就是由兩個(gè)節(jié)點(diǎn)拼接成的節(jié)點(diǎn)，其左中右分別可以掛一個(gè)子節(jié)點(diǎn)，由此我們才稱它為3節(jié)點(diǎn)。
2-3樹(shù)是絕對(duì)平衡樹(shù)
絕對(duì)平衡樹(shù)的定義即任何時(shí)刻任意節(jié)點(diǎn)，左節(jié)點(diǎn)和右節(jié)點(diǎn)的層數(shù)都是一樣的。那么2-3樹(shù)是如何實(shí)現(xiàn)絕對(duì)平衡的呢？假設(shè)我們要將下面的節(jié)點(diǎn)存放到2-3樹(shù)中：
42 37 12 18 6 11 5首先添加42，由于2-3樹(shù)為空，所以直接插入即可。
再插入37 ，因?yàn)?7比42小，所以理應(yīng)插入到42的左節(jié)點(diǎn)中，但是左節(jié)點(diǎn)為空，所以它只能作為42的鄰節(jié)點(diǎn)，由此構(gòu)成一個(gè)3節(jié)點(diǎn)。
再插入12，此時(shí)構(gòu)成了一個(gè)4節(jié)點(diǎn)，不符合2-3樹(shù)節(jié)點(diǎn)的特征。
所以我們需要將4節(jié)點(diǎn)進(jìn)程拆解，將37的左右鄰接節(jié)點(diǎn)全部拆為子節(jié)點(diǎn)：
在添加18，比37小，比12大，所以要插入到12的右子節(jié)點(diǎn)，但是右子節(jié)點(diǎn)為空，所以18就和12合并變?yōu)?節(jié)點(diǎn)
再添加6構(gòu)成一個(gè)4節(jié)點(diǎn)需要拆解，導(dǎo)致失衡：
所以我們對(duì)這個(gè)4節(jié)點(diǎn)進(jìn)程拆解，可以看到37的左右節(jié)點(diǎn)還是失衡。
所以我們將12向上合并，和37構(gòu)成3節(jié)點(diǎn)，最終2-3樹(shù)得以平衡。
三、紅黑樹(shù)詳解
紅黑樹(shù)和2-3樹(shù)的關(guān)系
前文我們提到紅黑樹(shù)可以理解為2-3樹(shù)的另一種變體，我們以2-3樹(shù)的2節(jié)點(diǎn)為例，對(duì)應(yīng)成紅黑樹(shù)的標(biāo)識(shí)就是將2節(jié)點(diǎn)的左邊染紅并作為右節(jié)點(diǎn)的子節(jié)點(diǎn)，注意，筆者這里雖說(shuō)12作為37的子節(jié)點(diǎn)，但是在紅黑樹(shù)的性質(zhì)中，這兩個(gè)節(jié)點(diǎn)邏輯上可以理解為一個(gè)節(jié)點(diǎn)，這樣的理解便于我們后續(xù)了解紅黑樹(shù)的黑平衡。
對(duì)應(yīng)的，我們根據(jù)上面描述我們給出這樣一棵2-3樹(shù)，將其轉(zhuǎn)為紅黑樹(shù)：
可以看到，轉(zhuǎn)為紅黑樹(shù)只需將2-3樹(shù)的3節(jié)點(diǎn)的左節(jié)點(diǎn)染紅，例如上圖的6、12組成的3節(jié)點(diǎn)，我們只需將6染紅，作為黑節(jié)點(diǎn)12的左節(jié)點(diǎn)即可。
紅黑樹(shù)的性質(zhì)詳解
了解了紅黑樹(shù)這個(gè)數(shù)據(jù)結(jié)構(gòu)的圖例之后，我們來(lái)總結(jié)一下紅黑樹(shù)的特性：
從任意節(jié)點(diǎn)到另外一個(gè)葉子節(jié)點(diǎn)，經(jīng)過(guò)的黑節(jié)點(diǎn)是一樣的。
嚴(yán)格意義上，紅黑樹(shù)是一個(gè)絕對(duì)的“黑平衡樹(shù)”，即我們將紅節(jié)點(diǎn)和其父節(jié)點(diǎn)當(dāng)作一個(gè)整體，我們就會(huì)發(fā)現(xiàn)，這個(gè)紅黑樹(shù)的層級(jí)是絕對(duì)平衡的。而將"將紅節(jié)點(diǎn)和其父節(jié)(黑節(jié)點(diǎn))點(diǎn)當(dāng)作一個(gè)整體"的過(guò)程，就是2-3樹(shù)。
紅黑樹(shù)最大高度為2N(logN),所以添加復(fù)雜度估算為O(logN)
紅黑樹(shù)如何添加元素
(1) 添加一個(gè)比插入位置大的節(jié)點(diǎn)
以2-3數(shù)為例，假設(shè)我們樹(shù)中只有一個(gè)節(jié)點(diǎn)37，此時(shí)插入一個(gè)42，按照2-3樹(shù)的做法，會(huì)將42插入到37的右子節(jié)點(diǎn)，但此時(shí)2-3數(shù)還沒(méi)有右子節(jié)點(diǎn)，所以就將其添加到自己的右邊，構(gòu)成3節(jié)點(diǎn)。
若是紅黑樹(shù)，42和37進(jìn)行比對(duì)之后發(fā)現(xiàn)，42大于37，最終42就會(huì)以右子節(jié)點(diǎn)的姿態(tài)在37的右邊，很明顯這違背了紅黑樹(shù)的特征，所有的紅節(jié)點(diǎn)都必須位于左節(jié)點(diǎn)。所以我們需要對(duì)其進(jìn)行左旋，并將右上節(jié)點(diǎn)染黑，左下節(jié)點(diǎn)染紅。
對(duì)于上述的左旋轉(zhuǎn)我們不妨來(lái)一個(gè)比較實(shí)際的例子，如下圖所示，假設(shè)經(jīng)過(guò)一輪的插入之后37作為42的根節(jié)點(diǎn)，很明顯此時(shí)紅黑樹(shù)的狀態(tài)是失衡的(從黑平衡角度來(lái)看，37左邊有1層，42為2層，是失衡的)。
所以我們需要進(jìn)行一次左旋轉(zhuǎn)，因?yàn)榧t黑樹(shù)的性質(zhì)保證黑節(jié)點(diǎn)37的右子樹(shù)都大于37，所以左旋時(shí)，先找到紅節(jié)點(diǎn)42的最小節(jié)點(diǎn)作為37的右子節(jié)點(diǎn)，于是37指向41：
因?yàn)?1頂替了紅節(jié)點(diǎn)42，42直接上升為父節(jié)點(diǎn)，自此以此保證黑平衡的左旋就完成了：
完整的代碼如下：
/**
* 插入的節(jié)點(diǎn)構(gòu)成3節(jié)點(diǎn)，但是紅節(jié)點(diǎn)在左邊，需要進(jìn)行左旋
*
* @param node
* @return
*/
private Node leftRotate(Node node) {
// 找到node節(jié)點(diǎn)的左節(jié)點(diǎn)
Node x = node.right;
//左旋
node.right = x.left;
x.left = node;
//顏色翻轉(zhuǎn)
x.color = node.color;
node.color = RED;
return x;
}(2) 連續(xù)添加兩個(gè)節(jié)點(diǎn)都在左邊
如下圖，構(gòu)成了一個(gè)左傾斜的節(jié)點(diǎn)，導(dǎo)致失衡。
對(duì)此我們就需要進(jìn)行一個(gè)右旋的操作，如下圖，因?yàn)榧t黑樹(shù)的有序性，這使得42這個(gè)根節(jié)點(diǎn)大于左邊的所有節(jié)點(diǎn)，所以我們將左節(jié)點(diǎn)中最大的節(jié)點(diǎn)作為42的左節(jié)點(diǎn)，讓37作為根節(jié)點(diǎn)，完成黑平衡，如下圖。
可以看到雖然完成了右旋轉(zhuǎn)的操作，但是最終的左右節(jié)點(diǎn)都是紅的，導(dǎo)致紅黑樹(shù)并不是黑平衡的，所以這里就需要一次顏色翻轉(zhuǎn)。這里我們先貼出右旋轉(zhuǎn)的代碼，在介紹顏色翻轉(zhuǎn)邏輯：
private Node rightRotate(Node node) {
Node x = node.left;
node.left = x.right;
x.right = node;
node.color = RED;
x.color = node.color;
return x;
}(3) 添加節(jié)點(diǎn)后子節(jié)點(diǎn)都變紅
在上文右旋操作導(dǎo)致，顏色錯(cuò)誤進(jìn)而出現(xiàn)紅黑樹(shù)違背黑平衡的情況，所以我們需要進(jìn)行顏色翻轉(zhuǎn)，如下圖，我們將子節(jié)點(diǎn)都為紅的節(jié)點(diǎn)染黑，再將父節(jié)點(diǎn)染紅(父節(jié)點(diǎn)會(huì)將筆者后續(xù)的遞歸邏輯中變黑)。
這樣依賴37左節(jié)點(diǎn)層級(jí)為1，右節(jié)點(diǎn)層級(jí)也為1(黑平衡要求我們將左紅節(jié)點(diǎn)和黑節(jié)點(diǎn)看作一個(gè)整體)
(4) 添加節(jié)點(diǎn)成為L(zhǎng)R型
如下圖，LR型就是37 12 13這樣的插入順序，對(duì)此我們只需左旋再右旋最后顏色翻轉(zhuǎn)一下即可
四、手寫一個(gè)紅黑樹(shù)
針對(duì)上述的圖解，我們給出實(shí)現(xiàn)紅黑樹(shù)的幾個(gè)問(wèn)題點(diǎn)：
- 紅黑樹(shù)是由一個(gè)個(gè)節(jié)點(diǎn)構(gòu)成，所以我們需要聲明節(jié)點(diǎn)內(nèi)部類，內(nèi)部類擁有顏色、左節(jié)點(diǎn)指針、右節(jié)點(diǎn)指針、key、value、顏色等幾個(gè)屬性。
- 有了節(jié)點(diǎn)內(nèi)部類，我們就需要對(duì)紅黑樹(shù)類添加相關(guān)屬性描述了，首先是紅黑樹(shù)的容量、其次紅黑樹(shù)的操作都需要從樹(shù)根開(kāi)始，所以我們需要首節(jié)點(diǎn)root、以及容量size。
- 紅黑樹(shù)插入都需要和每個(gè)key進(jìn)行比較，所以紅黑樹(shù)類的k要求可以比較，所以我們定義的紅黑樹(shù)要求是泛型類，并且泛型key必須是可比較的，所以這個(gè)k泛型需要繼承Comparable。
完成這些鋪墊之后，我們就需要進(jìn)行插入操作的邏輯分析了，我們不妨對(duì)上文長(zhǎng)篇論述的插入過(guò)程進(jìn)行整理一下:
- 插入的節(jié)點(diǎn)在當(dāng)前節(jié)點(diǎn)右邊，導(dǎo)致紅節(jié)點(diǎn)在右邊，需要進(jìn)行左旋轉(zhuǎn)保證黑平衡。
- 連續(xù)插入兩個(gè)節(jié)點(diǎn)都在當(dāng)前節(jié)點(diǎn)左邊，導(dǎo)致向左傾斜，需要進(jìn)行右旋轉(zhuǎn)保持平衡。
- 第一次插入的節(jié)點(diǎn)在當(dāng)前節(jié)點(diǎn)左邊，然后再插入一個(gè)節(jié)點(diǎn)在紅黑樹(shù)右邊導(dǎo)致紅黑樹(shù)失衡。我們需要先左旋一下，再右旋一下。
- 當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)和右節(jié)點(diǎn)都是紅色的，需要將顏色翻轉(zhuǎn)為黑色。
分析之后我們發(fā)現(xiàn)3這個(gè)一點(diǎn)包含了1、2的操作，所以我們編寫3、4兩個(gè)點(diǎn)的邏輯就可以實(shí)現(xiàn)上面的所有功能了，如下圖:
注意紅黑樹(shù)要求根節(jié)點(diǎn)為黑色，所以我們完成上述的操作之后，需要手動(dòng)將根節(jié)點(diǎn)變?yōu)楹谏?/p>
對(duì)核心邏輯完成梳理之后，我們就可以開(kāi)始對(duì)紅黑樹(shù)展開(kāi)編碼了。首先我們需要?jiǎng)?chuàng)建紅黑樹(shù)類，可以看到我們聲明的k泛型繼承Comparable：
public class RedBlackTree<K extends Comparable<K>, V>對(duì)于節(jié)點(diǎn)顏色只有紅黑兩種，所以我們將其常量化：
private static final boolean RED = true;
private static final boolean BLACK = false;然后我們?cè)俑鶕?jù)上文的描述給出紅黑樹(shù)每個(gè)節(jié)點(diǎn)的成員變量：
private class Node<K, V> {
private K key;
private V val;
private Node left, right;
private boolean color;
public Node(K key, V val) {
this.key = key;
this.val = val;
this.left = null;
this.right = null;
this.color = RED;
}
}然后在進(jìn)行紅黑樹(shù)容量、首節(jié)點(diǎn)、構(gòu)造方法聲明：
private Node root;
private int size;
public RedBlackTree() {
this.root = null;
this.size = 0;
}終于我們可以正式實(shí)現(xiàn)節(jié)點(diǎn)添加邏輯，首選是左旋的邏輯，這一點(diǎn)我們?cè)谏衔膱D解添加過(guò)程時(shí)已經(jīng)寫好了偽代碼，補(bǔ)充完成即可。
/**
* 插入的節(jié)點(diǎn)構(gòu)成3節(jié)點(diǎn)，但是紅節(jié)點(diǎn)在左邊，需要進(jìn)行左旋
*
* @param node
* @return
*/
private Node leftRotate(Node node) {
// 找到node節(jié)點(diǎn)的左節(jié)點(diǎn)
Node x = node.right;
//左旋
node.right = x.left;
x.left = node;
//顏色翻轉(zhuǎn)
x.color = node.color;
node.color = RED;
return x;
}右旋邏輯:
private Node rightRotate(Node node) {
Node x = node.left;
node.left = x.right;
x.right = node;
node.color = RED;
x.color = node.color;
return x;
}顏色翻轉(zhuǎn)：
private void flipColors(Node node) {
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}完成后我們就可以根據(jù)上文分析的添加邏輯，編寫3、4邏輯整合,首先為了代碼復(fù)用，我們編寫一下顏色判斷的邏輯，注意若節(jié)點(diǎn)不存在，我們也認(rèn)定這個(gè)節(jié)點(diǎn)為黑：
private boolean isRed(Node<K, V> node) {
if (node == null) {
return false;
}
return node.color == RED;
}然后完成添加邏輯，可以看到筆者通過(guò)遞歸將3、4邏輯完成的紅黑樹(shù)的添加操作，完成添加操作并旋轉(zhuǎn)平衡后的當(dāng)前節(jié)點(diǎn)。
private Node<K, V> add(Node<K, V> node, K key, V val) {
if (node == null) {
size++;
return new Node(key, val);
}
if (key.compareTo(node.key) < 0) {
node.left = add(node.left, key, val);
} else if (key.compareTo(node.key) > 0) {
node.right = add(node.right, key, val);
} else {
node.val = val;
}
// 左節(jié)點(diǎn)不為紅，右節(jié)點(diǎn)為紅，左旋
if (isRed(node.right) && !isRed(node.left)) {
node = leftRotate(node);
}
// 左鏈右旋
if (isRed(node.left) && isRed(node.left.left)) {
node = rightRotate(node);
}
// 顏色翻轉(zhuǎn)
if (isRed(node.left) && isRed(node.right)) {
flipColors(node);
}
return node;
}完成核心邏輯后，我們就將根節(jié)點(diǎn)變黑即可，考慮封裝性，我們將上文方法封裝成一個(gè)add允許外部傳鍵值進(jìn)來(lái)。
public void add(K key, V val) {
root = add(root, key, val);
root.color = BLACK;
}補(bǔ)充剩余邏輯
獲取容量和獲取根節(jié)點(diǎn)：
public int getSize() {
return size;
}
private Node getRoot() {
return root;
}用層次遍歷法測(cè)試結(jié)果
我們希望測(cè)試紅黑樹(shù)添加的準(zhǔn)確性，所以我們用嘗試用代碼添加以下幾個(gè)節(jié)點(diǎn)
150 172 194 271 293 370完成后的樹(shù)應(yīng)該如下圖所示
為了驗(yàn)證筆者代碼的準(zhǔn)確性，我們編寫一段層次遍歷的測(cè)試代碼，按層次順序以及顏色輸出節(jié)點(diǎn)
public void levelOrder() {
Node root = this.getRoot();
ArrayDeque<Node> queue = new ArrayDeque();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.pop();
System.out.println("key:" + node.key + " val: " + node.val + " color:" + (node.color == RED ? "red" : "black"));
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}測(cè)試代碼，可以看到輸出結(jié)果正確
public static void main(String[] args) {
RedBlackTree<Integer, String> rbTree = new RedBlackTree<>();
rbTree.add(150, "");
rbTree.add(172, "");
rbTree.add(194, "");
rbTree.add(271, "");
rbTree.add(293, "");
rbTree.add(370, "");
rbTree.levelOrder();
/**
* 輸出結(jié)果
*
* key:271 val: color:black
* key:172 val: color:red
* key:370 val: color:black
* key:150 val: color:black
* key:194 val: color:black
* key:293 val: color:red
*/
}五、Java中HashMap關(guān)于紅黑樹(shù)的使用
插入
我們都知道Java中的HashMap在底層數(shù)組容量為64且當(dāng)前這個(gè)bucket的鏈表長(zhǎng)度達(dá)到8時(shí)會(huì)觸發(fā)擴(kuò)容，對(duì)此我們不妨寫一段代碼測(cè)試一下，代碼如下所示，可以看到筆者為了更好的演示，將每一個(gè)map的value值聲明為當(dāng)前key在hashMap底層數(shù)組中的索引位置。所以我們?cè)趍ap.put("590", "Idx：12");打上斷點(diǎn)
HashMap<String, String> map = new HashMap<String, String>(64);
map.put("24", "Idx：2");
map.put("46", "Idx：2");
map.put("68", "Idx：2");
map.put("29", "Idx：7");
map.put("150", "Idx：12");
map.put("172", "Idx：12");
map.put("194", "Idx：12");
map.put("271", "Idx：12");
map.put("293", "Idx：12");
map.put("370", "Idx：12");
map.put("392", "Idx：12");
map.put("491", "Idx：12");
//轉(zhuǎn)紅黑樹(shù)
map.put("590", "Idx：12");核心代碼如下所示，我們傳入的590的key會(huì)在i為12的鏈表中不斷查找空閑的位置，然后完成插入，循環(huán)過(guò)程中會(huì)記錄當(dāng)前鏈表元素個(gè)數(shù)binCount ，經(jīng)過(guò)判斷binCount >TREEIFY_THRESHOLD - 1即8-1=7,然后調(diào)用treeifyBin看看是擴(kuò)容還是轉(zhuǎn)紅黑樹(shù)
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;
//計(jì)算出hashMap這個(gè)key對(duì)應(yīng)索引Ii的位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
....略
//核心邏輯在這里，我們傳入的590的key會(huì)在i為12的鏈表中不斷查找空閑的位置，然后完成插入，循環(huán)過(guò)程中會(huì)記錄當(dāng)前鏈表元素個(gè)數(shù)binCount ，經(jīng)過(guò)判斷binCount >TREEIFY_THRESHOLD - 1即8-1=7,然后調(diào)用treeifyBin轉(zhuǎn)紅黑樹(shù)
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
.....
}
}
.........略
}我們?cè)賮?lái)看看treeifyBin，可以看到如果數(shù)組容量小于64直接擴(kuò)容，反之就是將當(dāng)前節(jié)點(diǎn)轉(zhuǎn)為樹(shù)節(jié)點(diǎn)然后調(diào)用treeify轉(zhuǎn)紅黑樹(shù)，關(guān)于紅黑樹(shù)的邏輯上文已經(jīng)詳細(xì)說(shuō)明了這里就不多贅述了。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果數(shù)組容量小于64直接擴(kuò)容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
//將節(jié)點(diǎn)轉(zhuǎn)為樹(shù)節(jié)點(diǎn)，hd即為head指向當(dāng)前鏈表頭節(jié)點(diǎn)，然后后續(xù)節(jié)點(diǎn)一次轉(zhuǎn)為樹(shù)節(jié)點(diǎn)和前驅(qū)節(jié)點(diǎn)彼此指向，從而構(gòu)成一個(gè)雙向鏈表
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
//如果hd不為空說(shuō)明需要轉(zhuǎn)紅黑樹(shù)，調(diào)用treeify
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}HashMap中的紅黑樹(shù)是如何完成查詢的呢？(重點(diǎn))
HashMap源碼如下，首先通過(guò)hashCode找到桶的位置，然后判斷這個(gè)桶是否只有一個(gè)元素，如果沒(méi)有則直接返回，反之調(diào)用getTreeNode從紅黑樹(shù)中找到對(duì)應(yīng)的元素
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
//計(jì)算hash對(duì)應(yīng)的節(jié)點(diǎn)first
(first = tab[(n - 1) & hash]) != null) {
//如果有且只有一個(gè)則直接返回
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
//如果是紅黑樹(shù)則調(diào)用getTreeNode
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}我們步入getTreeNode會(huì)看到find方法，可以看到它查詢紅黑樹(shù)的元素邏輯很簡(jiǎn)單，根據(jù)紅黑樹(shù)的有序性找到和查詢?cè)豩ash值相同、equals為true的節(jié)點(diǎn)返回即可。
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
//比對(duì)元素hash值大于h，p指向p的左子節(jié)點(diǎn)進(jìn)行下一次比對(duì)
if ((ph = p.hash) > h)
p = pl;
//比對(duì)值小于查詢節(jié)點(diǎn)的hash，p指向右子節(jié)點(diǎn)進(jìn)行下一次比對(duì)
else if (ph < h)
p = pr;
//如果key一樣且equals為true直接返回這個(gè)元素
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}小結(jié)
本文通過(guò)圖解加實(shí)現(xiàn)為讀者演示了紅黑樹(shù)的特點(diǎn)和工作流程，可以看到紅黑樹(shù)的邏輯起始并沒(méi)有那么復(fù)雜，只要讀者專注核心概念，用一些簡(jiǎn)單的示例畫圖了解過(guò)程，再通過(guò)需求分析所有邏輯和設(shè)計(jì)之后，編碼就沒(méi)有那么困難了。既使遇到問(wèn)題，我們也可以抓住數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，配合使用debug+中序遍歷也能解決邏輯漏洞。從而加深對(duì)數(shù)據(jù)結(jié)構(gòu)的理解。
在此我們?cè)賹?duì)二分搜索樹(shù)、AVL樹(shù)、紅黑樹(shù)三者使用場(chǎng)景進(jìn)行一下說(shuō)明：
- 隨機(jī)添加節(jié)點(diǎn)：若節(jié)點(diǎn)存在大量隨機(jī)性，使用二分搜索樹(shù)即可，相比于紅黑樹(shù)的2O(nLogN)復(fù)雜度，二分搜索樹(shù)的O(logN)性能更佳，但是二分搜索樹(shù)可能存在退化成鏈表的情況，需謹(jǐn)慎考慮。
- 僅作查詢：對(duì)于查詢AVL最合適不過(guò)。他的平衡高度為logn比紅黑樹(shù)的“黑平衡”那種2logn的平衡要出色很多，在添加少，查詢多的情況下，使用AVL樹(shù)更合適。
- 綜合操作：若需要增刪改查等綜合操作，建議使用紅黑樹(shù)，紅黑樹(shù)雖然不是最優(yōu)但是綜合上是最優(yōu)的。
