java - 标准集合返回的 Stream 实现有多专业？

Question

Stream是一个接口(interface)，因此无论何时获取一个 Stream 对象，都会隐藏许多特定于实现的细节。

例如，拿下面的代码:

List<String> list = new ArrayList<>();
...
int size = list.stream()
               .count();

它是以恒定时间还是线性时间运行的？或者这样:

Set<String> set = new TreeSet<>();
...
set.stream()
   .sorted()
   .forEach(System.out::println);

会是 O(n) 还是 O(n log n)？

一般来说，标准集合返回的流实现有多专业？

Answer 1

Does it run in constant or linear time?

当前的实现以线性时间运行:

public final long count() {
    return mapToLong(e -> 1L).sum();
}

但是，这可以改进(某处有一个 RFE)以在恒定时间在某些情况下运行。

如何？一个流由一个流源、零个或多个中间操作和一个终端操作(这里是count() 是终端操作)。流实现维护一组关于源的特征，并且知道这些特征是如何被操作修改的。例如，由 Collection 支持的流具有 SIZED 特征，而由 Iterator 支持的流没有大小限制。类似地，操作 map() 是大小保持的，但是操作 filter() 破坏了任何关于大小的先验知识。流实现在开始终端操作之前知道管道的组成特征，因此它知道源是否有大小以及所有阶段是否都保持大小，在这种情况下，可以简单地向源询问大小并绕过所有实际的流计算。 (但 Java 8 中的实现并没有碰巧这样做。)

请注意，流不需要专门支持这一点； Collection 类使用了解其特性的 Spliterator 创建流，因此不需要 Collections 的专门实现，只需更新共享实现以利用这一特定信息。