ハッシュテーブルの衝突再ハッシング - 値はどのように読み取られますか？

Question

私はHashtableがC＃でどのように動作するかを理解しようとしています。私はMSDNの記事を読んで、C＃Hashtablesが衝突に対してrehashingを使うことを理解しています。つまり、ハッシュテーブルにキー/値のペアを挿入しようとするとHashFunction H1の結果が衝突した場合、HashFunction H2、H3衝突が検出されなくなるまで繰り返す。

MSDN引用：

ハッシュテーブルクラスは rehasingと呼ばれる別の技術を使用します。 （いくつかのソースは、二重ハッシュとして再ハッシュを参照。）

を次のように作品を焼き直し：最初に、そこハッシュ異なる 関数、H1 ... Hnのセットであり、 ハッシュテーブルから項目を挿入または取り出すときH1ハッシュ関数が使用されます。これにより、 が衝突した場合は、代わりにH2が試行され、必要に応じてHnまで実行されます。 前のセクションでは、最初のハッシュ関数（H1）が であるハッシュ関数が1つしか示されていませんでした。他のハッシュ関数はこの関数に対して非常によく似ていますが、乗法因子でしか区別できません。

のHk（キー）= [GETHASH（キー）+ K×（1 +（（（GETHASH（キー）>> 5）+ 1）％ （HASHSIZE： 一般に、ハッシュ関数Hkのは以下のように定義されます - 1）））]％のHASHSIZEしかし

、MSDNサイト1から例を取る：

private static Hashtable employees = new Hashtable(); 

public static void Main() 
{ 
    // Add some values to the Hashtable, indexed by a string key 
    employees.Add("111-22-3333", "Scott"); 
    employees.Add("222-33-4444", "Sam"); 
} 

はのは、2番目のキーを追加すると、衝突が発生すると仮定しましょう、そうH2がする必要があります中古。しかし、私が従業員に電話をかけたときには（ "222-33-4444"）、ハッシュテーブルはH2をどのように知っていますか？別のマッピングがありますか？ありがとう。

Answer 1

ハッシュテーブルは、キーとハッシュテーブル自体の値の両方を格納するステップに。このようにして、ハッシュテーブル参照などの操作中に後で検索された値がルックアップに使用されたインデックスと一致することが保証されます。ハッシュテーブルは単純な「成功までのルックアップの基本的な方法を試す」方法論を使用します。この場合、ルックアップの方法は、「使用ハッシュ関数X」であり、ここでXは失敗すると変化する。ルックアップの方法は、（それぞれハッシュ関数によって決定される）「テーブルエントリXを見る」であり、Xはそれぞれの失敗のラッピング方法で1だけ増加する。

テーブルの中に値が入っていない場合、どうにもならない問題が発生しますか？そうですね、それはむしろ醜いかもしれません：あなたが欠けているテーブルのエントリを叩いたり、さらに悪いことに、テーブルに格納されているエントリを何回も繰り返したときに、エントリisnそこには - しかし、最悪の場合には "しばらく"かかることがあります。

キーに関連付けられる値は1つだけなので、キーが見つかるとその値が見つかります。ハッシュテーブルでできる最悪のことは、ハッシュテーブル自体のすべての値に対してキャッシュ不自然な線形検索と同等の処理をしなければならないことです...しかし、最終的には、格納されたキーとリクエストされたキーが存在するかどうかをテストします。最適化された最適化されたハッシュテーブルの作成は、ハッシュ関数1が次に2、次に3がどこにあるかを最初に調べる場所です。

Answer 2

まずH1を試します。一致するものが見つからない場合は、H2を使用します。等々。

Answer 3

再ハッシングを誤解していると思います。ハッシュ関数は1つしかありません。つまり、仮想object.GetHashCode()（または、IHashCodeProviderまたはIEqualityComparerを指定した場合は、そのオブジェクトを使用してハッシュコードを計算します）。ハッシュテーブルがいっぱいになると、その容量が拡大され、要素が新しい大きな配列に再配布されます。これを行うプライベートメソッドはRehash()と呼ばれますが、ハッシュコードは再計算されません。

CORRECTION

再ハッシュが新しい機能を使用するのではなく、ハッシュコードの前回値に基づいて動作しません。これは、空の文字列が見つかるか（挿入/セットされる）、または同じ（初期の）ハッシュコードを持つすべてのキーがインデックスキーと等しいかどうか（検索のために）チェックされるまで、

をさんは、2番目のキーを追加すると、衝突が発生すると仮定しましょう、そうH2を使用する必要があります：直接あなたの質問に答えるために

EDIT

。しかし、私が従業員に電話をかけたときには（ "222-33-4444"）、ハッシュテーブルはH2をどのように知っていますか？別のマッピングがありますか？ありがとう。

1. 渡されたキーのハッシュコードに基づいて正しいバケットを計算します。
2. そのバケットが空の場合、失敗します。
3. バケットのキーが渡されたキーと一致する場合は、バケットの値を返します。
4. ハッシュの衝突回数がゼロの場合は失敗します。
5. 現在のハッシュコードから次のハッシュコードを計算します。
6. 新しいハッシュコードに基づいて正しいバケットを計算します。
7. 移動2.