Java 集合框架系列九：JDK 1.8 SortedSet 和 NavigableSet 详解

我会带着你远行 2022-12-05 01:37 352阅读 0赞

## SortedSet 继承关系 ##

![在这里插入图片描述][2020090818320921.png_pic_center]  
SortedSet 直接继承了 Set，是 JDK 1.2 提供的接口，SortedSet 意为按照对象的比较方法对元素排序，而不是元素的插入顺序，插入顺序用 LinkedHashSet 来保存即可，SortedSet 是以自然排序或者按照 Comparator 排序。由于乱序的数据查找性能略差，无法使用二分法等高效的查找算法，如果数据在插入时就排好顺序，查找的性能就会提升很多。SortedMap 接口就是为这种有序数据服务的。

SortedSet 已知实现类有：ConcurrentSkipListSet 和 TreeSet。SortedSet 要求插入到 SortedSet 中的元素必须实现 Comparable 接口或者可以被 Comparator 进行比较。

所有 SortedSet 的实现类都应该提供四个标准构造方法：

*  无参构造方法，它根据元素的自然顺序创建一个空的 SortedSet 。
 *  具有一个 Comparator 类型的参数的构造方法，它创建一个根据指定的 Comparator 排序的空的 SortedSet。
 *  具有一个 Collection 类型的参数的构造方法，它创建一个新的排序集，该集的元素与其参数相同，并根据元素的自然顺序排序。
 *  传入 SortedSet 类型的单参数的构造方法，它用与输入排序集相同的元素和相同的顺序创建一个新的排序集。

## SortedSet API ##

SortedSet 在 Set 接口的基础上添加了几个新的方法，主要提供了获取子集，以及获取最大值（最后一个值）和最小值（第一个值）的方法。如下：

public interface SortedSet<E> extends Set<E> { 
        /** * 返回比较器，如果是自然排序返回 null */
        Comparator<? super E> comparator();
    
        /** * 返回 e1 和 e2 之间的元素，包括 e1,不包括 e2 */
        SortedSet<E> subSet(E fromElement, E toElement);
    
        /** * 返回 e 之前的元素，不包括 e */
        SortedSet<E> headSet(E toElement);
    
        /** * 返回 e 之后的元素，不包括 e */
        SortedSet<E> tailSet(E fromElement);
    
        /** * 返回第一个元素 */
        E first();
    
        /** * 返回最后一个元素 */
        E last();
    
        @Override
        default Spliterator<E> spliterator() { 
            return new Spliterators.IteratorSpliterator<E>(
                    this, Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED) { 
                @Override
                public Comparator<? super E> getComparator() { 
                    return SortedSet.this.comparator();
                }
            };
        }
    }

## NavigableSet 继承关系 ##

![在这里插入图片描述][20200908183921330.png_pic_center]  
NavigableSet 继承自 SortedSet，在 JDK 1.6 才提供，相比于 SortedSet，NavigableSet 扩展了如下功能：

*  直接获取符合条件的最近的元素，这里条件主要是 lower(>)、 floor(>=)、 higher(<)、 ceiling(<=)。如果符合条件的元素不存在，就返回 null。
 *  逆向访问：descendingSet，descendingIterator。
 *  获取并弹出最大/最小值：pollFirst，pollLast。
 *  增强了 subSet 和 tailSet
 *  SortedSet 返回的集合边界是左闭右开的（也就是说，\[a, b)），NavigableSet 提供了另一个版本，制定左右边界是否闭合。

## NavigableSet API ##

public interface NavigableSet<E> extends SortedSet<E> { 
        /** * 严格返回小于元素e的最大元素，没有则返回null */
        E lower(E e); 
     
        /** *返回小于或者等于元素e的最大元素，没有则返回null */
        E floor(E e);
     
        /** * 返回大于或者等于元素e的最小元素，没有则返回null */
        E ceiling(E e);
     
        /** * 严格返回大于元素e的最小元素，没有则返回null */
        E higher(E e);
     
        /** * 返回并移除集合中第一个元素，没有则返回null */
        E pollFirst();
     
        /** * 返回并移除集合中最后一个元素，没有则返回null */
        E pollLast();
     
        /** * 按升序返回此集合中元素的迭代器 */
        Iterator<E> iterator();
     
        /** * 返回包含该集合中元素的逆序视图 */
        NavigableSet<E> descendingSet();
     
        /** * 按降序返回此集合中元素的迭代器。 */
        Iterator<E> descendingIterator();
     
        /** * 返回集合中在fromElement到toElement的元素构成的新集合，fromInclusive和toInclusive表示是否包含头和尾 */
        NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                               E toElement,   boolean toInclusive);
     
        /** * 返回小于toElement的元素构成的新集合，inclusive表示是否包含元素toElement */
        NavigableSet<E> headSet(E toElement, boolean inclusive);
     
        /** * 返回大于toElement的元素构成的新集合，inclusive表示是否包含元素fromElement */
        NavigableSet<E> tailSet(E fromElement, boolean inclusive);
     
        /** * <p>Equivalent to {@code subSet(fromElement, true, toElement, false)}. * 返回集合中在fromElement到toElement的元素构成的新集合，fromInclusive和toInclusive表示包含头不包含尾 */
        SortedSet<E> subSet(E fromElement, E toElement);
     
        /** * <p>Equivalent to {@code headSet(toElement, false)}. * 返回小于toElement的元素构成的新集合，不包含元素toElement */
        SortedSet<E> headSet(E toElement);
     
        /** * <p>Equivalent to {@code tailSet(fromElement, true)}. * 返回大于toElement的元素构成的新集合，不包含元素toElement */
        SortedSet<E> tailSet(E fromElement);
    
    }

[2020090818320921.png_pic_center]: /images/20221123/8988a3058ad74644a944a8dae9337011.png
[20200908183921330.png_pic_center]: /images/20221123/6749e2a4f28f49a69b6053355453b69b.png