JEP 431: Sequenced Collections | 有序集合

原文

摘要

引入新的接口来表示具有明确遍历顺序的集合。每个这样的集合都有一个明确定义的首个元素、第二个元素，依此类推，直到最后一个元素。它还提供了统一的 API 来访问其首个和最后一个元素，以及以相反顺序处理其元素。

“生活只能向后理解，但必须向前生活。”
—— 克尔凯郭尔

动机

Java 的集合框架缺乏一种表示具有明确遍历顺序的元素序列的集合类型。同时，它也缺乏适用于此类集合的统一操作集。这些空白一直是问题和投诉的重复来源。

例如，List 和 Deque 都定义了遍历顺序，但它们的共同超类型是 Collection，后者并未定义遍历顺序。类似地，Set 没有定义遍历顺序，其子类型如 HashSet 也没有定义，但子类型如 SortedSet 和 LinkedHashSet 则定义了遍历顺序。因此，对遍历顺序的支持分散在类型层次结构中，使得在 API 中表达某些有用的概念变得困难。无论是 Collection 还是 List，都无法描述具有遍历顺序的参数或返回值。Collection 太过通用，将此类约束下放到了散文式规范中，可能导致难以调试的错误。而 List 又太过具体，排除了 SortedSet 和 LinkedHashSet。

一个相关的问题是，视图集合经常被迫降级为较弱的语义。使用 Collections::unmodifiableSet 包装 LinkedHashSet 会得到一个 Set，从而丢弃了关于遍历顺序的信息。

如果没有定义它们的接口，与遍历顺序相关的操作要么不一致，要么缺失。虽然许多实现支持获取首个或最后一个元素，但每个集合都定义了自己的方式，而且有些方式既不明显又完全缺失：

首个元素最后一个元素
List list.get(0) list.get(list.size() - 1)
Deque deque.getFirst() deque.getLast()
SortedSet sortedSet.first() sortedSet.last()
LinkedHashSet linkedHashSet.iterator().next() // 缺失

	首个元素	最后一个元素
`List`	`list.get(0)`	`list.get(list.size() - 1)`
`Deque`	`deque.getFirst()`	`deque.getLast()`
`SortedSet`	`sortedSet.first()`	`sortedSet.last()`
`LinkedHashSet`	`linkedHashSet.iterator().next()`	`// 缺失`

其中一些操作（如获取 List 的最后一个元素）是不必要的繁琐。而有些操作（如获取 LinkedHashSet 的最后一个元素）甚至不可能实现，除非采取复杂的方法：获取 LinkedHashSet 的最后一个元素的唯一方法是遍历整个集合。

类似地，从第一个元素到最后一个元素遍历集合是简单且一致的，但反向遍历则不然。所有这些集合都可以使用 Iterator、增强的 for 循环、stream() 或 toArray() 方法向前遍历。但每种情况下反向遍历的方式都不同。NavigableSet 提供了 descendingSet() 视图以支持反向遍历：

java

for (var e : navSet.descendingSet())
    process(e);

Deque 则通过反向 Iterator 来实现：

java

for (var it = deque.descendingIterator(); it.hasNext();) {
    var e = it.next();
    process(e);
}

List 也支持反向遍历，但需要使用 ListIterator：

java

for (var it = list.listIterator(list.size()); it.hasPrevious();) {
    var e = it.previous();
    process(e);
}

最后，LinkedHashSet 不支持反向遍历。以反向顺序处理 LinkedHashSet 元素的唯一实际方法是将其元素复制到另一个集合中。

类似地，使用流来处理集合元素是处理循环中元素的强大且有效的替代方法，但获取反向顺序的流可能很困难。在定义遍历顺序的各种集合中，只有 NavigableSet 方便地支持这一点：

java

navSet.descendingSet().stream()

其他集合则需要将元素复制到另一个集合中，或者从自定义的 Spliterator 创建流，该 Spliterator 会反转遍历顺序。

这种情况令人遗憾。在集合框架中，具有明确遍历顺序的集合概念存在于多个地方，但没有一个类型能够代表它。因此，对这类集合的某些操作不一致或缺失，并且以反向顺序处理元素从不方便到几乎不可能。我们应该填补这些空白。

描述

我们为有序 Collection、有序 Set 和有序映射定义了新的接口，然后将它们整合到现有的集合类型层次结构中。这些接口中声明的所有新方法都有默认实现。

有序 Collection

有序 Collection 是一个 Collection，其元素具有定义的遍历顺序。（此处使用的 “sequenced” 是动词 “sequence” 的过去分词形式，意为“以特定顺序排列元素”。）有序 Collection 有第一个和最后一个元素，它们之间的元素有后继和前驱。有序 Collection 支持在两端执行常见操作，并支持从第一个到最后一个以及从最后一个到第一个（即正向和反向）处理元素。

java

interface SequencedCollection<E> extends Collection<E> {
    // 新方法
    SequencedCollection<E> reversed();
    // 从 Deque 提升的方法
    void addFirst(E);
    void addLast(E);
    E getFirst();
    E getLast();
    E removeFirst();
    E removeLast();
}

新的 reversed() 方法提供了原始集合的反向视图。对原始集合的任何修改在视图中都是可见的。如果允许，对视图的修改会反映到原始集合中。

反向视图使所有不同的有序类型都能够使用所有常用的迭代机制（增强的 for 循环、显式的 iterator() 循环、forEach()、stream()、parallelStream() 和 toArray()）在两个方向上处理元素。

例如，之前从 LinkedHashSet 获取反向流是相当困难的；现在只需简单地

java

linkedHashSet.reversed().stream()

（reversed() 方法本质上是重命名的 NavigableSet::descendingSet，并提升到了 SequencedCollection。）

SequencedCollection 的以下方法是从 Deque 提升的。它们支持在两端添加、获取和移除元素：

void addFirst(E)
void addLast(E)
E getFirst()
E getLast()
E removeFirst()
E removeLast()

add*(E) 和 remove*() 方法是可选的，主要是为了支持不可修改集合的情况。如果集合为空，则 get*() 和 remove*() 方法将抛出 NoSuchElementException。

SequencedCollection 中没有 equals() 和 hashCode() 的定义，因为其子接口具有冲突的定义。

有序 Set

有序 Set 是一个不包含重复元素的 Set，同时也是一个 SequencedCollection。

java

interface SequencedSet<E> extends Set<E>, SequencedCollection<E> {
    SequencedSet<E> reversed();    // 协变重写
}

像 SortedSet 这样的集合，它们通过相对比较来定位元素，无法支持 SequencedCollection 超接口中声明的 addFirst(E) 和 addLast(E) 等显式定位操作。因此，这些方法可能会抛出 UnsupportedOperationException。

对于像 LinkedHashSet 这样的集合，SequencedSet 的 addFirst(E) 和 addLast(E) 方法具有特殊情况的语义：如果元素已存在于集合中，则将其移动到适当的位置。这弥补了 LinkedHashSet 的一个长期存在的缺陷，即无法重新定位元素。

有序映射

有序映射 是一个 Map，其条目具有定义的遍历顺序。

java

interface SequencedMap<K,V> extends Map<K,V> {
    // 新方法
    SequencedMap<K,V> reversed();
    SequencedSet<K> sequencedKeySet();
    SequencedCollection<V> sequencedValues();
    SequencedSet<Entry<K,V>> sequencedEntrySet();
    V putFirst(K, V);
    V putLast(K, V);
    // 从 NavigableMap 提升的方法
    Entry<K, V> firstEntry();
    Entry<K, V> lastEntry();
    Entry<K, V> pollFirstEntry();
    Entry<K, V> pollLastEntry();
}

新的 put*(K, V) 方法具有类似于 SequencedSet 中相应 add*(E) 方法的特殊情况语义：对于像 LinkedHashMap 这样的映射，如果条目已存在于映射中，则它们还具有重新定位条目的额外效果。对于像 SortedMap 这样的映射，这些方法会抛出 UnsupportedOperationException。

SequencedMap 的以下方法是从 NavigableMap 提升的。它们支持在两端获取和移除条目：

Entry<K, V> firstEntry()
Entry<K, V> lastEntry()
Entry<K, V> pollFirstEntry()
Entry<K, V> pollLastEntry()

适配现有结构

上面定义的三个新接口完美地融入了现有的集合类型层次结构：

具体来说，我们对现有的类和接口进行了以下调整以进行适配：

List 现在将 SequencedCollection 作为其直接超接口，
Deque 现在将 SequencedCollection 作为其直接超接口，
LinkedHashSet 额外实现了 SequencedSet，
SortedSet 现在将 SequencedSet 作为其直接超接口，
LinkedHashMap 额外实现了 SequencedMap，
SortedMap 现在将 SequencedMap 作为其直接超接口。

我们在适当的位置为 reversed() 方法定义了协变重写。例如，List::reversed 被重写为返回 List 类型的值，而不是 SequencedCollection 类型的值。

我们还向 Collections 工具类添加了新方法，以创建这三种新类型的不可修改包装器：

Collections.unmodifiableSequencedCollection(sequencedCollection)
Collections.unmodifiableSequencedSet(sequencedSet)
Collections.unmodifiableSequencedMap(sequencedMap)

替代方案

类型

添加新类型的替代方案是将 List 接口重新用作一般的有序集合类型。确实，List 是有序的，但它还支持通过整数索引访问元素。许多有序数据结构并不自然支持索引，因此将需要迭代支持它。这将导致索引访问具有 $O (n)$ 性能，而不是预期的 $O (1)$ ，从而延续 LinkedList 的错误。

Deque 似乎是一个有前途的一般有序类型，因为它已经支持了正确的一组操作。然而，它与其他操作混杂在一起，包括一系列返回 null 的操作（offer、peek 和 poll）、栈操作（push 和 pop）以及从 Queue 继承的操作。这些操作对于队列来说是合理的，但对于其他集合来说则不然。如果 Deque 被重新用作一般有序类型，那么 List 也将是一个 Queue 并支持栈操作，从而导致 API 杂乱无章且令人困惑。

命名

我们在这里选择的术语 sequence（有序）意味着元素是按顺序排列的。它在各种平台上被广泛用于表示具有与上述描述类似语义的集合。

术语 ordered（有序）不够具体。我们需要双向迭代和两端操作。像 Queue 这样的有序集合是一个显著的例外：它是有序的，但显然是不对称的。

在此提案的早期版本中使用的术语 reversible（可逆）并没有立即唤起具有两端的概念。也许更大的问题是 Map 变体将被命名为 ReversibleMap，这误导性地暗示它支持通过键和值进行查找（有时称为 BiMap 或 BidiMap）。

添加、放入和 `UnsupportedOperationException`

如上所述，由于元素的顺序由相对比较确定，因此像 SortedSet::addFirst 和 SortedMap::putLast 这样的显式定位 API 会抛出 UnsupportedOperationException。某些集合不实现所有 SequencedCollection 操作的不对称性可能看起来令人不快。然而，这仍然是有价值的，因为它将 SortedSet 和 SortedMap 纳入了有序集合家族，使它们能够比以往更广泛地使用。这种不对称性也与集合框架中先前的设计决策相一致。例如，Map::keySet 方法返回一个 Set，即使返回的实现不支持添加操作。

或者，可以通过沿结构线重新排列接口来将添加操作分开。这将导致出现具有非常薄语义（例如，AddableCollection）的新接口类型，这些类型在实践中并不实用，并且会扰乱类型层次结构。

历史

本提案是我们 2021 年 ReversibleCollections 提案的渐进式演变。与那个提案相比，主要变化包括重命名、添加 SequencedMap 接口以及添加不可修改包装器方法。

ReversibleCollection 提案又基于 Tagir Valeev 在 2020 年提出的 OrderedMap/OrderedSet 提案。尽管细节上有很多不同，但该提案中的几个基本概念仍然存在。

多年来，我们收到了许多将 List 与 Set 或 Map 结合的请求和提案。反复出现的主题是包含唯一元素的 List，或保持排序的 Set 或 Map。这些请求包括 4152834、4245809、4264420、4268146、6447049和8037382。

其中一些请求在 Java 1.4 中引入 LinkedHashSet 和 LinkedHashMap 时得到了部分解决。虽然这些类确实满足了一些用例，但如上所述，它们的引入在集合框架提供的抽象和操作方面留下了空白。

测试

我们将向 JDK 的回归测试套件中添加一组全面的测试。

JEP 431: Sequenced Collections | 有序集合 ​

摘要 ​

动机 ​

描述 ​

有序 Collection ​

有序 Set ​

有序映射 ​

适配现有结构 ​

替代方案 ​

类型 ​

命名 ​

添加、放入和 UnsupportedOperationException ​

历史 ​

测试 ​

JEP 431: Sequenced Collections | 有序集合

摘要

动机

描述

有序 Collection

有序 Set

有序映射

适配现有结构

替代方案

类型

命名

添加、放入和 `UnsupportedOperationException`

历史

测试