TreeSet 深度解析：有序集合的底層原理與兩種排序機制

TreeSet 深度解析：有序集合的底層原理與兩種排序機制

在 Java 集合框架中，TreeSet 是唯一實現 SortedSet 介面的類別，它能確保元素始終處於排序狀態。本文將從 Set 介面特性切入，對比 HashSet，深入剖析 TreeSet 的自然排序與定制排序、底層紅黑樹結構、唯一性判斷邏輯，以及原始碼層面的關鍵方法。

一、Set 介面核心契約

• 不允許重複元素：add() 若元素已存在回傳 false。
• 無序性：HashSet 無序；TreeSet 有序。
• 相等判斷：依賴 equals() 而非 ==。兩物件 equals() 回傳 true，Set 視為相同。

二、HashSet 回顧：哈希表實現

• 底層：HashMap（陣列+鏈表/紅黑樹）。
• 特點：非同步、允許一個 null、順序不保證。
• 唯一性判斷：hashCode() 相同 且 equals() 相同。
• 最佳實踐：覆寫 equals() 必須覆寫 hashCode()，且用於 equals 比較的欄位必須參與 hashCode 計算。

三、TreeSet 核心機制

1. 兩種排序方式

2. 自然排序細節

• compareTo 回傳 負數：this < o；0：相等；正數：this > o。
• 若 equals() 恆回傳 true，則 compareTo() 應回傳 0（強一致性建議，非強制）。
• 預設升序；若需降序，可在 compareTo 內反轉邏輯或用 Comparator.reverseOrder()。

3. 定制排序細節

// 匿名內部類寫法
TreeSet<Student> ts = new TreeSet<>(new Comparator<Student>() {
    @Override
    public int compare(Student s1, Student s2) {
        return s1.getAge() - s2.getAge(); // 按年齡升序
    }
});

// Java 8+ Lambda 簡寫
TreeSet<Student> ts2 = new TreeSet<>(Comparator.comparingInt(Student::getAge));

4. 唯一性判斷：compareTo/compare 回傳 0 即視為重複

這與 HashSet 的 equals() 判斷不同。注意：若排序規則導致不同業務物件比較結果為 0，TreeSet 會拒絕後加入的物件，造成資料遺失！務必確保比較器能區分不同業務實體（如加上 ID 做次級排序）。

四、底層原理：TreeMap 紅黑樹

TreeSet 內部持有一個 NavigableMap<E, Object> 實例變數，實際類別為 TreeMap。所有操作委派給該 Map：

• add(e) → map.put(e, PRESENT)
• contains(e) → map.containsKey(e)
• 迭代器 → map.navigableKeySet().iterator()

TreeMap 採用紅黑樹（自平衡二元搜尋樹），保證增刪查 O(log n)。原始碼關鍵點：

• put()：從根節點開始比較，決定往左/右子樹，找到插入點建立 Entry 節點，最後 fixAfterInsertion() 旋轉著色維持紅黑樹性質。
• getEntry()：自然排序用 Comparable，定制排序用 Comparator，同樣從根節點二分查找。

中序遍歷（左-根-右）即可得到升序序列。

五、常見坑與最佳實踐

1. 可變物件加入後修改排序欄位：導致樹結構破壞，查詢失效。解決：排序欄位用 final 或不可變物件。
2. compareTo 與 equals 不一致：TreeSet 視為不同元素，但 HashSet 視為相同。解決：保持強一致性。
3. 大量資料插入效能：TreeSet O(log n) 慢於 HashSet O(1)。選型建議：不需排序用 HashSet/LinkedHashSet。
4. 併發環境：TreeSet 非執行緒安全。用 Collections.synchronizedSortedSet 或並發包 ConcurrentSkipListSet。

TreeSet 以紅黑樹賦予有序性，適合「需要排序、範圍查詢（subSet/headSet/tailSet）、且資料量中等」的場景。掌握其兩種排序機制與唯一性判斷邏輯，能避開大多數生產環境 Bug。