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未排序的列表。