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

问题描述

由于我在解决时间复杂性问题，我一直在通过oracle Java类库搜索List，Maps和Classes中使用的一些标准方法的时间复杂性。 （更具体地说，ArrayList，HashSet和HashMap）

现在，当查看 HashMap javadoc页面，它们只是真的谈论 get（）和 put（）方法。

我仍然需要知道的方法是：

  remove（Object o）
 size（）
 values（）
  

我认为 remove（）与 get（）， O（1），假设我们没有一个具有相同hashCodes的巨大HashMap等等。 b $ b

对于 size（）我也假设 O（1），因为HashSet，它也没有订单，它有一个复杂度 O（1）的 size（）方法。

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

感谢。

解决方案

源代码常常有帮助： http://kickjava.com/src/java/util/HashMap.java.htm

• 删除： O（1）
  
• 尺寸： O（1）


• values： O（n）（遍历遍历器） li>
  

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)

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

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...

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

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.

Thanks.

解决方案

The source is often helpful: http://kickjava.com/src/java/util/HashMap.java.htm

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

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