java基础:TreeSet
实现 Comparable 接口@Override// 先按分数排序，分数相同按姓名排序= 0?@Override// 同分数，按姓名排序// 输出: [Alice(85), Charlie(85), Bob(92)]使用 Comparator@Override// 按部门排序，同部门按薪资降序// 输出:TreeSet 是一个功能强大的有序集合实现，基于红黑树数据结构提供了高效的排序和导航操作。
·
1. TreeSet 概述
TreeSet 是 Java 集合框架中的一个重要实现类，它基于红黑树（Red-Black tree）实现，具有以下特点：
-
有序性：元素按照自然顺序或自定义比较器排序
-
唯一性：不允许重复元素
-
非同步：非线程安全，需要外部同步
-
基于 NavigableSet 接口：支持导航方法
2. 底层数据结构：红黑树
红黑树特性
红黑树是一种自平衡的二叉查找树，具有以下性质：
-
每个节点要么是红色，要么是黑色
-
根节点是黑色
-
所有叶子节点（NIL）都是黑色
-
红色节点的子节点必须是黑色
-
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
TreeSet 中的红黑树实现
// TreeSet 实际上使用 TreeMap 来实现
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable {
// 使用 TreeMap 作为存储
private transient NavigableMap<E,Object> m;
// 虚拟值，用于 TreeMap
private static final Object PRESENT = new Object();
}
3. TreeSet 的基本使用
创建 TreeSet
import java.util.TreeSet;
import java.util.Comparator;
// 1. 使用自然排序
TreeSet<Integer> naturalSet = new TreeSet<>();
// 2. 使用自定义比较器
TreeSet<String> customSet = new TreeSet<>(new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
return s1.length() - s2.length(); // 按字符串长度排序
}
});
// 3. 使用 Lambda 表达式
TreeSet<String> lambdaSet = new TreeSet<>(
(s1, s2) -> s1.length() - s2.length()
);
基本操作示例
public class TreeSetBasicExample {
public static void main(String[] args) {
TreeSet<Integer> numbers = new TreeSet<>();
// 添加元素
numbers.add(5);
numbers.add(2);
numbers.add(8);
numbers.add(1);
numbers.add(5); // 重复元素，不会被添加
System.out.println("TreeSet: " + numbers); // [1, 2, 5, 8]
// 删除元素
numbers.remove(2);
System.out.println("After removal: " + numbers); // [1, 5, 8]
// 检查元素是否存在
System.out.println("Contains 5: " + numbers.contains(5)); // true
// 获取大小
System.out.println("Size: " + numbers.size()); // 3
// 清空集合
numbers.clear();
System.out.println("After clear: " + numbers); // []
}
}
4. 导航方法详解
导航方法示例
public class TreeSetNavigationExample {
public static void main(String[] args) {
TreeSet<Integer> set = new TreeSet<>();
set.add(10);
set.add(20);
set.add(30);
set.add(40);
set.add(50);
// 第一个和最后一个元素
System.out.println("First: " + set.first()); // 10
System.out.println("Last: " + set.last()); // 50
// 小于等于指定值的最大元素
System.out.println("Floor(25): " + set.floor(25)); // 20
// 大于等于指定值的最小元素
System.out.println("Ceiling(25): " + set.ceiling(25)); // 30
// 严格小于指定值的最大元素
System.out.println("Lower(30): " + set.lower(30)); // 20
// 严格大于指定值的最小元素
System.out.println("Higher(30): " + set.higher(30)); // 40
// 获取并移除第一个元素
System.out.println("Poll first: " + set.pollFirst()); // 10
System.out.println("After pollFirst: " + set); // [20, 30, 40, 50]
// 获取并移除最后一个元素
System.out.println("Poll last: " + set.pollLast()); // 50
System.out.println("After pollLast: " + set); // [20, 30, 40]
}
}
5. 子集操作
子集方法示例
public class TreeSetSubsetExample {
public static void main(String[] args) {
TreeSet<Integer> set = new TreeSet<>();
for (int i = 1; i <= 10; i++) {
set.add(i);
}
// 获取子集 [fromElement, toElement)
SortedSet<Integer> subSet = set.subSet(3, 7);
System.out.println("Subset [3,7): " + subSet); // [3, 4, 5, 6]
// 获取头部子集（小于 toElement）
SortedSet<Integer> headSet = set.headSet(5);
System.out.println("HeadSet (<5): " + headSet); // [1, 2, 3, 4]
// 获取尾部子集（大于等于 fromElement）
SortedSet<Integer> tailSet = set.tailSet(5);
System.out.println("TailSet (>=5): " + tailSet); // [5, 6, 7, 8, 9, 10]
// 使用 NavigableSet 的精确控制方法
NavigableSet<Integer> descendingSet = set.descendingSet();
System.out.println("Descending set: " + descendingSet); // [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
}
}
6. 自定义对象排序
实现 Comparable 接口
class Student implements Comparable<Student> {
private String name;
private int score;
public Student(String name, int score) {
this.name = name;
this.score = score;
}
@Override
public int compareTo(Student other) {
// 先按分数排序，分数相同按姓名排序
int scoreCompare = Integer.compare(this.score, other.score);
return scoreCompare != 0 ? scoreCompare : this.name.compareTo(other.name);
}
@Override
public String toString() {
return name + "(" + score + ")";
}
}
public class ComparableExample {
public static void main(String[] args) {
TreeSet<Student> students = new TreeSet<>();
students.add(new Student("Alice", 85));
students.add(new Student("Bob", 92));
students.add(new Student("Charlie", 85)); // 同分数，按姓名排序
System.out.println("Students: " + students);
// 输出: [Alice(85), Charlie(85), Bob(92)]
}
}
使用 Comparator
class Employee {
private String name;
private String department;
private double salary;
public Employee(String name, String department, double salary) {
this.name = name;
this.department = department;
this.salary = salary;
}
// getters...
public String getName() { return name; }
public String getDepartment() { return department; }
public double getSalary() { return salary; }
@Override
public String toString() {
return name + "[" + department + "]-$" + salary;
}
}
public class ComparatorExample {
public static void main(String[] args) {
// 按部门排序，同部门按薪资降序
TreeSet<Employee> employees = new TreeSet<>(
Comparator.comparing(Employee::getDepartment)
.thenComparing(Comparator.comparingDouble(Employee::getSalary).reversed())
);
employees.add(new Employee("John", "IT", 75000));
employees.add(new Employee("Jane", "HR", 65000));
employees.add(new Employee("Mike", "IT", 80000));
System.out.println("Employees:");
employees.forEach(System.out::println);
// 输出:
// Mike[IT]-$80000.0
// John[IT]-$75000.0
// Jane[HR]-$65000.0
}
}
7. 性能分析
时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| add() | O(log n) | 插入操作 |
| remove() | O(log n) | 删除操作 |
| contains() | O(log n) | 查找操作 |
| first()/last() | O(1) | 获取首尾元素 |
| floor()/ceiling() | O(log n) | 导航操作 |
空间复杂度
- O(n)：需要存储 n 个元素
8. 使用注意事项
线程安全
// TreeSet 非线程安全，需要外部同步
Set<Integer> synchronizedSet = Collections.synchronizedSet(new TreeSet<>());
// 或者在多线程环境下使用 ConcurrentSkipListSet
// NavigableSet<Integer> concurrentSet = new ConcurrentSkipListSet<>();
比较一致性
public class ConsistencyExample {
public static void main(String[] args) {
TreeSet<String> set = new TreeSet<>();
set.add("apple");
set.add("banana");
set.add("cherry");
// 错误：修改会影响排序，但 TreeSet 不会重新排序
// 应该避免在添加到 TreeSet 后修改影响排序的字段
System.out.println("Original set: " + set);
// 正确的做法是删除后重新添加，如果需要修改
String toModify = "apple";
if (set.remove(toModify)) {
// 修改逻辑
String modified = "apricot";
set.add(modified);
}
System.out.println("Modified set: " + set);
}
}
9. 实际应用场景
场景1：维护有序数据
public class ScoreManager {
private TreeSet<Integer> scores;
public ScoreManager() {
scores = new TreeSet<>(Comparator.reverseOrder()); // 降序排列
}
public void addScore(int score) {
scores.add(score);
}
public List<Integer> getTopScores(int n) {
return scores.stream()
.limit(n)
.collect(Collectors.toList());
}
public Integer getScoreHigherThan(int threshold) {
return scores.higher(threshold);
}
}
场景2：范围查询
public class RangeQueryExample {
public static void main(String[] args) {
TreeSet<LocalDate> dates = new TreeSet<>();
dates.add(LocalDate.of(2023, 1, 15));
dates.add(LocalDate.of(2023, 3, 20));
dates.add(LocalDate.of(2023, 5, 10));
dates.add(LocalDate.of(2023, 7, 5));
dates.add(LocalDate.of(2023, 9, 30));
LocalDate start = LocalDate.of(2023, 2, 1);
LocalDate end = LocalDate.of(2023, 8, 1);
// 获取指定范围内的日期
SortedSet<LocalDate> range = dates.subSet(start, end);
System.out.println("Dates between " + start + " and " + end + ": " + range);
}
}
总结
TreeSet 是一个功能强大的有序集合实现，基于红黑树数据结构提供了高效的排序和导航操作。它在需要维护元素顺序、进行范围查询或需要快速查找最值的场景中非常有用。使用时需要注意其非线程安全的特性，以及在自定义对象排序时确保比较逻辑的一致性。
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
3
0- 0
已为社区贡献2条内容
所有评论(0)