TreeSet支持两种排序方法:自然排序和定制排序。TreeSet默认采用自然排序。
1、自然排序
TreeSet会调用集合元素的compareTo(Object obj)方法来比较元素之间大小关系,然后将集合元素按升序排列,这种方式就是自然排序。(比较的前提:两个对象的类型相同)。
java提供了一个Comparable接口,该接口里定义了一个compareTo(Object obj)方法,该方法返回一个整数值,实现该接口的类必须实现该方法,实现了该接口的类的对象就可以比较大小。当一个对象调用该方法与另一个对象进行比较,例如obj1.comparTo(obj2),如果该方法返回0,则表明这两个对象相等;如果返回一个正整数,则表明obj1大于obj2;如果该方 法返回一个负整数,则表明obj1小于obj2。
java常用类实现Comparable接口,并提供了比较大小的标准。实现Comparable接口的常用类:
l BigDecimal、BigInteger以及所有数值型对应包装类:按它们对应的数值的大小进行比较。
l Character:按字符的UNICODE值进行比较。
l Boolean:true对应的包装类实例大于false对应的包装类实例。
l String:按字符串中字符的UNICODE值进行比较。
l Date、Time:后面的时间、日期比前面的时间、日期大。
如果试图把一个对象添加进TreeSet时,则该对象的类必须实现Comparable接口。如下程序则会报错:
package cn.com.fxr.test;
class Err {}
public class TestTreeSetError {
public static void main(String[] args) {
TreeSet<Err> ts = new TreeSet<Err>();
//向TreeSet集合中添加两个Err对象
ts.add(new Err());
ts.add(new Err());
}
}
|
运行后:
Exception in thread "main" java.lang.ClassCastException:
cn.com.fxr.test.Err cannot be cast to java.lang.Comparable
at java.util.TreeMap.compare(TreeMap.java:1188)
at java.util.TreeMap.put(TreeMap.java:531)
at java.util.TreeSet.add(TreeSet.java:255)
at cn.com.fxr.test.TestTreeSetError.main(TestTreeSetError.java:14)
|
说明:
上面程序试图向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也会把它们当成两个对象进行处理。
如下程序所示:
package cn.com.fxr.test;
import java.util.TreeSet;
public class TestTreeSet {
public static void main(String[] args) {
TreeSet ts = new TreeSet();
Z z1 = new Z(6);
ts.add(z1);
System.out.println(ts.add(z1));
//下面输出set集合,将看到有2个元素
System.out.println(ts);
//修改set集合的第一个元素的age属性
((Z)(ts.first())).age = 9;
//输出set集合的最后一个元素的age属性,将看到也变成了9
System.out.println(((Z)(ts.last())).age);
}
}
//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;
}
}
运行结果:
true
[cn.com.fxr.test.Z@811c88, cn.com.fxr.test.Z@811c88]
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.
如下程序所示:
package cn.com.fxr.test;
import java.util.HashSet;
import java.util.Iterator;
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 TestHashSet {
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属性:5), R(count属性:9), R(count属性:-3), R(count属性:-2)]
[R(count属性:-3), R(count属性:9), R(count属性:-3), R(count属性:-2)]
[R(count属性:-3), R(count属性:9), R(count属性:-2)]
hs是否包含count为-3的R对象?false
hs是否包含count为5的R对象?false
|
说明:
上面程序中的R对象是一个正常重写了equals方法和comparable方法类,这两个方法都以R对象的count属性作为判断的依据。可以看 到程序第一次输出的结果是有序排列的。当改变R对象的count属性,程序的输出结果也发生了改变,而且包含了重