跳到主要内容

JEP 431：排序集合

概括​

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

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

动机​

Java 的集合框架缺少表示具有定义的遇到顺序的元素序列的集合类型。它还缺乏适用于此类集合的统一操作集。这些差距一再成为问题和投诉的根源。

例如，List和Deque都定义了遭遇顺序，但它们的共同超类型是Collection，但没有。类似地，Set没有定义遭遇顺序，并且诸如 的子类型也HashSet没有定义，但是诸如SortedSet和LinkedHashSet的子类型却定义了。因此，对遭遇顺序的支持分布在类型层次结构中，这使得在 API 中表达某些有用的概念变得困难。也Collection不能List描述具有遇到顺序的参数或返回值。Collection过于笼统，将此类约束归咎于散文规范，可能会导致难以调试的错误。List太具体了，排除了SortedSet和LinkedHashSet。

一个相关的问题是视图集合经常被迫降级到较弱的语义。将 a 包裹起来LinkedHashSet会Collections::unmodifiableSet产生 a Set，并丢弃有关遭遇顺序的信息。

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

第一个元素

最后一个元素

**List**

list.get(0)

list.get(list.size() - 1)

**Deque**

deque.getFirst()

deque.getLast()

**SortedSet**

sortedSet.first()

sortedSet.last()

**LinkedHashSet**

linkedHashSet.iterator().next()

// missing

其中一些是不必要的麻烦，例如获取 a 的最后一个元素List。如果没有英雄气概，有些甚至是不可能的：获取 a 的最后一个元素的唯一方法LinkedHashSet是迭代整个集合。

类似地，从第一个到最后一个集合的元素迭代是简单且一致的，但以相反的顺序迭代则不然。所有这些集合都可以使用Iterator、增强for循环、astream()或向前迭代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以相反顺序处理 a 元素的唯一实用方法是将其元素复制到另一个集合中。

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

navSet.descendingSet().stream()

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

这是一种不幸的情况。具有定义的遇到顺序的集合的概念存在于集合框架中的多个位置，但没有单一类型来表示它。结果，对此类集合的某些操作不一致或丢失，并且以相反的顺序处理元素从不方便到不可能。我们应该填补这些空白。

描述​

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

有序集合​

_有序集合_是其Collection元素具有定义的遇到顺序的集合。 （此处使用的“sequenced”一词是动词_toequence_的过去分词，意思是“以特定顺序排列元素。”）有序集合具有第一个和最后一个元素，它们之间的元素具有后继和前驱。排序集合支持两端的通用操作，并且支持从第一个到最后一个以及从最后一个到第一个（即正向和反向）处理元素。

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()。

例如，从 a 中获取逆序流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

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

序列集​

_有序集_是不包含重复元素Set的 a 。SequencedCollection

interface SequencedSet<E> extends Set<E>, SequencedCollection<E> {
    SequencedSet<E> reversed();    // covariant override
}

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

addFirst(E)和方法addLast(E)对于SequencedSet集合具有特殊情况语义，例如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)方法具有特殊情况语义，类似于 的相应add*(E)方法SequencedSet： 对于诸如 之类的地图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被重写以返回 type 的值List而不是 type 的值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也将是 aQueue并且支持堆栈操作，从而导致 API 混乱且令人困惑。

命名​

我们在这里选择的术语“_序列”_意味着按顺序排列的元素。它通常在各种平台上使用来表示具有与上述类似的语义的集合。

_订购_一词不够具体。我们需要双向迭代，并在两端进行操作。像 a 这样的有序集合Queue是一个值得注意的异常值：它是有序的，但它也明显是不对称的。

该提案的早期版本中使用的术语_“可逆”_并不能立即唤起具有两端的概念。也许一个更大的问题是该Map变体将被命名为ReversibleMap，这误导性地暗示它支持按键和按值查找（有时称为BiMapor BidiMap）。

添加、放置和UnsupportedOperationException​

如上所述，诸如SortedSet::addFirst和 之类的显式定位 APISortedMap::putLast会抛出异常，UnsupportedOperationException因为它们的元素顺序是通过相对比较确定的。某些集合未实现所有SequencedCollection操作的不对称性可能看起来令人不快。尽管如此，它还是很有价值的，因为它将SortedSet和SortedMap引入了测序集合家族，使它们能够比其他方式更广泛地使用。这种不对称性也与集合框架中先前的设计决策一致。例如，该Map::keySet方法返回 a Set，即使返回的实现不支持加法。

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

历史​

ReversibleCollections该提案是我们 2021 年提案的增量演变。该提案的主要变化是重命名、添加接口SequencedMap以及添加不可修改的包装方法。

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

多年来，我们收到了许多将 aList与 aSet或结合起来的请求和建议Map。重复出现的主题是List包含独特元素的 a 或Set保持Map排序的 or 。这些请求包括4152834、4245809、4264420、4268146、6447049和8037382 。​​​​​​

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

测试​

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

风险和假设​

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

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

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

请参阅 CSR 附带的报告JDK-8266572，了解不兼容风险的完整分析。