解决TreeSet类的排序问题

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); 
//取出第一个元素 
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对象负责集合元素的排序规则。