您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java TreeSet 排序機制完整解析：自然排序與定制排序

編輯：Java 相關知識

TreeSet 排序核心機制深度解析

TreeSet 基於紅黑樹實作，元素有序且不重複。支援兩種排序模式：自然排序 (實作 Comparable) 與 定制排序 (提供 Comparator)。本文完整解析兩者機制、陷阱與最佳實踐。

一、自然排序

核心介面：Comparable<T>

public interface Comparable {
    int compareTo(T o);  // 回傳：負數(小於)、0(相等)、正數(大於)
}

JDK 內建支援自然排序的類別

自訂類別實作 Comparable

public class Student implements Comparable {
    private String name;
    private int score;
    
    // 建構子、getter 略
    
    @Override
    public int compareTo(Student other) {
        // 主鍵：分數遞減 (高分在前)
        int scoreDiff = Integer.compare(other.score, this.score);
        if (scoreDiff != 0) return scoreDiff;
        
        // 次鍵：姓名字典序
        return this.name.compareTo(other.name);
    }
    
    // 關鍵：equals 與 compareTo 一致性
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Student)) return false;
        Student s = (Student) o;
        return score == s.score && Objects.equals(name, s.name);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(name, score);
    }
}

自然排序陷阱：equals 與 compareTo 不一致

// ❌ 危險：equals 為 true 但 compareTo != 0
public class Broken implements Comparable {
    @Override public boolean equals(Object o) { return true; }  // 永遠相等
    @Override public int compareTo(Broken o) { return 1; }       // 永遠大於
}

TreeSet set = new TreeSet<>();
set.add(new Broken());
set.add(new Broken());  // 會加入兩個元素！違反 Set 語意
System.out.println(set.size()); // 輸出 2

規範要求：(x.compareTo(y) == 0) == (x.equals(y)) 應為 true。違反此規範會導致 Set/Map 行為異常。

可變物件風險

TreeSet set = new TreeSet<>();
Student s = new Student("Alice", 90);
set.add(s);
// 修改已加入元素的排序關鍵欄位
s.setScore(60);  // ⚠️ 破壞樹結構！
// 後續操作會出現：找不到元素、重複元素、遍歷順序錯誤

⚠️ 鐵律：TreeSet/TreeMap 僅存放不可變物件

若必須存放可變物件，修改欄位前必須先移除，修改後重新加入。

二、定制排序

核心介面：Comparator<T>

@FunctionalInterface
public interface Comparator {
    int compare(T o1, T o2);
    
    // Java 8+ 靜態工廠方法
    static > Comparator comparing(
        Function keyExtractor) { ... }
    
    static  Comparator comparing(
        Function keyExtractor,
        Comparator keyComparator) { ... }
}

建立 TreeSet 時指定 Comparator

// 1. 匿名內部類 (Java 7 風格)
TreeSet set1 = new TreeSet<>(new Comparator() {
    @Override
    public int compare(Student s1, Student s2) {
        return Integer.compare(s2.getScore(), s1.getScore()); // 分數遞減
    }
});

// 2. Lambda 表達式 (Java 8+)
TreeSet set2 = new TreeSet<>((s1, s2) -> 
    Integer.compare(s2.getScore(), s1.getScore()));

// 3. 方法參考 + comparing (推薦，可讀性最佳)
TreeSet set3 = new TreeSet<>(Comparator
    .comparing(Student::getScore).reversed()  // 分數遞減
    .thenComparing(Student::getName));        // 次鍵：姓名升序

// 4. 多欄位複合排序
TreeSet empSet = new TreeSet<>(Comparator
    .comparing(Employee::getDept)             // 部門升序
    .thenComparing(Employee::getHireDate)     // 入職日期升序
    .thenComparing(Employee::getSalary).reversed()); // 薪資降序

Comparator 進階技巧

// 空值處理：nullsFirst / nullsLast
Comparator nullSafe = Comparator
    .nullsLast(Comparator.comparing(Student::getName));

// 反轉現有比較器
Comparator reversed = Comparator.comparing(Student::getScore).reversed();

// 條件式比較：先比部門，部門相同再比薪資
Comparator complex = (e1, e2) -> {
    int deptCmp = e1.getDept().compareTo(e2.getDept());
    if (deptCmp != 0) return deptCmp;
    return Double.compare(e2.getSalary(), e1.getSalary()); // 薪資降序
};

三、TreeSet 核心原理與效能

紅黑樹特性

自平衡二元搜尋樹
查詢、插入、刪除：O(log n)
中序遍歷即為排序結果
根節點為中位數區域

去重判斷邏輯

// TreeSet 判斷「相等」的邏輯：
// 1. compareTo(o1, o2) == 0  → 視為相同，不加入
// 2. 不呼叫 equals() 進行去重！

// 這意味著：
TreeSet set = new TreeSet<>(Comparator.comparing(Student::getScore));
set.add(new Student("A", 90));
set.add(new Student("B", 90)); // ❌ 不會加入！compareTo 回傳 0
System.out.println(set.size()); // 輸出 1

效能比較

類別	比較規則
String	Unicode 字元碼序 (字典序)
Integer, Long, Double 等包裝類	數值大小
BigInteger, BigDecimal	數值大小
Character	Unicode 字元碼序
Boolean	true > false
Date, LocalDate, Instant	時間先後 (較晚者較大)
Enum	宣告順序 (ordinal)

操作	HashSet	TreeSet	LinkedHashSet
add/contains/remove	O(1) 平均	O(log n)	O(1) 平均
遍歷順序	無序	排序序	插入序
記憶體	較低	較高 (樹節點)	中等
適用場景	高頻查重、不需排序	需有序、範圍查詢	需保持插入順序

四、實戰範例：範圍查詢與導航

TreeSet scores = new TreeSet<>(Arrays.asList(55, 67, 89, 90, 90, 76, 88, 92, 100));

// 範圍查詢 (包含頭、不含尾)
NavigableSet range = scores.subSet(80, true, 95, false); // [80, 95)
System.out.println(range); // [80, 88, 89, 90, 92]

// 首/尾元素
System.out.println("最低分: " + scores.first());   // 55
System.out.println("最高分: " + scores.last());    // 100

// 小於/大於指定值
System.out.println("小於 60: " + scores.headSet(60, false));  // [55]
System.out.println("大於 90: " + scores.tailSet(90, true));   // [90, 92, 100]

// 導航操作
System.out.println("≥85 的最小值: " + scores.ceiling(85));   // 88
System.out.println("≤85 的最大值: " + scores.floor(85));     // 76
System.out.println(">85 的最小值: " + scores.higher(85));    // 88
System.out.println("<85 的最大值: " + scores.lower(85));     // 76

// 彈出首/尾
Integer highest = scores.pollLast();  // 移除並回傳最高分 100
Integer lowest = scores.pollFirst();  // 移除並回傳最低分 55

TreeSet 以紅黑樹提供高效有序集合操作。掌握 Comparable (自然排序) 與 Comparator (定制排序) 兩大機制、理解 equals/compareTo 一致性規範、避免可變物件陷阱，並善用 NavigableSet 導航 API，能讓你在排序、去重、範圍查詢場景中遊刃有餘。