.NETでHashTable/Dictionaryの実装に選択される衝突解決のタイプは何ですか？

Question

私たちが知っているように、衝突解決には2つの古典的な戦略があります：セパレートチェインとオープンアドレッシング。

私はHashTable/Dictionary for .netでどちらが選ばれたのだろうかと思っています。

他の戦略が使用されていましたか？

Answer 1

それは、すべてのMSDNでこの論文で説明しています：.NET Frameworkのハッシュテーブルクラスで使用される 技術であるrehasing呼ばAn Extensive Examination of Data Structures Using C# 2.0

...衝突解像技術、。最後の セクションでは、ディクショナリクラスを参照します。ディクショナリクラスでは、チェーンとして認識されている解決方法 の衝突を使用します。次のように ....

は... Rehasing作品：ハッシュ異なる 関数、H1のセットがある... Hnを、および挿入または からハッシュテーブルをアイテムを検索、最初にH1ハッシュ関数が使用されます。これにより、 が衝突した場合は、代わりにH2が試行され、必要に応じてHnまで実行されます。 前のセクションでは、最初のハッシュ関数（H1）が であるハッシュ関数が1つしか示されていませんでした。他のハッシュ関数はこの関数に対して非常によく似ていますが、乗法因子でしか区別できません。辞書のクラスは多くの方法よりも にハッシュテーブルクラスと異なる

Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize 

： 一般に、ハッシュ関数Hkのは以下のように定義されます。厳密に型付けされていることに加えて、Dictionaryも は、チェーンと呼ばれる手法を使用して、Hashtable クラスとは異なる衝突解決戦略を採用しています。 プロービングでは、衝突の場合、 バケットのリスト内の別のスロットが試行されることを思い出してください。 （ハッシュを再計算すると、ハッシュが再計算され、 新しいスロットが試行されます）。ただし、チェーンを使用すると、副次的なデータ構造 が使用され、衝突を保持します。具体的には、 辞書の各スロットには、そのバケットにマップされる要素の配列があります。 の衝突のイベントでは、衝突する要素が バケットのリストの先頭に追加されます。

最初の文は、実際に本当に面白い質問ですね私自身:-)

Answer 2

あるだけ覚えておいてください。私はちょうどblog postをDictionaryの背後に実装されている方法で実行しました。私は後でHashtableをカバーするかもしれません。