Set 接口的实现类 TreeSet 介绍

2020-11-19 0 By admin

五、TreeSet 介绍

TreeSet是SortedSet接口的实现类,TreeSet可以确保集合元素处于排序状态。TreeSet底层使用红黑树结构存储数据。
新增的方法如下:

	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两种排序方法:自然排序和定制排序。默认情况下,TreeSet采用自然排序。

5.1、TreeSet的自然排序

TreeSet和后面要讲的TreeMap采用红黑树的存储结构;特点:有序,查询速度比List快。
自然排序:TreeSet会调用集合元素的compareTo(Object obj)方法来比较元素之间的大小关系,然后将集合元素按升序(默认情况)排列。

如果试图把一个对象添加到 TreeSet 时,则该对象的类必须实现Comparable 接口。
实现Comparable 的类必须实现compareTo(Object obj)方法,两个对象即通过compareTo(Object obj)方法的返回值来比较大小。

Comparable 的典型实现:

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

向TreeSet中添加元素的过程:

  1. 向TreeSet中添加元素时,只有第一个元素无须比较compareTo()方法,后面添加的所有元素都会调用compareTo()方法进行比较。
  2. 因为只有相同类的两个实例才会比较大小,所以向TreeSet中添加的应该是同一个类的对象
  3. 对于TreeSet集合而言,它判断两个对象是否相等的唯一标准是:两个对象通过compareTo(Object obj)方法比较返回值
  4. 当需要把一个对象放入TreeSet中,重写该对象对应的equals()方法时,应保证该方法与compareTo(Object obj) 方法有一致的结果。
  5. 如果两个对象通过equals()方法比较返回true,则通过compareTo(Object obj)方法比较应返回0。否则,让人难以理解。
红黑树
红黑树

向TreeSet中添加的数据

  1. 向TreeSet中添加的数据,要求是相同类的对象。
  2. 两种排序方式:自然排序(实现Comparable接口) 和 定制排序(Comparator)
  3. 自然排序中,比较两个对象是否相同的标准为:compareTo()返回0.不再是equals().
  4. 定制排序中,比较两个对象是否相同的标准为:compare()返回0.不再是equals().
public class TreeSetTest {
 @Test
 public void test() {
  TreeSet set = new TreeSet();
  set.add(new User("Tom",12));
  set.add(new User("Jerry",32));
  set.add(new User("Jim",2));
  set.add(new User("Mike",65));
  set.add(new User("Jack",33));
  set.add(new User("Jack",56));
  Iterator iterator = set.iterator();
  while(iterator.hasNext()){
   System.out.println(iterator.next());
  }
 }
}
//////////////// User.java
public class User implements Comparable{
 private String name;
 private int age;
// 构造函数、setXX()、getXX()、equals()、hashCode()
//按照姓名从大到小排列,年龄从小到大排列
 @Override
 public int compareTo(Object o) {
  if (o instanceof User) {
   User user = (User) o;
//   return this.name.compareTo(user.name);  //按照姓名从小到大排列
//   return -this.name.compareTo(user.name);  //按照姓名从大到小排列
   int compare = -this.name.compareTo(user.name);  //按照姓名从大到小排列
   if(compare != 0){  //年龄从小到大排列
    return compare;
   }else{
    return Integer.compare(this.age,user.age);
   }
  } else {
   throw new RuntimeException("输入的类型不匹配");
  }
 }
}

5.2、TreeSet的定制排序

TreeSet的自然排序要求元素所属的类实现Comparable接口。
如果元素所属的类没有实现Comparable接口,或不希望按照升序(默认情况)的方式排列元素或希望按照其它属性大小进行排序,则考虑使用定制排序。

定制排序通过Comparator接口来实现。需要重写compare(T o1,T o2)方法。
利用 int compare(T o1,T o2) 方法,比较o1和o2的大小:如果方法返回正整数,则表示o1大于o2;如果返回0,表示相等;返回负整数,表示o1小于o2。

  1. 要实现定制排序,需要将实现 Comparator接口的实例作为形参传递给TreeSet的构造器。
  2. 此时,仍然只能向TreeSet中添加类型相同的对象。否则发生ClassCastException异常。
  3. 使用定制排序判断两个元素相等的标准是:通过Comparator比较两个元素返回了0。
 public void test2(){
  Comparator com = new Comparator() {
   //按照年龄从小到大排列
   @Override
   public int compare(Object o1, Object o2) {
    if(o1 instanceof User && o2 instanceof User){
     User u1 = (User)o1;
     User u2 = (User)o2;
     return Integer.compare(u1.getAge(),u2.getAge());
    }else{
     throw new RuntimeException("输入的数据类型不匹配");
    }
   }
  };
  TreeSet set = new TreeSet(com);
  set.add(new User("Tom",12));
  set.add(new User("Jerry",32));

  Iterator iterator = set.iterator();
  while(iterator.hasNext()){
   System.out.println(iterator.next());
  }
 }