Java HashSet 最坏情况查找时间复杂度

Question

如果具有封闭哈希的哈希表/映射是最坏情况 O(n)，那么 HashSet 是否也需要 O(n) 时间来查找，或者它是常数时间？

Answer 1

当在 HashMap 中查找元素时，它执行 O(1) 计算以找到正确的桶，然后连续迭代那里的项目，直到找到等于的那个请求的 key ，或检查所有项目。

在最坏的情况下， map 中的所有项目都具有相同的哈希码，因此存储在同一个桶中。在这种情况下，您需要连续迭代所有这些，这将是一个 O(n) 操作。

HashSet 只是一个 HashMap，您不关心其中的值，只关心键 - 在幕后，它是一个 HashMap 其中所有值都是一个虚拟 Object。