Java Collection 12 - SortedSet & NavigableSet

  SortedSet和NavigableSet是两个继承了Set接口的子接口。除了常见的Set集合操作外,这两个接口提供了一种排序来更快的访问元素的机制和方法。

概述

  SortedSet和NavigableSet均是Set接口的子接口,其中SortedSet直接继承于Set,而NavigableSet则直接继承于SortedSet。SortedSet借助于接口java.lang.Comparablejava.util.Comparator提供了一种建立在元素上的全排序(即对象中的所有字段都参与排序,在某字段相同的情况下比较下一个字段的大小关系),而这种排序手段可以允许迭代器向前或者向后访问元素。因此,SortedSet额外声明了一些方法来充分利用这种双向访问的特点。LinkedHashSet也是有序访问的,但是LinkedHashSet维护的是元素插入集合时的先后顺序,这个顺序是固定的,不会随着元素的插入发生变化。而SortedSet维护的是元素之间大小关系的顺序(比如升序、 降序等),这种顺序会随着元素的插入而发生变更。

  但是SortedSet对加入集合中的元素也提出了一些要求,即需要实现Comparable或者comparator接口。此外,这些元素相互之间可以互相比较而不会抛出ClassCastException异常。

  NavigableSet<E>直接继承了SortedSet提供了更丰富的方法来完成元素查找,常用的有lower(E e), floor(E e),ceiling(E e),higher(E e)等。 除此之外,NavigableSet<E>可以以升序或者降序的任意一种方式来完成遍历操作。需要注意的是,通过升序访问的性能会优于通过降序访问的性能。

  为了避免null引起的误会,NavigableSet<E>的实现类不鼓励允许null元素的加入。

SortedSet

方法列表

方法声明 备注
Comparator<? super E> comparator(); 返回当前集合采用的比较器
SortedSet<E> subSet(E fromElement, E toElement); 返回当前集合中大于等于fromElement且小于toElement的元素集合。对该集合的修改会同步到原始集合上,反之亦然
SortedSet<E> headSet(E toElement); 返回当前集合中小于toElement的元素集合。对该集合的修改会同步到原始集合上,反之亦然
SortedSet<E> tailSet(E fromElement); 返回当前集合中大于等于fromElement的元素集合。对该集合的修改会同步到原始集合上,反之亦然
E first(); 返回当前集合中第一个(也是最小)的元素
E last(); 返回当前集合中最后(也是最大)的元素

方法列表

方法声明 备注
E lower(E e); 返回小于元素e的最大元素,如果没有返回null
E floor(E e); 返回小于或者等于元素e的最大元素,如果没有返回null
E ceiling(E e); 返回大于或者等于元素e的最小元素,如果没有返回null
E higher(E e); 返回大于元素e的最小元素,如果没有返回null
E pollFirst(); 移除并返回集合中的最小(第一个)元素,如果集合为空返回null
E pollLast(); 移除并返回集合中的最大(最后一个)元素,如果集合为空返回null
Iterator<E> iterator(); 返回一个以升序方式迭代集合的迭代器
NavigableSet<E> descendingSet(); 返回当前集合的一个逆序集合表示。对该集合的修改会同步到原始集合上,反之亦然
Iterator<E> descendingIterator(); 返回一个以降序方式迭代集合的迭代器
NavigableSet<E> subSet(E fromElement, boolean fromInclusive,E toElement, boolean toInclusive); 返回一个以fromElement为起点,toElement为终点的子集合。由fromInclusive和toInclusive字段标记是否包含fromElement和toElement节点。
NavigableSet<E> headSet(E toElement, boolean inclusive); 返回一个小于(等于)toElement元素的子集合。由inclusive指定是否可以返回等于toElement元素的元素。
NavigableSet<E> tailSet(E fromElement, boolean inclusive); 返回一个大于(等于)fromElement元素的子集合。由inclusive指定是否可以返回等于fromElement元素的元素
SortedSet<E> subSet(E fromElement, E toElement); 返回一个大于(等于)fromElement元素、小于toElement元素的子集合。
SortedSet<E> headSet(E toElement); 返回一个小于toElement元素的子集合。
SortedSet<E> tailSet(E fromElement); 返回一个大于(等于)fromElement元素的子集合。

涉及基础知识点

  1. “consistent with equals”的意义是什么

      标识比较结果和equals()方法结果一致。在java.lang.Comparable<T>接口中对“consistent with equals”做了如下定义:

    The natural ordering for a class C is said to be consistent with equals if and only if e1.compareTo(e2) == 0 has the same boolean value as e1.equals(e2) for every e1 and e2 of class C. Note that null is not an instance of any class, and e.compareTo(null) should throw a NullPointerException even though e.equals(null) returns false.

      翻译过来就是如果一个对象的自然排序被认为是consistent with equals当且仅当通过通过compareTo()和通过equals()方法可以得到一致的判断结果。如果是null元素,那么equals()方法返回false的同时compareTo()会抛出一个NullPointerException 异常。

      在java中,==用来比较两个变量是否相等。如果运算数是基本数据类型,那么==比较的是值,如果运算数是对象,那么==比较的是对象在内存中的地址。equals()方法的默认实现也是比较对象在内存中的地址。而compareTo()方法则需要被实现来完成元素之间的比较。只有equals()方法和compareTo()方法完成了同样的判断结果时就认为相等性是一致的。

  2. 覆盖equals()方法需要遵守的约定

      在《Effective Java》中,介绍了如下的几条规则:

    自反性(reflexive)。对于任何非 null 的引用值 x,x.equals(x) 必须返回 true 。

    对称性(symmetric)。对于任何非 null 的引用值 x 和 y,当且仅当 y.equals(x) 返回 true时,x.equals(y) 必须返回 true 。

    传递性(transitive)。对于任何非 null 的引用值 x 、 y 和 z 。如果 x.equals(y) 返回 true ,并且 y.equals(z) 也返回 true ,那么 x.equals(z) 也必须返回 true 。

    一致性(consistent)。对于任何非 null 的引用值 x 和 y ,只要 equals 的比较操作在对象中所用的信息没有被修改,多次调用 x.equals(x) 就会一致地返回 true ,或者一致的返回 false 。

    对于任何非 null 的引用值 x , x.equals(null) 必须返回 false 。

      如果确实需要覆盖equals()方法,那么需要同时覆盖hashCode()方法。否则无法保证可以在基于散列的集合中存储使用只覆盖了equals()方法的类。在覆盖hashCode()方法时,需要遵循如下规则:

    在应用程序的执行期间,只要对象的 equals 方法的比较操作所用到的信息没有被修改,那么对同一个对象调用多次, hashCode 方法都必须始终如一地返回同一个整数。在同一个应用程序的多次执行过程中 ,每次执行所返回的整数可以不一致。

    如果两个对象根据 equals(Object) 方法比较是相等的,那么调用这两个对象中任意一个对象的hashCode方法都必须产生同样的整数结果。

    如果两个对象根据 equals(Object) 方法比较是不等的,那么调用这两个对象中任意一个对象的hashCode 方法,则不一定要产生不同的整数结果。但是程序员应该知道,给不相等的对象产生截然不同的整数结果,有可能提高散列表(hash table)的性能。

  3. equals()和compartTo()的异同

      两个方法都可以用来完成元素比较操作。

      equals()方法默认比较对象的内存地址,用来比较两个对象物理上是否属于同一个对象,可以通过覆盖equals()方法实现对象的逻辑比较(即值比较)。compareTo()方法被设计用来做内容比较,如果两个通过new实例化的对象含有相同的内容,那么通过compareTo()方法比较这两个对象被认为是相等的。

      equals()方法是Object的自带方法,由于Java中所有类都是Object的父类,所以所有类都继承了equals()方法。由于equals()方法有默认实现,所以equals()方法只有在实际需要的情况下才会被子类覆盖,反之则可以使用默认实现完成相关操作。而compareTo()方法是Comparable接口声明的方法,只有实现了该接口的方法才会拥有compareTo()方法。但是该方法没有任何实现,任何实现了Comparable接口的类都需要自定义实现compareTo()方法。

      只有实现了Comparable接口的类才能被存储到TreeSet等依赖于内容比较的集合中。而只有equals()方法未实现compareTo()方法的类在尝试加入到上述集合中时会导致失败。

参考文献

  1. [美] Joshua Bloch. Effective Java 2nd Edtion[M]. Boston:Addison-Wesley.




------------- End of this article, thanks! -------------


  版权声明:本文由Nathan R. Lee创作和发表,采用署名(BY)-非商业性使用(NC)-相同方式共享(SA)国际许可协议进行许可,转载请注明作者及出处。
  本文作者为 Nathan R. Lee
  本文标题为 Java Collection 12 - SortedSet & NavigableSet
  本文链接为 https://marcuseddie.github.io/2018/java-Collection-SortedSet-NavigableSet.html