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

Question

如果具有封闭哈希的哈希表/映射是最坏情况O(n)，那么哈希集是否也需要O(n)时间进行查找，还是恒定时间？

Answer 1

当在 a 中查找元素时HashMap，它会执行 O(1) 计算来找到正确的存储桶，然后串行迭代那里的项目，直到找到与请求的键相等的项目，或者检查所有项目。

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

AHashSet只是一个HashMap你不关心值的地方，只关心键 - 在幕后，它是一个HashMap所有值都是虚拟的地方Object。