HashMap紅黑樹

1.7 數組 + 連結清單

1.8 數組 + （連結清單 | 紅黑樹）

樹化意義

紅黑樹用來避免 dos 攻擊，防止連結清單超長時性能下降，樹化應當是偶然情況，是保底政策

hash 表的查找，更新的時間複雜度是 $o(1)$，而紅黑樹的查找，更新的時間複雜度是 $o(log_2⁡n )$，treenode 占用空間也比普通 node 的大，如非必要，盡量還是使用連結清單

hash 值如果足夠随機，則在 hash 表内按泊松分布，在負載因子 0.75 的情況下，長度超過 8 的連結清單出現機率是 0.00000006，樹化門檻值選擇 8 就是為了讓樹化幾率足夠小

樹化規則

當連結清單長度超過樹化門檻值 8 時，先嘗試擴容來減少連結清單長度，如果數組容量已經 >=64，才會進行樹化

退化規則

情況1：在擴容時如果拆分樹時，樹元素個數 <= 6 則會退化連結清單

情況2：remove 樹節點時，若 root、root.left、root.right、root.left.left 有一個為 null ，也會退化為連結清單