详解java中的TreeSet集合

TreeSet是实现Set接口的实现类。所以它存储的值是唯一的,同时也可以对存储的值进行排序,排序用的是二叉树原理。所以要理解这个类,必须先简单理解一下什么是二叉树。

  • 二叉树原理简述

假如有这么一个集合TreeSet<Integer>是[5,11,6,5,23,14]

用二叉树是怎么排序的呢?

二叉树遍历方法比较多,有兴趣自己百度看下吧。这里只需要知道元素是怎么插入到二叉树即可。小的存储在左边(负数),大的存储在右边(正数),相等不存储。

 

  • TreeSet的基本使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void main(String[] args) {
        TreeSet<Integer> ts = new TreeSet<>();
        ts.add(2);
        ts.add(1);
        ts.add(3);
        ts.add(2);
        ts.add(3);
        ts.add(1);
        ts.add(2);
        System.out.println(ts);
    }
 
// 输出结果:
[1,2,3]

可以知道,TreeSet集合不仅可以保证集合元素的唯一性,还可以排序。

如果TreeSet里面存储的是对象呢?会出现什么情况呢?

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
        TreeSet<Students> ts = new TreeSet<>();
        ts.add(new Students("张三",13));
        ts.add(new Students("李四",14));
        ts.add(new Students("王五",15));
        System.out.println(ts);
    }
 
// 输出结果:
Exception in thread "main" java.lang.ClassCastException: com.lei.Students cannot be cast to java.lang.Comparable

报错了,因为集合里面的是对象,对象不能转换为比较可比较对象。

如果想根据年龄排序,打印出各个对象(toString方法),应该怎么做呢?

在API里面搜索一下Comparable,发现是个接口,那么我们就可以让Students类实现Comparable接口方法,这样Students对象就成为了可比较对象了。

Students类实现Comparable接口方法:

1
2
3
4
5
6
7
8
9
10
11
public class Students implements Comparable<Students> {
    private String name;
    private int age;
 
    ......
 
    @Override
    public int compareTo(Students o) {
        return this.age-o.age;
    }
}

为什么是this.age-o.age?this.age代表调用时的对象的age,返回的如果是正数(比o.age大),就存储在右边。返回的是如果是负数(比o.age小),就存储在左边。如果等于0,就不存储。

这就出问题了,如果两个人不同名字,同样年龄,this.age - o.age = 0,不就存不进二叉树了吗?

验证一下:

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
        TreeSet<Students> ts = new TreeSet<>();
        ts.add(new Students("李四",14));
        ts.add(new Students("张三",13));
        ts.add(new Students("王五",15));
        ts.add(new Students("赵六",13));
        System.out.println(ts);
    }
 
// 输出结果只有张三、李四、王五

所以需要改进一下Students类的compareTo方法,保证同年龄,但是不同名字的学生也能存进二叉树。

1
2
3
4
5
6
@Override
    public int compareTo(Students o) {
        int num = this.age - o.age;
        // String类里面已经重写了compareTo方法
        // int    compareTo(String anotherString)  按字典顺序比较两个字符串
        return num == 0 ? this.name.compareTo(o.name) : num;

这样就可以把四个不同的对象存储进来,并且先按照年龄排序,年龄相同的再按照字符串排序。

 

除了这种方式可以实现排序以外,还有一种方式可以实现排序。

TreeSet有这么一个构造方法:

TreeSet(Comparator<? super E> comparator)      构造一个新的,空的树集,根据指定的比较器进行排序。

Comparator是什么呢?API文档看一下:

Interface Comparator<T>,是一个接口,里面有一个要实现的接口方法:

int    compare(T o1, T o2)   比较其两个参数的顺序。

例如,我们要对字符串的长度进行排序,长度相同的安装字符串排序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Test5 {
    public static void main(String[] args) {
        TreeSet<String> ts = new TreeSet<>(new SortedByLen());    // 父类引用指向子类对象 Comparator c = new SortedByLen();
        ts.add("aaaaaaaaa");
        ts.add("wc");
        ts.add("nba");
        ts.add("cba");
        ts.add("chichung");
        System.out.println(ts);
    }
}
 
class SortedByLen implements Comparator<String> {
 
    @Override
    public int compare(String o1, String o2) {
        int num = o1.length() - o2.length();
        return num == 0 ? o1.compareTo(o2) : num;
    }
}
 
//输出结果:
[wc, cba, nba, chichung, aaaaaaaaa]

需要注意的是重写compare方法的o1,o2。o1代表调用的对象,o2代表集合中的对象。

两种实现排序方式视情况而用。

(1)自然顺序(Comparable)

  • TreeSet类的add()方法中会把存入的对象提升为Comparable类型
  • 调用对象的compareTo()方法和集合中的对象比较
  • 根据compareTo()方法返回的结果进行存储

(2)比较器顺序(Comparator)

  • 创建TreeSet的时候可以指定一个Comparator
  • 如果传入了Comparator的子类对象,那么TreeSet就会按照比较器中的顺序排序
  • 调用的对象是compare方法的第一个参数,集合中的对象是compare方法的第二个参数

(3)两种方式的区别

  • TreeSet构造函数什么都不传,默认按照类中Comparable的顺序(没有就报错ClassCastException)
  • TreeSet如果传入Comparator,就优先按照Comparator

如果不想保证元素的唯一性,改一下compare方法就可以了,永远不要让它返回0。

 


作者:chichung

链接:https://www.cnblogs.com/chichung/p/10252495.html

发表评论