c# - 代替コンパレータを使用する場合、O(1) はハッシュセット ルックアップで維持されますか?

Question

HashSet<T>ジェネリックinに独自のコンパレータを定義しSystem.Collections.Generic、そのランタイムが O(1) の場合、ハッシュセットのルックアップ時間は O(1) のままですか?

コンパレータを設定する方法がないように見えるという理由だけで、いいえと思います。

Answer 1

通常のハッシュセットのルックアップ時間が O(1) である理由は、オブジェクトを配列に配置するためにオープン アドレッシングを使用しているためです。そのため、独自のコンパレータを使用しても変わりません。

Answer 2

最良のケースでは、償却された O(1) の挿入と O(1) のルックアップがあります。

最悪の場合、償却された O(n) の挿入と O(n) のルックアップが行われます。

優れたコンパレーターは、優れたハッシュ方法を使用することで、実際のケースを最悪のケースよりも最良のケースに近づけるのに役立ちます。

悪いコンパレータは、まあ悪いでしょう。（すべてのハッシュコードに対して同じ値を返す意図的に悪いコンパレータを作成します[有効ですが無意味]、このO（n）の動作を見ることができます）。

優れたコンパレーターは運が悪くなる可能性がありますが、ほとんどの場合、実際のケースは O(1) に十分近いため、O(1) と見なすことができ、遠くに誘導することはできません。

編集：

「コンパレータを設定する方法がない」ということについて少し見逃しました。あります。 HashSet には、1 つを取るコンストラクターがあります。