HashSetのルックアップの複雑さ？

Question

ルックアップ操作またはシングルの場合containsは、最悪の場合はO(n)になる可能性がありますか？だから、nの要素はhashSetで検索するとO(n^2)になりますか？

Answer 1

はいOがかかりますが、それは本当に最悪のケースです：HashSet内のすべての要素が同じハッシュコード（またはにつながるハッシュコードを持っている場合同じバケット）。 hashCodeと正しく配布されたキーサンプルでは、​​参照はO（1）です。

Answer 2

lookpは（C）

C =一定値

Answer 3

はい、しかし、私たちがHashSetsを持っている理由は、このワーストケースに非常に低い確率で遭遇し、通常、ヒープや（セルフバランシング）TreeSetの保証されたnlognよりもはるかに高速です。ソートされていないリストに対して保証されたn^2。