我正在尝试实现平面扫描算法,为此我需要知道 java.util.HashMap class' keySet() 的时间复杂度方法。我怀疑它是 O(n log n)。我说得对吗?
澄清点:我说的是 keySet() 方法的时间复杂度;遍历返回的 Set 显然需要 O(n) 时间。
最佳答案
获取 key 集是O(1)
又便宜。这是因为 HashMap.keyset()
返回实际的 KeySet
与 HashMap
关联的对象.
返回的Set
不是 key 的副本,而是实际 HashMap
的包装器的状态。事实上,如果你更新集合,你实际上可以改变 HashMap
的状态;例如打电话clear()
在集合上将清除 HashMap
!
... iterating through the returned
Set
will take obviouslyO(n)
time.
实际上,这并不总是是正确的:
HashMap
为真使用new HashMap<>()
创建.最坏的情况是所有N
key 落在同一个哈希链中。然而,如果 map 自然增长,仍然会有N
。条目和O(N)
哈希数组中的槽。因此迭代条目集将涉及O(N)
操作。如果
HashMap
为假使用new HashMap<>(capacity)
创建和一个非常糟糕的(太大)capacity
估计。然后需要O(Cap) + O(N)
迭代条目集的操作。如果我们对待Cap
作为变量,即O(max(Cap, N))
,这可能比O(N)
更糟.
虽然有一个免责条款。自 capacity
是一个 int
在当前 HashMap
API,上限为Cap
是 231。所以对于 真的 很大的 Cap
值和 N
, 复杂度为 O(N)
.
另一方面,N
受可用内存量的限制,实际上您需要一个 238 字节(256GBytes)的堆 N
超过最大可能Cap
值(value)。对于这么大的 map ,最好使用针对大 map 调整的哈希表实现。或者没有使用过大的容量估计!
关于java - java.util.HashMap 类的 keySet() 方法的时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1850802/