Java 集合之 SortedSet 和 SortedMap

一时失言乱红尘 2024-04-07 15:03 135阅读 0赞

**目录**

1、 SortedSet 接口

（1）Set 操作

（2）范围操作

（3）端点操作

（4）比较器访问

2、SortedMap 接口

--------------------

### 1、 SortedSet 接口 ###

SortedSet 是一个按升序维护其元素的集合，根据元素的自然顺序或根据 SortedSet 创建时提供的Comparator进行排序。除了普通的Set操作外，SortedSet接口还提供以下操作:

*  `范围操作` — 允许对排序集进行任意范围操作
 *  端点操作 — 返回排序集的第一个或最后一个元素
 *  `访问比较器` — 返回用于对Set排序的Comparator(如果有的话)

下面是SortedSet接口的代码：

package java.util;
    public interface SortedSet<E> extends Set<E> {
        // 返回对集合中的元素排序的比较器，如果集合使用其元素的Comparable自然排序，则返回null。
        Comparator<? super E> comparator();
    
        // 返回该集合中元素范围从fromElement(包括)到toElement(排除)的部分的视图。
        // (如果fromElement和toElement相等，返回的集合为空。)
        SortedSet<E> subSet(E fromElement, E toElement);
    
        // 返回该集合中元素从开始元素到 toElement 的视图。
        SortedSet<E> headSet(E toElement);
    
        // 返回该集合中元素从 fromElement 到最后元素的视图。
        SortedSet<E> tailSet(E fromElement);
    
        // 返回当前集合中的第一个(最低的)元素。
        E first();
    
        // 返回当前在此集合中的最后(最高)元素
        E last();
    }

#### （1）Set 操作 ####

SortedSet 继承自 Set 的操作在 sorted sets 和 普通的 sets 的行为完全相同，只有两个例外:

*  迭代器操作返回的Iterator按顺序遍历已排序的集合。
 *  toArray返回的数组按顺序包含已排序集合的元素。

尽管 Set 接口不能保证 toString 方法的顺序，但是Java平台 SortedSet 实现的toString方法按顺序返回一个包含排序集所有元素的字符串。

**标准构造函数**

按照约定，所有Collection的实现都实现了Collection接口的标准转换构造函数，SortedSet的实现也不例外。在TreeSet中，这个构造函数将创建一个实例，该实例根据元素的自然顺序对元素进行排序。

![1f7397b6b2b94f618c60567ff35464e6.png][]

但是，最好是动态地去检查指定的集合是否为SortedSet实例，如果是，则根据相同的条件(比较器或自然排序)对新的TreeSet进行排序。因为TreeSet采用了它以前的做法，所以它还提供了一个构造函数，该构造函数接受SortedSet并返回一个新的TreeSet，其中包含按照相同条件排序的相同元素。在编译时决定调用这两个构造函数中的哪一个(以及是否保留排序条件)。![8a8e3fc94aa24d0a86b27ac4e5b87999.png][]

实现还按照约定提供了一个构造函数，该构造函数接受一个Comparator，并根据指定的Comparator返回一个空的有序集实例。如果将null传递给这个构造函数，它将返回一个集合实例，该集合根据元素的自然顺序对元素进行排序。

#### （2）范围操作 ####

SortedSet 的范围操作有点类似于List接口提供的范围操作，但是有一个很大的区别。如果直接修改了支持的排序集，排序集的范围视图仍然有效。因为排序集的范围视图的端点是元素空间中的绝对点，而列表范围视图的端点是支持集合(list)中的特定元素。一个有序集合的范围视图实际上只是一个窗口，它指向位于元素空间指定部分的集合的任何部分。对范围视图的更改会写回支持的排序集，反之亦然。因此，与在列表上使用范围视图不同，在长时间内对已排序的集合使用范围视图是可以的。// 这个问题可以通过程序验证一下

SortedSet 提供三个范围操作方法。第一个方法是 subSet ，它接受两个端点。接收的端点参数是对象而不是索引，并且必须与 SortedSet 中的元素具有可比性。和subblist一样，区间是半开的，左闭右开区间（包括左边，但不包括右边）。

下列代码代码中统计`SortedSet`集合`dictionary`中`"doorbell"` 和 `"pickle"之间包含了多少元素：`

int count = dictionary.subSet("doorbell", "pickle").size();

下面的一行程序删除了所有以字母在 \[" f ", " g ") 中开头的元素。

dictionary.subSet("f", "g").clear();
    
    // 示例
    public static void main(String[] args) {
            SortedSet<String> set = new TreeSet<>();
            set.add("was");set.add("elements");set.add("beginning");
            set.add("code");set.add("with");set.add("many");set.add("between");
            // 统计 SortedSet 集合中，每个字母开头的单词有多少
            set.forEach(x-> System.out.print(x+" "));System.out.println("");
            set.subSet("b","m").clear(); // 清除指定元素
            set.forEach(x-> System.out.print(x+" "));
        }

输出结果：

*  beginning between code elements many was with
 *  many was with

统计 SortedSet 集合中，每个字母开头的单词有多少

public static void main(String[] args) {
            SortedSet<String> set = new TreeSet<>();
            set.add("was");set.add("elements");set.add("beginning");
            set.add("code");set.add("with");set.add("many");set.add("between");
            // 统计 SortedSet 集合中，每个字母开头的单词有多少
            for (char ch = 'a'; ch <= 'z'; ) {
                String from = String.valueOf(ch++);
                String to = String.valueOf(ch);
                System.out.print(from + ": " + set.subSet(from, to).size() + "|");
            }
        }
    // 输出
    a: 0|b: 2|c: 1|d: 0|e: 1|f: 0|g: 0|h: 0|i: 0|j: 0|k: 0|l: 0|m: 1|n: 0|o: 0|p: 0|q: 0|r: 0|s: 0|t: 0|u: 0|v: 0|w: 2|x: 0|y: 0|z: 0|

如果想查看包含两个端点的封闭区间，且元素类型允许计算元素空间中给定值的后继节点，那么只需要请求从lowEndpoint到后继节点(highEndpoint)的子集。比如，在string的自然顺序中，字符串s的继承者是s +“\\0”（即，s加上一个空字符）。

包含两个端点的封闭区间示例：

int count = dictionary.subSet("doorbell", "pickle\0").size();
    // 测试数据
    public static void main(String[] args) {
            SortedSet<String> dictionary = new TreeSet<>();
            dictionary.add("was");dictionary.add("elements");dictionary.add("beginning");
            dictionary.add("code");dictionary.add("with");dictionary.add("many");dictionary.add("between");
            dictionary.add("doorbell");dictionary.add("pickle");
            // 统计 SortedSet 集合中，每个字母开头的单词有多少
            dictionary.forEach(x->System.out.print(x+" "));
            System.out.print(""); // 换行
            int count = dictionary.subSet("doorbell", "pickle\0").size();
            System.out.println("doorbell to pickle num:"+ count);
        }

输出结果：

*  beginning between code doorbell elements many picklewas with
 *  doorbell to pickle num:4 // 非封闭区间为3

类似的双开区间示例代码如下：

int count = dictionary.subSet("doorbell\0", "pickle").size();

SortedSet 接口包含另外两个范围视图操作— headSet 和 tailSet，

SortedSet<String> volume1 = dictionary.headSet("e");
    SortedSet<String> volume2 = dictionary.tailSet("e");
    
    // 示例程序
    public static void main(String[] args) {
            SortedSet<String> dictionary = new TreeSet<>();
            dictionary.add("was");dictionary.add("elements");dictionary.add("beginning");
            dictionary.add("code");dictionary.add("with");dictionary.add("many");dictionary.add("between");
            dictionary.add("doorbell");dictionary.add("pickle");
            // 统计 SortedSet 集合中，每个字母开头的单词有多少
            dictionary.forEach(x->System.out.print(x+" "));System.out.println("");
            SortedSet<String> volume1 = dictionary.headSet("e");
            volume1.forEach(x->System.out.print(x+" ")); System.out.println("");
            SortedSet<String> volume2 = dictionary.tailSet("e");
            volume2.forEach(x->System.out.print(x+" "));
        }

输出结果：

*  dictionary：beginning between code doorbell elements many pickle was with
 *  headSet：beginning between code doorbell
 *  tailSet：elements many pickle was with

#### （3）端点操作 ####

SortedSet 接口调用 first 和 last 方法返回排序集中的第一个和最后一个元素的操作，在 SortedSet 集合中，可能希望进入Set的内部并向前或向后迭代。从内部向前迭代比较容易实现：只需要获得一个尾集并在其上进行迭代，但是比较麻烦的是向后迭代。

String last = dictionary.headSet("e").last();
    
    // 示例代码
    public static void main(String[] args) {
            SortedSet<String> dictionary = new TreeSet<>();
            dictionary.add("was");dictionary.add("elements");dictionary.add("beginning");
            dictionary.add("code");dictionary.add("with");dictionary.add("many");dictionary.add("between");
            dictionary.add("doorbell");dictionary.add("pickle");
            // 统计 SortedSet 集合中，每个字母开头的单词有多少
            dictionary.forEach(x->System.out.print(x+" "));System.out.println("");
            String last = dictionary.headSet("e").last();
            System.out.println(last);
        }

上边方法实现了从排序集合内部的一个点向后移动一个元素。虽然可以重复应用它来实现向后迭代，但这种方法非常低效，需要查找返回的每个元素。// 仅作示例

#### （4）比较器访问 ####

SortedSet 接口有一个访问比较器的 comparator 方法，该方法返回用于对集合排序的comparator，如果集合根据其元素的自然顺序排序，则返回null。提供此方法是为了将排序集复制到具有相同排序的新排序集中。它由前面描述的 SortedSet 构造函数使用。

### 2、SortedMap 接口 ###

SortedMap 是一种按升序维护其 entries 的Map，根据 key 的自然顺序或根据创建SortedMap时提供的Comparator进行排序。SortedMap 接口除了提供正常的 Map 操作外还有以下操作:

*  `范围查询` — 对已排序的 Map 执行任意范围操作
 *  端点操作— 返回已排序 Map 中的第一个或最后一个Key
 *  `访问比较器` — 返回用于对 Map 进行排序的比较器(如果有的话)

下面的接口是 SortedSet 的 Map 模拟。// java中的SortedMap接口

package java.util;
    public interface SortedMap<K,V> extends Map<K,V> {
        // 返回用于对该Map中的key排序的比较器
        Comparator<? super K> comparator();
        // 子视图
        SortedMap<K,V> subMap(K fromKey, K toKey);
        // 指定key的前置视图
        SortedMap<K,V> headMap(K toKey);
        // 指定key的后置视图
        SortedMap<K,V> tailMap(K fromKey);
        // 第一个key
        K firstKey();
        // 最后一个key
        K lastKey();
        // 所有key的集合
        Set<K> keySet();
        // 所有值的集合
        Collection<V> values();
        // 所有键值对的集合
        Set<Map.Entry<K, V>> entrySet();
    }

因为SortedSet 接口的所有用法和代码示例只需要稍加修改就适用于SortedMap。在此不做过多赘述。

[1f7397b6b2b94f618c60567ff35464e6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/3d70f580bd4b4ed19382fb87ec4c9cdd.png
[8a8e3fc94aa24d0a86b27ac4e5b87999.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/56e3017727c04468b37808c9b6c5b3b1.png