Java 集合框架深度解析：TreeSet 有序去重原理與自定義對象排序實戰

前言

TreeSet 是 Java 集合框架中唯一同時具備「有序」與「去重」特性的 Set 實現，底層基於紅黑樹（自平衡二叉搜索樹），查詢/插入/刪除均為 O(log n)。本文深度解析其核心原理、自然排序與定製排序兩種模式、自定義對象存儲實戰及常見坑點。

一、核心特性對比

二、排序機制詳解

1. 自然排序

元素類實現 Comparable<E> 接口，重寫 compareTo(E o)：

• 返回 < 0：當前元素 < 指定元素
• 返回 = 0：當前元素 = 指定元素（視為重複，不添加）
• 返回 > 0：當前元素 > 指定元素

JDK 內置類已實現：String、Integer、Double、Date 等均按自然語義排序（字母序、數值序、時間序）。

2. 定製排序

構造 TreeSet 時傳入 Comparator<E>，適用於：

• 元素類無法修改（第三方庫、最終類）
• 需要多種排序規則（按姓名/年齡/薪資不同維度排序）
• 需要降序或複雜多鍵排序

三、自定義對象存儲實戰

場景：學生對象按年齡升序，年齡相同按姓名字母序

import java.util.TreeSet;

public class TreeSetDemo {
    public static void main(String[] args) {
        // 方式一：自然排序（Student 實現 Comparable）
        TreeSet set1 = new TreeSet<>();
        set1.add(new Student("taoshihan1", 30));
        set1.add(new Student("taoshihan2", 20));
        set1.add(new Student("taoshihan3", 40));
        set1.add(new Student("taoshihan4", 30));  // 年齡相同，按姓名排序
        
        System.out.println("=== 自然排序（年齡升序，同齡姓名序）===");
        for (Student s : set1) {
            System.out.println(s.getName() + " ===" + s.getAge());
        }
        
        // 方式二：定製排序（降序，無需修改 Student 類）
        TreeSet set2 = new TreeSet<>((s1, s2) -> {
            // 年齡降序
            int ageDiff = s2.getAge() - s1.getAge();
            if (ageDiff != 0) return ageDiff;
            // 年齡相同，姓名升序
            return s1.getName().compareTo(s2.getName());
        });
        set2.addAll(set1);
        
        System.out.println("\n=== 定製排序（年齡降序，同齡姓名序）===");
        for (Student s : set2) {
            System.out.println(s.getName() + " ===" + s.getAge());
        }
    }
}

// 學生類實現 Comparable 自然排序
class Student implements Comparable {
    private String name;
    private int age;
    
    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    public String getName() { return name; }
    public int getAge() { return age; }
    
    @Override
    public int compareTo(Student other) {
        // 主鍵：年齡升序
        int ageDiff = this.age - other.age;
        if (ageDiff != 0) return ageDiff;
        // 次鍵：姓名字母序
        return this.name.compareTo(other.name);
    }
    
    @Override
    public String toString() {
        return "Student{name='" + name + "', age=" + age + "}";
    }
}

輸出結果

=== 自然排序（年齡升序，同齡姓名序）===
taoshihan2 ===20
taoshihan1 ===30
taoshihan4 ===30
taoshihan3 ===40

=== 定製排序（年齡降序，同齡姓名序）===
taoshihan3 ===40
taoshihan1 ===30
taoshihan4 ===30
taoshihan2 ===20

四、核心原理：紅黑樹與去重判斷

1. 紅黑樹特性

• 每個節點非紅即黑
• 根節點黑、葉子節點（NIL）黑
• 紅節點的子節點必為黑（無連續紅）
• 任一節點到葉子的所有路徑黑節點數相同
• 最長路徑不超過最短路徑 2 倍 → 近似平衡 → O(log n) 保證

2. TreeSet 去重邏輯

// TreeMap.put() 核心邏輯（TreeSet 內部調用）
public V put(K key, V value) {
    // ... 紅黑樹插入邏輯 ...
    int cmp = compare(key, existingKey);  // 使用 compareTo 或 compare
    if (cmp == 0) {
        return existingValue;  // 視為重複，不插入，返回舊值
    }
    // ... 插入新節點 ...
}

關鍵結論：TreeSet 判斷重複完全依賴比較器返回 0，不調用 equals()。這意味著：

• 若 compareTo 返回 0 但 equals 返回 false → 視為重複，不存入（違反 Set 語義）
• 必須保證：(a.compareTo(b) == 0) == a.equals(b)（強一致性）

五、常見坑點與最佳實踐

六、進階：ConcurrentSkipListSet（併發有序去重）

// 線程安全的有序 Set，基於跳表實現，性能優於同步 TreeSet
Set concurrentSet = new ConcurrentSkipListSet<>();
// 支持更高併發吞吐，API 與 TreeSet 基本一致

七、總結

1. TreeSet = 去重 + 有序，底層紅黑樹，O(log n) 操作複雜度
2. 兩種排序：自然排序（實現 Comparable）+ 定製排序（構造傳 Comparator）
3. 去重判斷僅依賴比較器返回 0，必須保證與 equals 一致
4. 不允許 null，非線程安全，大量數據建議 HashSet 去重後轉 TreeSet
5. 併發場景首選 ConcurrentSkipListSet