java - 如何确定 HashMap 中方法的最坏情况复杂度？

Question

public void addOccurence(String word) { 
    if (hm.containsKey(word)){
          hm.put(word, hm.get(word)+1);
    }
    else {hm.put(word, 1); }
}

我知道平均 put(k,v) 和 get(v) 需要 o(1) 并且它们的最坏情况是o(n)。 containsKey(v) 怎么样？以及如何确定诸如此类的运行时间:

hm.put(word, hm.get(word)+1) 

最坏情况下是 o(n^2) 而平均情况下是 o(1) 吗？

Answer 1

hm.put(word, hm.get(word)+1) 的最坏情况时间复杂度是 O(N)。

如何: 假设您由于过度碰撞而将 hashMap 变成了链表。因此 get() 将不得不搜索整个链表，因此 O(N)。类似地，hm.put() 将需要遍历链表来插入值。所以 O(N)+O(N) = O(2N) ~ = O(N)。

即使对于插入，您不会遍历整个链表，get() 方法的时间复杂度也是 O(N)。所以总数是 O(N)。所以在这两种情况下，最坏情况下的时间复杂度都是O(N)。

这在 Java-8 中有所不同，因为如果桶变得大于 TREEIFY_THRESHOLD，它会将链接列表转换为树。

但同样的渐近下界是O(1)。

如何:因为如果您的 key 分布良好，那么 get() 将具有 o(1) 时间复杂度，对于 insert 也是如此。因此导致 O(1) 的渐近时间复杂度。