关于TreeSet的排序问题

作者:xcbeyond
疯狂源自梦想,技术成就辉煌!微信公众号:《程序猿技术大咖》号主,专注后端开发多年,拥有丰富的研发经验,乐于技术输出、分享,现阶段从事微服务架构项目的研发工作,涉及架构设计、技术选型、业务研发等工作。对于Java、微服务、数据库、Docker有深入了解,并有大量的调优经验。

TreeSet支持两种排序方法:自然排序和定制排序。TreeSet默认采用自然排序。
 
1 、自然排序
TreeSet 会调用集合元素的compareTo(Object obj)方法来比较元素之间大小关系,然后将集合元素按升序排列,这种方式就是自然排序。(比较的前提:两个对象的类型相同)。
 
java 提供了一个Comparable接口,该接口里定义了一个compareTo(Object obj)方法,该方法返回一个整数值,实现该接口的类必须实现该方法,实现了该接口的类的对象就可以比较大小。当一个对象调用该方法与另一个对象进行比较,例如obj1.comparTo(obj2),如果该方法返回0,则表明这两个对象相等;如果返回一个正整数,则表明obj1大于obj2;如果该方法返回一个负整数,则表明obj1小于 obj2.
 
java常用类实现Comparable接口,并提供了比较大小的标准。实现Comparable接口的常用类:
• BigDecimal、BigIneger以及所有数值型对应包装类:按它们对应的数值的大小进行比较。
• Character:按字符的UNICODE值进行比较。
• Boolean:true对应的包装类实例大于false对应的包装类实例。
• String:按字符串中字符的UNICODE值进行比较。
• Date、Time:后面的时间、日期比前面的时间、日期大。
如果试图把一个对象添加进TreeSet时,则该对象的类必须实现Comparable接口。
如下程序则会报错:

class Err
{
}
public class TestTreeSetError
{
    public static void main(String[] args)
    {
        TreeSet ts = new TreeSet();
        //向TreeSet集合中添加两个Err对象
        ts.add(new Err());
        ts.add(new Err());
    }
}

说明:
上面程序试图向TreeSet集合中添加2个Err对象,添加第一个对象时,TreeSet里没有任何元素,所以没有问题;当添加第二个Err对象时,TreeSet就会调用该对象的compareTo(Object obj)方法与集合中其他元素进行比较——如果对应的类没有实现Comparable接口,则会引发ClassCastException异常。而且当试图从TreeSet中取出元素第一个元素时,依然会引发ClassCastException异常。
 
当采用compareTo(Object obj)方法比较对象时,都需要将被比较对象obj强制类型转换成相同类型,因为只有相同类的两个实例才能比较大小。即向TreeSet中添加的应该是同一个类的对象,否则会引发ClassCastException异常。例如,当向TreeSet中添加一个字符串对象,这个操作完全正常。当添加第二个Date对象时,TreeSet就好调用该对象的compareTo(Object obj)方法与集合中其他元素进行比较,则此时程序会引发异常。
 
在实际编程中,程序员可以定义自己的类向TreeSet中添加多种类型的对象,前提是用户自定义类实现了Comparable接口,实现该接口时在实现compareTo(Object obj)方法时没有进行强制类型转换。但当操作TreeSet里的集合数据时,不同类型的元素依然会发生ClassCastExceptio异常。(认真阅读下就会明白)
 
 
当把一个对象加入TreeSet集合中时,TreeSet调用该对象的compareTo(Object obj)方法与容器中的其他对象比较大小,然后根据红黑树算法决定它的存储位置。如果两个对象通过compareTo(Object obj)比较相等,TreeSet即认为它们存储同一位置。
 
对于TreeSet集合而言,它判断两个对象不相等的标准是:两个对象通过equals方法比较返回false,或通过compareTo(Object obj)比较没有返回0——即使两个对象时同一个对象,TreeSet也会把它们当成两个对象进行处理。
如下程序所示:

//Z类,重写了equals方法,总是返回false,
//重写了compareTo(Object obj)方法,总是返回正整数
class Z implements Comparable
{
    int age;
    public Z(int age)
    {
        this.age = age;
    }
    public boolean equals(Object obj)
    {
        return false;
    }
    public int compareTo(Object obj)
    {
        return 1;
    }
}
public class TestTreeSet
{
    public static void main(String[] args)
    {
        TreeSet set = new TreeSet();
        Z z1 = new Z(6);
        set.add(z1);
        System.out.println(set.add(z1));
        //下面输出set集合,将看到有2个元素
        System.out.println(set);
        //修改set集合的第一个元素的age属性
        ((Z)(set.first())).age = 9;
        //输出set集合的最后一个元素的age属性,将看到也变成了9
        System.out.println(((Z)(set.last())).age);
    }
}
程序运行结果:
true
[TreeSet.Z@1fb8ee3, TreeSet.Z@1fb8ee3]
9
说明:
程序中把同一个对象添加了两次,因为z1对象的equals()方法总是返回false,而且compareTo(Object obj)方法总是返回1。这样TreeSet会认为z1对象和它自己也不相同,因此TreeSet中添加两个z1对象。而TreeSet对象保存的两个元素实际上是同一个元素。所以当修改TreeSet集合里第一个元素的age属性后,该TreeSet集合里最后一个元素的age属性也随之改变了。
 
总结:当需要把一个对象放入TreeSet中时,重写该对象对应类的equals()方法时,应保证该方法与compareTo(Object obj)方法有一致结果,其规则是:如果两个对象通过equals方法比较返回true时,这两个对象通过compareTo(Object obj)方法比较应返回0.
 
如果两个对象通过equals方法比较返回true,但这两个对象通过compareTo(Object obj)方法比较不返回0时,这将导致TreeSet将会把这两个对象保存在不同位置,从而两个对象都可以添加成功,这与Set集合的规则有点出入。
 
如果两个对象通过compareTo(Object obj)方法比较返回0时,但它们通过equals方法比较返回false时将更麻烦:因为两个对象通过compareTo(Object obj)方法比较相等,TreeSet将试图把它们保存在同一个位置,但实际上又不行(否则将只剩下一个对象),所以处理起来比较麻烦。
 
如果向TreeSet中添加一个可变对象后,并且后面程序修改了该可变对象的属性,导致它与其他对象的大小顺序发生改变,但TreeSet不会再次调整它们的顺序,甚至可能导致TreeSet中保存这两个对象,它们通过equals方法比较返回true,compareTo(Object obj)方法比较返回0.
如下程序所示:

class R
{
    int count;
    public R(int count)
    {
        this.count = count;
    }
    public String toString()
    {
        return "R(count属性:" + count + ")";
    }
    public boolean equals(Object obj)
    {
        if (obj instanceof R)
        {
            R r = (R)obj;
            if (r.count == this.count)
            {
                return true;
            }
        }
        return false;
    }
    public int hashCode()
    {
        return this.count;
    }
}
public class TestHashSet2
{
    public static void main(String[] args)
    {
        HashSet hs = new HashSet();
        hs.add(new R(5));
        hs.add(new R(-3));
        hs.add(new R(9));
        hs.add(new R(-2));
        //打印TreeSet集合,集合元素是有序排列的
        System.out.println(hs);
        //取出第一个元素 www.2cto.com
        Iterator it = hs.iterator();
        R first = (R)it.next();
        //为第一个元素的count属性赋值
        first.count = -3;
        //再次输出count将看到TreeSet里的元素处于无序状态
        System.out.println(hs);
        hs.remove(new R(-3));
        System.out.println(hs);
        //输出false
        System.out.println("hs是否包含count为-3的R对象?" + hs.contains(new R(-3)));
        //输出false
        System.out.println("hs是否包含count为5的R对象?" + hs.contains(new R(5)));
    }
}

程序运行结果:
[R(count属性:-3), R(count属性:-2), R(count属性:5), R(count属性:9)]
[R(count属性:20), R(count属性:-2), R(count属性:5), R(count属性:-2)]
[R(count属性:20), R(count属性:-2), R(count属性:5), R(count属性:-2)]
[R(count属性:20), R(count属性:-2), R(count属性:-2)]
 
 
说明:
上面程序中的R对象是一个正常重写了equals方法和comparable方法类,这两个方法都以R对象的count属性作为判断的依据。可以看到程序第一次输出的结果是有序排列的。当改变R对象的count属性,程序的输出结果也发生了改变,而且包含了重复元素。一旦改变了TreeSet集合里可变元素的属性,当再视图删除该对象时,TreeSet也会删除失败(甚至集合中原有的、属性没被修改,但与修改后元素相等的元素也无法删除),所以删除count
为-2的R对象时,没有任何元素被删除;程序可以删除count为5的R对象,这表明TreeSet可以删除没有被修改属性、且不与其他被修改属性的对象重复的对象。
 
总结:与HashSet在处理这些对象时将非常复杂,而且容易出错。为了让程序更具健壮,推荐HashSet和TreeSet集合中只放入不可变对象。





 
2、定制排序
TreeSet的自然排序是根据集合元素的大小,TreeSet将他们以升序排列。如果需要实现定制排序,例如降序,则可以使用Comparator接口。该接口里包含一个int compare(T o1, T o2)方法,该方法用于比较o1和o2的大小。
如果需要实现定制排序,则需要在创建TreeSet集合对象时,并提供一个Comparator对象与该TreeSet集合关联,由该Comparator对象负责集合元素的排序逻辑。
如下程序所示:

class M {
    int age;
    public M(int age) {
        this.age = age;
    }
    public String toString() {
        return "M对象(age:" + age + ")";
    }
}
public class TestTreeSet3 {
    public static void main(String[] args) {
        TreeSet ts = new TreeSet(new Comparator() {
            public int compare(Object o1, Object o2) {
                M m1 = (M) o1;
                M m2 = (M) o2;
                if (m1.age > m2.age) {
                    return -1;
                } else if (m1.age == m2.age) {
                    return 0;
                } else {
                    return 1;
                }
            }
        });
        ts.add(new M(5));
        ts.add(new M(-3));
        ts.add(new M(9));
        System.out.println(ts);
    }
}
 

程序运行结果:


[M对象(age:9), M对象(age:5), M对象(age:-3)]


说明:
上面程序中创建了一个Comparator接口的匿名内部类对象,该对象负责ts集合的排序。所以当我们把M对象添加到ts集合中时,无须M类实现Comparable接口,因为此时TreeSet无须通过M对象来比较大小,而是由与TreeSet关联的Comparator对象来负责集合元素的排序。使用定制排序时,TreeSet对集合元素排序时不管集合元素本身的大小,而是由Comparator对象负责集合元素的排序规则。

 

案例:

学生成绩排序

package 学生成绩排序TreeSet;
/**
 * java提供了一个Comparable接口,该接口里定义了一个compareTo方法,
 * 该方法返回一个整数值,实现该接口的类必须实现该方法,实现了该接口的类的对象就可以比较大小。
 * @author xcbeyond
 * @date 2012-4-25 上午12:48:42
 */
public class Student implements Comparable<Student> {
    private String name;
    private String id;
    private int chinese;//语文
    private int math;//数学
    private int english;//英语
    
    public Student() {
    }
    public Student(String name, String id, int chinese, int math, int english) {
        setName(name);
        setId(id);
        setChinese(chinese);
        setMath(math);
        setEnglish(english);
    }
 
    public String getName() {
        return name;
    }
 
    public void setName(String name) {
        this.name = name;
    }
 
    public String getId() {
        return id;
    }
 
    public void setId(String id) {
        this.id = id;
    }
 
    public int getChinese() {
        return chinese;
    }
 
    public void setChinese(int chinese) {
        this.chinese = chinese;
    }
 
    public int getMath() {
        return math;
    }
 
    public void setMath(int math) {
        this.math = math;
    }
 
    public int getEnglish() {
        return english;
    }
 
    public void setEnglish(int english) {
        this.english = english;
    }
 
    public int compareTo(Student other) {
        return average() - other.average();
    }
    //平均成绩
    public int average() {
        return (getChinese()+getMath()+getEnglish())/3;
        
    }
    
    @Override
    public String toString() {
        return getName()+"\t"+getId()+"\t"+getChinese()+"\t"+getMath()+"\t"+getEnglish()+"\t"+average()+"\n";
    }
 
}
package 学生成绩排序TreeSet;
 
import java.util.Scanner;
import java.util.TreeSet;
/**
 * 学生平均成绩排序
 * @author xcbeyond
 * @date 2012-4-25 上午12:47:48
 */
public class StudentTest {
    static TreeSet<Student> stu = new TreeSet<Student>();
    
    public static void main(String[] args) {
        addStudent();
        
        System.out.println("姓名\t学号\t语文\t数学\t英语\t平均分");
        System.out.println(stu);
    }
    
    //录入学生信息
    public static void addStudent() {
        Scanner input = new Scanner(System.in);
        String yesOrNo;
        
        do {
            System.out.print("姓名:");
            String name = input.next();
            System.out.print("学号:");
            String id = input.next();
            System.out.print("语文:");
            int chinese = input.nextInt();
            System.out.print("数学:");
            int math = input.nextInt();
            System.out.print("英语:");
            int english = input.nextInt();
            
            stu.add(new Student(name,id,chinese,math,english));
            
            System.out.println("是否继续添加学生信息(Y/N)?");
            yesOrNo = input.next();
        }while(yesOrNo.toUpperCase().equals("Y"));
    }
}
这个代码细心测试发现会发现,当输入的数据计算后,两个人的平均成绩相等时,输出结果只会显示其中一个人的信息,这也就符合了Set接口的定义了,“无序,不重复”
。只需稍稍修改下compareTo方法就可以解决这个问题了。

public int compareTo(Object o) {
        Student other = (Student)o;
        if(average()>other.average())
            return 1;
        if(average()<other.average())
            return -1;
        if(getId().compareTo(other.getId())>0)
            return 1;
        if(getId().compareTo(other.getId())<0)
            return -1;
        return 0;
        
    }