8.3.3 TreeSet类 1.自然排序

发表于 更新于 分类于 ， ， Waline： 本文字数： 8.5k 阅读时长 ≈ 8 分钟

8.3.3 TreeSet类

TreeSet是自动排序的集合

TreeSet是SortedSet接口的实现类,正如SortedSet名字所暗示的, TreeSet可以确保集合元素处于排序状态。

TreeSet比HashSet多出的方法

与HashSet集合相比, TreeSet还提供了如下几个额外的方法。

SortedSet接口方法

SortedSet接口方法 描述
Comparator<? super E> comparator() 如果TreeSet采用了定制排序,则该方法返回定制排序所使用的Comparator;如果TreeSet采用了自然排序,则返回null.
E first() 返回集合中的第一个元素。
SortedSet<E> headSet(E toElement) 返回此Set的子集,由小于toElement的元素组成。
E last() 返回集合中的最后一个元素。
default Spliterator<E> spliterator() Creates a Spliterator over the elements in this sorted set.
SortedSet<E> subSet(E fromElement, E toElement) 返回此Set的子集合,范围从fromElement(包含)到toElement(不包含)(范围前闭后开,类似String类的substring方法)。
SortedSet<E> tailSet(E fromElement) 返回此Set的子集,由大于或等于fromElement的元素组成。
方法 描述
E lower(E e) 返回集合中位于指定元素之前的元素(即集合中小于指定元素的最大元素,参考元素不需要是TreeSet集合里的元素)。
E higher(E e) 返回集合中位于指定元素之后的元素(即集合中大于指定元素的最小元素,参考元素不需要是TreeSet集合里的元素)。

小结

表面上看起来这些方法很多,其实它们很简单:因为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排序

根据上面程序的运行结果即可看出, TreeSet并不是根据元素的插入顺序进行排序的,而是根据元素实际值的大小来进行排序的。
与HashSet集合采用hash算法来决定元素的存储位置不同,

红黑树

TreeSet采用红黑树的数据结构来存储集合元素。

那么TreeSet进行排序的规则是怎样的呢? TreeSet支持两种排序方法:自然排序和定制排序。在默认情况下, TreeSet采用自然排序。

1.自然排序

TreeSet会调用集合元素的compareTo(Object object)方法来比较元素之间的大小关系,然后将集合元素按升序排列,这种方式就是自然排序。

Comparable接口

Java提供了一个Comparable接口,该接口里定义了一个compareTo(Object object)方法:

Comparable接口方法 描述
int compareTo(T o) Compares this object with the specified object for order.

该方法返回个整数值,实现该接口的类必须实现该方法,实现了该接口的类的对象就可以比较大小。当一个对象调用该方法与另一个对象进行比较时,例如object1.compareTo(object2)

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

实现了Comparable接口的常见类

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

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

TreeSet中的对象必须实现Comparable接口

如果试图把一个对象添加到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()方法与集合中的其他元素进行比较。
    • 如果其对应的类没有实现Comparable接口,则会引发ClassCastException异常。因此,上面程序将会在①号代码处引发该异常。

TreeSet中的第一个元素可以不实现Comparable接口

向TreeSet集合中添加元素时,只有第一个元素无须实现Comparable接口,后面添加的所有元素都必须实现Comparable接口。
当然这也不是一种好做法,当试图从TreeSet中取出元素时,依然会引发ClassCastException异常。
还有一点必须指出:大部分类在实现compareTo(Object object)方法时,都需要将被比较对象object强制类型转换成相同类型,因为只有相同类的两个实例才会比较大小。

TreeSet中应该存放同一个类的对象

当试图把一个对象添加到TreeSet集合时, TreeSet会调用该对象的compareTo(Object object)方法与集合中的其他元素进行比较——这就要求集合中的其他元素与该元素是同一个类的实例。也就是说,向TreeSet中添加的应该是同一个类的对象,否则也会引发ClassCastException异常。如下程序示范了这个错误。

程序 TreeSet中添加不同类型的对象会出现异常

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 object)方法与集合中的其他元素进行比较
    • Date对象的compareTo(Object object)方法无法与字符串对象比较大小,所以上面程序将在①代码处引发异常

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

总结 TreeSet只能添加同一种类的对象

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

相等的元素不会添加到TreeSet中

如果两个对象通过compareTo(Object object)方法比较相等,新对象将无法添加到TreeSet集合中。

compareTo返回0则TreeSet就认为这两个对象相等

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

  • 如果通过compareTo( Object object)方法比较返回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 object)
    {
        return true;
    }
    // 重写了compareTo(Object object)方法，总是返回1
    public int compareTo(Object object)
    {
        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 object)方法总是返回1,虽然它的equals方法总是返回true,但TreeSet会认为z1对象和它自己也不相等,因此TreeSet可以添加两个z1对象。图8.5显示了TreeSet及Z对象在内存中的存储示意图
这里有一张图片
从图8.5可以看到TreeSet对象保存的两个元素的引用,实际上是同一个元素的引用(集合里放的总是引用)。所以当修改TreeSet集合里第一个元素的age变量后,该TreeSet集合里最后一个元素的age变量也随之改变了。

TreeSet中元素的规则

要确保equals方法返回true时compareTo返回0

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

equals方法返回false时compareTo返回0引起的问题

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

TreeSet只会在添加元素时排序

如果向TreeSet中添加一个可变对象后,并且后面程序修改了该可变对象的实例变量,这将导致它与其他对象的大小顺序发生了改变,但**TreeSet不会再次调整它们的顺序**,甚至可能导致TreeSet中保存的这两个对象通过compareTo(Object object)方法比较返回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
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 object)
    {
        if (this == object)
        {
            return true;
        }
        if(object != null && object.getClass() == R.class)
        {
            R r = (R)object;
            return r.count == this.count;
        }
        return false;
    }
    // 重写compareTo方法，根据count来比较大小
    public int compareTo(Object object)
    {
        R r = (R)object;
        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可以删除没有被修改实例变量、且不与其他被修改实例变量的对象重复的对象。
注意
当执行了④代码后, TreeSet会对集合中的元素重新索引(不是重新排序),接下来就可以删除TreeSet中的所有元素了,包括那些被修改过实例变量的元素。与HashSet类似的是,如果TreeSet中包含了可变对象,当可变对象的实例变量被修改时, TreeSet在处理这些对象时将非常复杂,而且容易出错。

不要修改TreeSet中对象的关键实例变量值

为了让程序更加健壮,推荐不要修改放入HashSet和TreeSet集合中元素的关键实例变量