HashSet查找复杂性？

Question

在最坏的情况下contains,单个查找操作OR 是否O(n)合适？那么,对于n元素的查找hashSet会是O(n^2)什么？

Answer 1

是的,但这确实是最糟糕的情况:如果所有元素HashSet都具有相同的哈希码(或者哈希码导致相同的桶).使用正确写入hashCode和正态分布的密钥样本,查找为O(1).

Answer 2

是的,但是我们拥有HashSets的全部原因是我们遇到这种最坏情况的概率非常非常低,并且它通常比堆的保证nlogn或(自平衡)TreeSet要快得多,或者保证n ^ 2对于未分类的列表.