SortedSet和NavigableSet是两个继承了Set接口的子接口。除了常见的Set集合操作外，这两个接口提供了一种排序来更快的访问元素的机制和方法。
概述
SortedSet和NavigableSet均是Set接口的子接口，其中SortedSet直接继承于Set，而NavigableSet则直接继承于SortedSet。SortedSet借助于接口java.lang.Comparable和java.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(); | 返回当前集合中最后（也是最大）的元素 |
NavigableSet
方法列表
| 方法声明 | 备注 |
|---|---|
| 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元素的子集合。 |
涉及基础知识点
“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()方法完成了同样的判断结果时就认为相等性是一致的。
覆盖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）的性能。
equals()和compartTo()的异同
两个方法都可以用来完成元素比较操作。
equals()方法默认比较对象的内存地址，用来比较两个对象物理上是否属于同一个对象，可以通过覆盖equals()方法实现对象的逻辑比较（即值比较）。compareTo()方法被设计用来做内容比较，如果两个通过new实例化的对象含有相同的内容，那么通过compareTo()方法比较这两个对象被认为是相等的。
equals()方法是Object的自带方法，由于Java中所有类都是Object的父类，所以所有类都继承了equals()方法。由于equals()方法有默认实现，所以equals()方法只有在实际需要的情况下才会被子类覆盖，反之则可以使用默认实现完成相关操作。而compareTo()方法是Comparable接口声明的方法，只有实现了该接口的方法才会拥有compareTo()方法。但是该方法没有任何实现，任何实现了Comparable接口的类都需要自定义实现compareTo()方法。
只有实现了Comparable接口的类才能被存储到TreeSet等依赖于内容比较的集合中。而只有equals()方法未实现compareTo()方法的类在尝试加入到上述集合中时会导致失败。
参考文献
- [美] Joshua Bloch. Effective Java 2nd Edtion[M]. Boston:Addison-Wesley.