0%

8.3.3 TreeSet类 1.自然排序

发表于 更新于 分类于 ， ，

8.3.3 TreeSet类

TreeSet是SortedSet接口的实现类,正如SortedSet名字所暗示的, TreeSet可以确保集合元素处于排序状态。与HashSet集合相比, TreeSet还提供了如下几个额外的方法.

方法 描述
Comparator comparator() 如果TreeSet采用了定制排序,则该方法返回定制排序所使用的Comparator;如果TreeSet采用了自然排序,则返回null.
Object first() 返回集合中的第一个元素。
Object last() 返回集合中的最后一个元素。
Object lower(Object e) 返回集合中位于指定元素之前的元素(即集合中小于指定元素的最大元素,参考元素不需要是TreeSet集合里的元素)。
Object higher(Object e) 返回集合中位于指定元素之后的元素(即集合中大于指定元素的最小元素,参考元素不需要是TreeSet集合里的元素)。
SortedSet subSet(Object fromElement, Object toElement) 返回此Set的子集合,范围从fromElement(包含)到toElement(不包含)(范围前闭后开,类似String类的substring方法)。
SortedSet headSet(Object toElement) 返回此Set的子集,由小于toElement的元素组成。
SortedSet tailSet(Object fromElement) 返回此Set的子集,由大于或等于fromElement的元素组成。
表面上看起来这些方法很多,其实它们很简单:因为TreeSet中的元素是有序的,所以增加了访问第一个、前一个、后一个、最后一个元素的方法,并提供了三个从TreeSet中截取子TreeSet的方法。
下面程序测试了TreeSet的通用用法。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.*;

public class TreeSetTest
{
	public static void main(String[] args)
	{
		TreeSet nums = new TreeSet();
		// 向TreeSet中添加四个Integer对象
		nums.add(5);
		nums.add(2);
		nums.add(10);
		nums.add(-9);
		// 输出集合元素，看到集合元素已经处于排序状态
		System.out.println(nums);
		// 输出集合里的第一个元素
		System.out.println(nums.first()); // 输出-9
		// 输出集合里的最后一个元素
		System.out.println(nums.last());  // 输出10
		// 返回小于4的子集，不包含4
		System.out.println(nums.headSet(4)); // 输出[-9, 2]
		// 返回大于5的子集，如果Set中包含5，子集中还包含5
		System.out.println(nums.tailSet(5)); // 输出 [5, 10]
		// 返回大于等于-3，小于4的子集。
		System.out.println(nums.subSet(-3 , 4)); // 输出[2]
	}
}

运行效果:

1
2
3
4
5
6
[-9, 2, 5, 10]
-9
10
[-9, 2]
[5, 10]
[2]

根据上面程序的运行结果即可看出, TreeSet并不是根据元素的插入顺序进行排序的,而是根据元素实际值的大小来进行排序的.
与HashSet集合采用hash算法来决定元素的存储位置不同, TreeSet采用红黑树的数据结构来存储集合元素。那么TreeSet进行排序的规则是怎样的呢? TreeSet支持两种排序方法:自然排序和定制排序。在默认情况下, TreeSet采用自然排序。

1.自然排序

TreeSet会调用集合元素的compareTo(Object obj)方法来比较元素之间的大小关系,然后将集合元素按升序排列,这种方式就是自然排序。
Java提供了一个Comparable接口,该接口里定义了一个compareTo(Object obj)方法,该方法返回个整数值,实现该接口的类必须实现该方法,实现了该接口的类的对象就可以比较大小。当一个对象调用该方法与另一个对象进行比较时,例如obj1.compareTo(obj2),

  • 如果该方法返回0,则表明这两个对象相等;
  • 如果该方法返回一个正整数,则表明obj1大于obj2;
  • 如果该方法返回一个负整数,则表明obj小于obj2。

Java的一些常用类已经实现了Comparable接口,并提供了比较大小的标准。下面是实现了Comparable接口的常用类。

  • BigDecimal、 BigInteger以及所有的数值型对应的包装类:按它们对应的数值大小进行比较。
  • Character:按字符的unicode值进行比较。
  • Boolean:true对应的包装类实例大于false对应的包装类实例
  • String:按字符串中字符的unicode值进行比较.
  • Date、Time:后面的时间、日期比前面的时间、日期大。

如果试图把一个对象添加到TreeSet时,则该对象的类必须实现Comparable接口,否则程序将会抛出异常。如下程序示范了这个错误。

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.*;

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

运行效果:

1
2
3
4
5
Exception in thread "main" java.lang.ClassCastException: Err cannot be cast to java.lang.Comparable
	at java.util.TreeMap.compare(TreeMap.java:1290)
	at java.util.TreeMap.put(TreeMap.java:538)
	at java.util.TreeSet.add(TreeSet.java:255)
	at TreeSetErrorTest.main(TreeSetErrorTest.java:10)
  • 上面程序试图向TreeSet集合中添加两个Err对象,添加第一个对象时, TreeSet里没有任何元素,所以不会出现任何问题;
  • 当添加第二个Err对象时, TreeSet就会调用该对象的compareTo(Object obj)方法与集合中的其他元素进行比较.
    • 如果其对应的类没有实现Comparable接口,则会引发ClassCastException异常。因此,上面程序将会在①号代码处引发该异常。

注意
向TreeSet集合中添加元素时,只有第一个元素无须实现Comparable接口,后面添加的所有元素都必须实现Comparable接口。当然这也不是一种好做法,当试图从TreeSet中取出元素时,依然会引发ClassCastException异常。
还有一点必须指出:大部分类在实现compareTo( Object obj)方法时,都需要将被比较对象obj强制类型转换成相同类型,因为只有相同类的两个实例才会比较大小。
当试图把一个对象添加到TreeSet集合时, TreeSet会调用该对象的compareTo(Object obj)方法与集合中的其他元素进行比较——这就要求集合中的其他元素与该元素是同一个类的实例。也就是说,向TreeSet中添加的应该是同一个类的对象,否则也会引发ClassCastException异常。如下程序示范了这个错误。

1
2
3
4
5
6
7
8
9
10
11
12
import java.util.*;

public class TreeSetErrorTest2
{
	public static void main(String[] args)
	{
		TreeSet ts = new TreeSet();
		// 向TreeSet集合中添加两个对象
		ts.add(new String("疯狂Java讲义"));
		ts.add(new Date());   // ①
	}
}

运行效果:

1
2
3
4
5
Exception in thread "main" java.lang.ClassCastException: java.lang.String cannot be cast to java.util.Date
	at java.util.Date.compareTo(Date.java:131)
	at java.util.TreeMap.put(TreeMap.java:568)
	at java.util.TreeSet.add(TreeSet.java:255)
	at TreeSetErrorTest2.main(TreeSetErrorTest2.java:10)
  • 上面程序先向TreeSet集合中添加了一个字符串对象,这个操作完全正常。
  • 当添加第二个Date对象时, TreeSet就会调用该对象的compareTo(Object obj)方法与集合中的其他元素进行比较
    • Date对象的compareTo(Object obj)方法无法与字符串对象比较大小,所以上面程序将在①代码处引发异常

如果向TreeSet中添加的对象是程序员自定义类的对象,则可以向TreeSet中添加多种类型的对象,前提是用户自定义类实现了Comparable接口,且实现compareTo(Object obj)方法没有进行强制类型转换。但当试图取出TreeSet里的集合元素时,不同类型的元素依然会发生ClassCastException异常。

总结起来一句话:如果希望TreeSet能正常运作, TreeSet只能添加同一种类型的对象。
当把一个对象加入TreeSet集合中时, TreeSet调用该对象的compareTo(Object obj)方法与容器中的其他对象比较大小,然后根据红黑树结构找到它的存储位置。如果两个对象通过compareTo(Object obj)方法比较相等,新对象将无法添加到TreeSet集合中。

对于TreeSet集合而言,它判断两个对象是否相等的唯一标准是:两个对象通过compareTo( Object ob)方法比较是否返回0:

  • 如果通过compareTo( Object obj)方法比较返回0, TreeSet则会认为它们相等
  • 否则就认为它们不相等。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.*;

class Z implements Comparable
{
	int age;
	public Z(int age)
	{
		this.age = age;
	}
	// 重写equals()方法，总是返回true
	public boolean equals(Object obj)
	{
		return true;
	}
	// 重写了compareTo(Object obj)方法，总是返回1
	public int compareTo(Object obj)
	{
		return 1;
	}
}
public class TreeSetTest2
{
	public static void main(String[] args)
	{
		TreeSet set = new TreeSet();
		Z z1 = new Z(6);
		set.add(z1);
		// 第二次添加同一个对象，输出true，表明添加成功
		System.out.println(set.add(z1));    //①
		// 下面输出set集合，将看到有两个元素
		System.out.println(set);
		// 修改set集合的第一个元素的age变量
		 ((Z)(set.first())).age = 9;
		// 输出set集合的最后一个元素的age变量，将看到也变成了9
		System.out.println(((Z)(set.last())).age);
	}
}

程序中①代码行把同一个对象再次添加到TreeSet集合中,因为z1对象的compareTo(Object obj)方法总是返回1,虽然它的equals方法总是返回true,但TreeSet会认为z1对象和它自己也不相等,因此TreeSet可以添加两个z1对象。图8.5显示了TreeSet及Z对象在内存中的存储示意图
这里有一张图片
从图8.5可以看到TreeSet对象保存的两个元素的引用,实际上是同一个元素的引用(集合里放的总是引用)。所以当修改TreeSet集合里第一个元素的age变量后,该TreeSet集合里最后一个元素的age变量也随之改变了。

TreeSet中元素的规则

如果两个对象通过equals方法比较返回true时,这两个对象通过compareTo( Object obj)方法比较应返回0.

如果两个对象通过compareTo(Object obj)方法比较返回0时,但它们通过equals方法比较返回false将很麻烦,因为两个对象通过compareTo(Object obj)方法比较相等, TreeSet不会让第二个元素添加进去,这就会与Set集合的规则产生冲突。

如果向TreeSet中添加一个可变对象后,并且后面程序修改了该可变对象的实例变量,这将导致它与其他对象的大小顺序发生了改变,但TreeSet不会再次调整它们的顺序,甚至可能导致TreeSet中保存的这两个对象通过compareTo(Object obj)方法比较返回0。下面程序演示了这种情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.util.*;

class R implements Comparable
{
	int count;
	public R(int count)
	{
		this.count = count;
	}
	public String toString()
	{
		return "R[count:" + count + "]";
	}
	// 重写equals方法，根据count来判断是否相等
	public boolean equals(Object obj)
	{
		if (this == obj)
		{
			return true;
		}
		if(obj != null && obj.getClass() == R.class)
		{
			R r = (R)obj;
			return r.count == this.count;
		}
		return false;
	}
	// 重写compareTo方法，根据count来比较大小
	public int compareTo(Object obj)
	{
		R r = (R)obj;
		return count > r.count ? 1 :
			count < r.count ? -1 : 0;
	}
}
public class TreeSetTest3
{
	public static void main(String[] args)
	{
		TreeSet ts = new TreeSet();
		ts.add(new R(5));
		ts.add(new R(-3));
		ts.add(new R(9));
		ts.add(new R(-2));
		// 打印TreeSet集合，集合元素是有序排列的
		System.out.println(ts);    // ①
		// 取出第一个元素
		R first = (R)ts.first();
		// 对第一个元素的count赋值
		first.count = 20;
		// 取出最后一个元素
		R last = (R)ts.last();
		// 对最后一个元素的count赋值，与第二个元素的count相同
		last.count = -2;
		// 再次输出将看到TreeSet里的元素处于无序状态，且有重复元素
		System.out.println(ts);   // ②
		// 删除实例变量被改变的元素，删除失败
		System.out.println(ts.remove(new R(-2)));   // ③
		System.out.println(ts);
		// 删除实例变量没有被改变的元素，删除成功
		System.out.println(ts.remove(new R(5)));    // ④
		System.out.println(ts);
	}
}

上面程序中的R对象对应的类正常重写了equals()方法和compareTo()方法,这两个方法都以R对象的count实例变量作为判断的依据。当程序执行①行代码时,看到程序输出的Set集合元素处于有序状态;
因为R类是一个可变类,因此可以改变R对象的count实例变量的值,程序后续代码行改变了该集合里第一个元素和最后一个元素的count实例变量的值。当程序执行②行代码输出时,将看到该集合处于无序状态,而且集合中包含了重复元素。运行上面程序,看到如下所示的结果.

1
2
3
4
5
6
[R[count:-3], R[count:-2], R[count:5], R[count:9]]
[R[count:20], R[count:-2], R[count:5], R[count:-2]]
false
[R[count:20], R[count:-2], R[count:5], R[count:-2]]
true
[R[count:20], R[count:-2], R[count:-2]]

一旦改变了TreeSet集合里可变元素的实例变量,当再试图删除该对象时, TreeSet也会删除失败(甚至集合中原有的、实例变量没被修改但与修改后元素相等的元素也无法删除),所以在上面程序的③代码处,删除count为-2的R对象时,没有任何元素被删除;程序执行④代码时,可以看到删除了count为5的R对象,这表明TreeSet可以删除没有被修改实例变量、且不与其他被修改实例变量的对象重复的对象。
注意
当执行了④代码后, Tree Set会对集合中的元素重新索引(不是重新排序),接下来就可以删除TreeSet中的所有元素了,包括那些被修改过实例变量的元素。与HashSet类似的是,如果TreeSet中包含了可变对象,当可变对象的实例变量被修改时, TreeSet在处理这些对象时将非常复杂,而且容易出错。为了让程序更加健壮,推荐不要修改放入HashSet和TreeSet集合中元素的关键实例变量

原文链接: 8.3.3 TreeSet类 1.自然排序