c# - Dicionary.ContainsKey() のルックアップ時間

Question

私がウィキペディアで読んだように、ハッシュテーブルには平均O(1)検索時間があります。

たとえば、おそらく数千万のレコードを含む非常に大きな辞書があるとします。

特定のキーに対して値を抽出するために使用Dicionary.ContainsKeyすると、ルックアップ時間は実際には 1 になりますか、.NET による内部実装が異なるため、log n などのようになります。

Answer 1

Big Oh 記法は、何かにかかる時間を教えてくれません。どのようにスケーリングするかを示します。

最も簡単に想像できるのは、List<> 内の項目を検索することです。O(n) の複雑さがあります。100 万の要素を持つリスト内のアイテムを見つけるのに平均で 2 ミリ秒かかる場合、リストに 200 万の要素がある場合は 4 ミリ秒かかると予想できます。リストのサイズに比例してスケーリングします。

O(1)は、辞書内の要素を見つけるための一定の時間を予測します。つまり、辞書のサイズに依存しません。ディクショナリが 2 倍の大きさの場合、要素を見つけるのに 2 倍の時間はかかりませんが、(おおよそ) 時間がかかります。「おおよそ」とは、実際にはもう少し時間がかかることを意味し、O(1)で償却されます。

Answer 2

O(1)エントリの数には依存せず、衝突の数に依存するため、に近いままです。O(1)アイテムの数に関係なく、配列のインデックス作成は引き続き.

Dictionaryまた、実装に起因するサイズの上限があるようです: How is the c#/.net 3.5 dictionary implemented?

このサイズを渡すと、次のステップは内部配列の外になり、より大きな素数を手動で検索します。これはかなり遅くなります。7199369 (配列内の最大値) で初期化するか、Dictionary に約 500 万を超えるエントリがある場合、設計を再検討する必要があるかどうかを検討してください。

Answer 3

キーは何ですか？キーが Int32 の場合、はい、オーダー 1 に近くなります。

ハッシュの衝突がある場合、オーダー 1 未満しか得られません。
Int32 をキーとして使用すると、ハッシュの衝突はゼロになりますが、ハッシュ バケットの衝突がゼロになることは保証されません。

ハッシュの衝突を引き起こすキーには注意してください。
KVP とタプルは多くのハッシュ衝突を引き起こす可能性があり、キーの候補としては適していません。