TreeSet 排序機制深度解析：自然排序與定制排序

TreeSet 核心排序原理

TreeSet 基於紅黑樹實現，元素有序且不重複。它提供兩種排序方式：

• 自然排序（預設）：元素需實作 Comparable 介面，依 compareTo() 升序排列。
• 定制排序：建構時傳入 Comparator 實例，由其 compare() 決定順序。

自然排序詳解

Comparable 介面契約

public interface Comparable<T> {
    int compareTo(T o);
}

• 回傳 負數：當前物件 < 參數物件
• 回傳 0：兩物件相等
• 回傳 正數：當前物件 > 參數物件

JDK 內建類別的比較規則

常見陷阱與異常

1. ClassCastException：嘗試將未實作 Comparable 的物件加入 TreeSet，或加入不同型別物件導致比較失敗。
2. equals 與 compareTo 不一致：
   • 若 equals() 回傳 true 但 compareTo() 不為 0，違反 Set 唯一性語義，導致重複元素被保留。
   • 若 compareTo() 回傳 0 但 equals() 為 false，TreeSet 視為同一位置但實際不同，操作極其混亂。
3. 可變物件風險：加入後修改物件狀態導致排序依據改變，TreeSet 不會自動調整結構，造成查詢、刪除失效。

最佳實踐：確保一致性

public class Employee implements Comparable<Employee> {
    private int id;
    private String name;
    
    @Override
    public int compareTo(Employee o) {
        return Integer.compare(this.id, o.id); // 唯一標識比較
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof Employee)) return false;
        Employee other = (Employee) obj;
        return this.id == other.id; // 與 compareTo 一致
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

定制排序：Comparator 策略模式

當無法修改元素類別、或需多種排序邏輯時，使用 Comparator：

// 降序排列
TreeSet<Integer> descSet = new TreeSet<>((a, b) -> b - a);

// 多欄位排序：先按年齡降序，再按姓名升序
Comparator<User> multi = Comparator
    .comparing(User::getAge).reversed()
    .thenComparing(User::getName);

TreeSet<User> customSet = new TreeSet<>(multi);

匿名內部類寫法（舊版相容）

TreeSet<Student> ts = new TreeSet<>(new Comparator<Student>() {
    @Override
    public int compare(Student s1, Student s2) {
        return s2.getScore() - s1.getScore(); // 分數降序
    }
});

核心原理總結

• TreeSet 透過 compareTo() 或 compare() 判斷元素大小，決定紅黑樹中的插入位置。
• 判斷「相等」標準：compareTo() == 0，而非 equals()。
• 強烈建議：只存放不可變物件，並確保 equals()、hashCode()、compareTo() 三者語義一致。
• 定制排序時，元素類別無需實作 Comparable，排序邏輯完全由外部 Comparator 控制。

深入理解這些機制，能避免生產環境中詭異的資料不一致與效能問題，是 Java 集合框架進階必修課。