《Java 編程思想》學習筆記：第 11 章 Map 容器詳解 — HashMap、LinkedHashMap、TreeMap 核心原理與選型

《Java 編程思想》學習筆記：第 11 章 Map 容器詳解 — HashMap、LinkedHashMap、TreeMap 核心原理與選型

本文基於《Thinking in Java》第 4 版第 11 章持有對象，系統梳理 Map 接口層次結構、三大主流實現類原理、性能特徵、選型指南與源碼關鍵點。

Map 接口層次結構

• Map<K,V>：根接口，不繼承 Collection，提供 Key-Value 映射，Key 唯一，Value 可重複。
• AbstractMap<K,V>：骨幹實現，僅留 entrySet() 抽象，限制 put() 拋出 UnsupportedOperationException。
• 三大常用實現：HashMap (無序、高性能)、LinkedHashMap (插入/訪問序)、TreeMap (Key 自然序/定制序)。

HashMap — 基於哈希表的高性能映射

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

• 底層：JDK 7 數組 + 鏈表；JDK 8 數組 + 鏈表/紅黑樹 (鏈表長度 > 8 且數組長度 > 64 樹化)。
• 允許 null Key (僅一個) 和 null Value。
• 非線程安全，高併發下可導致死循環 (JDK 7 擴容) 或數據丟失。
• 參數：初始容量默認 16 (2 的冪)，負載因子默認 0.75f。擴容閾值 = capacity * loadFactor。
• 迭代器：快速失效，併發修改拋 ConcurrentModificationException。
• 適用：單線程、高性能查找/插入/刪除、無序場景。

LinkedHashMap — 可預知迭代順序的 HashMap

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

• 雙向鏈表：維護 head/tail，記錄插入順序 (默認) 或訪問順序 (accessOrder=true)。
• 覆寫方法：newNode()、newTreeNode()、afterNodeAccess()、afterNodeInsertion()、get()、clear()、containsValue()。
• 迭代性能：O(1) 只與 size 相關，HashMap 迭代 O(capacity)。
• LRU 緩存：構造函數 LinkedHashMap(16, 0.75f, true) + 覆寫 removeEldestEntry() 實現。
• 非線程安全，同 HashMap。

TreeMap — 基於紅黑樹的有序映射

• 底層：紅黑樹 (自平衡二叉搜索樹)，Key 按自然順序 (Comparable) 或定制比較器 (Comparator) 排序。
• 不允許 null Key (比較拋 NPE)，允許 null Value。
• 操作複雜度：get/put/remove/containsKey 均為 O(log n)。
• 導航方法：firstKey/lastKey、lowerKey/floorKey/ceilingKey/higherKey、subMap/headMap/tailMap、pollFirstEntry/pollLastEntry。
• 非線程安全。
• 適用：需要有序遍歷、範圍查詢、最近鄰查找場景。

性能與選型對比表

核心源碼關鍵點 (JDK 8 HashMap)

1. putVal()：計算 hash、索引定位、鏈表/樹插入、擴容判斷、樹化/反樹化。
2. resize()：2倍擴容，重新計算索引 (JDK 8 優化：高位不變或遷移)。
3. treeifyBin()：鏈表轉紅黑樹條件 (TREEIFY_THRESHOLD=8 且 MIN_TREEIFY_CAPACITY=64)。
4. getNode()：hash 定位 → 比較 key (== 或 equals) → 鏈表/樹查找。

最佳實踐

1. 預估數據量設置 initialCapacity，避免頻繁擴容：new HashMap<>(expectedSize * 4 / 3)。
2. Key 類正確實現 hashCode() 與 equals() 契約，不可變對象最佳。
3. 多線程環境必須用 ConcurrentHashMap 或 Collections.synchronizedMap (性能差)。
4. 需要有序遍歷用 LinkedHashMap，需要排序/範圍查詢用 TreeMap。
5. 避免在迭代中直接修改 Map，使用 iterator.remove() 或收集後批量處理。