關(guān)于TreeSet的排序問題

作者:xcbeyond
瘋狂源自夢想,技術(shù)成就輝煌!微信公眾號:《程序猿技術(shù)大咖》號主,專注后端開發(fā)多年,擁有豐富的研發(fā)經(jīng)驗(yàn),樂于技術(shù)輸出、分享,現(xiàn)階段從事微服務(wù)架構(gòu)項(xiàng)目的研發(fā)工作,涉及架構(gòu)設(shè)計(jì)、技術(shù)選型、業(yè)務(wù)研發(fā)等工作。對于Java、微服務(wù)、數(shù)據(jù)庫、Docker有深入了解,并有大量的調(diào)優(yōu)經(jīng)驗(yàn)。

TreeSet支持兩種排序方法:自然排序和定制排序。TreeSet默認(rèn)采用自然排序。
 
1 、自然排序
TreeSet 會調(diào)用集合元素的compareTo(Object obj)方法來比較元素之間大小關(guān)系,然后將集合元素按升序排列,這種方式就是自然排序。(比較的前提:兩個對象的類型相同)。
 
java 提供了一個Comparable接口,該接口里定義了一個compareTo(Object obj)方法,該方法返回一個整數(shù)值,實(shí)現(xiàn)該接口的類必須實(shí)現(xiàn)該方法,實(shí)現(xiàn)了該接口的類的對象就可以比較大小。當(dāng)一個對象調(diào)用該方法與另一個對象進(jìn)行比較,例如obj1.comparTo(obj2),如果該方法返回0,則表明這兩個對象相等;如果返回一個正整數(shù),則表明obj1大于obj2;如果該方法返回一個負(fù)整數(shù),則表明obj1小于 obj2.
 
java常用類實(shí)現(xiàn)Comparable接口,并提供了比較大小的標(biāo)準(zhǔn)。實(shí)現(xiàn)Comparable接口的常用類:
? BigDecimal、BigIneger以及所有數(shù)值型對應(yīng)包裝類:按它們對應(yīng)的數(shù)值的大小進(jìn)行比較。
? Character:按字符的UNICODE值進(jìn)行比較。
? Boolean:true對應(yīng)的包裝類實(shí)例大于false對應(yīng)的包裝類實(shí)例。
? String:按字符串中字符的UNICODE值進(jìn)行比較。
? Date、Time:后面的時間、日期比前面的時間、日期大。
如果試圖把一個對象添加進(jìn)TreeSet時,則該對象的類必須實(shí)現(xiàn)Comparable接口。
如下程序則會報(bào)錯:

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里沒有任何元素,所以沒有問題;當(dāng)添加第二個Err對象時,TreeSet就會調(diào)用該對象的compareTo(Object obj)方法與集合中其他元素進(jìn)行比較——如果對應(yīng)的類沒有實(shí)現(xiàn)Comparable接口,則會引發(fā)ClassCastException異常。而且當(dāng)試圖從TreeSet中取出元素第一個元素時,依然會引發(fā)ClassCastException異常。
 
當(dāng)采用compareTo(Object obj)方法比較對象時,都需要將被比較對象obj強(qiáng)制類型轉(zhuǎn)換成相同類型,因?yàn)橹挥邢嗤惖膬蓚€實(shí)例才能比較大小。即向TreeSet中添加的應(yīng)該是同一個類的對象,否則會引發(fā)ClassCastException異常。例如,當(dāng)向TreeSet中添加一個字符串對象,這個操作完全正常。當(dāng)添加第二個Date對象時,TreeSet就好調(diào)用該對象的compareTo(Object obj)方法與集合中其他元素進(jìn)行比較,則此時程序會引發(fā)異常。
 
在實(shí)際編程中,程序員可以定義自己的類向TreeSet中添加多種類型的對象,前提是用戶自定義類實(shí)現(xiàn)了Comparable接口,實(shí)現(xiàn)該接口時在實(shí)現(xiàn)compareTo(Object obj)方法時沒有進(jìn)行強(qiáng)制類型轉(zhuǎn)換。但當(dāng)操作TreeSet里的集合數(shù)據(jù)時,不同類型的元素依然會發(fā)生ClassCastExceptio異常。(認(rèn)真閱讀下就會明白)
 
 
當(dāng)把一個對象加入TreeSet集合中時,TreeSet調(diào)用該對象的compareTo(Object obj)方法與容器中的其他對象比較大小,然后根據(jù)紅黑樹算法決定它的存儲位置。如果兩個對象通過compareTo(Object obj)比較相等,TreeSet即認(rèn)為它們存儲同一位置。
 
對于TreeSet集合而言,它判斷兩個對象不相等的標(biāo)準(zhǔn)是:兩個對象通過equals方法比較返回false,或通過compareTo(Object obj)比較沒有返回0——即使兩個對象時同一個對象,TreeSet也會把它們當(dāng)成兩個對象進(jìn)行處理。
如下程序所示:

//Z類,重寫了equals方法,總是返回false,
//重寫了compareTo(Object obj)方法,總是返回正整數(shù)
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);
    }
}
程序運(yùn)行結(jié)果:
true
[TreeSet.Z@1fb8ee3, TreeSet.Z@1fb8ee3]
9
說明:
程序中把同一個對象添加了兩次,因?yàn)閦1對象的equals()方法總是返回false,而且compareTo(Object obj)方法總是返回1。這樣TreeSet會認(rèn)為z1對象和它自己也不相同,因此TreeSet中添加兩個z1對象。而TreeSet對象保存的兩個元素實(shí)際上是同一個元素。所以當(dāng)修改TreeSet集合里第一個元素的age屬性后,該TreeSet集合里最后一個元素的age屬性也隨之改變了。
 
總結(jié):當(dāng)需要把一個對象放入TreeSet中時,重寫該對象對應(yīng)類的equals()方法時,應(yīng)保證該方法與compareTo(Object obj)方法有一致結(jié)果,其規(guī)則是:如果兩個對象通過equals方法比較返回true時,這兩個對象通過compareTo(Object obj)方法比較應(yīng)返回0.
 
如果兩個對象通過equals方法比較返回true,但這兩個對象通過compareTo(Object obj)方法比較不返回0時,這將導(dǎo)致TreeSet將會把這兩個對象保存在不同位置,從而兩個對象都可以添加成功,這與Set集合的規(guī)則有點(diǎn)出入。
 
如果兩個對象通過compareTo(Object obj)方法比較返回0時,但它們通過equals方法比較返回false時將更麻煩:因?yàn)閮蓚€對象通過compareTo(Object obj)方法比較相等,TreeSet將試圖把它們保存在同一個位置,但實(shí)際上又不行(否則將只剩下一個對象),所以處理起來比較麻煩。
 
如果向TreeSet中添加一個可變對象后,并且后面程序修改了該可變對象的屬性,導(dǎo)致它與其他對象的大小順序發(fā)生改變,但TreeSet不會再次調(diào)整它們的順序,甚至可能導(dǎo)致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里的元素處于無序狀態(tài)
        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)));
    }
}

程序運(yùn)行結(jié)果:
[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屬性作為判斷的依據(jù)??梢钥吹匠绦虻谝淮屋敵龅慕Y(jié)果是有序排列的。當(dāng)改變R對象的count屬性,程序的輸出結(jié)果也發(fā)生了改變,而且包含了重復(fù)元素。一旦改變了TreeSet集合里可變元素的屬性,當(dāng)再視圖刪除該對象時,TreeSet也會刪除失?。ㄉ踔良现性械摹傩詻]被修改,但與修改后元素相等的元素也無法刪除),所以刪除count
為-2的R對象時,沒有任何元素被刪除;程序可以刪除count為5的R對象,這表明TreeSet可以刪除沒有被修改屬性、且不與其他被修改屬性的對象重復(fù)的對象。
 
總結(jié):與HashSet在處理這些對象時將非常復(fù)雜,而且容易出錯。為了讓程序更具健壯,推薦HashSet和TreeSet集合中只放入不可變對象。





 
2、定制排序
TreeSet的自然排序是根據(jù)集合元素的大小,TreeSet將他們以升序排列。如果需要實(shí)現(xiàn)定制排序,例如降序,則可以使用Comparator接口。該接口里包含一個int compare(T o1, T o2)方法,該方法用于比較o1和o2的大小。
如果需要實(shí)現(xiàn)定制排序,則需要在創(chuàng)建TreeSet集合對象時,并提供一個Comparator對象與該TreeSet集合關(guān)聯(lián),由該Comparator對象負(fù)責(zé)集合元素的排序邏輯。
如下程序所示:

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);
    }
}
 

程序運(yùn)行結(jié)果:


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


說明:
上面程序中創(chuàng)建了一個Comparator接口的匿名內(nèi)部類對象,該對象負(fù)責(zé)ts集合的排序。所以當(dāng)我們把M對象添加到ts集合中時,無須M類實(shí)現(xiàn)Comparable接口,因?yàn)榇藭rTreeSet無須通過M對象來比較大小,而是由與TreeSet關(guān)聯(lián)的Comparator對象來負(fù)責(zé)集合元素的排序。使用定制排序時,TreeSet對集合元素排序時不管集合元素本身的大小,而是由Comparator對象負(fù)責(zé)集合元素的排序規(guī)則。

 

案例:

學(xué)生成績排序

package 學(xué)生成績排序TreeSet;
/**
 * java提供了一個Comparable接口,該接口里定義了一個compareTo方法,
 * 該方法返回一個整數(shù)值,實(shí)現(xiàn)該接口的類必須實(shí)現(xiàn)該方法,實(shí)現(xiàn)了該接口的類的對象就可以比較大小。
 * @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;//數(shù)學(xué)
    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 學(xué)生成績排序TreeSet;
 
import java.util.Scanner;
import java.util.TreeSet;
/**
 * 學(xué)生平均成績排序
 * @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學(xué)號\t語文\t數(shù)學(xué)\t英語\t平均分");
        System.out.println(stu);
    }
    
    //錄入學(xué)生信息
    public static void addStudent() {
        Scanner input = new Scanner(System.in);
        String yesOrNo;
        
        do {
            System.out.print("姓名:");
            String name = input.next();
            System.out.print("學(xué)號:");
            String id = input.next();
            System.out.print("語文:");
            int chinese = input.nextInt();
            System.out.print("數(shù)學(xué):");
            int math = input.nextInt();
            System.out.print("英語:");
            int english = input.nextInt();
            
            stu.add(new Student(name,id,chinese,math,english));
            
            System.out.println("是否繼續(xù)添加學(xué)生信息(Y/N)?");
            yesOrNo = input.next();
        }while(yesOrNo.toUpperCase().equals("Y"));
    }
}
這個代碼細(xì)心測試發(fā)現(xiàn)會發(fā)現(xiàn),當(dāng)輸入的數(shù)據(jù)計(jì)算后,兩個人的平均成績相等時,輸出結(jié)果只會顯示其中一個人的信息,這也就符合了Set接口的定義了,“無序,不重復(fù)”
。只需稍稍修改下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;
        
    }