一、TreeSet 概述
1、TreeSet是 SortedSet 接口的实现类, TreeSet 可以确保集合元素处于排序状态。
2、TreeSet顾名思义他内部维护的是一个TreeMap,底层是红黑二叉树,他使得集合内都是有序的序列。
3、Tree可以按照添加对象的指定属性,进行排序,所以向TreeSet中添加的数据,要求是相同类的对象。
4、两种排序方式:自然排序(实现Comparable接口) 和 定制排序(Comparator);
5、自然排序中,比较两个对象是否相同的标准为:compareTo()返回0.不再是equals();
6、定制排序中,比较两个对象是否相同的标准为:compare()返回0.不再是equals();
7、对 TreeSet进行遍历的时候,默认是使用自然排序的规则来排序的;
8、TreeSet 添加自定义类的对象时候,必须要有自然排序或定制排序,否则抛出异常:cannot cast to java.lang.Comparable;
二、TreeSet 结构
1、TreeSet 声明
1 public class TreeSet<E> extends AbstractSet<E> 2 implements NavigableSet<E>, Cloneable, java.io.Serializable
2、TreeSet 类继承结构
3、红黑树
TreeSet
和后要的TreeMap
采用红黑树的存储结构
特点:有序,查询速度比List快
三、TreeSet 创建
1、构造器
TreeSet是基于红黑树结构实现的,会对元素进行排序,TreeSet 提供了五种构造器:
public TreeSet() { this(new TreeMap<E,Object>()); } TreeSet(NavigableMap<E,Object> m) { this.m = m; } public TreeSet(Comparator<? super E> comparator) { this(new TreeMap<>(comparator)); } public TreeSet(Collection<? extends E> c) { this(); addAll(c); } public TreeSet(SortedSet<E> s) { this(s.comparator()); addAll(s); }
里面的 m 属性是什么:
/** * The backing map. */ private transient NavigableMap<E,Object> m; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); //加入Java开发交流君样:593142328一起吹水聊天
可以看到里面是维护了一个 NavigableMap。
2、通过 Comparator 实例创建 TreeSet
上面的四个构造函数中着重要介绍第三个,它通过Comparator
实例来创建TreeMap
,那么Comparator
到底是何方神圣呢?
通过阅读Comparator
的源码发现,这是一个用于集合类排序的辅助接口,用户需要实现compare方法。
如果用户用了这种方式创建TreeSet
,那么集合元素就不需要做额外处理,否则集合元素都需要实现Comparable
接口,因为Tree在排序的时候会调用compare
或者compareTo
方法(介绍TreeMap
的时候会具体讲解)。
下面来看看写的一个样例代码:
public class MyComparator implements Comparator<Person> { @Override public int compare(Person o1, Person o2) { return o1.age - o2.age; } } public class Person { public Integer age; public Person(Integer value) { this.age = value; } } public static void TreeSetTest() { // TreeMap在底层put元素的时候会判断是否存在Comparator实例,如果存在,则每次添加元素排序比较的时候会调用compare接口。 TreeSet<Person> set = new TreeSet<Person>(new MyComparator()); Person p1 = new Person(1); Person p2 = new Person(1); Person p3 = new Person(5); Person p4 = new Person(9); Person p5 = new Person(10); set.add(p1); set.add(p2); set.add(p3); set.add(p4); set.add(p5); Iterator<Person> i = set.iterator(); while (i.hasNext()) { Person p = (Person) i.next(); System.out.println(p.age); }//加入Java开发交流君样:593142328一起吹水聊天 }
打印结果:
1 5 9 10
四、TreeSet 方法
五、NavigableSet接口介绍
常用方法:
// 返回比当前元素小的最近的一个元素 public E lower(E e) { return m.lowerKey(e); } // 返回小于等于当前元素的最近一个元素 public E floor(E e) { return m.floorKey(e); } // 返回大于等于当前元素的最近一个元素 public E ceiling(E e) { return m.ceilingKey(e); }//加入Java开发交流君样:593142328一起吹水聊天 // 返回大于当前元素的最近一个元素 public E higher(E e) { return m.higherKey(e); }
六、TreeSet 与 比较器
1、自然排序
(1)自然排序:TreeSet会调用集合元素的 compareTo(Object obj) 方法来比较元素之间的大小关系,然后将集合元素按升序(默认情况)排列。
(2)如果试图把一个对象添加到TreeSet
时,则该对象的类必须实现 Comparable
接口。
实现Comparable
的类必须实现compareTo(Object obj)
方法,两个对象即通过compareTo(Object obj)
方法的返回值来比较大小。
(3)Comparable
的典型实现:
- ① BigDecimal、BigInteger 以及所有的数值型对应的包装类:按它们对应的数值大小进行比较;
- ② Character:按字符的 unicode值来进行比较;
- ③ Boolean:true 对应的包装类实例大于 false 对应的包装类实例;
- ④String:按字符串中字符的 unicode 值进行比较
- ⑤ Date、Time:后边的时间、日期比前面的时间、日期大
(4)向 TreeSet 中添加元素时,只有第一个元素无须比较compareTo()
方法,后面添加的所有元素都会调用compareTo()
方法进行比较。
(5)因为只有相同类的两个实例才会比较大小,所以向 TreeSet 中添加的应该是同一个类的对象。
(6)对于 TreeSet 集合而言,它判断两个对象是否相等的唯一标准是:两个对象通过 compareTo(Object obj)方法比较返回值。
(7)当需要把一个对象放入 TreeSet中,重写该对象对应的 equals()方法时,应保证该方法与 compareTo(Object obj) 方法有一致的结果:如果两个对象通过 equals() 方法比较返回 true,则通过 compareTo(Object obj)方法比较应返回 0。否则,让人难以理解。
2、定制排序
(1)TreeSet的自然排序要求元素所属的类实现Comparable接口,如果元素所属的类没有实现Comparable接口,或不希望按照升序(默认情况)的方式排列元素或希望按照其它属性大小进行排序,则考虑使用定制排序。定制排序,通过Comparator接口来实现。需要重写compare(T o1,T o2)方法。
(2)利用int compare(T o1,T o2)方法,比较o1和o2的大小:如果方法返回正整数,则表示o1大于o2;如果返回0,表示相等;返回负整数,表示o1小于o2。【面试资料】
(3)要实现定制排序,需要将实现Comparator接口的实例作为形参传递给TreeSet的构造器。
(4)此时,仍然只能向TreeSet中添加类型相同的对象。否则发生ClassCastException异常。
(5)使用定制排序判断两个元素相等的标准是:通过Comparator比较两个元素返回了0。
七、案例
1、自定义类的自然排序
案例:
public class User implements Comparable{ private String name; private int age; public User() { } public User(String name, int age) { this.name = name; this.age = age; } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } @Override public String toString() { return "User{" + "name="" + name + """ + ", age=" + age + "}"; } @Override public boolean equals(Object o) { System.out.println("User equals()...."); if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; User user = (User) o; if (age != user.age) return false; return name != null ? name.equals(user.name) : user.name == null; } @Override public int hashCode() { //return name.hashCode() + age; int result = name != null ? name.hashCode() : 0; result = 31 * result + age; return result; } //按照姓名从大到小排列,年龄从小到大排列 @Override public int compareTo(Object o) { if(o instanceof User){ User user = (User)o; // 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{//加入Java开发交流君样:593142328一起吹水聊天 throw new RuntimeException("输入的类型不匹配"); } } }
使用TreeSet保存:
@Test public void test1(){ 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()); } }
注意:如果在自然比较器中并没有对年龄进行比较,当姓名一样时,就会认为这两个对象一样,不会再次存放;
如果在比较器中对两个属性都进行了比较,当有一个属性不一样就会放入 TreeSet中。
可以发现,这里对两个对象的比较并不是使用 equals() 方法,而是使用比较器来进行比较的。
2、自定义类的定制排序
定制排序:
@Test 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)); set.add(new User("Jim",2)); set.add(new User("Mike",65)); set.add(new User("Mary",33)); set.add(new User("Jack",33)); set.add(new User("Jack",56)); Iterator iterator = set.iterator(); while(iterator.hasNext()){ System.out.println(iterator.next()); } }
总结
本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注服务器之家的更多内容!
原文链接:https://blog.csdn.net/wj1314250/article/details/118635072