Java 集合深度解析：TreeSet 核心原理與原始碼剖析

TreeSet 核心架構

從原始碼可見，TreeSet 本質上是 TreeMap 的一層薄包裝。它實作了 NavigableSet、Cloneable、Serializable 介面，其中 NavigableSet 繼承自 SortedSet。

public class TreeSet<E> extends AbstractSet<E> 
    implements NavigableSet<E>, Cloneable, java.io.Serializable {

    // 底層使用 NavigableMap 實作，鍵為元素，值為固定物件 PRESENT
    private transient NavigableMap<E, Object> m;
    private static final Object PRESENT = new Object();

    // 內部建構子，直接注入 NavigableMap
    TreeSet(NavigableMap<E, Object> m) {
        this.m = m;
    }

    // 預設建構子，使用自然排序的 TreeMap
    public TreeSet() {
        this(new TreeMap<E, Object>());
    }

    // 客製化比較器建構子
    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }

    // 從 Collection 建構
    public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    // 從 SortedSet 建構
    public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s);
    }
    // ... 後續方法皆委派給內部 TreeMap 實作
}

關鍵設計特點

• 策略模式：透過 Comparator 實現客製化排序，內部邏輯不感知具體比較策略
• 鍵值分離：元素儲存為 TreeMap 的鍵，值統一使用 PRESENT 常數
• 完整委派：所有集合操作（add、remove、contains、迭代器等）皆轉發給內部 TreeMap
• 導航功能：支援 lower、floor、ceiling、higher、pollFirst、pollLast 等進階查詢
• 範圍視圖：subSet、headSet、tailSet 提供高效區間查詢
• 序列化支援：自訂 writeObject/readObject 確保比較器與元素順序正確還原

核心方法委派對照

效能特徵

• 基本操作（add、remove、contains）時間複雜度：O(log n)
• 迭代時間複雜度：O(n)
• 空間複雜度：O(n)
• 非同步安全，多執行緒環境需外部同步或使用 Collections.synchronizedSortedSet
• 迭代器為 fail-fast 機制，結構性修改會拋出 ConcurrentModificationException

詳細原始碼請參考 JDK 官方文件或 java.util.TreeSet 來源。