流在分组后不能保持顺序。

Question

我有一个名为availableSeats的列表，我按照下面的代码通过blockIndex属性进行排序和分组：

availableSeats.stream()
                .sorted(Comparator.comparing(SeatedTicketAssignment::getBlockIndex))
                .collect(Collectors.groupingBy(SeatedTicketAssignment::getBlockIndex))
                .forEach((block, blockAssignments) -> {
                     //Rest of the code
                } 

问题在于按组分组的结果未按 blockIndex 排序。

- Milad

Answer 1

请记住，Collectors#groupingBy(Function) 将返回一个 HashMap，它不保证顺序。如果你希望顺序按照聚合标识（例如你的 i % 2 == 0 的结果）出现的顺序，则可以使用 LinkedHashMap：

.collect(Collectors.groupingBy(i -> i % 2 == 0, LinkedHashMap::new, Collectors.toList()))

返回一个 LinkedHashMap<Boolean, List<SeatedTicketAssignment>>（因为您的收集器是按布尔值分组的）。 此外，由收集器使用的列表是一个ArrayList，它应该相对于列表保留流的迭代顺序。

- Rogue

---

如果键类型为Boolean，则可以使用partitioningBy并获得具有固有顺序的映射，但是，在问题的哪个位置出现了该键函数？由于顺序是上一个排序步骤（按相同值）的顺序，因此去除排序操作并收集到TreeMap中会更简单... - Holger

谢谢你节省了我的时间。 - Sviatlana

@Holger，groupingBy 的第三个参数创建的列表是否应该保留初始列表的输入顺序？ - Cristiano

@Cristiano 它返回一个ArrayList，因此对于顺序流之前的任何顺序都是相关的。 - Rogue

@Cristiano toList()收集器保留顺序。但最终结果是一个包含最多两个组的Map。当分组为LinkedHashMap时，映射的顺序取决于第一个元素。当分组为TreeMap时，它将始终为false, true。当使用partitioningBy(i -> i % 2 == 0)时，顺序也将始终为false, true，但这没有被记录在文档中。此外，当使用partitioningBy(i -> i % 2 == 0)时，即使在流中不存在（然后为空列表），两个键也将始终存在。这些缺失的信息已经在Java 9的文档中添加了。 - Holger

Answer 2

不幸的是，流 API 实现并没有意识到你所传递的流已经按照需要排序，因此 "分组" 实际上是微不足道的。因此，它使用默认方式，这与SO 回答实质上类似，即为组创建一个 Map，并将流的元素填充到其中。默认情况下使用的 Map 实现是 HashMap (请参见这里的代码)，这对于性能来说很好，但对于你的目标来说不好，因为 HashMap 不保留键的顺序，而应该首先排序。

可能会觉得有点不幸，Group By 在 Stream API 中只作为 "收集器" 实现，因此你不能在一行中先分组再排序。但这似乎是有意为之的：没有办法在完全材料化结果的情况下实现 Group By，因此它不能懒惰地执行，因此必须是一个收集器。@Rogue 提供了一种不错的技巧，使用 LinkedHashMap，但我认为它太过于绑定于实现细节。我仍然会写更多的代码，先将列表条目(即实际分组的 HashMap)按键排序。很可能这样会更快。

- SergGr

---

为什么要事后排序，当你可以在分组时进行排序呢？Collectors.groupingBy(SeatedTicketAssignment::getBlockIndex, TreeMap::new, Collectors.toList())，如果这不是一行代码，我就不知道了... - Holger

流氓的回答不依赖于实现细节。无论您是否使用并行流，保留遇到顺序都是有保证的。但他的回答仍然依赖于先前的排序操作，即使使用LinkedHashMap，它的最坏情况时间复杂度仍为O(n log n)，还需要一个临时的O(n)存储操作来操作集合之前。而且还需要实际的collect操作。因此，直接将收集到TreeMap中，而不进行先前的排序操作可能会更快一些。 - Holger

但是你说得对，当组数较少时，将分组后的结果排序到普通的 HashMap 中可能会更快。那么这个 Collectors.collectingAndThen(Collectors.groupingBy(SeatedTicketAssignment::getBlockIndex), TreeMap::new) 如何？它是否合适作为一行代码？ - Holger

有趣的是，即使你在这里不需要并发映射，如果你正在寻找一个本质上排序的并发映射，ConcurrentSkipListMap 自 Java 6 开始就已经存在了...... - Holger

groupingByConcurrent是一个无序的收集器，因此它不会保持流的原始遇见顺序（如果有的话），但如果您将ConcurrentSkipListMap用作目标，则它将无论如何对插入的元素进行排序，并且这个排序顺序是您感兴趣的。 - Holger

Answer 3

groupingBy收集器不要求输入进行排序，因此您可以在收集后对组进行排序。无论如何，这比先对项目进行排序要快，假设组比项目少：

availableSeats.stream()
        .collect(Collectors.groupingBy(SeatedTicketAssignment::getBlockIndex))
        .entrySet().stream()
        .sorted(Comparator.comparing(Map.Entry::getKey))
        .forEach(mapEntry -> {
             //Rest of the code
        } 

- Matt Timmermans

---

你也可以使用Map.Entry.comparingByKey()... - Holger