HashMap 方法的时间复杂度 [英] Time Complexity of HashMap methods

问题描述

由于我正在研究时间复杂度，因此我一直在 Oracle Java 类库中搜索用于列表、映射和类的一些标准方法的时间复杂度.(更具体地说，ArrayList、HashSet 和 HashMap)

Since i'm working around time complexity, i've been searching through the oracle Java class library for the time complexity of some standard methods used on Lists, Maps and Classes. (more specifically, ArrayList, HashSet and HashMap)

现在，当查看 HashMap javadoc 页面，他们只真正谈论 get() 和 put() 方法.

Now, when looking at the HashMap javadoc page, they only really speak about the get() and put() methods.

我还需要知道的方法是:

The methods i still need to know are:

remove(Object o)
size()
values()

我认为 remove() 与 get()、O(1) 的复杂度相同，假设我们没有有一个巨大的 HashMap，具有相同的 hashCodes 等等......

I think that remove() will be the same complexity as get(), O(1), assuming we don't have a giant HashMap with equal hashCodes, etc etc...

对于 size() 我也假设 O(1)，因为一个 HashSet 也没有顺序，有一个 size() 复杂度O(1)的方法.

For size() i'd also assume O(1), since a HashSet, which also has no order, has a size() method with complexity O(1).

我不知道的是 values() - 我不确定这个方法是否会以某种方式复制"HashMap，时间复杂度为 O(1)，或者它是否必须遍历 HashMap，使复杂度等于 HashMap 中存储的元素数量.

The one i have no idea of is values() - I'm not sure whether this method will just somehow "copy" the HashMap, giving a time complexity of O(1), or if it will have to iterate over the HashMap, making the complexity equal to the amount of elements stored in the HashMap.

谢谢.

推荐答案

来源通常很有帮助:http://kickjava.com/src/java/util/HashMap.java.htm

• 移除: O(1)
• 大小: O(1)
• values: O(n)(遍历迭代器)

• remove: O(1)
• size: O(1)
• values: O(n) (on traversal through iterator)

这篇关于HashMap 方法的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！