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

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)吗？

最佳答案

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)。

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

怎么样：
因为如果密钥分配合理，则get()的时间复杂度与o(1)相同。因此，导致insert的渐近时间复杂度。