TreeSet
从名字上可以看出,此集合的实现和树结构有关。
与HashSet集合类似,TreeSet基于TreeMap来实现的,其底层结构为红黑树(特殊的二叉查找树,即在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black)。
与HashSet不同的是,TreeSet具有排序功能,分为自然排序(123456)和自定义排序两类,默认是自然排序;在程序中,我们可以按照任意顺序将元素插入到集合中,等到遍历时TreeSet会按照一定顺序输出–倒序或者升序。
特点
- 对插入的元素进行排序,是一个有序的集合(这是主要与HashSet的区别);
- 底层使用红黑树结构,而不是哈希表结构;
- 允许插入Null值;
- 不允许插入重复元素;
- 线程不安全。
TreeSet基本操作
public class TreeSetTest {
public static void main(String[] agrs){
TreeSet<String> treeSet = new TreeSet<String>();
System.out.println("TreeSet初始化容量大小:"+treeSet.size());
//元素添加:
treeSet.add("my");
treeSet.add("name");
treeSet.add("jiaboyan");
treeSet.add("hello");
treeSet.add("world");
treeSet.add("1");
treeSet.add("2");
treeSet.add("3");
System.out.println("TreeSet容量大小:" + treeSet.size());
System.out.println("TreeSet元素顺序为:" + treeSet.toString());
//增加for循环遍历:
for(String str:treeSet){
System.out.println("遍历元素:"+str);
}
//迭代器遍历:升序
Iterator<String> iteratorAesc = treeSet.iterator();
while(iteratorAesc.hasNext()){
String str = iteratorAesc.next();
System.out.println("遍历元素升序:"+str);
}
//迭代器遍历:降序
Iterator<String> iteratorDesc = treeSet.descendingIterator();
while(iteratorDesc.hasNext()){
String str = iteratorDesc.next();
System.out.println("遍历元素降序:"+str);
}
//元素获取:实现NavigableSet接口
String firstEle = treeSet.first();//获取TreeSet头节点:
System.out.println("TreeSet头节点为:" + firstEle);
// 获取指定元素之前的所有元素集合:(不包含指定元素)
SortedSet<String> headSet = treeSet.headSet("jiaboyan");
System.out.println("jiaboyan节点之前的元素为:"+headSet.toString());
//获取给定元素之间的集合:(包含头,不包含尾)
SortedSet subSet = treeSet.subSet("1","world");
System.out.println("1--jiaboan之间节点元素为:"+subSet.toString());
//集合判断:
boolean isEmpty = treeSet.isEmpty();
System.out.println("TreeSet是否为空:"+isEmpty);
boolean isContain = treeSet.contains("who");
System.out.println("TreeSet是否包含who元素:"+isContain);
//元素删除:
boolean jiaboyanRemove = treeSet.remove("jiaboyan");
System.out.println("jiaboyan元素是否被删除"+jiaboyanRemove);
//集合中不存在的元素,删除返回false
boolean whoRemove = treeSet.remove("who");
System.out.println("who元素是否被删除"+whoRemove);
//删除并返回第一个元素:如果set集合不存在元素,则返回null
String pollFirst = treeSet.pollFirst();
System.out.println("删除的第一个元素:"+pollFirst);
//删除并返回最后一个元素:如果set集合不存在元素,则返回null
String pollLast = treeSet.pollLast();
System.out.println("删除的最后一个元素:"+pollLast);
treeSet.clear();//清空集合:
}
}
TreeSet元素排序
在前面,我们提到了TreeSet是一个有序集合,可以对集合元素排序,其中分为自然排序和自定义排序,那么这两种方式如何实现呢?
情况1
首先,我们通过JDK提供的对象来展示,我们使用String、Integer:
public class TreeSetTest {
public static void main(String[] agrs){
naturalSort();
}
//自然排序顺序:升序
public static void naturalSort(){
TreeSet<String> treeSetString = new TreeSet<String>();
treeSetString.add("a");
treeSetString.add("z");
treeSetString.add("d");
treeSetString.add("b");
System.out.println("字母顺序:" + treeSetString.toString());
TreeSet<Integer> treeSetInteger = new TreeSet<Integer>();
treeSetInteger.add(1);
treeSetInteger.add(24);
treeSetInteger.add(23);
treeSetInteger.add(6);
System.out.println(treeSetInteger.toString());
System.out.println("数字顺序:" + treeSetString.toString());
}
}
结果
字母顺序:[a, b, d, z]
数字顺序:[1, 6, 23, 24]
情况2 - 自定义对象
接下来,我们自定义对象,看能否实现:
public class App{
private String name;
private Integer age;
public App(){}
public App(String name,Integer age){
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getAge() {
return age;
}
public void setAge(Integer age) {
this.age = age;
}
public static void main(String[] args ){
System.out.println( "Hello World!" );
}
}
public class TreeSetTest {
public static void main(String[] agrs){
customSort();
}
//自定义排序顺序:升序
public static void customSort(){
TreeSet<App> treeSet = new TreeSet<App>();
//排序对象:
App app1 = new App("hello",10);
App app2 = new App("world",20);
App app3 = new App("my",15);
App app4 = new App("name",25);
//添加到集合:
treeSet.add(app1);
treeSet.add(app2);
treeSet.add(app3);
treeSet.add(app4);
System.out.println("TreeSet集合顺序为:"+treeSet);
}
}
结果
抛出异常:提示App不能转换为Comparable对象:
Exception in thread "main" java.lang.ClassCastException: com.jiaboyan.collection.App cannot be cast to java.lang.Comparable
分析
为什么会报错呢?
compare(key, key); // type (and possibly null) check
final int compare(Object k1, Object k2) {
return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
: comparator.compare((K)k1, (K)k2);
}
通过查看源码发现,在TreeSet调用add方法时,会调用到底层TreeMap的put方法,在put方法中会调用到compare(key, key)方法,进行key大小的比较。
在比较的时候,会将传入的key进行类型强转,所以当我们自定义的App类进行比较的时候,自然就会抛出异常,因为App类并没有实现Comparable接口。
将App实现Comparable接口,再做比较:
public class App implements Comparable<App>{
private String name;
private Integer age;
public App(){}
public App(String name,Integer age){
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getAge() {
return age;
}
public void setAge(Integer age) {
this.age = age;
}
//自定义比较:先比较name的长度,在比较age的大小;
public int compareTo(App app) {
//比较name的长度:
int num = this.name.length() - app.name.length();
//如果name长度一样,则比较年龄的大小:
return num == 0 ? this.age - app.age : num;
}
@Override
public String toString() {
return "App{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}
结果
TreeSet集合顺序为:[App{name='my', age=15}, App{name='name', age=25}, App{name='hello', age=10}, App{name='world', age=20}]
情况3 - 实现Comparetor<T>接口
此外,还有另一种方式,那就是实现Comparetor接口,并重写compare方法;
//自定义App类的比较器:
public class AppComparator implements Comparator<App> {
//比较方法:先比较年龄,年龄若相同在比较名字长度;
public int compare(App app1, App app2) {
int num = app1.getAge() - app2.getAge();
return num == 0 ? app1.getName().length() - app2.getName().length() : num;
}
}
此时,App不用在实现Comparerable接口了,单纯的定义一个类即可;
public class App{
private String name;
private Integer age;
public App(){}
public App(String name,Integer age){
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getAge() {
return age;
}
public void setAge(Integer age) {
this.age = age;
}
public static void main(String[] args ){
System.out.println( "Hello World!" );
}
}
public class TreeSetTest {
public static void main(String[] agrs){
customSort();
}
//自定义比较器:升序
public static void customComparatorSort(){
TreeSet<App> treeSet = new TreeSet<App>(new AppComparator());
//排序对象:
App app1 = new App("hello",10);
App app2 = new App("world",20);
App app3 = new App("my",15);
App app4 = new App("name",25);
//添加到集合:
treeSet.add(app1);
treeSet.add(app2);
treeSet.add(app3);
treeSet.add(app4);
System.out.println("TreeSet集合顺序为:"+treeSet);
}
}
结果
TreeSet集合顺序为:[App{name='hello', age=10}, App{name='my', age=15}, App{name='world', age=20}, App{name='name', age=25}]
Reference
- Java集合–Set(基础) - https://www.jianshu.com/p/b48c47a42916