java.util.HashMap 类的时间复杂度是多少？ keySet() 方法？
我正在尝试实现平面扫描算法，为此我需要知道 java.util.HashMap 类的 keySet() 方法。我怀疑它是 O(n log n)。我说得对吗？
澄清点：我说的是 keySet() 方法的时间复杂度；迭代返回的 Set 显然需要 O(n) 时间。
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?
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
获取密钥集的时间复杂度为
O(1)，而且成本低廉。这是因为HashMap.keyset()返回与HashMap关联的实际KeySet对象。返回的
Set不是键的副本，而是实际HashMap状态的包装器。事实上，如果您更新集合，您实际上可以更改HashMap的状态；例如，在集合上调用clear()将清除HashMap！实际上，这并不总是正确：
对于使用
new HashMap<>()创建HashMap来说，这是正确的。最坏的情况是所有N个键都位于同一个哈希链中。但是，如果映射自然增长，哈希数组中仍然会有N个条目和O(N)个槽。因此，迭代条目集将涉及O(N)运算。如果
HashMap是使用new HashMap<>(capacity)创建的，并且capacity非常糟糕（太大），则为 false估计。然后将需要 O(Cap) + O(N) 操作来迭代条目集。如果我们将Cap视为变量，即O(max(Cap, N))，这可能比O(N)更糟糕.但有一个例外条款。由于当前
HashMapAPI 中capacity是int，因此Cap的上限为 231 。因此，对于Cap和N的真正较大值，复杂度为O(N)。另一方面，
N受到可用内存量的限制，实际上，您需要一个 238 字节 (256GBytes) 的堆来存储N超过可能的最大Cap值。对于这种大小的地图，您最好使用针对大型地图进行调整的哈希表实现。或者不使用过大的容量估计！Getting the keyset is
O(1)and cheap. This is becauseHashMap.keyset()returns the actualKeySetobject associated with theHashMap.The returned
Setis not a copy of the keys, but a wrapper for the actualHashMap's state. Indeed, if you update the set you can actually change theHashMap's state; e.g. callingclear()on the set will clear theHashMap!Actually that is not always true:
It is true for a
HashMapis created usingnew HashMap<>(). The worst case is to have allNkeys land in the same hash chain. However if the map has grown naturally, there will still beNentries andO(N)slots in the hash array. Thus iterating the entry set will involveO(N)operations.It is false if the
HashMapis created withnew HashMap<>(capacity)and a singularly bad (too large)capacityestimate. Then it will takeO(Cap) + O(N)operations to iterate the entry set. If we treatCapas a variable, that isO(max(Cap, N)), which could be worse thanO(N).There is an escape clause though. Since
capacityis anintin the currentHashMapAPI, the upper bound forCapis 231. So for really large values ofCapandN, the complexity isO(N).On the other hand,
Nis limited by the amount of memory available and in practice you need a heap in the order of 238 bytes (256GBytes) forNto exceed the largest possibleCapvalue. 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!当然是 O(1)。它所做的就是在 HashMap 上返回一个包装对象。
如果您正在谈论遍历键集，那么这是 O(n)，因为每个 next() 调用都是 O(1)，并且需要执行 n 次。
Surely it would be O(1). All that it is doing is returning a wrapper object on the 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) 时间内完成...哈希映射通常被实现为一个大桶数组，桶的大小（通常）与哈希映射的大小成正比。为了检索键集，必须迭代存储桶，并且对于每个集合项，必须检索键（通过中间集合或直接访问存储桶的迭代器）...
**编辑：作为其他人指出，实际的 keyset() 方法将在 O(1) 时间内运行，但是，迭代键集或将其传输到专用集合将是 O(n) 操作。不太确定您要找哪一个 **
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)...
**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 **
根据Java官方文档，
keySet()方法的时间复杂度为O(1)。因为当映射中发生任何更改时，与 key 相关的所有更改也会发生在 keySet() 方法中。
想象一下，有一个静态的 ArrayList，它是全局的，并且所有更改都是在添加或删除某个键时进行的。
但在面试中或者如果你从头开始实现 hashmap 那么你可以执行 keySet() 时间复杂度 O(1)，如果你使用一些遍历找到所有这些键，那么它的时间复杂度将是 O(n)。
有关更多信息，请阅读 Java 官方 hashmap 文档。
Java 哈希映射
According to official Java documentation,
The time complexity of keySet() method is O(1). Because when anything changes happens in map at any time those all change related to key happens for keySet() method also.
Think like there is a static ArrayList which is gobally and all changes are made when some key is added or removed.
But in interview or if you are implementing hashmap from scratch then You can do keySet() time complexity O(1) and if you are finding all those key's using some traversal then its time complexity will be O(n).
For More information read Java official hashmap documention.
Java Hashmap
Java 集合有很大的空间，因此不需要太多时间。我认为该方法的复杂度为 O(1)。收藏品就放在那里。
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.
为了解决“迭代返回的 Set 显然需要 O(n) 时间”的评论，这实际上是不正确的
HashMap的文档注释：换句话说，迭代返回的
Set将需要O(n + c)，其中n是地图的大小，>c是它的容量，而不是O(n)。如果选择了不适当大小的初始容量或负载因子，则 c 的值在迭代时间方面可能会超过地图的实际大小。To address the "iterating through the returned Set will take obviously O(n) time" comment, this is not actually correct per the doc comments of
HashMap:So in other words, iterating over the returned
Setwill takeO(n + c)wherenis the size of the map andcis its capacity, notO(n). If an inappropriately sized initial capacity or load factor were chosen, the value ofccould outweigh the actual size of the map in terms of iteration time.