c# - Hashtable - 再ハッシュ

Question

衝突を軽減/回避するために再ハッシュを使用しHashtableていると言われています。.NET

すなわち。「再ハッシュは次のように機能します。ハッシュの異なる関数 H1 ... Hn のセットがあると仮定します。ハッシュ テーブルからアイテムを挿入または取得するとき、最初に H1 ハッシュ関数が使用されます。これが衝突につながる場合は、代わりに H2 が試行され、Hashtable での衝突を回避するために Hn まで試行されます。」</p>

仮定: 漸近的な時間の複雑さが o(1) である n (n < Infinity) 要素を持つハッシュテーブルがあります。私たち (CLR) は、いくつかのハッシュ関数 (n>1 の Hn-1 ハッシュ関数) を適用しながらこれを達成しました。

質問: (異なるハッシュ関数が使用されている場合) 任意の要素をシーク (取得) するときに、CLR が Key をハッシュ コードにマップする方法を誰か説明してもらえますか? CLR はどのようにライブ オブジェクト (ハッシュ テーブル) のハッシュ関数を (もしあれば) 追跡しますか?

前もって感謝します

Answer 1

ハッシュ関数のランダムな選択は、Universal Hashingアプローチとして知られています。私の知る限り、ハッシュ関数は初期化プロセスごとに1回選択されるため、単一のハッシュテーブルの範囲内で複数のハッシュ関数が使用された場合、これは実際のケースではありません。

編集：詳細

家に戻って、「アルゴリズムの紹介」T.コーメンの本を開いて、セクション11.3.3ユニバーサルハッシュで次のことを見つけました：

ユニバーサル ハッシュの背後にある主なアイデアは、実行の開始時に、慎重に設計された関数のクラスからランダムにハッシュ関数を選択することです。

詳細については、こちらの Google ブックス サイトで書籍をプレビューしてください。