c# - HashSet 作成の最悪の場合の複雑さコレクションから

Question

int次の方法で値を設定する値のコレクションがありますHashSet<int>-

var hashSet = new HashSet<int>(myIEnumerable);

を反復すると仮定すると、そのような方法で を作成する最悪のケースの複雑さはIEnumerable何O(n)ですか?HashSet<int>

Answer 1

ドキュメントには実際に次のように記載されています。

このコンストラクターはO（n）操作です。ここで、nはコレクションパラメーター内の要素の数です。

http://msdn.microsoft.com/en-us/library/bb301504.aspx

Answer 2

セットが最大サイズに達したときにO(N^2)すべてが同じバケットにハッシュするオブジェクトを提供することで、最悪のケースをもたらすことができます。たとえば、次のように構成された17519のシーケンスを渡す場合int

x[i] = i * 17519

1からi17519までの場合、すべての数値は、Microsoftの実装の最初のバケットにハッシュされ、次のようHashSet<int>にO(N^2)挿入されます。

var h = new HashSet<int>(Enumerable.Range(1, 17519).Select(i => i*17519));

ブレイクポイントを設定し、デバッガーで調べhます。RawView/非公開メンバー/m_bucketsを見てください。最初のバケットには17519の要素があり、残りの17518にはすべてゼロがあることに注意してください。

Answer 3

縮退ハッシュコード (定数) を使った簡単な実験は、それが 2 次であることを示しています。

for(int n=0;n<100;n++)
{
    var start=DateTime.UtcNow;
    var s=new HashSet<Dumb>(Enumerable.Range(0,n*10000).Select(_=>new Dumb()));
    Console.Write(n+" ");
    Console.WriteLine((int)((DateTime.UtcNow-start).TotalSeconds*10));
}

出力:

0 0
1 8
2 34
3 73
4 131

---

HashCodefor intの多重衝突が発生しないと主張する人もいます。技術的にはそうですが、パフォーマンスにとって重要なのは HashCode の衝突ではなく、バケット インデックスの衝突です。HashSet<T>のようなものを使うと思いますbucket = (hash&0x7FFFFFFF)%Capacity。したがって、優先バケット サイズの倍数である一連の整数を追加しても、それでも非常に遅くなります。