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

Question

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

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

Answer 1

获取 key 集是O(1)又便宜。这是因为 HashMap.keyset()返回实际的 KeySet与 HashMap 关联的对象.

返回的Set 不是 key 的副本，而是实际 HashMap 的包装器的状态。事实上，如果你更新集合，你实际上可以改变 HashMap的状态；例如打电话clear()在集合上将清除 HashMap !

---

... iterating through the returned Set will take obviously O(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是 2³¹。所以对于 真的 很大的 Cap 值和 N , 复杂度为 O(N) .

另一方面，N受可用内存量的限制，实际上您需要一个 2³⁸ 字节(256GBytes)的堆 N超过最大可能Cap值(value)。对于这么大的 map ，最好使用针对大 map 调整的哈希表实现。或者没有使用过大的容量估计!