TreeSet 详解

本章定位：集合框架中专门提供"有序且不重复"元素的 Set 实现。TreeSet 底层基于 TreeMap（红黑树），所有元素按照自然顺序或自定义 Comparator 排序。虽然 add/remove/contains 的时间复杂度 O(log n) 不如 HashSet 的 O(1)，但 TreeSet 保证了元素的排序和丰富的导航查询能力。飞翔科技的员工 ID 去重排序、考试成绩排名、部门编号管理都依赖 TreeSet。本章由白歌讲解红黑树底层，小崔用实际代码验证排序规则，孔蓝发现并修复了 compareTo 不一致的 bug。

定义速览表

属性说明
底层实现TreeMap<E, Object> —— 元素作为 TreeMap 的 key 存储，value 为共享的 PRESENT 常量
元素顺序自然顺序（元素实现 Comparable）或定制顺序（构造时传入 Comparator）
是否允许 null不允许（插入时需调用 compareTo/compare，会 NPE）
线程安全否
时间复杂度add/remove/contains 均为 O(log n)
元素唯一性判断compareTo 或 compare 返回 0（不是 equals！）
实现接口NavigableSet<E> → SortedSet<E> → Set<E> → Collection<E> → Iterable<E>
fail-fast是（迭代器在结构性修改时抛 ConcurrentModificationException）
内存占用每个元素作为 TreeMap 的 Entry 存储，有 parent/left/right/color 四个引用

完整接口继承图

方法速查表

基础 Set 操作

方法描述时间复杂度
add(E e)添加元素，按排序规则插入红黑树O(log n)
remove(Object o)删除元素，之后重新平衡红黑树O(log n)
contains(Object o)判断是否包含元素（沿树查找）O(log n)
size()返回元素数量O(1)
isEmpty()判断集合是否为空O(1)
clear()清空所有元素O(1)（释放 root 引用）

导航方法（NavigableSet 接口）

方法描述时间复杂度
first()返回最小元素O(log n)
last()返回最大元素O(log n)
lower(E e)返回严格小于 e 的最大元素O(log n)
floor(E e)返回小于等于 e 的最大元素O(log n)
ceiling(E e)返回大于等于 e 的最小元素O(log n)
higher(E e)返回严格大于 e 的最小元素O(log n)
pollFirst()移除并返回最小元素O(log n)
pollLast()移除并返回最大元素O(log n)

范围视图方法

方法描述
subSet(E from, E to)返回 [from, to) 子集（左闭右开）
subSet(E from, boolean fromInclusive, E to, boolean toInclusive)可指定两边界是否包含
headSet(E to)返回 < to 的元素视图
headSet(E to, boolean inclusive)可指定是否包含 to
tailSet(E from)返回 >= from 的元素视图
tailSet(E from, boolean inclusive)可指定是否包含 from
descendingSet()返回逆序视图的 NavigableSet
descendingIterator()返回逆序迭代器

核心原理

TreeSet 底层委托给 TreeMap

TreeSet 的源码极其简短，本质上是对 TreeMap 的装饰：

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable {

    // 底层存储：TreeMap，元素作为 key，所有 key 共享同一个 value
    private transient NavigableMap<E, Object> m;
    private static final Object PRESENT = new Object();

    // 默认构造器：创建自然排序的 TreeMap
    public TreeSet() {
        this(new TreeMap<>());
    }

    // 自定义 Comparator 构造器
    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }

    // add 操作 —— 核心：元素作为 key 存入 TreeMap
    public boolean add(E e) {
        return m.put(e, PRESENT) == null;
        // TreeMap.put 返回 null 表示新键 → 插入成功返回 true
        // TreeMap.put 返回旧值（PRESENT）表示已存在 → 插入失败返回 false
    }

    public boolean remove(Object o) {
        return m.remove(o) == PRESENT;
    }

    public boolean contains(Object o) {
        return m.containsKey(o);
    }

    public E first() { return m.firstKey(); }
    public E last()  { return m.lastKey(); }
}

关键结论：TreeSet 的所有特性（排序、唯一性、复杂度）完全由 TreeMap 决定。理解 TreeSet 的前提是理解 TreeMap。

红黑树与 TreeSet 关系图

两种排序方式速查

方式代码TreeSet 构造
自然排序元素类实现 Comparable<E>，重写 compareTonew TreeSet<>()
定制排序外部实现 Comparator<E>，重写 comparenew TreeSet<>(comparator)
// 自然排序示例
class Employee implements Comparable<Employee> {
    public int compareTo(Employee o) {
        return this.id.compareTo(o.id);
    }
}
TreeSet<Employee> set = new TreeSet<>();  // 使用 Employee.compareTo

// 定制排序示例（Java 8 Lambda）
TreeSet<Employee> set = new TreeSet<>(
    (a, b) -> Double.compare(a.getSalary(), b.getSalary())
);

完整代码示例

示例一：飞翔科技员工 ID 去重排序

import java.util.*;

/**
 * 场景：飞翔科技人事系统需要维护在职员工的 ID 集合。
 * 大翔要求工号自动排序且不能重复，白歌选择了 TreeSet。
 * 小崔负责实现，孔蓝验证了重复元素的处理。
 */
public class FeiXiangEmployeeIdSet {
    public static void main(String[] args) {
        // ========== 1. 创建 TreeSet（String 自然排序：字典序） ==========
        TreeSet<String> employeeIds = new TreeSet<>();

        // ========== 2. 添加工号 ==========
        employeeIds.add("EMP003");
        employeeIds.add("EMP001");
        employeeIds.add("EMP005");
        employeeIds.add("EMP002");
        employeeIds.add("EMP004");

        // 注意：添加顺序是乱的，但 TreeSet 自动排序
        System.out.println("=== 飞翔科技员工ID（自动排序） ===");
        System.out.println(employeeIds);
        System.out.println("员工总数: " + employeeIds.size());

        // ========== 3. 重复元素测试 ==========
        System.out.println("\n=== 重复元素测试 ===");
        boolean added1 = employeeIds.add("EMP003");  // 已存在
        boolean added2 = employeeIds.add("EMP006");  // 新工号
        System.out.println("再次添加 EMP003: " + added1 + "（失败——已存在）");
        System.out.println("添加 EMP006: " + added2 + "（成功——新工号）");
        System.out.println("当前集合: " + employeeIds);

        // ========== 4. 导航方法 ==========
        System.out.println("\n=== 导航方法 ===");
        System.out.println("first（最小）: " + employeeIds.first());
        System.out.println("last（最大）: " + employeeIds.last());

        String middle = "EMP003";
        System.out.println("lower  (< EMP003): " + employeeIds.lower(middle));
        System.out.println("floor  (<= EMP003): " + employeeIds.floor(middle));
        System.out.println("ceiling(>= EMP003): " + employeeIds.ceiling(middle));
        System.out.println("higher (> EMP003): " + employeeIds.higher(middle));

        // ========== 5. 范围查询 ==========
        System.out.println("\n=== 范围查询 ===");
        // subSet: [EMP002, EMP005) 左闭右开
        System.out.println("[EMP002, EMP005): " + employeeIds.subSet("EMP002", "EMP005"));

        // headSet: < EMP004
        System.out.println("< EMP004: " + employeeIds.headSet("EMP004"));

        // tailSet: >= EMP004
        System.out.println(">= EMP004: " + employeeIds.tailSet("EMP004"));

        // ========== 6. 逆序视图 ==========
        System.out.println("\n=== 逆序视图 ===");
        System.out.println("逆序: " + employeeIds.descendingSet());

        // ========== 7. pollFirst / pollLast（取出并移除） ==========
        System.out.println("\n=== 取出最值 ===");
        String first = employeeIds.pollFirst();
        System.out.println("取出 first: " + first);
        String last = employeeIds.pollLast();
        System.out.println("取出 last: " + last);
        System.out.println("剩余: " + employeeIds);

        // ========== 8. 遍历方式 ==========
        System.out.println("\n=== 遍历 ===");
        // 方式一：增强 for
        for (String id : employeeIds) {
            System.out.println("  " + id);
        }

        // 方式二：JDK 8 forEach
        System.out.println("--- forEach Lambda ---");
        employeeIds.forEach(id -> System.out.println("  " + id));
    }
}

=== 飞翔科技员工ID（自动排序） ===
[EMP001, EMP002, EMP003, EMP004, EMP005]
员工总数: 5

=== 重复元素测试 ===
再次添加 EMP003: false（失败——已存在）
添加 EMP006: true（成功——新工号）
当前集合: [EMP001, EMP002, EMP003, EMP004, EMP005, EMP006]

=== 导航方法 ===
first（最小）: EMP001
last（最大）: EMP006
lower  (< EMP003): EMP002
floor  (<= EMP003): EMP003
ceiling(>= EMP003): EMP003
higher (> EMP003): EMP004

=== 范围查询 ===
[EMP002, EMP005): [EMP002, EMP003, EMP004]
< EMP004: [EMP001, EMP002, EMP003]
>= EMP004: [EMP004, EMP005, EMP006]

=== 逆序视图 ===
逆序: [EMP006, EMP005, EMP004, EMP003, EMP002, EMP001]

=== 取出最值 ===
取出 first: EMP001
取出 last: EMP006
剩余: [EMP002, EMP003, EMP004, EMP005]

=== 遍历 ===
  EMP002
  EMP003
  EMP004
  EMP005
--- forEach Lambda ---
  EMP002
  EMP003
  EMP004
  EMP005

示例二：飞翔科技员工考试成绩排名

import java.util.*;

/**
 * 场景：飞翔科技内部技术考试后，大翔要求对成绩进行排名（从高到低），
 * 同时排除缺考员工。白歌选择 TreeSet 搭配自定义 Comparator 实现。
 * 小崔实现了按分数降序、分数相同时按姓名升序的复合排序。
 */
public class FeiXiangExamRanking {

    /** 考生实体 */
    static class Examinee implements Comparable<Examinee> {
        private final String name;
        private final int score;
        private final String department;

        public Examinee(String name, int score, String department) {
            this.name = name;
            this.score = score;
            this.department = department;
        }

        public String getName() { return name; }
        public int getScore() { return score; }
        public String getDepartment() { return department; }

        // 自然排序：按姓名字典序
        @Override
        public int compareTo(Examinee other) {
            return this.name.compareTo(other.name);
        }

        @Override
        public String toString() {
            return String.format("%s | %s | %d分", name, department, score);
        }
    }

    public static void main(String[] args) {
        // ========== 1. 定制排序：按分数降序，同分按姓名升序 ==========
        TreeSet<Examinee> ranking = new TreeSet<>(
            Comparator.comparingInt(Examinee::getScore)
                      .reversed()                            // 分数从高到低
                      .thenComparing(Examinee::getName)      // 同分按姓名字典序
        );

        // ========== 2. 添加考生成绩 ==========
        ranking.add(new Examinee("白歌", 98, "技术部"));
        ranking.add(new Examinee("小崔", 72, "技术部"));
        ranking.add(new Examinee("大翔", 85, "管理层"));
        ranking.add(new Examinee("孔蓝", 88, "测试部"));
        ranking.add(new Examinee("Frank", 76, "市场部"));
        ranking.add(new Examinee("赵鸣", 88, "技术部"));   // 与孔蓝同分
        ranking.add(new Examinee("孙鹤", 72, "技术部"));   // 与小崔同分
        ranking.add(new Examinee("黄俪", 80, "人事部"));

        // ========== 3. 输出排名 ==========
        System.out.println("=== 飞翔科技技术考试成绩排名 ===");
        System.out.println("（按分数降序，同分按姓名升序）\n");

        int rank = 1;
        for (Examinee e : ranking) {
            System.out.printf("  第%d名: %s%n", rank++, e);
        }

        // ========== 4. 导航查询 ==========
        System.out.println("\n=== 成绩分析 ===");
        System.out.println("第一名（最高分）: " + ranking.first());
        System.out.println("最后一名（最低分）: " + ranking.last());

        // 找出 85 分上下最近的选手
        int target = 85;
        System.out.println("\n以 " + target + " 分为基准：");
        System.out.println("  >= " + target + " 的最小: " + ranking.ceiling(
            new Examinee("", target, "")));
        System.out.println("  <= " + target + " 的最大: " + ranking.floor(
            new Examinee("", target, "")));

        // ========== 5. 范围查询：80~90 分区间 ==========
        System.out.println("\n=== 范围查询：80 ~ 90 分段 ===");
        NavigableSet<Examinee> midRange = ranking.subSet(
            new Examinee("", 90, ""), true,   // 包含 90
            new Examinee("", 80, ""), false   // 不包含 80
        );
        // 注意：因为是降序排列，from > to
        // 实际 subSet 基于自然顺序（Comparator），所以用 Comparator 的比较逻辑

        // 用另一个更直观的方式来展示 80 分及以上
        NavigableSet<Examinee> above80 = ranking.tailSet(
            new Examinee("", 80, ""), true  // >= 80
        );
        System.out.println("80 分及以上的选手:");
        above80.forEach(e -> System.out.println("  " + e));

        // ========== 6. 部门统计 ==========
        System.out.println("\n=== 按部门统计平均分 ===");
        Map<String, List<Examinee>> byDept = new TreeMap<>();
        for (Examinee e : ranking) {
            byDept.computeIfAbsent(e.getDepartment(), k -> new ArrayList<>()).add(e);
        }
        byDept.forEach((dept, list) -> {
            double avg = list.stream().mapToInt(Examinee::getScore).average().orElse(0);
            System.out.printf("  %s: %.1f 分 (%d人)%n", dept, avg, list.size());
        });
    }
}

=== 飞翔科技技术考试成绩排名 ===
（按分数降序，同分按姓名升序）

  第1名: 白歌 | 技术部 | 98分
  第2名: 孔蓝 | 测试部 | 88分
  第3名: 赵鸣 | 技术部 | 88分
  第4名: 大翔 | 管理层 | 85分
  第5名: 黄俪 | 人事部 | 80分
  第6名: Frank | 市场部 | 76分
  第7名: 孙鹤 | 技术部 | 72分
  第8名: 小崔 | 技术部 | 72分

=== 成绩分析 ===
第一名（最高分）: 白歌 | 技术部 | 98分
最后一名（最低分）: 小崔 | 技术部 | 72分

以 85 分为基准：
  >= 85 的最小: 大翔 | 管理层 | 85分
  <= 85 的最大: 大翔 | 管理层 | 85分

=== 范围查询：80 ~ 90 分段 ===
80 分及以上的选手:
  白歌 | 技术部 | 98分
  孔蓝 | 测试部 | 88分
  赵鸣 | 技术部 | 88分
  大翔 | 管理层 | 85分
  黄俪 | 人事部 | 80分

=== 按部门统计平均分 ===
  人事部: 80.0 分 (1人)
  市场部: 76.0 分 (1人)
  技术部: 82.5 分 (4人)
  测试部: 88.0 分 (1人)
  管理层: 85.0 分 (1人)

易错场景

反例一：compareTo 不一致导致元素"消失"

小崔在写 Employee 的排序时，只用薪资做 compareTo，导致相同薪资的不同员工被 TreeSet 判定为重复：

// ❌ 错误：compareTo 仅用 salary，同薪不同人被 TreeSet 视为重复
class Employee implements Comparable<Employee> {
    String name;
    double salary;

    @Override
    public int compareTo(Employee o) {
        return Double.compare(this.salary, o.salary);  // 只用薪资！
    }
}

TreeSet<Employee> set = new TreeSet<>();
set.add(new Employee("小崔", 12000));
set.add(new Employee("孙鹤", 12000));  // compareTo 返回 0 → 被视为重复
System.out.println(set.size());  // 1 —— 孙鹤消失了！

原理：TreeSet 判断元素是否相等使用的是 compareTo/compare（返回 0 即相等），不是 equals。这与 HashSet（依赖 hashCode + equals）有本质区别。

纠正：

// ✅ 方案一：compareTo 覆盖所有决定唯一性的字段
@Override
public int compareTo(Employee o) {
    int cmp = Double.compare(this.salary, o.salary);
    if (cmp != 0) return cmp;
    return this.name.compareTo(o.name);  // 工资相同时按姓名区分
}

// ✅ 方案二：使用 Comparator 链式组合（推荐）
TreeSet<Employee> set = new TreeSet<>(
    Comparator.comparingDouble(Employee::getSalary)
              .thenComparing(Employee::getName)
);

反例二：TreeSet 中添加 null 导致 NPE

// ❌ 错误：TreeSet 不允许 null
TreeSet<String> set = new TreeSet<>();
set.add("A");
set.add("B");
set.add(null);  // NullPointerException！
// TreeSet 内部调用 m.put(null, PRESENT)
// → TreeMap.put(null, ...) → compareTo/compare(null, ...) → NPE

纠正：

// ✅ 方案一：使用 HashSet 替代（允许 null）
Set<String> set = new HashSet<>();
set.add(null);  // OK

// ✅ 方案二：使用特殊标记代替 null（如业务要求有序）
TreeSet<String> set = new TreeSet<>();
set.add("");    // 空字符串代表"未设置"

// ✅ 方案三：插入前做 null 检查
if (element != null) {
    treeSet.add(element);
}

反例三：subSet 视图的边界陷阱

// ❌ 错误：subSet 是视图，修改受边界限制
TreeSet<Integer> set = new TreeSet<>();
set.add(1); set.add(3); set.add(5); set.add(7); set.add(9);

SortedSet<Integer> sub = set.subSet(3, 7);  // [3, 7) = {3, 5}
System.out.println(sub);  // [3, 5]

// 尝试向 sub 插入超出范围的元素
sub.add(8);  // IllegalArgumentException: key out of range!
// sub 的边界是 [3, 7)，8 不在范围内

// 修改原 set 会影响 sub 视图，反之亦然
set.add(4);   // 在原 set 中添加 4（在范围内）
System.out.println(sub);  // [3, 4, 5] —— sub 视图自动更新了！

纠正：

// ✅ 如需独立副本，使用 new TreeSet<>(subSet)
Set<Integer> independentCopy = new TreeSet<>(set.subSet(3, 7));
// independentCopy 与原 set 完全独立，互不影响
independentCopy.add(100);  // 不影响原 set

反例四：遍历时修改导致 ConcurrentModificationException

// ❌ 错误：for-each 遍历中直接 add/remove
TreeSet<Integer> set = new TreeSet<>(Arrays.asList(1, 2, 3, 4, 5));
for (Integer n : set) {
    if (n % 2 == 0) {
        set.remove(n);  // ConcurrentModificationException！
    }
}

纠正：

// ✅ 方案一：使用迭代器
Iterator<Integer> it = set.iterator();
while (it.hasNext()) {
    if (it.next() % 2 == 0) {
        it.remove();  // 安全删除
    }
}

// ✅ 方案二：JDK 8 removeIf
set.removeIf(n -> n % 2 == 0);  // 内部使用迭代器，安全

面试考点

Q1：Comparable 和 Comparator 的区别？各在什么场景下使用？

维度Comparable（自然排序）Comparator（定制排序）
包java.langjava.util
核心方法compareTo(T o)compare(T o1, T o2)
实现位置元素类自身实现（侵入式）外部独立实现（无侵入）
耦度高——排序逻辑侵入类代码低——策略模式，解耦
排序数量仅一种（唯一的自然顺序）可定义任意多种
TreeSet 构造new TreeSet<>()new TreeSet<>(comparator)

使用原则：如果元素有"天然的"唯一排序方式（如 String 的字典序、Integer 的数值序），使用 Comparable；如果需要多种排序（如 Employee 既可"按工资"又可"按入职日期"），使用 Comparator。Java 8 中 Comparator 支持 Lambda 和方法引用（如 Comparator.comparing(Person::getAge).thenComparing(Person::getName)），使用极为灵活。

Q2：TreeSet 如何判断两个元素相等？与 HashSet 有何不同？

TreeSet 完全不依赖 equals 方法判断相等，而是使用 compareTo（或 Comparator 的 compare）的返回值。当 compareTo 返回 0 时，TreeSet 认为两个元素相等，后续 add 会返回 false。这与 HashSet（依赖 hashCode 定位桶 + equals 判断相等）有本质区别。

这意味着：即使两个对象的 equals 返回 false，只要 compareTo 返回 0，TreeSet 就认为它们是"相同"的。这也是为什么 Set 接口的通用契约建议 compareTo 返回 0 与 equals 返回 true 保持一致性。

Q3：为什么 TreeSet 不允许 null 元素？

TreeSet 底层是 TreeMap，在插入时需要调用 compareTo 或 compare 方法来决定元素在红黑树中的位置。null.compareTo(obj) 或 comparator.compare(null, obj) 会直接抛出 NullPointerException。从设计哲学角度，null 没有"顺序"的概念，放入有序集合中语义不清（无法确定 null 应该排在第一位还是最后一位）。相比之下，HashSet 允许 null 因为它只需要 hashCode()（JVM 为 null 特殊处理返回 0），不涉及比较操作。

Q4：TreeSet 的时间复杂度为什么是 O(log n)？什么情况会退化？

TreeSet 底层是 TreeMap，TreeMap 底层是红黑树——一种自平衡二叉搜索树。红黑树通过五大性质（特别是"无连续红色节点"和"黑高一致"）保证树高始终保持在 O(log n) 级别。查找、插入、删除每次操作沿树向下遍历最多 O(log n) 层，每层比较操作 O(1)，总复杂度 O(log n)。

红黑树是自平衡的，不会退化到 O(n)（这是与普通 BST 的本质区别）。普通二叉搜索树在按顺序插入递增/递减数据时会退化为链表（O(n)），但红黑树的旋转和着色操作始终维持近似平衡（最长路径 ≤ 2 × 最短路径）。

Q5：subSet/headSet/tailSet 返回的是副本还是视图？有哪些隐患？

返回的是视图（view），不是独立副本。这带来三个关键影响： ① 双向影响：对视图的修改会直接反映到原 TreeSet，反之亦然； ② 边界限制：向 subSet 中插入超出 [from, to) 范围的元素会立即抛出 IllegalArgumentException； ③ 视图失效：如果原 TreeSet 发生结构性修改（不是通过该视图本身操作的），视图的后续操作会抛 ConcurrentModificationException。 如需独立副本，使用 new TreeSet<>(set.subSet(from, to)) 创建拷贝。