Saul's blog
SaulJWu
2020-12-27

TreeSet

# 前言

Java 集合可分为Collection 和Map 两种体系:

  • Collection接口：单列数据，定义了存取一组对象的方法的集合
    • List：元素有序、可重复的集合
      • ArrayList、LinkedList、Vector
    • Set：元素无序、不可重复的集合
      • HashSet、LinkedHashSet、TreeSet
  • Map接口：双列数据，保存具有映射关系“key-value对”的集合，也称为键值对。
    • HashMap、LinkedHashMap、TreeMap、Hashtable、Properties

接下来学习Set接口的实现类TreeSet

# 概述

  • TreeSet是SortedSet接口的实现类，TreeSet可以确保集合元素处于排序状态。
  • TreeSet基于TreeMap实现，底层使用红黑树结构存储数据。
  • TreeSet只能存储相同类型的对象。
  • TreeSet两种排序方法：自然排序和定制排序。默认情况下，TreeSet采用自然排序。

# 底层结构

  • TreeSet和后面要讲的TreeMap采用红黑树的存储结构
  • 特点：有序，查询速度比List快

image-20201226210408937

说明：

假设使用数字来代表一个对象，比18小的都放左边，比18大的对象放右边。

所以14是在18的左边，22在18的右边。

接下来TreeSet添加了10，比18小，所以肯定在18的左边里面，那么18的左边里面，又比14小，所以放在14的左边。

TreeSet添加了15，比18小，所以肯定在18的左边里面，那么18的左边里面，又比14大，所以放在14的右边。

TreeSet添加了8，比18小，所以肯定在18的左边里面，那么18的左边里面，又比10小，所以放在10的左边

……

这就是红黑树结构，也叫二叉查找树。

8也比15小啊，为什么没有放在15的左边，这里涉及了红黑树底层，以后会讲到，目前只需要了解什么是红黑树结构。

测试案例

我们来尝试添加多个不同类型的元素看看：

@Test
public void test3() {
    TreeSet set = new TreeSet();
    set.add(123);
    set.add(456);
    set.add("AA");
    set.add(new Person("Tom", 12));
    Iterator iterator = set.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

结果：

java.lang.ClassCastException: java.lang.Integer cannot be cast to java.lang.String
1

说明TreeSet只能存储相同类型的对象。

试试相同类型是否能存储以及它的排序。

@Test
public void test3() {
    TreeSet set = new TreeSet();
    set.add(123);
    set.add(456);
    set.add(33);
    set.add(65);
    set.add(-55);
    Iterator iterator = set.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

结果：

-55
33
65
123
456
1
2
3
4
5

发现它能存储了，而且是从小到大排序的。

试试自定义类型的对象的排序

@Test
public void test4() {
    TreeSet set = new TreeSet();
    set.add(new Person("Tom", 12));
    set.add(new Person("Jerry", 32));
    set.add(new Person("Jim", 2));
    set.add(new Person("Mike", 65));
    set.add(new Person("Jack", 74));
    Iterator iterator = set.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

结果程序报错：

java.lang.ClassCastException: Person cannot be cast to java.lang.Comparable

	at java.util.TreeMap.compare(TreeMap.java:1294)
	at java.util.TreeMap.put(TreeMap.java:538)
	at java.util.TreeSet.add(TreeSet.java:255)
1
2
3
4
5

发现它要调用对象的Comparable接口，而实现Comparable 的类必须实现compareTo(Object obj) 方法，两个对象即通过compareTo(Object obj) 方法的返回值来比较大小。

# 自然排序

  • TreeSet会调用集合元素的compareTo(Object obj) 方法来比较元素之间的大小关系，然后将集合元素按升序(默认情况)排列
  • 如果试图把一个对象添加到TreeSet时，则该对象的类必须实现Comparable 接口。
    • 实现Comparable 的类必须实现compareTo(Object obj) 方法，两个对象即通过compareTo(Object obj) 方法的返回值来比较大小。
    • 自然排序中，比较2个对象是否相同的标准：compareTo(Object obj) 方法返回0，不再是equals方法。
  • Comparable 的典型实现：
    • BigDecimal、BigInteger 以及所有的数值型对应的包装类：按它们对应的数值大小进行比较
    • Character：按字符的unicode值来进行比较
    • Boolean：true 对应的包装类实例大于false 对应的包装类实例
    • String：按字符串中字符的unicode 值进行比较
    • Date、Time：后边的时间、日期比前面的时间、日期大。

既然这样，上面案例我就得把Person类实现Comparable 接口，并且compareTo方法就可以了。

先只比较一个属性，试试刚才的测试案例

  • 按照姓名从小到大排列
@Override
public int compareTo(Object o) {
    if (o instanceof Person) {
        Person person = (Person) o;
        return this.name.compareTo(person.name);
    }
    throw new RuntimeException("对象类型不一致……");
}
1
2
3
4
5
6
7
8
  • 测试案例
@Test
public void test4() {
    TreeSet set = new TreeSet();
    set.add(new Person("Tom", 12));
    set.add(new Person("Jerry", 32));
    set.add(new Person("Jim", 2));
    set.add(new Person("Mike", 65));
    set.add(new Person("Jack", 74));
    Iterator iterator = set.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
  • 输出结果
Person{name='Jack', age=74}
Person{name='Jerry', age=32}
Person{name='Jim', age=2}
Person{name='Mike', age=65}
Person{name='Tom', age=12}
1
2
3
4
5

确实也实现了我们的需求。

接下来试试2个相同名字的对象

  • 测试案例
@Test
public void test5() {
    TreeSet set = new TreeSet();
    set.add(new Person("Tom", 12));
    set.add(new Person("Tom", 52));
    Iterator iterator = set.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}
1
2
3
4
5
6
7
8
9
10
  • 输出结果
Person{name='Tom', age=12}
1

发现只添加了第一个对象，第二个对象没有添加成功

把另一个属性也放入compareTo中

  • 年龄从小到大排列
@Override
public int compareTo(Object o) {
    if (o instanceof Person) {
        Person person = (Person) o;
        int compare = this.name.compareTo(person.name);
        return compare == 0 ? Integer.compare(this.age, person.age) : compare;
    }
    throw new RuntimeException("对象类型不一致……");
}
1
2
3
4
5
6
7
8
9
  • 测试案例
@Test
public void test5() {
    TreeSet set = new TreeSet();
    set.add(new Person("Tom", 52));
    set.add(new Person("Tom", 42));
    set.add(new Person("Tom", 32));
    set.add(new Person("Tom", 72));
    set.add(new Person("Tom", 12));
    Iterator iterator = set.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
  • 结果
Person{name='Tom', age=12}
Person{name='Tom', age=32}
Person{name='Tom', age=42}
Person{name='Tom', age=52}
Person{name='Tom', age=72}
1
2
3
4
5

这就实现了自然排序，除非2个对象的name和age都相等，否则就算是不是同一个对象。

自然排序中，比较2个对象是否相同的标准：compareTo(Object obj) 方法返回0，不再是equals方法。

# 定制排序

  • TreeSet的自然排序要求元素所属的类实现Comparable接口，如果元素所属的类没有实现Comparable接口，或不希望按照升序(默认情况)的方式排列元素或希望按照其它属性大小进行排序，则考虑使用定制排序。定制排序，通过Comparator接口来实现。需要重写compare(T o1,T o2)方法。
  • 利用int compare(T o1,T o2)方法，比较o1和o2的大小：
    • 如果方法返回正整数，则表示o1大于o2；
    • 如果返回0，表示相等；
    • 返回负整数，表示o1小于o2。
  • 要实现定制排序，需要将实现Comparator接口的实例作为形参传递给TreeSet的构造器。
  • 此时，仍然只能向TreeSet中添加类型相同的对象。否则发生ClassCastException异常。
  • 定制排序中，判断两个元素相等的标准是：通过Comparator比较两个元素返回了0。

具体实现

@Test
public void test6() {
    Comparator comparator = new Comparator() {
        //按照年龄从大到小排列
        @Override
        public int compare(Object o1, Object o2) {
            if (o1 instanceof Person && o2 instanceof Person) {
                Person p1 = (Person) o1;
                Person p2 = (Person) o2;
                int result = -Integer.compare(p1.getAge(), p2.getAge());
                return result == 0 ? p1.getName().compareTo(p2.getName()) : result;
            }
            throw new RuntimeException("数据类型不是Person……");
        }
    };
    //把comparator接口放入TreeSet中
    TreeSet set = new TreeSet(comparator);
    set.add(new Person("Tom", 52));
    set.add(new Person("Tom", 42));
    set.add(new Person("Tom", 32));
    set.add(new Person("Tom", 72));
    set.add(new Person("Tom", 12));
    Iterator iterator = set.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}
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
  • 结果
Person{name='Tom', age=72}
Person{name='Tom', age=52}
Person{name='Tom', age=42}
Person{name='Tom', age=32}
Person{name='Tom', age=12}
1
2
3
4
5

虽然Person类中，自带将年龄从小到大排列的compareTo方法，但是这次TreeSet实例化时，用了Comparator的具体实现，所以是优先按Comparator的compare(Object o1, Object o2) 方法，年龄自然是从大到小排序。

记得要比较全部属性，不然相同年龄的2个人，就会按照先来后到的方式，后面来的元素就添加失败了。

# 新增方法

  • Comparator comparator()
  • Object first()
  • Object last()
  • Object lower(Object e)
  • Object higher(Object e)
  • SortedSet subSet(fromElement, toElement)
  • SortedSet headSet(toElement)
  • SortedSet tailSet(fromElement)

因为TreeSet其实开发中用得很少，这里就不展开了说明了，日后需要用到参考API即可。

帮我改善此页面 (opens new window)
#TreeSet
上次更新: 2020/12/27, 05:00:47
LinkedHashSet
Map

← Map→

最近更新
01
zabbix学习笔记二
02-28
02
zabbix学习笔记一
02-10
03
Linux访问不了github
12-08
更多文章>
Theme by Vdoing | Copyright © 2020-2022 Saul.J.Wu | MIT License