JDK 1.8 HashMap 核心優化：從鏈表到紅黑樹的演進

背景與動機

JDK 1.8 前，HashMap 採用「數組 + 鏈表」結構解決哈希沖突。極端情況下（大量鍵哈希碰撞），鏈表退化導致 get() 時間複雜度從 O(1) 降為 O(n)。為解決此性能隱患，JDK 1.8 引入紅黑樹替代長鏈表。

關鍵機制：樹化閾值

• TREEIFY_THRESHOLD = 8：當同一桶位元素數量超過 8 且數組長度 ≥ 64 時，鏈表轉為紅黑樹。
• UNTREEIFY_THRESHOLD = 6：擴容或刪除導致元素數低於 6 時，樹退化為鏈表。
• MIN_TREEIFY_CAPACITY = 64：數組長度未達 64 時優先擴容而非樹化，避免小數據量過度優化。

此動態切換將最壞情況查找複雜度從 O(n) 降為 O(log n)。

適用範圍與例外

採用此優化的類：HashMap、LinkedHashMap、ConcurrentHashMap。

不採用的類： Hashtable、WeakHashMap、IdentityHashMap。Hashtable 為保持迭代順序兼容性拒絕樹化；WeakHashMap、IdentityHashMap 因特殊用途未引入。

沖突產生根因

• 調用鍵對象的 hashCode() 計算索引。
• 不同對象可能產生相同 hashCode（哈希碰撞），導致進入同一桶位。
• equals() 與 hashCode() 契約：相同對象 hashCode 必相同，但 hashCode 相同不代表對象相同。

迭代順序說明

樹化後迭代順序會改變，但 HashMap 本身不保證迭代順序，故不影響正確性。Hashtable 為兼容舊代碼依賴順序特性，堅持不樹化。

總結

JDK 1.8 通過紅黑樹優化極端哈希沖突性能，體現「鏈表存儲、頻繁沖突樹化」的動態適應策略。開發者應正確重寫 hashCode() 與 equals()，減少碰撞概率，發揮 HashMap 最佳性能。