您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

Java Map 實作深度比較：HashMap vs TreeMap vs Hashtable vs LinkedHashMap

編輯：Java 綜合教學

四大 Map 實作一覽表

實作類別	底層資料結構	順序特性	執行緒安全	允許 Null Key/Value	主要適用場景
HashMap	雜湊表 (陣列+鏈表/紅黑樹)	無序	否	Key:1個, Value:多個	通用鍵值存取、高效能查找
LinkedHashMap	雜湊表 + 雙向鏈表	插入順序 / 存取順序	否	Key:1個, Value:多個	需保持插入順序、LRU 快取
TreeMap	紅黑樹	Key 自然序或自訂 Comparator 排序	否	Key:不允許, Value:多個	需排序、範圍查詢
Hashtable	雜湊表	無序	是 (synchronized)	Key/Value 皆不允許	舊版代碼相容、已被 ConcurrentHashMap 取代

HashMap：核心實作與 Key 設計陷阱

基本用法

Map<Dog, Integer> map = new HashMap<>();
map.put(new Dog("red"), 10);
map.put(new Dog("black"), 15);

關鍵陷阱：自訂 Key 必須重寫 equals() 與 hashCode()

預設 Object.equals() 比較記憶體位址，hashCode() 回傳物件位址衍生值。若不重寫，邏輯上相等的物件會被視為不同 Key：

// ❌ 錯誤示範：未重寫 equals/hashCode
class Dog { String color; Dog(String c){ color=c; } }
map.put(new Dog("white"), 5);
map.put(new Dog("white"), 20); // 視為不同 Key，size=2

// ✅ 正確實作
class Dog {
    String color;
    Dog(String c) { color = c; }
    
    @Override public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Dog)) return false;
        return color.equals(((Dog)o).color);
    }
    
    @Override public int hashCode() {
        return color.hashCode(); // 或 Objects.hash(color)
    }
}
// 現在 put 兩個 "white" 會覆蓋，size=1

TreeMap：排序與 Comparable 契約

TreeMap 要求 Key 實作 Comparable 或提供 Comparator：

class Dog implements Comparable<Dog> {
    String color; int size;
    Dog(String c, int s) { color=c; size=s; }
    
    @Override public int compareTo(Dog o) {
        return Integer.compare(this.size, o.size); // 按 size 升序
    }
}

TreeMap<Dog, Integer> treeMap = new TreeMap<>();
treeMap.put(new Dog("red", 30), 10);
treeMap.put(new Dog("black", 20), 15);
treeMap.put(new Dog("white", 10), 5);
// 遍歷順序：white(10) → black(20) → red(30)

比較器靈活運用

// 使用 Lambda 定義比較邏輯 (Java 8+)
TreeMap<Dog, Integer> map = new TreeMap<>((d1, d2) -> d2.size - d1.size); // 降序
// 或
TreeMap<Dog, Integer> map = new TreeMap<>(Comparator.comparingInt(d -> d.size));

LinkedHashMap：順序保持與 LRU 快取

繼承 HashMap，額外維護雙向鏈表記錄插入順序（或存取順序）：

Map<Dog, Integer> linked = new LinkedHashMap<>();
linked.put(new Dog("red"), 10);
linked.put(new Dog("black"), 15);
linked.put(new Dog("white"), 5);
// 遍歷順序固定為：red → black → white (插入順序)

// LRU 快取範例：存取順序模式 + 移除最舊
Map<Integer, String> lruCache = new LinkedHashMap<Integer, String>(16, 0.75f, true) {
    @Override protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
        return size() > 100; // 超過 100 筆移除最久未存取
    }
};