流filter的时间复杂度
我有这样的代码：
List Listings = new ArrayList(); Listings.add(listing1); Listings.add(listing2); ... ... ... Listing listing= listings.stream() .filter(l -> l.getVin() == 456) .findFirst(); 我的问题是过滤过程的时间复杂度是多少？ 如果它是O（n），我的直觉是将它转换为HashSet，就像数据结构一样，这样时间复杂度可能变成O（1），是否有一种优雅的方式来实现流 ？
它是O(n) 。 流过滤在内部使用迭代。
您可以将其转换为地图，如下所示：
Map mapOfVinToListing = listings.stream().collect(Collectors.toMap(Listing::getVin, Functions.identity()); // Assuming vin is unique per listing mapOfVinToListing.get(456);// O(1)
但是，转换过程也是O（n）。 因此，如果您只需要执行一次，请使用filter。 如果您需要多次查询同一个列表，那么将其转换为地图可能有意义。
您也可以尝试使用并行流。 在某些情况下，它们可能更具性能，但这在很大程度上取决于具体情况。
最坏的情况是O(n)但由于Stream是惰性的，如果之前找到了值，它将停止迭代。 如果您需要不断的时间查找，那么转换为Map是一个好主意，需要额外的空间; 如果列表如果巨大，你应该考虑这个方面。 实际上，如果列表很小，则Map和List之间的差异几乎不会引起注意，除非您在时间关键系统中工作。
没有终端操作的filter本身就会有零开销 – 因为它绝对没有; 流只由终端操作驱动 – 没有终端操作，没有任何执行。
然后是filter必须迭代 源 （懒惰）的所有元素（可能全部） 的情况 。 因此，filter的时间复杂度将取决于您从中流式传输的来源; 在你的案例List ，所以它将是O(n) 。
但那将是最糟糕的情况 。 一般来说 ，我无法预测平均情况，因为它取决于底层来源。