TreeSet 集合
- 1. 概述
- 2. 方法
- 3. 遍历方式
- 4. 两种排序方式
- 4.1 默认排序规则/自然排序
- 4.1.1 概述
- 4.1.2 compareTo()方法
- 4.1.3 代码示例1
- 4.1.4 代码示例2
- 4.2 比较器排序
- 4.2.1 概述
- 4.2.2 compare()方法
- 4.2.3 代码示例1
- 4.2.4 代码示例2
- 4.3 排序方式的对比
- 5. 注意事项
文章中的部分照片来源于哔站
黑马程序员阿伟老师
处,仅用学习,无商用,侵权联系删除!
其他集合类
祖父类 Collection
父类 Set
集合类的遍历方式
具体信息请查看 API 帮助文档
1. 概述
TreeSet是Java中的一个有序集合,它实现了Set接口。它使用红黑树数据结构来存储元素,并且保证元素按照升序排列。每个元素都必须是可比较的,或者在创建TreeSet时提供一个定制的Comparator来比较元素。
TreeSet集合:(底层是红黑树)
-
不重复,无索引,可排序
-
可排序:按照元素的默认规则(由小到大)进行排序
-
TreeSet集合底层是基于红黑树的数据结构实现排序的,增删改查性能都较好
TreeSet的特点:
-
有序性:TreeSet中的元素按照升序排列,默认使用元素自然顺序进行比较,或者可以通过提供一个Comparator来指定定制的排序规则。
-
无重复性:TreeSet不允许存储重复的元素。如果尝试添加重复的元素,添加操作会被忽略。
-
高效性:由于采用了红黑树数据结构,TreeSet支持快速的插入、删除和查找操作,时间复杂度为O(logN)。
2. 方法
TreeSet
集合是Set
集合的子类,是Collection
集合的孙子类,因此Set
集合和Collection
集合的方法都可以使用
Collection集合
Set集合
方法名 | 说明 |
---|---|
boolean add(E e) | 添加元素 |
boolean remove(Object o) | 从集合中移除指定的元素 |
boolean removeIf(Object o) | 根据条件进行移除 |
void clear() | 清空集合中的元素 |
boolean contains(Object o) | 判断集合中是否存在指定的元素 |
boolean isEmpty() | 判断集合是否为空 |
int size() | 集合的长度,也就是集合中元素的个数 |
3. 遍历方式
【注意】TreeSet集合没有索引,因此只能用迭代器遍历、增强 for ,Lambda表达式遍历。
与共有的 集合遍历方式 一样
- 代码示例:
package text.text02;
import java.util.Iterator;
import java.util.TreeSet;
/*
TreeSet集合:(底层是红黑树)
1.不重复,无索引,可排序
2.可排序:按照元素的默认规则(由小到大)进行排序
3.TreeSet集合底层是基于红黑树的数据结构实现排序的,增删改查性能都较好
需求:存储整数并进行排序
*/
public class text40 {
public static void main(String[] args) {
//创建集合并添加数据
TreeSet<Integer> ts = new TreeSet<>();
ts.add(4);
ts.add(7);
ts.add(6);
ts.add(3);
ts.add(1);
ts.add(5);
ts.add(2);
ts.add(8);
ts.add(9);
//打印集合
System.out.println(ts); //[1, 2, 3, 4, 5, 6, 7, 8, 9]
//遍历集合
Iterator<Integer> it = ts.iterator();
while (it.hasNext()) {
Integer i = it.next();
System.out.print(i + " "); //1 2 3 4 5 6 7 8 9
}
}
}
- 输出结果
4. 两种排序方式
-
方法一:默认排序规则/自然排序
JavaBean类实现Comparable接口指定比较规则(重写里面的抽象方法,再比较)
-
方法二:比较器排序
创建TreeSet对象时候,自定义比较器Comparator对象,指定比较规则
4.1 默认排序规则/自然排序
4.1.1 概述
默认排序规则,也称为自然排序,是指针对某种数据类型的元素,按照它们的自身特性进行排序的规则。在Java中,如果一个类实现了Comparable接口,就意味着它具有自然顺序,并且可以使用默认排序规则。
在使用默认排序规则进行排序时,会根据元素的特定属性或者重写的compareTo()方法来进行比较。默认情况下,元素按照升序排列,也就是具有较小值的元素在集合中排在前面。
例如,对于整数类型,自然排序规则就是按照数值大小进行排序。而对于字符串类型,自然排序规则是按照字典顺序进行排序。
以下是一些实现了Comparable接口的示例类及其默认排序规则:
- Integer类:按数值大小进行升序排序。
- String类:按字典顺序进行排序。
- LocalDate类:按日期进行升序排序。
- 自定义类:可以通过实现Comparable接口,并重写compareTo()方法来定义自己的默认排序规则。
注意,如果你想使用不同于默认排序规则的排序方式,可以通过提供一个定制的Comparator来实现定制排序。
默认排序示意图:
4.1.2 compareTo()方法
compareTo()方法是Comparable接口中定义的方法,用于比较当前对象与另一个对象的顺序。它的方法签名如下:
int compareTo(T obj)
其中,T表示要比较的对象的类型。compareTo()方法接受一个参数obj,表示要与当前对象进行比较的另一个对象,返回一个整数值表示它们的顺序关系。
this: 要添加的元素(当前对象)
obj:红黑树中已经存在的数据
compareTo()方法返回的整数值有以下三种情况:
-
当compare()方法返回一个负数时,表示第一个元素应排在前面;
-
当返回0时,表示两个元素相等;
-
当返回一个正数时,表示第一个元素应排在后面。
具体返回的值大小并不重要,只有它们的正负号和零的关系才有意义。返回的值为负,当前对象就应该排在obj之前;返回的值为正,当前对象就应该排在obj之后。
4.1.3 代码示例1
- 代码示例:
需求:创建TreeSet集合,并添加3个学生对象
学生对象属性:姓名、年龄
要求:按照学生的年龄进行排序,同年龄按照姓名字母排列(暂不考虑中文),同姓名、同年龄认为是同一个人
package text.text02;
import java.util.Iterator;
import java.util.TreeSet;
/* 方法一:默认排序规则/自然排序
方法一:默认排序规则/自然排序
JavaBean类实现Comparable接口指定比较规则(重写里面的抽象方法,再比较)
方法二:比较器排序
创建TreeSet对象时候,传递比较器Comparator指定规则
TreeSet对象排序练习题:
需求:创建TreeSet集合,并添加3个学生对象
学生对象属性:姓名、年龄
要求:按照学生的年龄进行排序,同年龄按照姓名字母排列(暂不考虑中文),同姓名、同年龄认为是同一个人
*/
public class text41 {
public static void main(String[] args) {
//创建学生对象
Student4 student1 = new Student4("zhangsan", 13);
Student4 student2 = new Student4("llisi", 25);
Student4 student3 = new Student4("wangwu", 12);
Student4 student4 = new Student4("zhaoliu", 20);
Student4 student5 = new Student4("liuqi", 11);
//创建集合,并添加元素
TreeSet<Student4> ts = new TreeSet<>();
ts.add(student1);
ts.add(student2);
ts.add(student3);
ts.add(student4);
ts.add(student5);
//遍历集合
Iterator<Student4> it = ts.iterator();
while (it.hasNext()) {
Student4 student = it.next();
System.out.println(student.getName() + "," + student.getAge());
/*
liuqi,11
wangwu,12
zhangsan,13
zhaoliu,20
llisi,25
*/
}
}
}
//重写CompareTo的实现了Comparable接口的学生类
class Student4 implements Comparable<Student4> {
private String name;
private int age;
public Student4() {
}
public Student4(String name, int age) {
this.name = name;
this.age = age;
}
/**
* 获取
*
* @return name
*/
public String getName() {
return name;
}
/**
* 设置
*
* @param name
*/
public void setName(String name) {
this.name = name;
}
/**
* 获取
*
* @return age
*/
public int getAge() {
return age;
}
/**
* 设置
*
* @param age
*/
public void setAge(int age) {
this.age = age;
}
public String toString() {
return "Student4{name = " + name + ", age = " + age + "}";
}
//重写抽象方法CompareTo方法
@Override
//this:表示当前要添加的元素
//o:表示已经在红黑树中的元素
//返回值:
//负数:表示当前要添加的数据是小的,存左边
//正数:表示当前要添加的数据是大的,存右边
//0:表示当前要添加的元素已经存在,舍弃
public int compareTo(Student4 o) {
System.out.println("---------------CompareTo方法-----------");
System.out.println("this:" + this);
System.out.println("o:" + o);
System.out.println();
//指定排序的规则
//只看年龄:按照年龄的升序进行排列
return this.getAge() - o.getAge();
}
}
- 输出结果
4.1.4 代码示例2
- 代码示例:
需求:创建5个学生对象
属性:姓名、年龄,语文成绩。数学成绩、英语成绩
要求:按照总分从高到低输出到控制台
如果总分一样,按照语文成绩排
如果语文一样,按照数学成绩排
如果数学一样,按照英语成绩排
如果英语一样,按照年龄排
如果都一样,认为是同一个学生,不存
package text.text02;
/*
TreeSet对象排序练习题:
需求:创建5个学生对象
属性:姓名、年龄,语文成绩。数学成绩、英语成绩
要求:按照总分从高到低输出到控制台
如果总分一样,按照语文成绩排
如果语文一样,按照数学成绩排
如果数学一样,按照英语成绩排
如果英语一样,按照年龄排
如果都一样,认为是同一个学生,不存
*/
//方法一:默认排序规则/自然排序
// JavaBean类实现Comparable接口指定比较规则(重写里面的抽象方法,再比较)
import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;
public class text43 {
public static void main(String[] args) {
//创建5个学生对象
text.text02.Student6 student1 = new text.text02.Student6("张三", 15, 99, 98, 90);
text.text02.Student6 student2 = new text.text02.Student6("李四", 14, 79, 56, 36);
text.text02.Student6 student3 = new text.text02.Student6("王五", 16, 95, 96, 85);
text.text02.Student6 student4 = new text.text02.Student6("赵六", 19, 93, 68, 83);
text.text02.Student6 student5 = new text.text02.Student6("刘备", 12, 75, 68, 73);
//创建集合
TreeSet<Student6> ts = new TreeSet<>();
//添加学生对象
ts.add(student1);
ts.add(student2);
ts.add(student3);
ts.add(student4);
ts.add(student5);
//遍历输出集合
System.out.println("方法一:默认排序规则/自然排序:");
Iterator<Student6> it = ts.iterator();
while (it.hasNext()) {
Student6 s = it.next();
int num = s.getEnglish() + s.getMath() + s.getChinese();
System.out.println(s.getName() + "," + s.getAge() + "," + s.getChinese() + "," + s.getMath() + "," + s.getEnglish() + "," + num);
}
/*
张三,15,99,98,90,287
王五,16,95,96,85,276
赵六,19,93,68,83,244
刘备,12,75,68,73,216
李四,14,79,56,36,171
*/
}
}
class Student6 implements Comparable<Student6> {
private String name;
private int age;
private int Chinese;
private int Math;
private int English;
public Student6() {
}
public Student6(String name, int age, int Chinese, int Math, int English) {
this.name = name;
this.age = age;
this.Chinese = Chinese;
this.Math = Math;
this.English = English;
}
/**
* 获取
*
* @return name
*/
public String getName() {
return name;
}
/**
* 设置
*
* @param name
*/
public void setName(String name) {
this.name = name;
}
/**
* 获取
*
* @return age
*/
public int getAge() {
return age;
}
/**
* 设置
*
* @param age
*/
public void setAge(int age) {
this.age = age;
}
/**
* 获取
*
* @return Chinese
*/
public int getChinese() {
return Chinese;
}
/**
* 设置
*
* @param Chinese
*/
public void setChinese(int Chinese) {
this.Chinese = Chinese;
}
/**
* 获取
*
* @return Math
*/
public int getMath() {
return Math;
}
/**
* 设置
*
* @param Math
*/
public void setMath(int Math) {
this.Math = Math;
}
/**
* 获取
*
* @return English
*/
public int getEnglish() {
return English;
}
/**
* 设置
*
* @param English
*/
public void setEnglish(int English) {
this.English = English;
}
public String toString() {
return "Student6{name = " + name + ", age = " + age + ", Chinese = " + Chinese + ", Math = " + Math + ", English = " + English + "}";
}
@Override
//this:要添加的数据
//o:红黑树中已经存在的数据
public int compareTo(Student6 o) {
//定义变量记录红黑树中已经存入的数据的成绩总和
int sum = o.getChinese() + o.getMath() + o.getEnglish();
//定义变量记录要添加的数据的成绩总和
int sum1 = this.getChinese() + this.getMath() + this.getEnglish();
//按照总分从高到低输出到控制台
int i = sum - sum1;
//如果总分一样,按照语文成绩排
i = i == 0 ? o.getChinese() - this.getChinese() : i;
//如果语文一样,按照数学成绩排
i = i == 0 ? o.getMath() - this.getMath() : i;
//如果数学一样,按照英语成绩排
i = i == 0 ? o.getEnglish() - this.getEnglish() : i;
//如果英语一样,按照年龄排
i = i == 0 ? o.getAge() - this.getAge() : i;
//如果年龄一样,按照姓名首字母排
i = i == 0 ? o.getName().compareTo(this.getName()) : i;
//返回值:
//负数:表示当前要添加的数据是小的,存左边
//正数:表示当前要添加的数据是大的,存右边
//0:表示当前要添加的元素已经存在,舍弃
return i;
}
}
- 输出结果
4.2 比较器排序
4.2.1 概述
比较器排序是一种在不修改元素的类定义或实现Comparable接口的情况下,通过提供一个独立的比较器来排序元素的方法。
在Java中,比较器(Comparator)是一个可以自定义排序规则的对象,实现了Comparator接口。通过使用比较器,可以按照自己定义的排序方式对元素进行排序,而不依赖于元素自身的特性或默认的自然排序规则。
使用比较器进行排序的过程如下:
-
创建一个实现了Comparator接口的比较器类,其中包含compare()方法的实现。此方法定义了排序规则。
-
使用比较器对象创建一个集合(如TreeSet、PriorityQueue等)或者使用比较器作为参数调用排序方法(如Arrays.sort())。
-
比较器会根据自定义的排序规则对集合中的元素进行排序。
4.2.2 compare()方法
比较器排序常用的方法是compare()方法,该方法接受两个参数,用于比较两个元素的顺序。
compare()方法是Comparator接口中定义的方法,用于比较两个对象的顺序。它的方法签名如下:
int compare(T obj1, T obj2)
其中,T表示要比较的对象的类型。
compare()
方法接受两个参数obj1
和obj2
,分别表示要比较的两个对象,返回一个整数值表示它们的顺序关系。
obj1:要添加的元素
obj2:红黑树中已经存在的数据
compare()方法返回的整数值有以下三种情况:
-
当compare()方法返回一个负数时,表示第一个元素应排在前面;
-
当返回0时,表示两个元素相等;
-
当返回一个正数时,表示第一个元素应排在后面。
具体返回的值大小并不重要,只有它们的正负号和零的关系才有意义。返回的值为负,obj1就越应该排在obj2之前;返回的值为正,obj1就越应该排在obj2之后。
4.2.3 代码示例1
- 代码示例1:
需求:请自行选择比较器排序和自然排序两种方式;
要求:存入是个字符串: “c”,“ab”,“df”,“qwer”,按照长度排序,如果一样长则按照首字母进行排序
package text.text02;
import java.util.Comparator;
import java.util.TreeSet;
/* 方法二:比较器排序
方法一:默认排序规则/自然排序
JavaBean类实现Comparable接口指定比较规则(重写里面的抽象方法,再比较)
方法二:比较器排序
创建TreeSet对象时候,传递比较器Comparator指定规则
TreeSet对象排序练习题:
需求:请自行选择比较器排序和自然排序两种方式;
要求:存入是个字符串: "c","ab","df","qwer",按照长度排序,如果一样长则按照首字母进行排序
*/
public class text42 {
public static void main(String[] args) {
//创建未排序的集合对象
TreeSet<String> ts1 = new TreeSet<>();
//添加元素
ts1.add("c");
ts1.add("ab");
ts1.add("df");
ts1.add("qwer");
//输出未排序的集合
System.out.println("输出未排序的集合:" + ts1); //输出未排序得到集合:[ab, c, df, qwer]
// 创建排序的集合对象
// 创建TreeSet对象时候,传递比较器Comparator指定规则
//o1:表示当前要添加的元素
//o2:表示已经在红黑树存在的元素
//返回值:
//负数:表示当前要添加的数据是小的,存左边
//正数:表示当前要添加的数据是大的,存右边
//0:表示当前要添加的元素已经存在,舍弃
TreeSet<String> ts2 = new TreeSet<>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
//按照长度排序
int i = o1.length() - o2.length();
//长度一样则按照首字母进行排序
i = i == 0 ? o1.compareTo(o2) : i;
return i;
}
});
//添加元素
ts2.add("c");
ts2.add("ab");
ts2.add("df");
ts2.add("qwer");
//输出排序的集合
System.out.println("输出排序的集合:" + ts2); //输出排序的集合:[c, ab, df, qwer]
}
}
- 输出结果
4.2.4 代码示例2
- 代码示例2:
求:创建5个学生对象
属性:姓名、年龄,语文成绩。数学成绩、英语成绩
要求:按照总分从高到低输出到控制台
如果总分一样,按照语文成绩排
如果语文一样,按照数学成绩排
如果数学一样,按照英语成绩排
如果英语一样,按照年龄排
如果都一样,认为是同一个学生,不存
package text.text02;
import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;
/*
TreeSet对象排序练习题:
需求:创建5个学生对象
属性:姓名、年龄,语文成绩。数学成绩、英语成绩
要求:按照总分从高到低输出到控制台
如果总分一样,按照语文成绩排
如果语文一样,按照数学成绩排
如果数学一样,按照英语成绩排
如果英语一样,按照年龄排
如果都一样,认为是同一个学生,不存
*/
//方法二:比较器排序
// 创建TreeSet对象时候,传递比较器Comparator指定规则
public class text44 {
public static void main(String[] args) {
//创建5个学生对象
Student5 student1 = new Student5("张三", 15, 99, 98, 90);
Student5 student2 = new Student5("李四", 14, 79, 56, 36);
Student5 student3 = new Student5("王五", 16, 95, 96, 85);
Student5 student4 = new Student5("赵六", 19, 93, 68, 83);
Student5 student5 = new Student5("刘备", 12, 75, 68, 73);
//创建集合
TreeSet<Student5> ts = new TreeSet<>(new Comparator<Student5>() {
@Override
//o2:红黑树中已经存在的数据
//o1:要添加的数据
public int compare(Student5 o1, Student5 o2) {
//定义变量记录红黑树中已经存入的数据的成绩总和
int sum = o2.getChinese() + o2.getMath() + o2.getEnglish();
//定义变量记录要添加的数据的成绩总和
int sum1 = o1.getChinese() + o1.getMath() + o1.getEnglish();
//按照总分从高到低输出到控制台
int i = sum - sum1;
//如果总分一样,按照语文成绩排
i = i == 0 ? o2.getChinese() - o1.getChinese() : i;
//如果语文一样,按照数学成绩排
i = i == 0 ? o2.getMath() - o1.getMath() : i;
//如果数学一样,按照英语成绩排
i = i == 0 ? o2.getEnglish() - o1.getEnglish() : i;
//如果英语一样,按照年龄排
i = i == 0 ? o2.getAge() - o1.getAge() : i;
//如果年龄一样,按照姓名首字母排
i = i == 0 ? o2.getName().compareTo(o1.getName()) : i;
//返回值:
//负数:表示当前要添加的数据是小的,存左边
//正数:表示当前要添加的数据是大的,存右边
//0:表示当前要添加的元素已经存在,舍弃
return i;
}
});
//添加学生对象
ts.add(student1);
ts.add(student2);
ts.add(student3);
ts.add(student4);
ts.add(student5);
//遍历输出集合
System.out.println("方法二:比较器排序:");
Iterator<Student5> it = ts.iterator();
while (it.hasNext()) {
Student5 s = it.next();
int num = s.getEnglish() + s.getMath() + s.getChinese();
System.out.println(s.getName() + "," + s.getAge() + "," + s.getChinese() + "," + s.getMath() + "," + s.getEnglish() + "," + num);
}
/*
张三,15,99,98,90,287
王五,16,95,96,85,276
赵六,19,93,68,83,244
刘备,12,75,68,73,216
李四,14,79,56,36,171
*/
}
}
class Student5 {
private String name;
private int age;
private int Chinese;
private int Math;
private int English;
public Student5() {
}
public Student5(String name, int age, int Chinese, int Math, int English) {
this.name = name;
this.age = age;
this.Chinese = Chinese;
this.Math = Math;
this.English = English;
}
/**
* 获取
*
* @return name
*/
public String getName() {
return name;
}
/**
* 设置
*
* @param name
*/
public void setName(String name) {
this.name = name;
}
/**
* 获取
*
* @return age
*/
public int getAge() {
return age;
}
/**
* 设置
*
* @param age
*/
public void setAge(int age) {
this.age = age;
}
/**
* 获取
*
* @return Chinese
*/
public int getChinese() {
return Chinese;
}
/**
* 设置
*
* @param Chinese
*/
public void setChinese(int Chinese) {
this.Chinese = Chinese;
}
/**
* 获取
*
* @return Math
*/
public int getMath() {
return Math;
}
/**
* 设置
*
* @param Math
*/
public void setMath(int Math) {
this.Math = Math;
}
/**
* 获取
*
* @return English
*/
public int getEnglish() {
return English;
}
/**
* 设置
*
* @param English
*/
public void setEnglish(int English) {
this.English = English;
}
public String toString() {
return "Student5{name = " + name + ", age = " + age + ", Chinese = " + Chinese + ", Math = " + Math + ", English = " + English + "}";
}
}
- 输出结果
4.3 排序方式的对比
- 定义方式:
-
自然排序:通过实现Comparable接口,在类的定义中定义排序规则。
-
比较器排序:通过实现Comparator接口,在类的外部提供一个独立的比较器对象定义排序规则。
- 依赖性:
-
自然排序:依赖于类的定义,对象必须实现Comparable接口来定义默认的自然排序规则。
-
比较器排序:不依赖于类的定义,可以根据不同的排序需求提供不同的比较器对象。
- 修改类定义:
-
自然排序:需要修改类的定义,将实现Comparable接口,并重写compareTo()方法来定义排序规则。
-
比较器排序:无需修改类的定义,可以提供一个独立的比较器对象来定义排序规则,对类的定义没有侵入性。
- 灵活性:
-
自然排序:对于具体的类,只能有一种自然排序规则,不易灵活更改。
-
比较器排序:可以根据具体的使用需求,提供不同的比较器对象,灵活定义不同的排序规则。
- 使用场景:
-
自然排序:适用于类的默认排序需求,可以直接使用已定义的自然排序规则进行排序。
-
比较器排序:适用于自定义的排序需求,或者需要对无法修改类定义的类进行排序。
5. 注意事项
-
元素的可比较性:TreeSet是基于红黑树实现的有序集合,要保证集合中的元素是可比较的,即元素类必须实现Comparable接口或传入一个比较器(Comparator)对象来比较元素的顺序。
-
元素的唯一性:TreeSet不允许重复的元素存在。在插入新元素时,TreeSet会根据元素的比较规则判断是否已经存在相同的元素,如果存在,则新元素不会被插入。
-
性能:由于TreeSet是基于红黑树实现的,插入、删除和查找操作的时间复杂度都是O(logN),其中N是集合中元素的个数。这使得TreeSet在大多数情况下具有较好的性能。但是,与HashSet相比,在非排序需求的情况下,HashSet具有更好的性能。
-
无法使用null元素:TreeSet不允许使用null元素。由于TreeSet需要比较元素,并将其放入正确的位置,如果集合中出现null元素,则无法确定其正确的位置,因此会抛出NullPointerException。
-
自然顺序和比较器:TreeSet可以使用元素类的自然顺序(如果元素类实现了Comparable接口),也可以通过传入一个比较器对象来定义元素的顺序。在创建TreeSet时,可以选择传入一个Comparator对象来进行自定义的排序比较。