从哈希集获得的流过滤器的时间复杂度是多少?

Question

Set<Integer> set = new HashSet<>();
set.add(1);
set.add(2);
...

以下操作的时间复杂度是多少？O(n( 还是 O(1(？

set.stream().filter(e -> e == 1).findFirst();

Answer 1

如果从另一面看，可以更好地理解它，您的解决方案是这样的：

for(Integer i : set){
if(i == 1){
break;
}
}

所以它O(n)因为它遍历所有集合，并逐个检查，如果条件正确返回值，否则继续n

Answer 2

它是O(n( -创建Stream实例后，您不再在HashSet上运行，而是在遍历源Set的所有元素的Stream上运行。

这是一个惰性的线性序列，所有元素都被逐个访问 - 因此 O(n(