Java 8：map.merge 时间复杂度

Question

我正在尝试找出以下代码的复杂度，由于for循环，它将是O(n * map.merge的复杂度)。

public int solution(int K, int[] A) {    
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for(int i =0; i < A.length; i++){
        map.merge(K - A[i], 1, Integer::sum);
    }   
    return Arrays.stream(A).map(element -> map.getOrDefault(element,0)).sum();
} 

有人能帮我理解上述代码和Java 8中map.merge()的时间复杂度吗？

- Avinash

---

你需要为此编写一个 [MCVE]。 - pvg

您需要什么额外信息才能回答这个问题？ - Yahya

只是一些风格注意事项。自从 Java 5，你可以使用 for-each: for(int a: A) map.merge(K - a, 1, Integer::sum); 而自从 Java 7，你不需要在实例化时重复类型参数: Map<Integer, Integer> map = new HashMap<>(); - Holger

Answer 1

根据JDK 8 Javadoc的引用： https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#merge-K-V-java.util.function.BiFunction-

The default implementation is equivalent to performing the following steps for this map, then returning the current value or null if absent:

V oldValue = map.get(key);
V newValue = (oldValue == null) ? value :
          remappingFunction.apply(oldValue, value);
if (newValue == null)
    map.remove(key);
else
    map.put(key, newValue);

所有put，remove和get对于HashMap都是O(1)。你使用的remappingFunction是Integer::sum，与n无关。因此，你的解决方案中的for循环只是O(n)。

对于流操作，stream + map + sum应该大致等同于简单的for循环，这使得它为O(n)。你传递给map()的lambda正在调用map.getOrDefault，对于HashMap来说也是O(1)。所以总体上也是O(n)。

因此，你的解决方案只是O(n)。

- Adrian Shum

---

我也是这么想的...好答案。 - Yahya

Map.getOrDefault 的时间复杂度是 O(1)。另外，如果你特别关注 HashMap，那么 default 实现将不再相关，因为 HashMap 覆盖了 merge 方法。但是，这并不会使操作变得更糟糕，因此时间复杂度仍然是 O(1)。 - Holger

糟糕，这里打错字了 :) - Adrian Shum