Sequenced Collections

JDK21在JEP 431提出了有序集合（Sequenced Collections）。引入新的接口来表示有序集合。这样的集合都有一个明确的第一个元素、第二个元素，依此类推，直到最后一个元素。它还提供了统一的 API 来访问其第一个和最后一个元素，并以相反的顺序处理其元素。

提出背景

Java 的集合框架缺少一种有序集合类型。同时，也缺乏一套适用于此类集合的统一操作。这些缺失一直是问题和抱怨的反复来源。

例如，List 和 Deque 都定义了遍历顺序，但它们的共同超类 Collection 并没有定义。类似地，Set 也没有定义遍历顺序，其子类型如 HashSet 也没有定义，但像 SortedSet 和 LinkedHashSet 这样的子类型却定义了。因此，对遍历顺序的支持分散在类型层次结构中，使得在 API 中表达某些有用的概念变得困难。无论是 Collection 还是 List，都无法描述具有遍历顺序的参数或返回值。Collection 过于宽泛，将这样的约束留给说明性文档，可能导致难以调试的错误；而 List 又过于具体，排除了 SortedSet 和 LinkedHashSet。

另一个相关的问题是，视图集合（view collections）常常被迫降级为较弱的语义。例如，使用 Collections::unmodifiableSet 包装一个 LinkedHashSet 会返回一个 Set，从而丢失了关于遍历顺序的信息。由于缺乏定义这些行为的接口，与遍历顺序相关的操作要么不一致，要么缺失。虽然许多实现支持获取第一个或最后一个元素，但每个集合都以自己的方式定义这些操作，有些方式并不直观，甚至完全缺失：

其中一些方法过于繁琐，例如获取 List 的最后一个元素。而有些甚至无法直接实现，除非采取复杂的操作：获取 LinkedHashSet 的最后一个元素的唯一方法是遍历整个集合。类似地，按从头到尾的顺序迭代集合的元素是简单且一致的，但反向迭代却并非如此。所有这些集合都可以通过 Iterator、增强的 for 循环、stream() 或 toArray() 按正向进行迭代。然而，反向迭代在每种情况下都不一样。

NavigableSet 提供了 descendingSet() 视图来支持反向迭代：

for (var e : navSet.descendingSet())

process(e);

Deque does so with a reverse Iterator:

for (var it = deque.descendingIterator(); it.hasNext();) {

var e = it.next();

process(e);

}

List does so but with ListIterator:

for (var it = list.listIterator(list.size()); it.hasPrevious();) {

var e = it.previous();

process(e);

}

LinkedHashSet 并未提供对反向迭代的支持。实际操作中，处理 LinkedHashSet 元素的唯一方法是将其元素复制到另一个集合中以实现反向顺序。类似地，使用流（streams）处理集合元素是一种强大且高效的替代方式，但获取反向顺序的流可能会很困难。在定义了遍历顺序的各种集合中，唯一能够方便地支持这一点的是 NavigableSet：navSet.descendingSet().stream()。其他集合则需要将元素复制到另一个集合，或者通过定制的 Spliterator 创建一个反向迭代的流。这是一种令人遗憾的现状。具有定义好的遍历顺序的集合这一概念在集合框架中多次出现，但却没有一个统一的类型来表示它。因此，针对这些集合的一些操作要么不一致，要么缺失，而以反向顺序处理元素的难度从不方便到完全不可能不等。我们应该填补这些空白。

解决办法

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

Sequenced collections

有序集合（sequenced collection）是一种其元素具有定义好的遍历顺序的集合。（这里使用的“sequenced”一词是动词“to sequence”的过去分词形式，意思是“将元素按特定顺序排列”。）有序集合有第一个和最后一个元素，并且它们之间的元素都有前驱和后继。有序集合支持在两端进行常见操作，并且支持从头到尾（正向）以及从尾到头（反向）处理元素。

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

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

例如，以前从 LinkedHashSet 获取一个反向排序的流非常困难；现在只需：

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

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

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

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

Sequenced sets

有序集（sequenced set）是一种不包含重复元素的 Set，同时也是 SequencedCollection。

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

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

Sequenced maps

有序映射（sequenced map）是一种其条目具有定义好的遍历顺序的 Map。

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

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

Entry<K, V> firstEntry()：获取第一个条目。

Entry<K, V> lastEntry()：获取最后一个条目。

Entry<K, V> pollFirstEntry()：移除并返回第一个条目。

Entry<K, V> pollLastEntry()：移除并返回最后一个条目。

通过这些方法，SequencedMap 不仅能够提供对映射元素的基本操作，还能方便地进行反向迭代以及对两端元素的操作，增强了集合框架的功能性和灵活性。

改造

上面定义的三个新接口可以很好地融入现有的集合类型层次结构中：

具体来说，对现有的类和接口进行了以下调整以适配新定义的功能：

List 现在将 SequencedCollection 作为其直接的父接口。

Deque 现在将 SequencedCollection 作为其直接的父接口。

LinkedHashSet 额外实现了 SequencedSet。

SortedSet 现在将 SequencedSet 作为其直接的父接口。

LinkedHashMap 额外实现了 SequencedMap。

SortedMap 现在将 SequencedMap 作为其直接的父接口。

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

此外，还在 Collections 工具类中添加了新的方法，用于创建这三种新类型的不可修改包装器：

示例代码

public class SequencedCollectionsTest {

public static void main(String[] args) {

List<String> list = new ArrayList<>();

list.add("1");

list.add("2");

list.add("3");

System.out.println(list);

list.addFirst("4");

list.addLast("5");

System.out.println(list);

List<String> reversed = list.reversed();

System.out.println(reversed);

}

}

运行结果：

[1, 2, 3]

[4, 1, 2, 3, 5]

[5, 3, 2, 1, 4]