TreeSet 与 Comparable

本章定位：掌握 TreeSet 基于红黑树的有序集合特性，理解 Comparable（自然排序）和 Comparator（定制排序）两种排序方式的原理与使用场景。TreeSet 在飞翔科技的员工工资排序、项目优先级队列等场景中发挥关键作用。

概述

TreeSet 是基于 TreeMap 的 NavigableSet 实现，底层使用红黑树（自平衡二叉搜索树）维护元素的有序性。每个元素作为 TreeMap 的 key 存储，value 同样是 PRESENT 常量。

特性描述
底层实现TreeMap<E, Object>（红黑树）
元素顺序自然顺序（Comparable）或定制顺序（Comparator）
是否允许 null不允许（需要调用 compareTo/compare 比较，会 NPE）
线程安全否
时间复杂度add/remove/contains 均为 O(log n)
实现接口NavigableSet<E>, SortedSet<E>, Set<E>

方法速查表

方法描述时间复杂度
add(E e)添加元素，按照排序规则插入O(log n)
remove(Object o)删除元素O(log n)
contains(Object o)判断是否包含O(log n)
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(from, to)返回 [from, to) 子集视图—
headSet(to)返回小于 to 的元素视图—
tailSet(from)返回大于等于 from 的元素视图—
descendingSet()返回逆序视图—

两种排序方式

方式一：Comparable 自然排序

对象实现 Comparable<T> 接口，重写 compareTo(T o) 方法：

public interface Comparable<T> {
    int compareTo(T o);
    // 返回值规则：
    //  this < o  →  负整数
    //  this == o →  0
    //  this > o  →  正整数
}

约定：强烈建议 compareTo 返回 0 时 equals 也返回 true（虽然并非强制）。

方式二：Comparator 定制排序

通过 Comparator<T> 接口的 compare(T o1, T o2) 方法实现：

@FunctionalInterface
public interface Comparator<T> {
    int compare(T o1, T o2);
    // 返回值规则同 compareTo
}

在 Java 8 中可以用 Lambda 表达式简洁写出：

TreeSet<Employee> bySalary = new TreeSet<>(
    (a, b) -> Double.compare(a.getSalary(), b.getSalary())
);

排序方式对比

维度ComparableComparator
包java.langjava.util
方法compareTo(T o)compare(T o1, T o2)
实现位置元素类自身实现外部独立实现（策略模式）
耦合度侵入元素类无侵入，解耦
灵活性仅一种排序方式可定义多种排序方式
使用方式new TreeSet<>()new TreeSet<>(comparator)
适用场景元素有"天然的"唯一排序需要多种排序规则或元素不可修改

核心原理：红黑树

红黑树的核心价值：通过颜色约束 + 旋转维持树的平衡（最长路径不超过最短路径的 2 倍），保证插入、删除、查找的最坏时间复杂度为 O(log n)。

TreeSet 的排序完全委托给 TreeMap。添加元素时调用 TreeMap.put(e, PRESENT)，TreeMap 通过红黑树的 compare 比较决定插入位置。

完整示例

示例一：飞翔科技员工按工资排序

import java.util.*;

// 场景：飞翔科技年终调薪，大翔要求按工资从低到高排列所有员工
class Employee implements Comparable<Employee> {
    private String name;
    private double salary;
    private String department;

    public Employee(String name, double salary, String department) {
        this.name = name;
        this.salary = salary;
        this.department = department;
    }

    // 自然排序：按工资从低到高
    @Override
    public int compareTo(Employee other) {
        return Double.compare(this.salary, other.salary);
    }

    public String getName() { return name; }
    public double getSalary() { return salary; }
    public String getDepartment() { return department; }

    @Override
    public String toString() {
        return String.format("%s | %s | ¥%.0f", name, department, salary);
    }
}

public class SalarySort {
    public static void main(String[] args) {
        // === 方式一：自然排序（Comparable：按工资升序） ===
        TreeSet<Employee> bySalary = new TreeSet<>();
        bySalary.add(new Employee("大翔", 80000, "管理层"));
        bySalary.add(new Employee("白歌", 35000, "技术部"));
        bySalary.add(new Employee("小崔", 12000, "技术部"));
        bySalary.add(new Employee("孔蓝", 15000, "测试部"));
        bySalary.add(new Employee("韩信", 25000, "技术部"));

        System.out.println("=== 按工资自然排序（升序） ===");
        for (Employee e : bySalary) {
            System.out.println("  " + e);
        }

        System.out.println("\n工资最低: " + bySalary.first());
        System.out.println("工资最高: " + bySalary.last());

        // === 方式二：Comparator 定制排序（按工资降序） ===
        TreeSet<Employee> bySalaryDesc = new TreeSet<>(
            (a, b) -> Double.compare(b.getSalary(), a.getSalary())
        );
        bySalaryDesc.addAll(bySalary);

        System.out.println("\n=== 按工资降序（Comparator Lambda） ===");
        for (Employee e : bySalaryDesc) {
            System.out.println("  " + e);
        }

        // === 方式三：Comparator 按部门 → 工资排序 ===
        TreeSet<Employee> byDeptThenSalary = new TreeSet<>(
            Comparator.comparing(Employee::getDepartment)
                      .thenComparingDouble(Employee::getSalary)
        );
        byDeptThenSalary.addAll(bySalary);

        System.out.println("\n=== 按部门 → 工资排序 ===");
        for (Employee e : byDeptThenSalary) {
            System.out.println("  " + e);
        }
    }
}

运行输出：
=== 按工资自然排序（升序） ===
  小崔 | 技术部 | ¥12000
  孔蓝 | 测试部 | ¥15000
  韩信 | 技术部 | ¥25000
  白歌 | 技术部 | ¥35000
  大翔 | 管理层 | ¥80000

工资最低: 小崔 | 技术部 | ¥12000
工资最高: 大翔 | 管理层 | ¥80000

=== 按工资降序（Comparator Lambda） ===
  大翔 | 管理层 | ¥80000
  白歌 | 技术部 | ¥35000
  韩信 | 技术部 | ¥25000
  孔蓝 | 测试部 | ¥15000
  小崔 | 技术部 | ¥12000

=== 按部门 → 工资排序 ===
  大翔 | 管理层 | ¥80000
  小崔 | 技术部 | ¥12000
  韩信 | 技术部 | ¥25000
  白歌 | 技术部 | ¥35000
  孔蓝 | 测试部 | ¥15000

示例二：NavigableSet 范围查询——工资区间筛选

import java.util.*;

// 场景：白歌需要筛选出工资在 15000 ~ 40000 之间的员工
public class NavigableSetDemo {
    public static void main(String[] args) {
        TreeSet<Double> salaries = new TreeSet<>(Arrays.asList(
            8000.0, 12000.0, 15000.0, 18000.0, 
            22000.0, 25000.0, 30000.0, 35000.0, 50000.0
        ));

        System.out.println("全部工资: " + salaries);
        System.out.println("最低: " + salaries.first() + ", 最高: " + salaries.last());

        // subSet: [15000, 35000)  左闭右开
        System.out.println("\n工资区间 [15000, 35000): " + salaries.subSet(15000.0, 35000.0));

        // headSet: < 20000
        System.out.println("工资 < 20000: " + salaries.headSet(20000.0));

        // tailSet: >= 25000
        System.out.println("工资 >= 25000: " + salaries.tailSet(25000.0));

        // lower / floor / ceiling / higher
        double target = 20000.0;
        System.out.println("\n以 " + target + " 为基准：");
        System.out.println("  lower  (严格小于): " + salaries.lower(target));
        System.out.println("  floor  (小于等于): " + salaries.floor(target));
        System.out.println("  ceiling(大于等于): " + salaries.ceiling(target));
        System.out.println("  higher (严格大于): " + salaries.higher(target));

        // descendingSet: 逆序视图
        System.out.println("\n逆序: " + salaries.descendingSet());
    }
}

运行输出：
全部工资: [8000.0, 12000.0, 15000.0, 18000.0, 22000.0, 25000.0, 30000.0, 35000.0, 50000.0]
最低: 8000.0, 最高: 50000.0

工资区间 [15000, 35000): [15000.0, 18000.0, 22000.0, 25000.0, 30000.0]
工资 < 20000: [8000.0, 12000.0, 15000.0, 18000.0]
工资 >= 25000: [25000.0, 30000.0, 35000.0, 50000.0]

以 20000.0 为基准：
  lower  (严格小于): 18000.0
  floor  (小于等于): 18000.0
  ceiling(大于等于): 22000.0
  higher (严格大于): 22000.0

逆序: [50000.0, 35000.0, 30000.0, 25000.0, 22000.0, 18000.0, 15000.0, 12000.0, 8000.0]

易错场景

反例一：compareTo 不一致导致元素丢失

小崔在写 Employee 的排序时同时实现了 Comparable 和传入 Comparator，导致困惑：

// ❌ 错误：compareTo 仅用 salary，但 HashSet/TreeSet 混用导致困惑
class Employee implements Comparable<Employee> {
    String name;
    double salary;
    
    @Override
    public int compareTo(Employee o) {
        return Double.compare(this.salary, o.salary);  // 只用 salary
    }
}

// TreeSet 中 小崔(12000) 和 张三(12000) 被视为相同元素！
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。当两个不同的员工工资相同时，compareTo 返回 0，TreeSet 认为它们是重复元素。

纠正方案：

// ✅ 正确：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(null);  // NullPointerException!
// 因为 TreeSet 需要调用 compareTo/compare 比较 null

纠正：使用 HashSet（允许 null）或在使用前做 null 检查。

面试考点

Q1：Comparable 和 Comparator 的区别？

Comparable 是内部比较器，由元素类自身实现 compareTo 方法，定义"自然排序"；Comparator 是外部比较器，独立于元素类，通过 compare 方法定义排序规则。Comparable 侵入类代码且只能有一种排序；Comparator 无侵入，可定义任意多种排序。Java 8 中 Comparator 支持 Lambda 表达式和方法引用（如 Comparator.comparing(Person::getAge)），使用更加灵活。

Q2：TreeSet 如何判断两个元素相等？

TreeSet 不依赖 equals 方法判断相等，而是使用 compareTo（或 Comparator 的 compare）的返回值。当 compareTo 返回 0 时，TreeSet 认为两个元素相等，后续添加的会被拒绝。这与 HashSet（依赖 hashCode + equals）有本质区别。Set 接口的通用契约要求 compareTo 返回 0 与 equals 返回 true 保持一致性。

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

TreeSet 在插入、查找、删除时都需要调用 compareTo 或 compare 方法进行比较。null.compareTo(obj) 或 comparator.compare(null, obj) 都会抛出 NullPointerException。从设计角度，null 没有"顺序"的概念，放入有序集合中语义不清。HashSet 允许 null 因为它只依赖 hashCode（null.hashCode() 被 JVM 特殊处理返回 0）。

Q4：TreeSet 的时间复杂度为什么是 O(log n)？

TreeSet 底层是 TreeMap，TreeMap 底层是红黑树——一种自平衡二叉搜索树。红黑树通过颜色约束保证树的高度始终保持在 O(log n) 级别，因此查找、插入、删除操作都需要沿树向下遍历 O(log n) 层。每次比较操作是 O(1)，总复杂度 O(log n)。相比之下，HashSet 的 O(1) 是平均情况（哈希冲突会退化）。

Q5：subSet/headSet/tailSet 返回的是副本还是视图？

返回的是视图（view），不是独立副本。对视图的修改会反映到原 TreeSet，反之亦然。但视图有边界限制：向 subSet 中添加超出边界范围的元素会抛出 IllegalArgumentException。如果需要独立副本，应该 new TreeSet<>(originalSet.subSet(from, to))。