TreeSet 完全指南：自然排序、定製比較器與底層 TreeMap 原理

一、TreeSet 核心特性

• 有序、不重複：元素按升序排列（默認自然序）。
• 底層實現：基於 TreeMap（紅黑樹），操作複雜度 O(log n)。
• 排序方式：
  1. 自然排序：元素實現 Comparable 接口。
  2. 定製排序：構造時傳入 Comparator。

二、自然排序實戰

String、Integer 等內置類型已實現 Comparable，可直接排序。

Set<String> ts = new TreeSet<>();
ts.add("xyz");
ts.add("abc");
ts.add("rst");
// 輸出: abc, rst, xyz（字典序）

自定義類實現 Comparable

class Teacher implements Comparable<Teacher> {
    int num;
    String name;

    Teacher(String name, int num) { this.name = name; this.num = num; }

    @Override
    public int compareTo(Teacher o) {
        // 先按 num 降序
        int result = Integer.compare(o.num, this.num);
        // num 相同按 name 升序
        if (result == 0) result = this.name.compareTo(o.name);
        return result;
    }

    @Override public String toString() { return "學號：" + num + "\t姓名：" + name; }
}

// 測試
Set<Teacher> set = new TreeSet<>();
set.add(new Teacher("zhangsan", 1));
set.add(new Teacher("lisi", 2));
set.add(new Teacher("wangmazi", 3));
set.add(new Teacher("mazi", 3));
// 輸出: 學號：3 姓名：mazi / 學號：3 姓名：wangmazi / 學號：2 姓名：lisi / 學號：1 姓名：zhangsan

關鍵點：compareTo 返回正/負/零分別代表 大於/小於/等於。TreeSet 通過它決定插入位置，返回 0 視為重複元素不插入，故需結合次要字段區分。

三、定製比較器

不修改實體類，或需多種排序規則時使用。

class Teacher2 {
    int num; String name;
    Teacher2(String name, int num) { this.name = name; this.num = num; }
    @Override public String toString() { return "學號：" + num + " 姓名：" + name; }

    static class TeacherCompare implements Comparator<Teacher2> {
        @Override
        public int compare(Teacher2 o1, Teacher2 o2) {
            int result = Integer.compare(o1.num, o2.num); // 升序
            if (result == 0) result = o1.name.compareTo(o2.name);
            return result;
        }
    }
}

// 使用
TreeSet<Teacher2> ts = new TreeSet<>(new Teacher2.TeacherCompare());
ts.add(new Teacher2("zhangsan", 2));
ts.add(new Teacher2("lisi", 1));
ts.add(new Teacher2("wangmazi", 3));
ts.add(new Teacher2("mazi", 3));
// 輸出: 學號：1 姓名：lisi / 學號：2 姓名：zhangsan / 學號：3 姓名：mazi / 學號：3 姓名：wangmazi

四、構造方法源碼解析

public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<E, Object>(comparator));
}

證明 TreeSet 內部持有 TreeMap 實例，Key 為元素，Value 為固定常量 PRESENT。

五、TreeSet vs HashSet vs LinkedHashSet

六、常見坑點

1. compareTo 不一致導致數據丟失：若 compareTo 認為兩對象相等，add 會失敗。
2. 可變對象作元素：插入後修改排序字段，導致樹結構破壞，查詢異常。
3. null 元素：自然排序不允許 null（拋 NPE），定製比較器可自行處理。

總結

TreeSet 以紅黑樹實現有序去重，適合「需要排序 + 去重 + 頻繁範圍查詢」場景。自然排序靠 Comparable，定製排序靠 Comparator，二者不可混用。牢記 compareTo 返回 0 == 去重 原則，避免業務數據意外丟失。