JEP 431：顺序集合

原文：https://openjdk.org/jeps/431
翻译：张欢

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

“生活只有向后看才能理解，但必须向前看才能活下去。”

——克尔凯郭尔

动机

Java的集合框架缺少一种表示具有定义出现顺序的元素集合类型。它还缺少一套适用于此类集合的统一操作。这些缺陷一直是问题和投诉的根源。

例如，List和Deque都定义了一个出现顺序，但它们的共同父类型是Collection，而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的最后一个元素。有些操作甚至不费点劲就无法完成：获取LinkedHashSet中最后一个元素的唯一方法是迭代整个集合。

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

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

Deque使用反向迭代器来实现这一点：

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

List也是这样，但是使用ListIterator：

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

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

类似地，使用流处理集合的元素是使用循环处理元素的强大而有效的替代方法，但以相反的顺序获取流可能很困难。在定义出现顺序的各种集合中，唯一方便地支持此顺序的是NavigableSet：

navSet.descendingSet().stream()

其他方法要么需要将元素复制到另一个集合，要么需要从自定义的Spliterator创建反向迭代器的流。

这是一种不幸的状况。集合框架中多处都存在具有定义出现顺序的集合的概念，但没有统一类型来表示它。因此，对此类集合的某些操作不一致或缺失，并且以反向的顺序处理元素不方便，甚至不可能。我们应该填补这些空白。

描述

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

顺序的Collection

顺序集合是指元素具有定义的出现顺序的Collection。（此处使用的“顺序”（sequenced）一词是动词“to sequence”的过去分词，意为“按特定顺序排列元素”。）顺序集合具有第一个元素和最后一个元素，它们之间的元素具有后继元素和前驱元素。顺序集合支持两端的常见操作，并支持从第一个到最后一个和从最后一个到第一个（即正向和反向）处理元素。

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获取反向排序的流以前非常困难；现在它很简单：

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

顺序集是一个不包含重复元素的SequencedCollection集合。

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

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

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

顺序的Map

顺序映射是指其条目具有定义的出现顺序的映射。

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混乱且令人困惑。

命名

我们在这里选择的术语“顺序”（sequenced）表示按顺序排列的元素。它通常用于跨各种平台表示具有与上述语义类似的语义的集合。

术语“有序”（ordered）还不够具体。我们需要双向迭代，以及两端的操作。有序集合（例如Queue）是一个明显的异常值：它是有序的，但也明显不对称。

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

add、put和UnsupportedOperationException

如上所述，显式定位 API（例如SortedSet::addFirst和SortedMap::putLast）会抛出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的回归测试套件中添加一套全面的测试。

风险与假设

在继承层次结构的高层引入新方法可能会因明显的方法名称（例如reversed()和getFirst()）而产生冲突的风险。

特别值得关注的是List和Deque上reversed()方法的协变重写。这些方法与实现List和Deque的现有集合在源代码和二进制上不兼容。JDK中有两个此类集合的示例：LinkedList和内部类sun.awt.util.IdentityLinkedList。通过在LinkedList本身上引入新的reversed()协变重写来处理LinkedList类。内部IdentityLinkedList类已被删除，因为它不再需要。

本提案的早期版本引入了对SequencedMap接口的keySet()、values()和entrySet()方法的协变重写。经过一些分析，确定这种方法引入了太大的不兼容风险；本质上，它使任何现有子类无效。选择了另一种方法，即在SequencedMap中引入新方法sequencedKeySet()、sequencedValues()和sequencedEntrySet()，而不是将现有方法调整为协变重写。回想起来，可能是出于同样的原因，在Java 6中采用了类似的方法，引入了navigableKeySet()方法，而不是将现有的keySet()方法修改为协变重写。

请参阅CSR附带的报告JDK-8266572，以获得对不兼容风险的全面分析。