Java集合详解——TreeSet集合的介绍及其排序_treeset排序原理

一、TreeSet集合的自动排序

1、TreeSet集合使用红黑树数据结构实现元素的排序和存储，底层实际上是一个TreeMap集合

2、Tree Map集合底层实际上是一个二叉树。

3、放到TreeSet集合中的元素，等同于放到TreeMap集合中去了。

4、放到TreeSet集合中的元素：有序且唯一，即不可重复，有序是指可以按照元素的大小顺序自动排序。

5、TerrSet不允许插入null 元素，否则报空指针异常。

6、高效性能： 由于底层数据结构的特点，TreeSet 提供了高效的插入、删除和查找操作。它的时间复杂度通常是 O(log n)，其中 n 是集合的大小。

7、可导航性： TreeSet 提供了一系列方法，如 first()、last()、lower()、higher()、ceiling()、floor() 等，用于在集合中查找元素或获取与给定元素最接近的元素。

8、不可变性： TreeSet 是不可变的集合，一旦创建，它的内容不可修改。如果需要对集合进行修改，可以创建一个新的 TreeSet 并复制元素。

import java.util.*;
public class test03 {
    public static void main(String[] args) throws Exception {
        TreeSet<String> ts = new TreeSet<>();
        ts.add("a");
        ts.add("b");
        ts.add("zhangsan");
        ts.add("laoliu");
        ts.add("老六");
        ts.add("zhangss");
// 字符串默认重写了compare方法
        for (Object i:ts) {
            System.out.println(i);
        }
        System.out.println("--------------------------");
        TreeMap tm = new TreeMap();
        tm.put(1,"zhangsan");
        tm.put(2,"lisi");
        tm.put(2,"liss");
        tm.put(3,"lisi");
        Set<Map.Entry> set = tm.entrySet();
        for (Map.Entry i:set) {
            System.out.println(i);
        } 
    }
}

运行结果：  a
                    b
                    laoliu
                    zhangsan
                    zhangss
                    老六
                    --------------------------
                    1=zhangsan
                    2=liss
                    3=lisi

9、放到TreeSet或者TreeMap集合key部分中的元素要想做到排序，包括两种方式：

• 第一种：放在集合中的元素实现java.lang.Comparable接口。

• 第二种：在构造TreeSet或者TreeMap集合的时候给它传一个比较器对象。

  • 下面就分别介绍一下这两种方式的实现。

二、TreeSet集合自定义类型排序

TreeSet集合无法对自定义类型排序：出现这种情况的原因是没有实现java.lang.comParable接口

这里的排序规则可参考下图所示的自平衡二叉树的讲解原理：

 所以需要实现comParable接口，代码实现如下所示：

import java.util.*;
public class test03 {
    public static void main(String[] args){
        person p = new person(12);
        person p1 = new person(52);
        person p2 = new person(102);
        person p3 = new person(92);
        TreeSet ts = new TreeSet<>();
        ts.add(p);
        ts.add(p1);
        ts.add(p2);
        ts.add(p3);
        for (Object i:ts ) {
            System.out.println(i);
        }
 
    }
}
//放在Treeset集合中的元素需要实现comParable接口。
//并且实现comParaTo方法，equals可以不写。。
class person implements Comparable<person>{
    int age;
    public person(int age){
        this.age=age;
    }
//需要重写这个方法，编写比较的逻辑或规则，
    //k.comParaTo(t.key)
    //拿着参数k和集合中的每一个key进行比较，返回值可能是>0,<0,=0;
    //比较规则最终还是由程序员决定：例如按年龄升序或者降序。
    @Override
    public int compareTo(person c) {//c1.comParaTo(c2);
        //this是c1
        //c是c2
        //c1和c2比较的时候，就是this和c比较
       /* int age1 = this.age;
        int age2 = c.age;
        if (age1 ==age2){
            return 0;
        } else if (age1 >age2) {
            return 1;
        } else{
            return -1;
        }*/
        //也可以直接写成下面的这种形式
        //return this.age-c.age;//   =,<0,>0    升序
        return c.age-this.age;      //降序
    }
    public String toString(){
        return "person[age="+age+"]";
    }
}

运行结果：person[age=12]

                 person[age=52]

                 person[age=92]

                 person[age=102]

三、TreeSet集合中的元素可排序的第二种方式：使用比较器的方式。 

import java.util.*;
//排序的第二种方式：使用比较器的方式
public class test03 {
    public static void main(String[] args){
        person p = new person(12);
        person p1 = new person(52);
        person p2 = new person(102);
        person p3 = new person(92);
        //创建TreeSet集合的时候，一定要给构造方法传递一个比较器
        TreeSet<person> ts = new TreeSet<>(new PersonComparator());
        //这里也可以使用创建匿名内部类的方式：
        /*TreeSet<person> ts = new TreeSet<>(new Comparator<person>(){
            @Override
            public int compare(person o1, person o2) {
                return o1.age - o2.age;
            }
        });*/
        ts.add(p);
        ts.add(p1);
        ts.add(p2);
        ts.add(p3);
        for (Object i:ts ) {
            System.out.println(i);
        }
    }
}
//单独在这里写一个比较器
//比较器实现java.util.Comparator接口
class person{
    int age;
    public person(int age){
        this.age=age;
    }
    public String toString(){
        return "person[age="+age+"]";
    }
}
//比较器
class PersonComparator implements Comparator<person>{
    @Override
    public int compare(person o1, person o2) {
        //按照年龄排序
        return o1.age-o2.age;
    }
}

 运行结果：

•   person[age=12]
    person[age=52]
    person[age=92]
    person[age=102]

Comparable接口和Comparator怎么选择呢？

• 当比较规则不会发生改变的时候，或比较规则只有1个的时候，建议实现Comparable接口。

• 如果比较规则有多个的时候，并且需要多个比较规则之间频繁切换，建议使用Comparator比较器。

Comparator的设计符合OCP原则。。

支持：