Java 8:map.merge时间复杂度

Question

我试图找到下面代码的复杂性,因为for循环它将是O(n*complexity_of_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();
} 

有人可以帮我理解上面代码和map.merge() Java 8中的时间复杂度.

Answer 1

引自JDK 8的Javadoc:https: //docs.oracle.com/javase/8/docs/api/java/util/Map.html#merge-KV-java.util.function.BiFunction-

默认实现等效于为此映射执行以下步骤,然后返回当前值,如果不存在则返回null:

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都O(1)对HashMap. remappingFunction你使用的是Integer::sum与之无关的n.所以解决方案中的for循环很简单O(n).

对于流操作,stream + map + sum应该大致相当于一个简单的for循环,这就是它O(n).你传递给的lambda map()是调用map.getOrDefault,也是O(1)为了HashMap.所以这也是O(n)整体的.

所以你的解决方案很简单O(n).