前言

? ? ? ? 我們都知道在HashMap中，當(dāng)數(shù)組長度大于64并且鏈表長度大于8時，HashMap會從數(shù)組+鏈表的結(jié)構(gòu)轉(zhuǎn)換成紅黑樹，那為什么要轉(zhuǎn)換成紅黑樹呢，或者為什么不一開始就使用紅黑樹呢？接下來我們將去具體的去剖析一下！

一、首先介紹一下紅黑樹？

????????紅黑樹是一種自平衡的二叉搜索樹，它是一種在插入和刪除操作時能夠自我調(diào)整以保持平衡的數(shù)據(jù)結(jié)構(gòu)。紅黑樹之所以稱為紅黑樹，是因?yàn)槊總€節(jié)點(diǎn)都具有顏色屬性，可以是紅色或黑色，這些顏色屬性必須滿足一定的約束條件，以確保樹的平衡性。

紅黑樹必須滿足四個條件！

1. 根節(jié)點(diǎn)是黑色的。
2. 每個葉子節(jié)點(diǎn)（NIL節(jié)點(diǎn)，即空節(jié)點(diǎn)）是黑色的。
3. 如果一個節(jié)點(diǎn)是紅色的，則它的兩個子節(jié)點(diǎn)都是黑色的（不能有連續(xù)的紅色節(jié)點(diǎn)）。
4. 從任一節(jié)點(diǎn)到其每個葉子的所有路徑都包含相同數(shù)量的黑色節(jié)點(diǎn)（黑色節(jié)點(diǎn)的數(shù)量被稱為該節(jié)點(diǎn)的“黑色高度”）。

然后它在插入和刪除具體是怎么實(shí)現(xiàn)的，相對來說過程會比較復(fù)雜，簡單概括以下步驟：

1. 剛插入的節(jié)點(diǎn)，默認(rèn)是紅色節(jié)點(diǎn)，它會一次次進(jìn)行比較，比當(dāng)前節(jié)點(diǎn)小就放在左邊，比當(dāng)前節(jié)點(diǎn)大就放在右邊，也就是二分查找，所以復(fù)雜度是O(log n)；
2. 那接下來就是要滿足上面的四個條件了，大概實(shí)現(xiàn)就是會在爺叔父節(jié)點(diǎn)之間進(jìn)行一個紅黑顏色互換，或者說在自旋之后再進(jìn)行顏色互換，以滿足上述四個條件。

當(dāng)然，想了解紅黑樹插入和刪除具體是怎么實(shí)現(xiàn)的，可以看這個視頻，講的很清晰：https://www.bilibili.com/video/BV18C4y137jn?vd_source=b16ef7f0a66010623908ff61e2645909

二、HashMap為什么使用紅黑樹代替數(shù)組+鏈表？

在說這個問題之前，先說一下數(shù)組、鏈表和紅黑樹各自的一個特點(diǎn)

1、數(shù)組

• 查詢快：數(shù)組支持通過索引進(jìn)行 O(1) 時間復(fù)雜度的一個隨機(jī)訪問，這意味著可以直接訪問任何位置的元素。并且數(shù)組在內(nèi)存中是連續(xù)存儲的，這種緊湊的布局有利于 CPU 緩存的命中率，提高訪問效率；
• 增刪慢：在數(shù)組中插入元素需要將插入位置后面的所有元素向后移動一個位置，以便為新元素騰出空間，這涉及到大量元素的移動，尤其是在數(shù)組的開頭或中間插入元素時。?類似地，從數(shù)組中刪除元素時，需要將刪除位置后面的所有元素向前移動一個位置，以填補(bǔ)刪除元素留下的空隙。所以當(dāng)對最后一個元素進(jìn)行增刪時，復(fù)雜度是O(1)，對其它元素進(jìn)行增刪時，復(fù)雜度是O(n)；
• 需要預(yù)先分配內(nèi)存：數(shù)組在使用前需要預(yù)先分配內(nèi)存空間，其大小通常是固定的。

2、鏈表

• 查詢慢：鏈表查找元素需要從頭節(jié)點(diǎn)開始按順序遍歷到目標(biāo)位置，時間復(fù)雜度為 O(n)。并且，鏈表中的節(jié)點(diǎn)在內(nèi)存中是分散存儲的，這可能導(dǎo)致緩存不命中，從而降低訪問效率。
• 增刪快：鏈表的插入和刪除操作具有 O(1) 的時間復(fù)雜度，無論是在鏈表的頭部、尾部還是中間插入或刪除元素，都只需要修改相鄰節(jié)點(diǎn)的指針，而不需要移動其他元素。
• 無需預(yù)先分配內(nèi)存： 鏈表不需要預(yù)先分配連續(xù)的內(nèi)存空間，每個節(jié)點(diǎn)可以在需要時動態(tài)分配，這意味著鏈表可以輕松地?cái)U(kuò)展或收縮，不會浪費(fèi)內(nèi)存。

3、紅黑樹

• 查詢，增刪都比較快：因?yàn)樗且环N二分查找樹，它的查詢、增刪的時間復(fù)雜度都為O(log n)，雖然它的查詢速度比不過數(shù)組，修改速度比不過鏈表，但是在大量的數(shù)據(jù)下，紅黑樹非常的穩(wěn)定，它的修改效率遠(yuǎn)遠(yuǎn)大于數(shù)組，查詢效率遠(yuǎn)遠(yuǎn)大于鏈表；
• 有序性：?紅黑樹是一種有序的數(shù)據(jù)結(jié)構(gòu)，可以輕松實(shí)現(xiàn)范圍查詢、有序遍歷等操作。
• 動態(tài)性能好：?紅黑樹能夠適應(yīng)動態(tài)數(shù)據(jù)的變化，保持較為穩(wěn)定的性能表現(xiàn)。

那其實(shí)答案也是很明顯了，也就是在HashMap存了大量的數(shù)據(jù)情況下，數(shù)組的查詢效率可以，但是增刪效率太慢了，鏈表的增刪效率可以，但是查詢效率太慢了，而紅黑樹剛好是個折中的選擇，它的增刪改查效率都很不錯，都是O(log n)。

那為什么是數(shù)組長度大于64并且鏈表長度大于8才轉(zhuǎn)換成紅黑樹？為什么不一開始就使用紅黑樹呢？

我們來看看HashMap源碼注釋是怎么說的：

????????大概意思就是說，因?yàn)?strong>樹節(jié)點(diǎn)所占的空間是普通節(jié)點(diǎn)的兩倍，所以我們只有在桶中包含足夠的普通節(jié)點(diǎn)時才使用樹節(jié)點(diǎn)。

????????而為什么閾值是8，這涉及到一個泊松分布的概念，在理想情況下，桶(bins)中鏈表長度的值符合泊松分布，當(dāng)鏈表長度為 8 的時候，概率僅為 0.00000006。 所以在理論上來說，當(dāng)存入1666萬數(shù)據(jù)的時候，鏈表長度才會達(dá)到8。

????????從平均查找長度來看，紅黑樹復(fù)雜度是O(log n)，它的平均查找長度是log n，如果長度為8，則log n=3；而鏈表的復(fù)雜度為O(n)，最好的情況為1次，最壞的情況為n次，平均查找長度為n/2，長度為8時，n/2=4，所以閾值8時，紅黑樹的檢索效率要大于鏈表。

????????當(dāng)長度為6時紅黑樹退化為鏈表，是因?yàn)閘og n=log 6約等于2.6，而n/2=6/2=3，兩者相差不大，而紅黑樹節(jié)點(diǎn)占用的內(nèi)存空間是普通節(jié)點(diǎn)的兩倍，所以此時轉(zhuǎn)換最合適。

三、總結(jié)

為什么不一開始就使用紅黑樹？

1. 在數(shù)組長度和鏈表長度不大的時候，數(shù)組+鏈表的性能也很好；
2. 而紅黑樹插入元素時，需要保證滿足紅黑樹的四個特性，那它紅黑顏色替換，或者自旋后替換，需要消耗一定的性能；
3. 并且樹節(jié)點(diǎn)所占的空間是普通節(jié)點(diǎn)的兩倍，那它需要占用更多的內(nèi)存空間。
4. 一句話就是，小而美，迫不得已才用紅黑樹，殺雞焉用牛刀！

那為什么是當(dāng)數(shù)組長度大于64并且鏈表長度大于8時，才轉(zhuǎn)換成紅黑樹？

1. 在理想情況下，桶(bins)中鏈表長度的值符合泊松分布，當(dāng)鏈表長度為 8 的時候，概率僅為 0.00000006。 在理論上來說，當(dāng)存入1666萬數(shù)據(jù)的時候，鏈表長度才會達(dá)到8。
2. 而通常我們的 Map 里面是不會存儲這么多的數(shù)據(jù)的，所以通常情況下，并不會發(fā)生從鏈表向紅黑樹的轉(zhuǎn)換。
3. 所以我們平時基本見不到轉(zhuǎn)換成紅黑樹的場景，但是假如你重寫hashCode()方法進(jìn)行惡搞，讓它每次都是固定值，那他就會發(fā)生hash碰撞，每次碰撞都會加入鏈表尾部，當(dāng)鏈表長度大于8時，很可能就轉(zhuǎn)換成紅黑樹了。這點(diǎn)可以注意一下，hashCode()請不要設(shè)置固定值，不然很容易樹化，到時候內(nèi)存占用會增加一倍！

ps：以下是我整理的java面試資料，感興趣的可以看看。最后，創(chuàng)作不易，覺得寫得不錯的可以點(diǎn)點(diǎn)關(guān)注！

鏈接：https://www.yuque.com/u39298356/uu4hxh?# 《Java知識寶典》?文章來源地址http://www.zghlxwxcb.cn/news/detail-851068.html

到了這里，關(guān)于紅黑樹是什么，為什么HashMap使用紅黑樹代替數(shù)組+鏈表？的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！