Dictionary <TKey、TValue>でのハッシュ処理の仕組み

Question

Dictionaryでのハッシュ処理はどのように機能しますか？私は辞書を使用することでより速い検索ができると読んでいます。しかし、どのように理解できませんでしたか？ハッシュとインデックスへのマッピングはどのように行われますか？良い参照を見つけることができませんでした。

EDIT： オブジェクトが格納されている実際のメモリ位置は、ハッシュ関数の結果からどのように取得されますか？

Answer 1

ディクショナリのハッシュ処理では、チェーンと呼ばれる手法を使用します。 チェーニングでは、2次データ構造を使用して衝突を保持します。具体的には、ディクショナリの各スロットには、バケットにマップされる要素の配列があります。衝突の場合、衝突要素はバケットのリストの前に追加されます。

MSDNのthisの記事を参照してください。

Answer 2

Hash Mapと呼ばれるコンピュータサイエンスの概念を使用します。これはリストを検索するよりも速く動作します。これは、一致したものが見つかるまで、リストを反復処理する必要がないように検索を維持することによって機能します。代わりに、キーは "hashed"であり、リストのインデックスとして使用されます。このハッシュ関数は、リストを検索する（複数の比較を繰り返す）よりも、常に常に高速です。

Answer 3

通常、％arrayサイズのハッシュ値を取ることで、衝突が発生する可能性があります。

Answer 4

辞書では、参照のためにハッシュキーを使用して、my answer to your other questionで説明しようとしました。したがって、すべてのキーとしてカスタムオブジェクトタイプがある場合は、カスタムオブジェクトのGetHashKey()実装に依存します。

Answer 5

ハッシュテーブルまたは辞書は、キーと値のペアを格納するデータ構造です。ハッシュテーブルの利点は、対応する値がかなり高速であることがわかっているキーがある場合です。簡略化して、ハッシュテーブルでキーと値のペアを見つける時間は、テーブルのサイズに依存しません。キーと値のペアをリストまたは配列に格納する方法と比較してください。キーと値のペアを見つけるには、最初から一致するキーが見つかるまでリストを検索する必要があります。リストが長ければ長いほど、キーと値のペアを見つけるのに多くの時間がかかります。 big-O表記を使用すると、リスト内のキーをO（N）（簡略化）オーダーの線形検索を使用して検索しながら、ハッシュ・テーブルのキーを検索することはO（1）であると言うことができます。

ハッシュテーブルにキーと値のペアを挿入するには、まずそのキーのハッシュコードを計算する必要があります。 .NETでは、すべてのオブジェクトにGetHashCodeという名前のメソッドがあり、その特定のオブジェクトのハッシュコード（32ビット整数）が返されます。等しいオブジェクトが同じハッシュコードを返すことは重要ですが、異なるオブジェクトが異なるハッシュコードを返す場合は非常に便利です。異なるオブジェクトが同じハッシュコードを返すことはできないという誤解に気をつけてください。可能であれば、の衝突（下記参照）が発生します。一例として、

2つの文字列のハッシュコードを考えてみます。文字列は、彼らが異なるハッシュコードを持っている非常によく似ているにもかかわらず

 
"Boo" 0x598FD95A 
"Foo" 0x598FD8DE 

。

ここでは、ハッシュテーブルの重要な側面に焦点を当てるために少し簡略化していますので、今度は内部でDictionary<TKey, TValue>がキーと値のペアを配列に格納しています。この配列内のキーと値のペアが格納されるインデックスを見つけるには、配列のサイズを法とするキーのハッシュコードを計算する必要があります。

 
Index("Boo") = 0x598FD95A % 5 = 4 
Index("Foo") = 0x598FD8DE % 5 = 0 

これは、この内部ハッシュテーブルアレイにつながる：ハッシュテーブル内のエントリを探し

 
+---+---------+ 
| 0 | "Foo" | 
+---+---------+ 
| 1 | (empty) | 
+---+---------+ 
| 2 | (empty) | 
+---+---------+ 
| 3 | (empty) | 
+---+---------+ 
| 4 | "Boo" | 
+---+---------+ 

は非常に高速である配列のサイズが5であると仮定します。内部配列のサイズを法とするキーのハッシュコードを計算し、そのインデックスで文字列を取得するだけで済みます。それは、キー「ブー」と同じインデックスを持つ

 
Index("Zoo") = 0x598FDC62 % 5 = 0 

：

は今キー「動物園」を検討してください。この結果、の衝突が発生します。ハッシュテーブルを適切に実装するには、衝突を処理する必要があり、different strategies for doing thatがあります。また、内部配列がいっぱいになると、配列内の空要素が少なくなり、衝突の数が増えます。 負荷係数は、使用された要素と内部配列の合計要素の比率です。上記の例では、負荷率は2/5 = 0.4です。ほとんどのハッシュテーブルの実装では、負荷係数が特定のしきい値を超えたときに内部配列のサイズが大きくなります。

これらの概念のいくつかについてもっと知りたい場合は、他の回答にリンクされているより包括的なリソースのいくつかを検討する必要があります。