HashSet查找复杂度？

Question

查询操作OR contains单个可以在最坏的情况下是O(n)对不对？那么，对于n元素，在hashSet中查找的将是O(n^2)？

Answer 1

是的，但它确实是最糟糕的情况：如果在HashSet所有元素都具有相同的散列码（或散列码导致同一个桶）。用正确书写的hashCode和正态分布的密钥样本，查找是O（1）。

Answer 2

lookp需要O（C）

C =常数

Answer 3

是的，但是我们有HashSets的全部原因是我们遇到这种最坏的情况，其概率非常非常低，而且它通常比堆或者（自平衡）TreeSet的保证nlogn快得多，或者保证n^2未排序的列表。