为何Java Streams在Codility OddOccurrencesInArray题性能得分为0

我在做Codility课程的OddOccurrencesInArray题目时，遇到了不同代码实现得分差异很大的问题：

• 第一版用Java Stream实现的代码提交后总分只有66%，其中性能得分0%：

public int solution(int[] A) {
    return Arrays
            .stream(A)
            .parallel()
            .boxed()
            .collect(Collectors.groupingBy(n -> n, Collectors.counting()))
            .entrySet()
            .parallelStream()
            .filter(entry -> entry.getValue() % 2 != 0)
            .findAny()
            .map(Map.Entry::getKey)
            .orElseThrow();
}

• 第二版用普通for循环加HashMap的参考实现提交后总分100%，性能得分100%：

public int solution(int[] A) {
    HashMap<Integer, Integer> histogram = new HashMap<>();
    for (int i = 0; i < A.length; i++) {
        if (histogram.containsKey(A[i])) {
            int occurrences = histogram.get(A[i]);
            occurrences++;
            histogram.put(A[i], occurrences);
        } else {
            histogram.put(A[i], 1);
        }
    }
    Set<Integer> keySet = histogram.keySet();
    for (int currentKey : keySet) {
        int occurrences = histogram.get(currentKey);
        if (occurrences % 2 != 0) return currentKey;
    }
    throw new RuntimeException();
}

• 第三版混合写法，前面用for循环构建HashMap，后面用Stream遍历统计结果，提交后总分88%，仅1项性能测试未通过：

public int solution(int[] A) {
    HashMap<Integer, Integer> histogram = new HashMap<>();
    for (int i = 0; i < A.length; i++) {
        if (histogram.containsKey(A[i])) {
            int occurrences = histogram.get(A[i]);
            occurrences++;
            histogram.put(A[i], occurrences);
        } else {
            histogram.put(A[i], 1);
        }
    }
    return histogram.entrySet()
            .parallelStream()
            .filter(n -> (n.getValue() % 2 != 0))
            .findAny()
            .map(Map.Entry::getKey)
            .orElseThrow();
}

我也尝试把所有parallelStream()替换成普通stream()，测试结果没有变化。请问这种差异是Java Streams本身效率更低导致的，还是Codility平台的特性导致的？

这个差异主要是Java Stream本身的开销和你实现的额外成本共同导致的，和Codility平台特性关系不大。
首先，你的第一版Stream实现有三个明显的额外开销：

1. 装箱成本：boxed()操作会把所有int基本类型转成Integer对象，大量对象的创建、销毁、哈希查找都比基本类型多了很多额外开销，这在测试用例数组规模很大的时候会被放大。
2. Stream的固有开销：Stream本身的初始化、lambda调用、管道执行都有额外的性能损耗，对于这种运算逻辑非常简单的场景，Stream的开销占比会非常高，甚至超过核心逻辑的耗时。
3. 并行流在这里完全是负优化：并行流的线程调度、任务拆分合并都有成本，这种CPU密集型且运算逻辑极简单的场景，并行的开销远大于收益，反而会变慢。

至于第三版混合实现差一点过性能测试，就是因为最后遍历HashMap用Stream带来的额外开销，换成普通for循环就没有这部分成本了。
另外补充一点，这道题最优解法根本不需要用HashMap，直接用异或运算遍历一次数组就能得到结果，时间复杂度O(n)，空间复杂度O(1)，性能比HashMap的实现还要高很多：

public int solution(int[] A) {
    int res = 0;
    for (int num : A) {
        res ^= num;
    }
    return res;
}

你可以试试这个版本，性能肯定是满分。

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