深入理解 Java 中的 TreeSet 集合
深入理解 Java 中的 TreeSet 集合
TreeSet 是 Java 集合框架中的一种集合类，它基于 TreeMap 实现，底层使用了红黑树这一平衡二叉搜索树结构。TreeSet 提供了一种确保元素有序且不重复的集合，它在排序和去重方面非常有用。在这篇文章中，我们将深入了解 TreeSet 的特点、基本用法、以及如何通过自然排序和比较器排序进行元素排序。
TreeSet 集合概述和特点
- 不可存储重复元素：
TreeSet不允许存储重复的元素。如果试图添加重复的元素，则会被忽略。 - 没有索引：与
ArrayList不同，TreeSet不能通过索引访问元素。它是基于树结构的集合，所有的操作（如查找、插入、删除）都遵循树的规则。 - 有序存储：
TreeSet可以将元素按照一定的规则进行排序，主要有以下两种方式：TreeSet()：默认使用元素的自然排序（Comparable）。TreeSet(Comparator comparator)：通过自定义比较器（Comparator）进行排序。
TreeSet 集合基本使用
我们先来看一个简单的例子，如何使用 TreeSet 存储 Integer 类型的元素，并遍历它们：
import java.util.TreeSet;public class TreeSetDemo01 {public static void main(String[] args) {// 创建集合对象TreeSet<Integer> ts = new TreeSet<Integer>();// 添加元素ts.add(10);ts.add(40);ts.add(30);ts.add(50);ts.add(20);ts.add(30); // 重复元素，不会被添加// 遍历集合for (Integer i : ts) {System.out.println(i); // 输出结果：[10, 20, 30, 40, 50]}}
}
在上面的例子中，TreeSet 自动对元素进行排序，并确保集合中没有重复的元素。
自然排序（Comparable）的使用
接下来我们看一个更复杂的例子，如何使用 TreeSet 存储自定义对象。在此案例中，我们存储 Student 对象并要求按年龄升序排序，若年龄相同，则按姓名的字母顺序排序。
实现步骤
第一步：添加第一个元素 wangwu (25)
-
添加对象：
new Student("wangwu", 25) -
树的状态：
- 这是树中的第一个节点，因此
wangwu作为根节点。 - 根据红黑树的性质，根节点必须是黑色。
图示：
- 初始插入时，
wangwu (25)是红色节点。 - 由于是第一个节点，调整为黑色节点。
- 这是树中的第一个节点，因此
wangwu (25, 黑)
第二步：添加第二个元素 lisi (24)
-
添加对象：
new Student("lisi", 24) -
插入过程：
- 与根节点
wangwu (25)进行比较：24 < 25，lisi应该插入到wangwu的左子树中。- 新插入的节点默认是红色。
图示：
- 插入后，
lisi (24)为红色节点，wangwu (25)仍然为黑色。
- 与根节点
wangwu (25, 黑)/lisi (24, 红)
第三步：添加第三个元素 zhangsan (23)
-
添加对象：
new Student("zhangsan", 23) -
插入过程：
- 首先与根节点
wangwu (25)比较：23 < 25，继续向左，进入左子树。
- 再与
lisi (24)比较：23 < 24，因此zhangsan应插入到lisi的左子树中。- 新插入的节点默认是红色。
- 此时，
lisi和zhangsan都是红色，违反了红黑树中不能有两个连续红色节点的规则，需要进行调整。
- 首先与根节点
调整过程：
- 对
lisi (24)进行右旋，lisi变为黑色，zhangsan (23)保持红色。
图示：
lisi (24, 黑)/ \
zhangsan (23, 红) wangwu (25, 红)
第四步：添加第四个元素 zhaoliu (26)
- 添加对象：
new Student("zhaoliu", 26) - 插入过程：
- 首先与根节点
lisi (24)比较：26 > 24，因此向右，进入右子树。
- 再与
wangwu (25)比较：26 > 25，所以zhaoliu应插入到wangwu的右子树中。- 新插入的节点默认是红色。
- 首先与根节点
调整过程：
- 此时
wangwu为红色，zhaoliu也是红色，违反了两个连续红色节点的规则。 - 为了修复此违反，执行以下步骤：
- 将
wangwu (25)变为黑色，将根节点lisi (24)变为红色，zhaoliu (26)保持红色。
- 将
图示：
lisi (24, 红)/ \
zhangsan (23, 黑) wangwu (25, 黑)\zhaoliu (26, 红)
代码实现
学生类：
public class Student implements Comparable<Student> {private String name;private int age;public Student(String name, int age) {this.name = name;this.age = age;}public String getName() {return name;}public int getAge() {return age;}@Overridepublic String toString() {return "Student{" +"name='" + name + '\'' +", age=" + age +'}';}@Overridepublic int compareTo(Student o) {// 按照年龄排序int result = this.age - o.age;// 如果年龄相同，按姓名的字母顺序排序return result == 0 ? this.name.compareTo(o.getName()) : result;}
}
测试类：
import java.util.TreeSet;public class MyTreeSet2 {public static void main(String[] args) {// 创建集合对象TreeSet<Student> ts = new TreeSet<>();// 添加学生对象ts.add(new Student("wangwu", 25));ts.add(new Student("lisi", 24));ts.add(new Student("zhangsan", 23));ts.add(new Student("zhaoliu", 26));// 遍历集合for (Student student : ts) {System.out.println(student);}}
}
在这个示例中，我们使用 compareTo 方法来定义排序规则：首先按年龄排序，若年龄相同，则按姓名字母顺序排序。这样，TreeSet 会自动对 Student 对象进行排序。
比较器排序（Comparator）的使用
有时，我们希望能够动态指定排序规则，而不是在类中实现 Comparable 接口。这时可以使用 Comparator 接口，利用 TreeSet 的带参构造函数传入排序规则。
案例需求
存储 Teacher 对象，并要求按年龄升序排序，若年龄相同，则按姓名字母顺序排序。
实现步骤
- 使用
TreeSet的带参构造方法，传递Comparator对象来指定排序规则。 - 重写
compare方法，定义排序规则。
代码实现
老师类：
public class Teacher {private String name;private int age;public Teacher(String name, int age) {this.name = name;this.age = age;}public String getName() {return name;}public int getAge() {return age;}@Overridepublic String toString() {return "Teacher{" +"name='" + name + '\'' +", age=" + age +'}';}
}
测试类：
import java.util.Comparator;
import java.util.TreeSet;public class MyTreeSet4 {public static void main(String[] args) {// 创建集合对象，使用比较器排序TreeSet<Teacher> ts = new TreeSet<>(new Comparator<Teacher>() {@Overridepublic int compare(Teacher o1, Teacher o2) {// 按照年龄排序int result = o1.getAge() - o2.getAge();// 如果年龄相同，按姓名字母顺序排序return result == 0 ? o1.getName().compareTo(o2.getName()) : result;}});// 添加老师对象ts.add(new Teacher("zhangsan", 23));ts.add(new Teacher("lisi", 22));ts.add(new Teacher("wangwu", 24));ts.add(new Teacher("zhaoliu", 24));// 遍历集合for (Teacher teacher : ts) {System.out.println(teacher);}}
}
在这个示例中，我们通过 TreeSet 的构造函数传递 Comparator 对象，从而定义排序规则。这样，即使不修改 Teacher 类，我们也能灵活地对其进行排序。
两种比较方式总结
-
自然排序 (
Comparable)：- 让自定义类实现
Comparable接口，并重写compareTo方法来定义排序规则。 - 适用于对象的类本身具备稳定的排序逻辑。
- 让自定义类实现
-
比较器排序 (
Comparator)：- 在创建
TreeSet对象时传递Comparator的实现类对象来定义排序规则。 - 适用于需要灵活更改排序逻辑，或者类本身不方便实现
Comparable的情况。
- 在创建
返回值规则
- 返回值为负数：表示当前存入的元素较小，存储在左子树。
- 返回值为0：表示当前存入的元素与已有元素重复，不存储。
- 返回值为正数：表示当前存入的元素较大，存储在右子树。
总结
compareTo` 方法来定义排序规则。
- 适用于对象的类本身具备稳定的排序逻辑。
- 比较器排序 (
Comparator)：- 在创建
TreeSet对象时传递Comparator的实现类对象来定义排序规则。 - 适用于需要灵活更改排序逻辑，或者类本身不方便实现
Comparable的情况。
- 在创建
返回值规则
- 返回值为负数：表示当前存入的元素较小，存储在左子树。
- 返回值为0：表示当前存入的元素与已有元素重复，不存储。
- 返回值为正数：表示当前存入的元素较大，存储在右子树。
总结
TreeSet 是 Java 中非常有用的集合类，可以用来对元素进行自动排序和去重。它的两种排序方式（自然排序和比较器排序）使得 TreeSet 在处理复杂对象的排序时非常灵活。理解并灵活运用 Comparable 和 Comparator，可以帮助我们更好地控制集合中的元素顺序和行为。