Java Map 詳解：HashMap vs TreeMap 實戰與原理解析

Map 介面與常用實作

java.util.Map 是鍵值對集合，不允許重複鍵。常用實作：

• HashMap：雜湊表，O(1) 存取，無序，允許 null key/value
• LinkedHashMap：維護插入順序或存取順序
• TreeMap：紅黑樹，鍵自然排序 或依 Comparator，O(log n) 存取
• Hashtable：舊版線程安全，已被 ConcurrentHashMap 取代

實戰範例：員工資料存儲與排序

實體類

public class Emp {
    private String eId;
    private String eName;
    public Emp(String eId, String eName) { this.eId = eId; this.eName = eName; }
    // Getter/Setter 省略
    @Override public String toString() { return eId + "=" + eName; }
}

HashMap (無序) vs TreeMap (有序)

public class MapDemo {
    public static void main(String[] args) {
        Map<String, String> hashMap = new HashMap<>();
        hashMap.put("001", "張三");
        hashMap.put("002", "李四");
        hashMap.put("005", "王五");
        hashMap.put("006", "馬六");

        System.out.println("=== HashMap (無序) ===");
        hashMap.forEach((k, v) -> System.out.println(k + " -> " + v));

        // TreeMap 自動按鍵自然順序 (字串字典序) 排序
        Map<String, String> treeMap = new TreeMap<>(hashMap);
        System.out.println("\n=== TreeMap (有序) ===");
        treeMap.forEach((k, v) -> System.out.println(k + " -> " + v));

        // 刪除操作
        hashMap.remove("005");
        treeMap.remove("005");
        System.out.println("\n刪除 005 後 HashMap: " + hashMap);
        System.out.println("刪除 005 後 TreeMap: " + treeMap);
    }
}

執行結果

=== HashMap (無序) ===
001 -> 張三
002 -> 李四
005 -> 王五
006 -> 馬六

=== TreeMap (有序) ===
001 -> 張三
002 -> 李四
005 -> 王五
006 -> 馬六

刪除 005 後 HashMap: {001=張三, 002=李四, 006=馬六}
刪除 005 後 TreeMap: {001=張三, 002=李四, 006=馬六}

核心原理解析

HashMap (JDK 8+)

• 陣列 + 鏈表 + 紅黑樹 (鏈表長度 > 8 且陣列長度 > 64 時樹化)
• 擴容機制：負載因子 0.75，容量翻倍 (2 的冪次)
• 雜湊計算：hash(key) ^ (hash(key) >>> 16) 減少碰撞

TreeMap

• 紅黑樹 (自平衡二元搜尋樹)
• 鍵必須實作 Comparable 或提供 Comparator
• 支援 firstKey(), lastKey(), subMap(), headMap(), tailMap() 等範圍操作

選型指南

常見坑點

1. 可變鍵：放入 Map 的鍵物件若修改了影響 equals/hashCode 的欄位，會導致找不到原值。
2. 初始容量：預估資料量大時指定 new HashMap<>(1024) 避免頻繁擴容。
3. 序列化：TreeMap 需鍵實作 Serializable 才能序列化。