如果具有封闭哈希的哈希表/映射是最坏情况 O(n)
,那么 HashSet 是否也需要 O(n)
时间来查找,或者它是常数时间?
最佳答案
当在 HashMap
中查找元素时,它执行 O(1) 计算以找到正确的桶,然后连续迭代那里的项目,直到找到等于的那个请求的 key ,或检查所有项目。
在最坏的情况下, map 中的所有项目都具有相同的哈希码,因此存储在同一个桶中。在这种情况下,您需要连续迭代所有这些,这将是一个 O(n) 操作。
HashSet
只是一个 HashMap
,您不关心其中的值,只关心键 - 在幕后,它是一个 HashMap
其中所有值都是一个虚拟 Object
。
关于Java HashSet 最坏情况查找时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65161033/