java.util.HashMap 类的 keySet() 方法的时间复杂度是多少？

What is the time complexity of java.util.HashMap class' keySet() method?

提问by agrawalankur

I am trying to implement a plane sweep algorithm and for this I need to know the time complexity of java.util.HashMap class' keySet()method. I suspect that it is O(n log n). Am I correct?

我正在尝试实现平面扫描算法，为此我需要知道java.util.HashMap 类的 keySet()方法的时间复杂度。我怀疑它是 O(n log n)。我对么？

Point of clarification:I am talking about the time complexity of the keySet() method; iterating through the returned Set will take obviously O(n) time.

澄清点：我说的是keySet()方法的时间复杂度；遍历返回的 Set 显然需要 O(n) 时间。

回答by Stephen C

Getting the keyset is O(1)and cheap. This is because HashMap.keyset()returns the actual KeySetobject associated with the HashMap.

获得密钥集很O(1)便宜。这是因为HashMap.keyset()返回KeySet与HashMap.

The returned Setis not a copyof the keys, but a wrapper for the actual HashMap's state. Indeed, if you update the set you can actually change the HashMap's state; e.g. calling clear()on the set will clear the HashMap!

返回Set的不是键的副本，而是实际HashMap状态的包装器。事实上，如果你更新集合，你实际上可以改变HashMap的状态；例如，呼叫clear()设置将清除HashMap！

---

---

... iterating through the returned Setwill take obviously O(n)time.

...遍历返回的Set内容显然需要O(n)时间。

Actually that is not alwaystrue:

实际上，这并不总是正确的：

• It is true for a HashMapis created using new HashMap<>(). The worst case is to have all Nkeys land in the same hash chain. However if the map has grown naturally, there will still be Nentries and O(N)slots in the hash array. Thus iterating the entry set will involve O(N)operations.

• It is false if the HashMapis created with new HashMap<>(capacity)and a singularly bad (too large) capacityestimate. Then it will take O(Cap) + O(N)operations to iterate the entry set. If we treat Capas a variable, that is O(max(Cap, N)), which could be worse than O(N).

• 对于 aHashMap是使用创建的，这是正确的new HashMap<>()。最坏的情况是让所有N密钥都位于同一哈希链中。但是，如果地图自然增长，散列数组中仍然会有N条目和O(N)插槽。因此迭代条目集将涉及O(N)操作。

• 如果HashMap是用new HashMap<>(capacity)一个非常糟糕（太大）的capacity估计创建的，那么它是错误的。然后将需要O(Cap) + O(N)操作来迭代条目集。如果我们将其Cap视为变量，即O(max(Cap, N))可能比 更糟O(N)。

There is an escape clause though. Since capacityis an intin the current HashMapAPI, the upper bound for Capis 2³¹. So for reallylarge values of Capand N, the complexity is O(N).

不过有一个转义条款。由于capacity是int当前HashMapAPI中的an ，因此上限为Cap2 ³¹。所以对于非常大的Cap和值N，复杂度是O(N)。

On the other hand, Nis limited by the amount of memory available and in practice you need a heap in the order of 2³⁸bytes (256GBytes) for Nto exceed the largest possible Capvalue. And for a map that size, you would be better off using a hashtable implementation tuned for huge maps. Or not using an excessively large capacity estimate!

另一方面，N受可用内存量的限制，实际上您需要一个大约 2 ³⁸字节 (256GBytes)的堆N才能超过最大可能Cap值。对于这种大小的地图，最好使用针对大型地图进行调整的哈希表实现。或者不使用过大的容量估计！

回答by Paul Wagland

Surely it would be O(1). All that it is doing is returning a wrapper object on the HashMap.

肯定是 O(1)。它所做的只是在 HashMap 上返回一个包装对象。

If you are talking about walking over the keyset, then this is O(n), since each next() call is O(1), and this needs to be performed n times.

如果您正在谈论遍历键集，那么这是 O(n)，因为每个 next() 调用都是 O(1)，并且这需要执行 n 次。

回答by LorenVS

This should be doable in O(n) time... A hash map is usually implemented as a large bucket array, the bucket's size is (usually) directly proportional to the size of the hash map. In order to retrieve the key set, the bucket must be iterated through, and for each set item, the key must be retrieved (either through an intermediate collection or an iterator with direct access to the bucket)...

这应该在 O(n) 时间内是可行的......哈希映射通常被实现为一个大的存储桶数组，存储桶的大小（通常）与哈希映射的大小成正比。为了检索密钥集，必须迭代存储桶，并且对于每个设置项，必须检索密钥（通过中间集合或直接访问存储桶的迭代器）...

**EDIT: As others have pointed out, the actual keyset() method will run in O(1) time, however, iterating over the keyset or transferring it to a dedicated collection will be an O(n) operation. Not quite sure which one you are looking for **

**编辑：正如其他人所指出的，实际的 keyset() 方法将在 O(1) 时间内运行，但是，迭代键集或将其传输到专用集合将是 O(n) 操作。不太确定您要找哪一个 **

回答by bmargulies

Java collections have a lot of space and thus don't take much time. That method is, I believe, O(1). The collection is just sitting there.

Java 集合有很多空间，因此不会占用太多时间。我相信这种方法是 O(1)。收藏品只是坐在那里。

回答by M. Justin

To address the "iterating through the returned Set will take obviously O(n) time" comment, this is not actually correct per the doc commentsof HashMap:

为了解决“通过对返回的Set迭代显然需要O（n）的时间”的评论，这不是每实际上是正确的文档注释的HashMap：

Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

迭代集合视图需要的时间与 HashMap 实例的“容量”（桶的数量）加上它的大小（键值映射的数量）成正比。因此，如果迭代性能很重要，则不要将初始容量设置得太高（或负载因子太低），这一点非常重要。

So in other words, iterating over the returned Setwill take O(n + c)where nis the size of the map and cis its capacity, not O(n). If an inappropriately sized initial capacity or load factor were chosen, the value of ccould outweigh the actual size of the map in terms of iteration time.

因此，换句话说，遍历返回Set将采取O(n + c)地方n是地图的大小，并c为它的能力，而不是O(n)。如果选择了大小不合适的初始容量或负载因子，则 的值c可能会在迭代时间方面超过地图的实际大小。