TreeSet 入門詳解：從繼承體系到比較器實戰

一、類結構與接口體系

• 繼承：AbstractSet → AbstractCollection → Object
• 實現：NavigableSet、Cloneable、Serializable
• 底層：NavigableMap 接口，實際由 TreeMap 實現

二、基本用法：自然排序

Set<String> ts = new TreeSet<>();
ts.add("xyz");
ts.add("abc");
ts.add("rst");

for (String s : ts) System.out.println(s);
// 輸出: abc, rst, xyz

三、自定義對象存入：必須實現 Comparable

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

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

// 測試
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));
// 輸出按學號升序，同學號按姓名升序

注意：若寫成 Integer.compare(o.num, this.num) 則為降序。compareTo 邏輯直接決定樹中節點左右分佈。

四、使用 Comparator 定製排序

構造方法：public TreeSet(Comparator<? super E> comparator)

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

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

// 使用
TreeSet<Teacher> ts = new TreeSet<>(new Teacher.TeacherCompare());
ts.add(new Teacher("zhangsan", 2));
ts.add(new Teacher("lisi", 1));
ts.add(new Teacher("wangmazi", 3));
ts.add(new Teacher("mazi", 3));
// 輸出: 1-lisi, 2-zhangsan, 3-mazi, 3-wangmazi

五、底層實現原理

• TreeSet 內部持有 NavigableMap<E, Object> m，實際為 TreeMap。
• 所有元素作為 Key 存入 Map，Value 統一為 PRESENT = new Object()。
• 利用 TreeMap 的紅黑樹特性實現有序、去重、範圍查詢（subSet、headSet、tailSet）。

深度探究可參考：TreeMap/TreeSet 源碼深度解析

六、常見問題彙總

1. 拋 ClassCastException：元素未實現 Comparable 且構造未傳 Comparator。
2. 添加失敗不報錯：compareTo 返回 0 視為重複，靜默忽略。
3. 併發不安全：多線程環境用 Collections.synchronizedSortedSet 或並發包替代品。