Java集合性能对比：Stream与普通循环实现Codility任务的差异

嘿，针对你在Codility遇到的这个问题，我来帮你逐一拆解疑问，顺便聊聊Java 8 Stream和传统循环的性能差异～

首先明确问题背景：给定包含N个整数的数组A（N范围[1..100,000]，元素范围[-1,000,000..1,000,000]），返回数组中未出现的最小正整数。

你的第一次Java 8方案：问题出在哪？有没有优化空间？ #

你的第一个方案逻辑完全正确，但超时的核心原因是常数项开销过大，具体来说：

• Arrays.stream(A).boxed()会把每个int装箱成Integer，这一步在大数据量下会产生大量对象，带来额外的内存分配和GC开销。
• 用HashSet存储正整数，虽然contains()是平均O(1)复杂度，但哈希表需要计算哈希值、处理冲突，相比布尔数组的直接内存索引访问，开销要大得多。
• IntStream.iterate(1, a -> a + 1)作为无限流，在最坏场景（比如数组包含1到1e6的所有数）下，要循环1e6次，每次的Set查询都比布尔数组的直接检查慢很多。

那这个方案有没有优化空间？当然有！我们可以利用一个关键的算法思路：如果数组长度是N，那么未出现的最小正整数要么在1到N之间，要么是N+1。因为如果1到N都出现在数组里，那结果必然是N+1；如果有缺失，那缺失的那个就是答案。基于这个思路，我们可以只保留数组中1<=x<=N的正整数，大幅减少需要存储的数据量：

public int solution(int[] A) {
    int n = A.length;
    Set<Integer> present = Arrays.stream(A)
                                .filter(i -> i > 0 && i <= n)
                                .boxed()
                                .collect(Collectors.toSet());
    for (int i = 1; i <= n; i++) {
        if (!present.contains(i)) {
            return i;
        }
    }
    return n + 1;
}

这个优化后的版本内存占用更少，查询次数也大幅减少，性能会比原版本好很多，但还是比不上布尔数组的版本——毕竟Set的本质开销还是存在。

Codility测试是否过于严苛？实际场景性能差异会缩小吗？ #

Codility的测试其实是在模拟极端性能场景，比如数组刚好包含1到1e6的所有数、全是负数，或者全是远大于N的正数。这种场景下，性能差异会被无限放大，所以你的第一个方案会超时。

在普通业务场景中，如果数组规模不大（比如几千个元素），Stream版本和循环版本的差异可能几乎感知不到，但如果是处理十万级甚至百万级别的数据，循环版本的优势就会非常明显——因为Stream的底层虽然也是循环，但它加了很多封装（流水线操作、装箱、甚至并行流的线程调度开销），这些在大数据量下都会累积成显著的性能差距。

说白了，Codility的评分标准非常看重时间复杂度的常数项，你的第二个方案是O(N)时间复杂度+极小的常数项，所以能轻松通过所有测试用例。

有没有更优的Java 8解决方案？ #

如果一定要用Java 8的特性，同时追求极致性能，我推荐用BitSet替代布尔数组——它比布尔数组更节省内存（用单个bit存储状态，而布尔数组每个元素占1字节），同时结合Stream来填充：

import java.util.BitSet;

public int solution(int[] A) {
    int n = A.length;
    BitSet bitSet = new BitSet(n + 1);
    Arrays.stream(A)
          .filter(i -> i > 0 && i <= n)
          .forEach(bitSet::set);
    // 从1开始找第一个未被设置的位
    int missing = bitSet.nextClearBit(1);
    return missing == 0 ? n + 1 : missing;
}

这个版本的内存占用比布尔数组小一个数量级（比如n=1e5时，BitSet只需要约12KB，而布尔数组需要100KB），性能接近普通循环的布尔数组版本，同时保留了Java 8的简洁性。

另外你提到的“IntStream是小数组场景下的性能瓶颈”完全正确——因为Stream的初始化开销（创建流水线、包装中间操作）在小数组时，占比会远大于实际处理数据的开销，而普通循环没有这个初始化成本，所以小数组下循环更快。

至于你看到的“Stream较新所以性能差”的旧文章，现在Java版本已经更新到20+，Stream的实现确实有不少优化，但Stream的设计目标是代码简洁、可读性高，而非极致性能。它的性能在大部分场景下足够，但在算法题这种需要压榨性能的场景，还是不如手动循环来得直接。

内容的提问来源于stack exchange，提问作者PeMa