TreeSet的两种排序规则

TreeSet是SortedSet接口的实现类，正如SortedSet名字所表示的，TreeSet可以保证集合元素 处于排序状态 。与HashSet集合相比，TreeSet还提供了几个额外的方法：

• Object first(): 返回集合的第一个元素。
• Object last(): 返回集合的最后一个元素。
• Object lower(Object e): 返回集合中位于指定元素(e)之前的元素。
• Object higher(Object e): 返回集合中位于指定元素(e)之后的元素。
• SortedSet subSet(Object fromElement, Object toElement): 返回此Set的子集合，返回从fromElement(包含)到toElement(不包含)。
• SortedSet headSet(Object toElement): 返回Set的子集合，返回toElement之前的集合。
• SortedSet tailSet(Object fromElement): 返回Set的子集合，返回fromElement之后的集合。

这里的话我们简单写个代码示例看看 TreeSet :

public class TreeSetShow {

    public static void main(String args[]) {
        TreeSet<Integer> values = new TreeSet<>();
        values.add(3);
        values.add(5);
        values.add(1);
        values.add(10);
        values.add(7);

        // 输出的是排序好的集合元素
        System.out.println(values);

        // 输出集合中第一个元素
        System.out.println(values.first()); // 输出 1

        // 集合中最后一个元素
        System.out.println(values.last()); // 输出 10

        // 输出小于5的子集 ( 不包含5 )
        System.out.println(values.headSet(5)); // 输出 [1, 3]

        // 输出大于5的子集，如果Set中有5，则包含5
        System.out.println(values.tailSet(5)); // 输出 [5, 7, 10]

        // 返回大于2小于8的子集
        System.out.println(values.subSet(2, 8)); // 输出 [3, 5, 7]
    }
}
复制代码

根据上面的程序运行结果可以看出，TreeSet 「 并不是根据元素的插入顺序来进行排序的 」 。而是根据元素的实际大小的值来排序的。

这里跟 HashSet 采用的hash算法来决定元素的存储位置不同，TreeSet采用的是 红黑树 的数据结构来存储集合元素。

这里说到了插入的顺序和实际存储的顺序，那么TreeSet的 排序规则 是怎么样的呢？

TreeSet采用两种排序方法: 自然排序 和 定制器排序 。

自然排序

自然排序:TreeSet 会调用集合元素的 compareTo(Object obj) 方法来比较元素之间的大小关系，然后将元素按升序排列。

Comparable接口

这里还没了解过Comparable接口的同学可以简单了解一下，很有用的一个Java接口，包括自己做排序也会经常用到的。

Java提供了一个Comparable接口，该接口里面定义了一个 compareTo(Object obj) 的方法，该方法返回一个整数值， 「 实现该接口的类必须实现该方法 」 ，实现了该接口的类的对象就可以比较大小了。

当一个对象使用该方法与另一个对象比较时，例: obj1.compareTo(obj2) ，如果该方法返回0， 则表明这两个对象相等; 如果返回正整数， 则表示 obj1 大于 obj2 ; 如果返回负整数， 则表示 obj1 小于 obj2 。

Java 一些常用类已经实现了Comparable接口， 并提供了比较大小的标准，这里的话大家可以简单看一下String类。

这里我们可以看到String已经 继承了Comparable接口类 了，那么String是如何做比较的呢，我们来看看它的 compareTo(String anotherString) 方法：

关于Comparable接口类就大概这样把，感兴趣的可以自己去看看别的类,像 BigDecimal、 BigInteger、 Integer、 Date等等很多类，都是有继承Comparable的。

TreeSet里的CompareTo()

大部分类在实现 compareTo(Object obj) 方法时，都需要将被比较对象强制转换成相同类型，因为只有相同类型的两个对象才可以比较大小。当我们试图把一个对象添加到TreeSet的时候， TreeSet就会先用 compareTo(Object obj) 比较一下（这时候如果添加的对象与其它的元素不是同一个类，就会引发 ClassCastException 异常）， 如下：

public class TreeSetError {
    public static void main(String args[]) {
        TreeSet ts = new TreeSet();
        
        ts.add("我很帅");
        ts.add(1);
    }
}
复制代码

上面程序很明显就会出异常了哈。首先新增 第一个字符串对象 ，这个操作就完全正常。但当添加 第二个整型对象 时，TreeSet就会调用该对象的compareTo方法与集合中的其它元素进行比较，你看看， 这明显对象不一样呀，那铁定报异常 ClassCastException 了。

总结起来就是，TreeSet只能添加同一种类型的对象。

当把一个对象加入TreeSet集合时， TreeSet会调用该对象的 compareTo() 方法与集合中的其它对象比较大小，然后根据 红黑树 来找到它存储的位置。如果两个对象通过比较方法返回相等( compareTo()方法返回0 )，新的对象就无法加入到TreeSet集合中。 那么现在我们来自定义一个对象来仔细看看，TreeSet到底是如何添加元素的：

// 这里我们假设所有的compareTo() 和 equeals() 方法都返回true
class Student implements Comparable {
    int age;
    
    public Student(int age) {
        this.age = age; 
    } 
    
    // 重写 equals() 方法 
    public boolean equals(Student student) {
        return true; 
    } 
    
    // 重写 compareTo() 方法 
    public int compareTo(Student student) {
        return 1;
    }
}

public class TreeSetTest {
    public static void main(String args[]) { 
        TreeSet set = new TreeSet();
        Student student1 = new Student(12); 
        
        // 尝试插入相同元素
        set.add(student1); 
        set.add(student1); 
    }
}
复制代码

从上述程序中，我们来看看我们实例化了一个Student对象并且继承了Comparable接口， 并且把它重复添加进Set集合中。

很显然，插入进去了，这里是不是很奇怪？为什么往同一个Set里面插入相同的元素，却插入成功了？？(逗我玩呢是吧！)

这里是因为compareTo()方法总是返回1， 虽然equals()方法总是返回true， 但TreeSet会认为 student1对象跟它自己不相等 ，因此treeSet可以添加两个student对象。

废话少说，大家看图，TreeSet对象保存的两个元素（集合里的元素总是引用，但习惯上把被引用的对象称为集合元素），简单理解一下，假如我们修改了图中treeSet的第一个元素（将Student的年龄改为10岁），那么图中最后一个元素的年龄也会改变（同时指向同一个对象）。

所以很明显我们需要注意一个问题了:当我们需要把一个对象放入TreeSet里面的话，重写该对象的equals()方法时，应该保证该方法的compareTo()方法有一致的结果，规则为: 「 如果两个对象使用equals()方法返回true时， 使用compareTo()方法也应该返回0。 」

还有，如果向TreeSet中插入可改变的对象， 并且后面程序修改了该可变对象的实例变量，这将导致它与其它对象的大小顺序发生改变，但TreeSet不会再次调整他们的顺序，甚至可能导致该可变对象与其它对象compareTo()方法比较返回为0。

定制器排序

TreeSet的自然排序时 根据集合元素的大小， TreeSet将他们以升序排列。 如果需要实现定制排序，例如降序排列，则可以通过Comparable接口的帮助。该接口包含了一个 int compare(T o1, T o2) 方法，该方法用于比较 o1 和 o2 的大小: 如果该方法返回正整数则表示 o1 大于 o2 ， 0表示相等， 负整数表示 o2 大 于o1 。

下面我们看看代码：

class Student {
    int age;
    
    public Student(int age) {
        this.age = age; 
    } 
    
    public String toString() {
        return "Student[age:" + age + "]";
    }
}
public class TreeSetTest {
    public static void main(String args[]) {
        
        TreeSet ts = new TreeSet((o1, o2) -> {
            Student stu1 = (Student) o1;
            Student stu2 = (Student) o2;
            
            // 这里倒序排的话就是年纪大的反而返回负整数
            return stu1.age > stu2.age ? -1 : stu1.age < stu2.age ? 1 : 0
        })
        
        ts.add(new Student(1));
        ts.add(new Student(5));
        ts.add(new Student(9));
        System.out.println(ts);
    }
}
复制代码

这里用了 lambda表达式 来重写 compare(T o1, T o2) 方法, 它来负责treeSet集合的排序。所以当Student对象添加到ts集合中时，不需要Student实现Comparable接口， 因为此时TreeSet无需通过Student对象本身来比较大小，而是 由TreeSet关联的Lambda表达式来负责集合元素的排序 。

运行结果: Student[age:9] Student[age:5] Student[age:1]