個(gè)人中心
退出
關(guān)于TreeSet的排序問(wèn)題
作者：xcbeyond
瘋狂源自夢(mèng)想，技術(shù)成就輝煌！微信公眾號(hào)：《程序猿技術(shù)大咖》號(hào)主，專(zhuān)注后端開(kāi)發(fā)多年，擁有豐富的研發(fā)經(jīng)驗(yàn)，樂(lè)于技術(shù)輸出、分享，現(xiàn)階段從事微服務(wù)架構(gòu)項(xiàng)目的研發(fā)工作，涉及架構(gòu)設(shè)計(jì)、技術(shù)選型、業(yè)務(wù)研發(fā)等工作。對(duì)于Java、微服務(wù)、數(shù)據(jù)庫(kù)、Docker有深入了解，并有大量的調(diào)優(yōu)經(jīng)驗(yàn)。
TreeSet支持兩種排序方法：自然排序和定制排序。TreeSet默認(rèn)采用自然排序。
1 、自然排序
TreeSet 會(huì)調(diào)用集合元素的compareTo(Object obj)方法來(lái)比較元素之間大小關(guān)系，然后將集合元素按升序排列，這種方式就是自然排序。（比較的前提：兩個(gè)對(duì)象的類(lèi)型相同）。
java 提供了一個(gè)Comparable接口，該接口里定義了一個(gè)compareTo(Object obj)方法，該方法返回一個(gè)整數(shù)值，實(shí)現(xiàn)該接口的類(lèi)必須實(shí)現(xiàn)該方法，實(shí)現(xiàn)了該接口的類(lèi)的對(duì)象就可以比較大小。當(dāng)一個(gè)對(duì)象調(diào)用該方法與另一個(gè)對(duì)象進(jìn)行比較，例如obj1.comparTo(obj2),如果該方法返回0，則表明這兩個(gè)對(duì)象相等；如果返回一個(gè)正整數(shù)，則表明obj1大于obj2；如果該方法返回一個(gè)負(fù)整數(shù)，則表明obj1小于 obj2.
java常用類(lèi)實(shí)現(xiàn)Comparable接口，并提供了比較大小的標(biāo)準(zhǔn)。實(shí)現(xiàn)Comparable接口的常用類(lèi)：
? BigDecimal、BigIneger以及所有數(shù)值型對(duì)應(yīng)包裝類(lèi)：按它們對(duì)應(yīng)的數(shù)值的大小進(jìn)行比較。
? Character：按字符的UNICODE值進(jìn)行比較。
? Boolean：true對(duì)應(yīng)的包裝類(lèi)實(shí)例大于false對(duì)應(yīng)的包裝類(lèi)實(shí)例。
? String：按字符串中字符的UNICODE值進(jìn)行比較。
? Date、Time：后面的時(shí)間、日期比前面的時(shí)間、日期大。
如果試圖把一個(gè)對(duì)象添加進(jìn)TreeSet時(shí)，則該對(duì)象的類(lèi)必須實(shí)現(xiàn)Comparable接口。
如下程序則會(huì)報(bào)錯(cuò)：
class Err
{
}
public class TestTreeSetError
{
public static void main(String[] args)
{
TreeSet ts = new TreeSet();
//向TreeSet集合中添加兩個(gè)Err對(duì)象
ts.add(new Err());
ts.add(new Err());
}
}
說(shuō)明：
上面程序試圖向TreeSet集合中添加2個(gè)Err對(duì)象，添加第一個(gè)對(duì)象時(shí)，TreeSet里沒(méi)有任何元素，所以沒(méi)有問(wèn)題；當(dāng)添加第二個(gè)Err對(duì)象時(shí)，TreeSet就會(huì)調(diào)用該對(duì)象的compareTo(Object obj)方法與集合中其他元素進(jìn)行比較——如果對(duì)應(yīng)的類(lèi)沒(méi)有實(shí)現(xiàn)Comparable接口，則會(huì)引發(fā)ClassCastException異常。而且當(dāng)試圖從TreeSet中取出元素第一個(gè)元素時(shí)，依然會(huì)引發(fā)ClassCastException異常。
當(dāng)采用compareTo(Object obj)方法比較對(duì)象時(shí)，都需要將被比較對(duì)象obj強(qiáng)制類(lèi)型轉(zhuǎn)換成相同類(lèi)型，因?yàn)橹挥邢嗤?lèi)的兩個(gè)實(shí)例才能比較大小。即向TreeSet中添加的應(yīng)該是同一個(gè)類(lèi)的對(duì)象，否則會(huì)引發(fā)ClassCastException異常。例如，當(dāng)向TreeSet中添加一個(gè)字符串對(duì)象，這個(gè)操作完全正常。當(dāng)添加第二個(gè)Date對(duì)象時(shí)，TreeSet就好調(diào)用該對(duì)象的compareTo(Object obj)方法與集合中其他元素進(jìn)行比較，則此時(shí)程序會(huì)引發(fā)異常。
在實(shí)際編程中，程序員可以定義自己的類(lèi)向TreeSet中添加多種類(lèi)型的對(duì)象，前提是用戶(hù)自定義類(lèi)實(shí)現(xiàn)了Comparable接口，實(shí)現(xiàn)該接口時(shí)在實(shí)現(xiàn)compareTo(Object obj)方法時(shí)沒(méi)有進(jìn)行強(qiáng)制類(lèi)型轉(zhuǎn)換。但當(dāng)操作TreeSet里的集合數(shù)據(jù)時(shí)，不同類(lèi)型的元素依然會(huì)發(fā)生ClassCastExceptio異常。（認(rèn)真閱讀下就會(huì)明白)
當(dāng)把一個(gè)對(duì)象加入TreeSet集合中時(shí)，TreeSet調(diào)用該對(duì)象的compareTo(Object obj)方法與容器中的其他對(duì)象比較大小，然后根據(jù)紅黑樹(shù)算法決定它的存儲(chǔ)位置。如果兩個(gè)對(duì)象通過(guò)compareTo(Object obj)比較相等，TreeSet即認(rèn)為它們存儲(chǔ)同一位置。
對(duì)于TreeSet集合而言，它判斷兩個(gè)對(duì)象不相等的標(biāo)準(zhǔn)是：兩個(gè)對(duì)象通過(guò)equals方法比較返回false，或通過(guò)compareTo（Object obj）比較沒(méi)有返回0——即使兩個(gè)對(duì)象時(shí)同一個(gè)對(duì)象，TreeSet也會(huì)把它們當(dāng)成兩個(gè)對(duì)象進(jìn)行處理。
如下程序所示：
//Z類(lèi)，重寫(xiě)了equals方法，總是返回false，
//重寫(xiě)了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個(gè)元素
System.out.println(set);
//修改set集合的第一個(gè)元素的age屬性
((Z)(set.first())).age = 9;
//輸出set集合的最后一個(gè)元素的age屬性，將看到也變成了9
System.out.println(((Z)(set.last())).age);
}
}
程序運(yùn)行結(jié)果：
true
[TreeSet.Z@1fb8ee3, TreeSet.Z@1fb8ee3]
9
說(shuō)明：
程序中把同一個(gè)對(duì)象添加了兩次，因?yàn)閦1對(duì)象的equals()方法總是返回false，而且compareTo(Object obj)方法總是返回1。這樣TreeSet會(huì)認(rèn)為z1對(duì)象和它自己也不相同，因此TreeSet中添加兩個(gè)z1對(duì)象。而TreeSet對(duì)象保存的兩個(gè)元素實(shí)際上是同一個(gè)元素。所以當(dāng)修改TreeSet集合里第一個(gè)元素的age屬性后，該TreeSet集合里最后一個(gè)元素的age屬性也隨之改變了。
總結(jié)：當(dāng)需要把一個(gè)對(duì)象放入TreeSet中時(shí)，重寫(xiě)該對(duì)象對(duì)應(yīng)類(lèi)的equals()方法時(shí)，應(yīng)保證該方法與compareTo(Object obj)方法有一致結(jié)果，其規(guī)則是：如果兩個(gè)對(duì)象通過(guò)equals方法比較返回true時(shí)，這兩個(gè)對(duì)象通過(guò)compareTo（Object obj）方法比較應(yīng)返回0.
如果兩個(gè)對(duì)象通過(guò)equals方法比較返回true，但這兩個(gè)對(duì)象通過(guò)compareTo(Object obj)方法比較不返回0時(shí)，這將導(dǎo)致TreeSet將會(huì)把這兩個(gè)對(duì)象保存在不同位置，從而兩個(gè)對(duì)象都可以添加成功，這與Set集合的規(guī)則有點(diǎn)出入。
如果兩個(gè)對(duì)象通過(guò)compareTo(Object obj)方法比較返回0時(shí)，但它們通過(guò)equals方法比較返回false時(shí)將更麻煩：因?yàn)閮蓚€(gè)對(duì)象通過(guò)compareTo（Object obj）方法比較相等，TreeSet將試圖把它們保存在同一個(gè)位置，但實(shí)際上又不行（否則將只剩下一個(gè)對(duì)象），所以處理起來(lái)比較麻煩。
如果向TreeSet中添加一個(gè)可變對(duì)象后，并且后面程序修改了該可變對(duì)象的屬性，導(dǎo)致它與其他對(duì)象的大小順序發(fā)生改變，但TreeSet不會(huì)再次調(diào)整它們的順序，甚至可能導(dǎo)致TreeSet中保存這兩個(gè)對(duì)象，它們通過(guò)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);
//取出第一個(gè)元素 www.2cto.com
Iterator it = hs.iterator();
R first = (R)it.next();
//為第一個(gè)元素的count屬性賦值
first.count = -3;
//再次輸出count將看到TreeSet里的元素處于無(wú)序狀態(tài)
System.out.println(hs);
hs.remove(new R(-3));
System.out.println(hs);
//輸出false
System.out.println("hs是否包含count為-3的R對(duì)象？" + hs.contains(new R(-3)));
//輸出false
System.out.println("hs是否包含count為5的R對(duì)象？" + 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)]
說(shuō)明：
上面程序中的R對(duì)象是一個(gè)正常重寫(xiě)了equals方法和comparable方法類(lèi)，這兩個(gè)方法都以R對(duì)象的count屬性作為判斷的依據(jù)。可以看到程序第一次輸出的結(jié)果是有序排列的。當(dāng)改變R對(duì)象的count屬性，程序的輸出結(jié)果也發(fā)生了改變，而且包含了重復(fù)元素。一旦改變了TreeSet集合里可變?cè)氐膶傩?，?dāng)再視圖刪除該對(duì)象時(shí)，TreeSet也會(huì)刪除失?。ㄉ踔良现性械?、屬性沒(méi)被修改，但與修改后元素相等的元素也無(wú)法刪除），所以刪除count
為-2的R對(duì)象時(shí)，沒(méi)有任何元素被刪除；程序可以刪除count為5的R對(duì)象，這表明TreeSet可以刪除沒(méi)有被修改屬性、且不與其他被修改屬性的對(duì)象重復(fù)的對(duì)象。
總結(jié)：與HashSet在處理這些對(duì)象時(shí)將非常復(fù)雜，而且容易出錯(cuò)。為了讓程序更具健壯，推薦HashSet和TreeSet集合中只放入不可變對(duì)象。
2、定制排序
TreeSet的自然排序是根據(jù)集合元素的大小，TreeSet將他們以升序排列。如果需要實(shí)現(xiàn)定制排序，例如降序，則可以使用Comparator接口。該接口里包含一個(gè)int compare（T o1， T o2）方法，該方法用于比較o1和o2的大小。
如果需要實(shí)現(xiàn)定制排序，則需要在創(chuàng)建TreeSet集合對(duì)象時(shí)，并提供一個(gè)Comparator對(duì)象與該TreeSet集合關(guān)聯(lián)，由該Comparator對(duì)象負(fù)責(zé)集合元素的排序邏輯。
如下程序所示：
class M {
int age;
public M(int age) {
this.age = age;
}
public String toString() {
return "M對(duì)象（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對(duì)象（age：9), M對(duì)象（age：5), M對(duì)象（age：-3)]
說(shuō)明：
上面程序中創(chuàng)建了一個(gè)Comparator接口的匿名內(nèi)部類(lèi)對(duì)象，該對(duì)象負(fù)責(zé)ts集合的排序。所以當(dāng)我們把M對(duì)象添加到ts集合中時(shí)，無(wú)須M類(lèi)實(shí)現(xiàn)Comparable接口，因?yàn)榇藭r(shí)TreeSet無(wú)須通過(guò)M對(duì)象來(lái)比較大小，而是由與TreeSet關(guān)聯(lián)的Comparator對(duì)象來(lái)負(fù)責(zé)集合元素的排序。使用定制排序時(shí)，TreeSet對(duì)集合元素排序時(shí)不管集合元素本身的大小，而是由Comparator對(duì)象負(fù)責(zé)集合元素的排序規(guī)則。
案例：
學(xué)生成績(jī)排序
package 學(xué)生成績(jī)排序TreeSet;
/**
* java提供了一個(gè)Comparable接口，該接口里定義了一個(gè)compareTo方法，
* 該方法返回一個(gè)整數(shù)值，實(shí)現(xiàn)該接口的類(lèi)必須實(shí)現(xiàn)該方法，實(shí)現(xiàn)了該接口的類(lèi)的對(duì)象就可以比較大小。
* @author xcbeyond
* @date 2012-4-25 上午12:48:42
*/
public class Student implements Comparable<Student> {
private String name;
private String id;
private int chinese;//語(yǔ)文
private int math;//數(shù)學(xué)
private int english;//英語(yǔ)
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();
}
//平均成績(jī)
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é)生成績(jī)排序TreeSet;
import java.util.Scanner;
import java.util.TreeSet;
/**
* 學(xué)生平均成績(jī)排序
* @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é)號(hào)\t語(yǔ)文\t數(shù)學(xué)\t英語(yǔ)\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é)號(hào)：");
String id = input.next();
System.out.print("語(yǔ)文：");
int chinese = input.nextInt();
System.out.print("數(shù)學(xué)：");
int math = input.nextInt();
System.out.print("英語(yǔ)：");
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"));
}
}
這個(gè)代碼細(xì)心測(cè)試發(fā)現(xiàn)會(huì)發(fā)現(xiàn)，當(dāng)輸入的數(shù)據(jù)計(jì)算后，兩個(gè)人的平均成績(jī)相等時(shí)，輸出結(jié)果只會(huì)顯示其中一個(gè)人的信息，這也就符合了Set接口的定義了，“無(wú)序，不重復(fù)”
。只需稍稍修改下compareTo方法就可以解決這個(gè)問(wèn)題了。
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;
}
分類(lèi)導(dǎo)航