TreeMap 深度解析：紅黑樹實現、Comparator/Comparable 雙軌排序與常用 API 實戰

前言：為何選 TreeMap？

TreeMap 基於紅黑樹 (Red-Black Tree) 實現 NavigableMap 接口，鍵天然有序 (默認自然順序升序)，支持範圍查詢、最近鍵定位等 HashMap 不具備的能力。本文剖析核心原理、四種構造器、排序機制雙軌制、常用 API 及實戰代碼。

一、核心特性速覽

二、四種構造器：決定排序策略的關鍵

// 1. 默認自然順序 (鍵需實現 Comparable)
TreeMap map1 = new TreeMap<>();

// 2. 自定義比較器 (鍵無需實現 Comparable)
TreeMap map2 = new TreeMap<>(Comparator comparator);

// 3. 複製現有 Map (按自然順序排序)
TreeMap map3 = new TreeMap<>(Map m);

// 4. 複製 SortedMap (保持原排序器)
TreeMap map4 = new TreeMap<>(SortedMap m);

三、排序雙軌制：Comparable vs Comparator

1. Comparable (內部比較器) — 「我自己知道怎麼比」

• 鍵類實現 Comparable<T>，重寫 compareTo(T o)。
• 定義自然順序 (如 String 字典序、Integer 數值序)。
• 優點：類自帶排序邏輯，通用性強；缺點：修改排序需改類源碼。

class Student implements Comparable {
    String name; int score;
    @Override public int compareTo(Student o) {
        return Integer.compare(this.score, o.score); // 按分數升序
    }
}

2. Comparator (外部比較器) — 「我幫你定規則」

• 獨立類實現 Comparator<T>，重寫 compare(T o1, T o2)。
• 構造 TreeMap 時傳入：new TreeMap<>(new ScoreDescComparator())。
• 優點：不侵入原類、多種排序共存、支持 Lambda 簡寫；缺點：類爆炸 (Java 8 前)。

// Java 8+ Lambda 寫法：按分數降序，分數相同按姓名升序
TreeMap map = new TreeMap<>((s1, s2) -> {
    int cmp = Integer.compare(s2.score, s1.score); // 降序
    return cmp != 0 ? cmp : s1.name.compareTo(s2.name);
});

3. 選擇原則

四、常用 API 實戰速查

TreeMap tm = new TreeMap<>();
tm.put("zhang", "張三");
tm.put("jack", "小明");
tm.put("mary", "小紅");
tm.put("free", "小葉");
tm.put("mary", "小草"); // 覆蓋

// 輸出: {free=小葉, jack=小明, mary=小草, zhang=張三} (按鍵字典序)
System.out.println(tm);

// 遍歷鍵值對
for (Map.Entry entry : tm.entrySet()) {
    System.out.println(entry.getKey() + " -> " + entry.getValue());
}

// NavigableMap 獨有高級查詢
System.out.println("首項: " + tm.firstEntry());      // free=小葉
System.out.println("末項: " + tm.lastEntry());       // zhang=張三
System.out.println("≥jack: " + tm.ceilingEntry("jack")); // jack=小明
System.out.println("≤mary: " + tm.floorEntry("mary"));   // mary=小草
System.out.println(">jack: " + tm.higherEntry("jack"));  // mary=小草
System.out.println(" sub = tm.subMap("jack", true, "mary", false);
System.out.println("jack~mary: " + sub); // {jack=小明}

// 反序視圖
NavigableMap desc = tm.descendingMap();
System.out.println("反序: " + desc); // {zhang=張三, mary=小草, jack=小明, free=小葉}

五、紅黑樹性能保證

• 樹高 ≤ 2·log₂(n+1)，最壞情況增刷查 O(log n)。
• 旋轉 + 重着色 維持五大性質：根黑、葉黑、紅節點子必黑、路徑黑高一致。
• JDK 實現為非递归迭代，避免棧溢出。

六、避坑指南

1. 自然順序下鍵不可為 null：tm.put(null, "v") → NPE。若需存 null 鍵，必須提供允許 null 的 Comparator。
2. compareTo / compare 與 equals 必須一致：比較器返回 0 的兩個鍵，equals 必須為 true，否則違反 Map 契約 (如鍵重複判定失效)。
3. 非線程安全：多線程寫入請用 Collections.synchronizedSortedMap 或 ConcurrentSkipListMap (跳表實現，並發性能更好)。
4. 大量範圍查詢優先選 TreeMap；純點查詢 HashMap 更快 (O(1))。

七、總結

TreeMap = 紅黑樹 + 雙軌排序 + NavigableMap 豐富查詢 API。掌握 Comparable 定自然序、Comparator 定定制序，善用 subMap/headMap/tailMap 範圍視圖、descendingMap 反序遍歷，即可優雅解決「有序鍵值存儲+範圍查詢」類問題。記住：順序有代價 (log n)，按需選擇。