辞書はどのように高速検索を行うのですか

Question

辞書の記憶/検索のメカニズムを理解しようとしているItem[TKey]の出典を調べています。

私が混乱するところは、bucketsフィールドの素数のユーザーと、Entry<TKey,TValue>.nextの相互作用です。

誰かが私にその論理を説明することができますか、または私がそれを理解できる参照先を指すことができます。

ありがとうございました。ハッシュコードに

Answer 1

は、このWikipediaの記事でHash Tablesおそらくthis article about using prime numbers in hash table implementations.

Answer 2

見て、彼らは 'バケツ' に辞書のキー許可：

http://msdn.microsoft.com/en-us/library/4yh14awz%28VS.80%29.aspx

コリン・E.

Answer 3

ルックを参照してください。 Hashtable

辞書は単なる強タイプですハッシュテーブルの実装それは、キーで項目を置くいくつかの "バケツ"を持っています。

ハッシュテーブルに項目を追加すると、キーのハッシュコードを使用して、それを置くバケットを決定します（通常は非常に高速ですが、GetHashCodeを呼び出してモジュロを適用します）。バケット（ある種のリスト）があれば、バケットにすでに同じキーを持つアイテムが含まれているかどうかを確認し、そうでない場合は追加します。各バケットには、ハッシュテーブル内のすべてのアイテムの小さなサブセットしか含まれていないので、これも非常に高速です。

キーに基づいてアイテムを取得する場合は、キーのハッシュコードに基づいてバケットを決定し、バケット内のこのキーを持つアイテムを探します。

もちろん、これは非常に単純な説明です...詳細については、Wikipediaの記事をご覧ください。