在Java8中為什麼要使用紅黑樹來實作的HashMap？

一、前言

在jdk1.8版本後，Java對HashMap做了改進，在連結清單長度大于8的時候，将後面的資料存在紅黑樹中，以加快檢索速度。

二、紅黑樹回顧

紅黑樹的英文是“Red-Black Tree"，簡稱R-B Tree。它是一種不嚴格的平衡二叉查找樹，我前面說了，它的定義是不嚴格符合平衡二叉查找樹的定義的。那紅黑樹空間是怎麼定義的呢？

顧名思義，紅黑樹中的節點，一類被标記為黑色，一類被标記為紅色除此之外，一棵紅黑樹還需要滿足這樣幾個要求：

• 根節點是黑色的；
• 每個葉子節點都是黑色的空節點（NIL），也就是說，葉子節點不存儲資料；
• 任何相鄰的節點都不能同時為紅色，紅色節點是被黑色節點隔開的；
• 每個節點，從該節點到達其可達葉子節點的所有路徑，都包含相同數目的黑色節點

1. 紅黑樹概念和圖示

紅黑樹比較傳統的定義是需要滿足以下五個特征：

1. 每個節點或者是黑色，或者是紅色。
2. 根節點是黑色。
3. 每個葉子節點（NIL）是黑色。 [注意：這裡葉子節點，是指為空(NIL或NULL)的葉子節點！]
4. 如果一個節點是紅色的，則它的子節點必須是黑色的。
5. 從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。

其特點在于給數的每一個節點加上了顔色屬性，在插入的過程中通過顔色變換和節點旋轉調平衡。其實部落客不是很喜歡上面的定義，還有一種視角就是将它與二三樹比較。

2.紅黑樹的優勢

紅黑樹是”近似平衡“的。

紅黑樹相比avl樹，在檢索的時候效率其實差不多，都是通過平衡來二分查找。但對于插入删除等操作效率提高很多。紅黑樹不像avl樹一樣追求絕對的平衡，他允許局部很少的不完全平衡，這樣對于效率影響不大，但省去了很多沒有必要的調平衡操作，avl樹調平衡有時候代價較大，是以效率不如紅黑樹，在現在很多地方都是底層都是紅黑樹的天下啦。

紅黑樹的高度隻比高度平衡的AVL樹的高度（log2n）僅僅大了一倍，在性能上卻好很多。

HashMap在裡面就是連結清單加上紅黑樹的一種結構，這樣利用了連結清單對記憶體的使用率以及紅黑樹的高效檢索，是一種很happy的資料結構。

AVL樹是一種高度平衡的二叉樹，是以查找的非常高，但是，有利就有弊，AVL樹為了維持這種高度的平衡，就要付出更多代價。每次插入、删除都要做調整，就比較複雜、耗時。是以，對于有頻繁的插入、删除操作的資料集合，使用AVL樹的代價就有點高了。

紅黑樹隻是做到了近似平衡，并不嚴格的平衡，是以在維護的成本上，要比AVL樹要低。

是以，紅黑樹的插入、删除、查找各種操作性能都比較穩定。對于工程應用來說，要面對各種異常情況，為了支撐這種工業級的應用，我們更傾向于這種性能穩定的平衡二叉查找樹。

三、總結

java8不是用紅黑樹來管理hashmap，而是在hash值相同的情況下（且重複數量大于8），用紅黑樹來管理資料。 紅黑樹相當于排序資料，可以自動的使用二分法進行定位，性能較高。一般情況下，hash值做的比較好的話基本上用不到紅黑樹。

紅黑樹犧牲了一些查找性能 但其本身并不是完全平衡的二叉樹。是以插入删除操作效率略高于AVL樹。

AVL樹用于自平衡的計算犧牲了插入删除性能，但是因為最多隻有一層的高度差，查詢效率會高一些。

-------------------------

本文為轉載，原文https://blog.csdn.net/it_qingfengzhuimeng/article/details/103308308

這裡寫下自己看後的通俗回答：紅黑樹是非标準的平衡樹，隻要求部分絕對平衡，但是三次之後都可以轉為平衡樹。查詢效率上和平衡二叉樹其實是一樣的都是二分法。平衡二叉樹在插入删除中為了維持絕對平衡需要進行節點調整，浪費時間，而紅黑樹不需要，是以在插入删除操作中時間複雜度會比平衡二叉樹更低。這就是HashMap選擇紅黑樹結構的原因（這也算是面試一題）

• 紅黑樹測試網站：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

一、前言

在jdk1.8版本後，Java對HashMap做了改進，在連結清單長度大于8的時候，将後面的資料存在紅黑樹中，以加快檢索速度。

二、紅黑樹回顧

紅黑樹的英文是“Red-Black Tree"，簡稱R-B Tree。它是一種不嚴格的平衡二叉查找樹，我前面說了，它的定義是不嚴格符合平衡二叉查找樹的定義的。那紅黑樹空間是怎麼定義的呢？

顧名思義，紅黑樹中的節點，一類被标記為黑色，一類被标記為紅色除此之外，一棵紅黑樹還需要滿足這樣幾個要求：

• 根節點是黑色的；
• 每個葉子節點都是黑色的空節點（NIL），也就是說，葉子節點不存儲資料；
• 任何相鄰的節點都不能同時為紅色，紅色節點是被黑色節點隔開的；
• 每個節點，從該節點到達其可達葉子節點的所有路徑，都包含相同數目的黑色節點

1. 紅黑樹概念和圖示

紅黑樹比較傳統的定義是需要滿足以下五個特征：

1. 每個節點或者是黑色，或者是紅色。
2. 根節點是黑色。
3. 每個葉子節點（NIL）是黑色。 [注意：這裡葉子節點，是指為空(NIL或NULL)的葉子節點！]
4. 如果一個節點是紅色的，則它的子節點必須是黑色的。
5. 從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。

其特點在于給數的每一個節點加上了顔色屬性，在插入的過程中通過顔色變換和節點旋轉調平衡。其實部落客不是很喜歡上面的定義，還有一種視角就是将它與二三樹比較。

2.紅黑樹的優勢

紅黑樹是”近似平衡“的。

紅黑樹相比avl樹，在檢索的時候效率其實差不多，都是通過平衡來二分查找。但對于插入删除等操作效率提高很多。紅黑樹不像avl樹一樣追求絕對的平衡，他允許局部很少的不完全平衡，這樣對于效率影響不大，但省去了很多沒有必要的調平衡操作，avl樹調平衡有時候代價較大，是以效率不如紅黑樹，在現在很多地方都是底層都是紅黑樹的天下啦。

紅黑樹的高度隻比高度平衡的AVL樹的高度（log2n）僅僅大了一倍，在性能上卻好很多。

HashMap在裡面就是連結清單加上紅黑樹的一種結構，這樣利用了連結清單對記憶體的使用率以及紅黑樹的高效檢索，是一種很happy的資料結構。

AVL樹是一種高度平衡的二叉樹，是以查找的非常高，但是，有利就有弊，AVL樹為了維持這種高度的平衡，就要付出更多代價。每次插入、删除都要做調整，就比較複雜、耗時。是以，對于有頻繁的插入、删除操作的資料集合，使用AVL樹的代價就有點高了。

紅黑樹隻是做到了近似平衡，并不嚴格的平衡，是以在維護的成本上，要比AVL樹要低。

是以，紅黑樹的插入、删除、查找各種操作性能都比較穩定。對于工程應用來說，要面對各種異常情況，為了支撐這種工業級的應用，我們更傾向于這種性能穩定的平衡二叉查找樹。

三、總結

java8不是用紅黑樹來管理hashmap，而是在hash值相同的情況下（且重複數量大于8），用紅黑樹來管理資料。 紅黑樹相當于排序資料，可以自動的使用二分法進行定位，性能較高。一般情況下，hash值做的比較好的話基本上用不到紅黑樹。

紅黑樹犧牲了一些查找性能 但其本身并不是完全平衡的二叉樹。是以插入删除操作效率略高于AVL樹。

AVL樹用于自平衡的計算犧牲了插入删除性能，但是因為最多隻有一層的高度差，查詢效率會高一些。

-------------------------