JEP 431：有序集合（Sequenced Collections）
总结
引入新的接口来表示具有确定遭遇顺序的集合。每个这样的集合都有一个明确的第一个元素、第二个元素，依此类推，直到最后一个元素。它还提供了统一的 API 来访问其第一个和最后一个元素，以及按相反顺序处理其元素。
“生命只能回顾才能理解；但必须展望才能活着。”
— 克尔凯郭尔
动机
Java 的 集合框架 缺少一种表示具有定义的遭遇顺序的元素序列的集合类型。它还缺少一套适用于此类集合的统一操作。这些差距一直是问题和抱怨的反复来源。
例如，List 和 Deque 都定义了遭遇顺序（encounter order），但它们的共同超类型是 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 使用反向 Iterator 来实现：
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 的元素，唯一实际的方法是将其元素复制到另一个集合中。
同样，使用流（streams）处理集合的元素是使用循环处理元素的一种强大且有效的替代方法，但获取逆序的流可能会比较困难。在定义了遍历顺序的各种集合中，唯一一个方便支持此功能的是 NavigableSet：
navSet.descendingSet().stream()
其他方法则需要将元素复制到另一个集合，或者从自定义的 Spliterator 创建一个流以反转迭代。
这是一个不幸的情况。在集合框架的多个地方存在具有定义的遭遇顺序的集合概念，但没有单一的类型来表示它。因此，对此类集合的一些操作不一致或缺失，按相反顺序处理元素的难度从不方便到不可能不等。我们应该填补这些空白。
描述
我们为有序集合、有序集和有序映射定义了新的接口，然后将它们改造后融入现有的集合类型层次结构中。这些接口中声明的所有新方法都有默认实现。
有序集合
有序集合 是一种 Collection，其元素具有定义好的遭遇顺序。（此处使用的“有序”一词是动词 to sequence 的过去分词，意思是“按特定顺序排列元素”。）有序集合有第一个和最后一个元素，并且它们之间的元素有前驱和后继。有序集合支持在两端进行常见操作，并且支持从头到尾以及从尾到头处理元素（即，正向和反向）。
interface SequencedCollection<E> extends Collection<E> {
// new method
SequencedCollection<E> reversed();
// methods promoted from 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() 的定义。
有序集合
一个 sequenced set 是一个 Set，它是一个不包含重复元素的 SequencedCollection。
interface SequencedSet<E> extends Set<E>, SequencedCollection<E> {
SequencedSet<E> reversed(); // covariant override
}
像 SortedSet 这样通过相对比较来定位元素的集合，无法支持显式位置操作，例如在 SequencedCollection 超接口中声明的 addFirst(E) 和 addLast(E) 方法。因此，这些方法可能会抛出 UnsupportedOperationException。
SequencedSet 的 addFirst(E) 和 addLast(E) 方法对诸如 LinkedHashSet 之类的集合有着特殊的情况语义：如果元素已经存在于集合中，则它会被移动到适当的位置。这弥补了 LinkedHashSet 长期以来的一个缺陷，即无法重新定位元素。
有序映射
有序映射 是指其条目具有定义好的遭遇顺序的 Map。
interface SequencedMap<K,V> extends Map<K,V> {
// new methods
SequencedMap<K,V> reversed();
SequencedSet<K> sequencedKeySet();
SequencedCollection<V> sequencedValues();
SequencedSet<Entry<K,V>> sequencedEntrySet();
V putFirst(K, V);
V putLast(K, V);
// methods promoted from 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 作为一种通用的序列类型似乎很有前景，因为它已经支持了正确的操作集合。然而，它还混杂着其他操作，包括一系列返回空值的操作（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 提案。尽管在细节上存在许多差异，但该提案中的几个基本概念仍然保留了下来。
其中一些请求在 Java 1.4 中引入 LinkedHashSet 和 LinkedHashMap 时得到了部分解决。虽然这些类确实满足了一些使用场景，但它们的引入导致了集合框架所提供的抽象和操作上出现了空白，如上所述。
测试
我们将为 JDK 的回归测试套件添加一套全面的测试。
风险与假设
在继承层次结构中引入新方法可能会导致一些显而易见的方法名称（例如 reversed() 和 getFirst()）发生冲突。
特别值得关注的是 List 和 Deque 上对 reversed() 方法的协变重写。这些方法与现有的同时实现 List 和 Deque 的集合在源码和二进制层面都不兼容。JDK 中有两个这样的集合示例：LinkedList 和一个内部类 sun.awt.util.IdentityLinkedList。针对 LinkedList 类，通过在其自身引入一个新的 reversed() 协变重写来解决此问题。而内部类 IdentityLinkedList 已被移除，因为它不再必要。
提案的早期版本为 SequencedMap 接口的 keySet()、values() 和 entrySet() 方法引入了协变重写。经过一些分析后，确定这种方法带来了太大的不兼容风险；本质上，它会使任何现有的子类失效。因此选择了另一种方法，即在 SequencedMap 中引入新的方法 sequencedKeySet()、sequencedValues() 和 sequencedEntrySet()，而不是调整现有方法使其成为协变重写。回想起来，可能出于相同的原因，在 Java 6 中采用了类似的方法，引入了 navigableKeySet() 方法，而不是修改现有的 keySet() 方法使其成为协变重写。
请参阅附加到 CSR 的报告，JDK-8266572，以获取对不兼容风险的完整分析。