【Java】集合类 - Set - TreeSet

Posted by 西维蜀黍 on 2019-03-15, Last Modified on 2023-02-28

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