简述TreeSet排序机制

2019-12-11

字数统计: 1.4k字 | 阅读时长≈ 6分

TreeSet简介

此集合的实现和树结构有关。与HashSet集合类似，TreeSet也是基于Map来实现，具体实现TreeMap，其底层结构为红黑树（特殊的二叉查找树）；
与HashSet不同的是，TreeSet具有排序功能，分为自然排序(123456)和自定义排序两类，默认是自然排序；在程序中，我们可以按照任意顺序将元素插入到集合中，等到遍历时TreeSet会按照一定顺序输出（倒序/升序）；
它继承AbstractSet，实现NavigableSet, Cloneable, Serializable接口。
（1）与HashSet同理，TreeSet继承AbstractSet类，获得了Set集合基础实现操作；

（2）TreeSet实现NavigableSet接口，而NavigableSet又扩展了SortedSet接口。实现NavigableSet接口使得TreeSet具备了元素搜索功能；
（3）TreeSet实现Cloneable接口，可以被克隆；
（4）TreeSet实现了Serializable接口，可以被序列化；
具有如下特点：

对插入的元素进行排序，是一个有序的集合（主要与HashSet的区别）;
底层使用红黑树结构，而不是哈希表结构；
允许插入Null值；
不允许插入重复元素；
线程不安全；

TreeSet元素排序

TreeSet是一个有序集合，可以对集合元素排序，其中分为自然排序和自定义排序。
使用String、Intege类型：

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]

使用对象类型：

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.huangqiuping.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}]

此外，还有另一种方式，那就是实现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}]

关于compareTo()、compare()方法：
结果返回大于0时，方法前面的值大于方法中的值；
结果返回等于0时，方法前面的值等于方法中的值；
结果返回小于0时，方法前面的值小于方法中的值；

本文作者： 生活,生活?
本文链接： ayjcsgm.github.io/2019/12/11/简述TreeSet排序机制/
版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！