Java 集合深度解析：TreeMap 紅黑樹實現、有序映射與導航接口全景

前言

HashMap 雖高效但無序，TreeMap 基於紅黑樹實現鍵的自然順序或定制順序，並實現 SortedMap、NavigableMap 接口，提供豐富的區間查詢、鄰近鍵搜索能力。本文從基本用法、高級導航 API、紅黑樹核心源碼、特點對比四個維度深度解析。

一、 基本用法：構造器、比較器與排序策略

1. 兩大核心構造器

// 1. 自然順序：鍵必須實現 Comparable
new TreeMap<>();

// 2. 定制順序：傳入 Comparator，鍵無需實現 Comparable
new TreeMap<>(Comparator comparator);

選型原則：自然順序簡單直接；定制順序靈活解耦，支持多維度排序（如忽略大小寫、逆序、複合鍵）。

2. 常見比較器組合技巧

// 忽略大小寫
new TreeMap<>(String.CASE_INSENSITIVE_ORDER);

// 逆序
new TreeMap<>(Collections.reverseOrder());
// 逆序 + 忽略大小寫
new TreeMap<>(Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER));

// 自定義：字符串日期按時間排序
new TreeMap<>(new Comparator() {
    SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd");
    public int compare(String o1, String o2) {
        try { return sdf.parse(o1).compareTo(sdf.parse(o2)); }
        catch (ParseException e) { return 0; }
    }
});

3. 鍵去重規則：比較結果為 0 視為同鍵

TreeMap map = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
map.put("T", "tree");
map.put("t", "try"); // 比較器認為 "T" == "t"
// 結果：只有 "T=try"，鍵保留首次，值覆蓋為最後一次

二、 高級導航 API：SortedMap 與 NavigableMap

TreeMap 實現鏈：Map → SortedMap → NavigableMap

1. SortedMap 核心方法

2. NavigableMap 增強：精準邊界與鄰近搜索

3. 實戰示例

NavigableMap map = new TreeMap<>();
map.put("a", "abstract"); map.put("f", "final"); map.put("c", "call");

map.firstEntry();      // a=abstract
map.lastEntry();       // f=final
map.floorEntry("d");   // c=call (≤d 最大)
map.ceilingEntry("d"); // f=final (≥d 最小)
map.descendingMap().subMap("d", false, "a", true); // {c=call, a=abstract} 逆序區間

三、 紅黑樹核心源碼解析 (JDK 8)

1. 節點結構 Entry

static final class Entry implements Map.Entry {
    K key; V value;
    Entry left, right, parent;
    boolean color = BLACK; // 紅黑樹顏色
    Entry(K key, V value, Entry parent) { ... }
}

2. put 流程：查找父節點 → 插入 → 修復平衡

public V put(K key, V value) {
    Entry t = root;
    if (t == null) { // 首節點
        compare(key, key); // 類型/空檢查
        root = new Entry<>(key, value, null);
        size = 1; modCount++; return null;
    }
    // 尋找插入位置
    Comparator cpr = comparator;
    Entry parent;
    int cmp;
    if (cpr != null) { // 定制比較器路徑
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0) t = t.left;
            else if (cmp > 0) t = t.right;
            else return t.setValue(value); // 鍵已存在，覆蓋值
        } while (t != null);
    } else { // 自然順序路徑
        if (key == null) throw new NullPointerException();
        Comparable k = (Comparable) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0) t = t.left;
            else if (cmp > 0) t = t.right;
            else return t.setValue(value);
        } while (t != null);
    }
    // 插入新節點
    Entry e = new Entry<>(key, value, parent);
    if (cmp < 0) parent.left = e; else parent.right = e;
    fixAfterInsertion(e); // 關鍵：紅黑樹旋轉+變色，保持平衡
    size++; modCount++;
    return null;
}

3. get 流程：二叉搜索樹標準查找

final Entry getEntry(Object key) {
    if (comparator != null) return getEntryUsingComparator(key);
    if (key == null) throw new NullPointerException();
    Comparable k = (Comparable) key;
    Entry p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0) p = p.left;
        else if (cmp > 0) p = p.right;
        else return p;
    }
    return null;
}

4. 刪除 deleteEntry：三種情況統一轉換

• 雙子節點：找後繼 successor(p)，複製其鍵值到當前節點，轉為刪除後繼節點（後繼最多一子）；
• 單子節點：用子節點替換當前節點，修復父鏈接，若刪除節點為黑則 fixAfterDeletion(replacement)；
• 葉子節點：直接斷開父鏈接，若為黑則 fixAfterDeletion(p)。

successor() 實現：有右子樹 → 右子樹最左節點；無右子樹 → 向上找首個作為左孩子的祖先。

5. 遍歷順序：中序遍歷 (左-根-右)

final Entry getFirstEntry() { // 最左節點
    Entry p = root;
    if (p != null) while (p.left != null) p = p.left;
    return p;
}
static  Entry successor(Entry t) { // 後繼邏輯同上 }

四、 TreeMap vs HashMap：選型決策表

五、 總結與擴展

TreeMap 以紅黑樹為骨架，實現了有序映射與導航查詢的完美平衡。理解其比較器策略、旋轉修復邏輯、子映射視圖機制，是掌握 Java 集合框架進階能力的關鍵一環。

延伸學習：
🔹 TreeSet：基於 TreeMap 實現的有序集合；
🔹 ConcurrentSkipListMap：無鎖併發有序映射，基於跳表；
🔹 B+ 樹在數據庫索引中的應用，對比紅黑樹在內存場景的優勢。