[面試|HashMap|紅黑樹] 轉載：HashMap到8時轉為紅黑樹到6轉為連結清單 原因詳解

來源：HashMap到8時轉為紅黑樹到6轉為連結清單 原因詳解

HashMap的初始長度是16，每次擴容時都會在原始的長度上翻倍（size × 2），是以長度一定是2的n次方。

紅黑樹的出現時機（連結清單樹化）：1. 連結清單的長度達到8； 2. 元素的總數量達到64。

紅黑樹退哈成連結清單： 紅黑樹中元素的數量小于6。

哈希桶擴容的條件：元素數量 >= 長度（16）× 加載因子（0.75）

擴容時，需重新計算桶中每一個位置的内容：

如果原桶内容為空，則直接複制過去；

當桶位置連有連結清單時，則計算出該連結清單的低位鍊和高位鍊，如果是低位鍊則直接複制到原索引位置，如果是高位鍊，則複制到（原索引 + 原長度）的位置（新索引），桶位置是紅黑樹時，同理，因為樹種有退化成連結清單時需要的節點位址值，是以紅黑樹同樣可計算出該樹的低位鍊和高位鍊。

連結清單轉換成紅黑樹的門檻值為什麼是 8 ，而加載因子為什麼是0.75？

在hashCode離散性很好的情況下，紅黑樹用到的機率非常小，因為資料均勻分布在每個桶中，幾乎不會有桶中連結清單長度會達到門檻值(8)。但是在随機hashCode下，離散性可能會變差，然而JDK又不能阻止使用者實作這種不好的hash算法，是以就可能導緻不均勻的資料分布。

事實上，随機hashCode算法下所有桶中節點的分布頻率遵循如下的泊松分布。在擴容門檻值為0.75的情況下，（即使因為擴容而方差很大）遵循着參數平均為0.5的泊松分布。一個桶中連結清單長度達到8個元素的機率為0.00000006，幾乎是不可能事件。之是以選擇8，是時間和空間的權衡(trade-off)，是根據機率統計決定的, 是非常嚴謹和科學的。

大部分情況下，連結清單存儲能節約存儲空間同時有着良好的查找性能；極個别情況下，節點數達到8個，轉為紅黑樹，能獲得更好的查找性能，同時因為是個别情況，不需要大量的存儲空間。

1、TreeNodes(紅黑樹)占用空間是普通Nodes(連結清單)的兩倍，為了時間和空間的權衡。

2、節點的分布頻率會遵循泊松分布，連結清單長度達到8個元素的機率為0.00000006，幾乎是不可能事件.

為什麼轉化為紅黑樹的門檻值8和轉化為連結清單的門檻值6不一樣?

為了避免頻繁來回轉化。