2択ハッシュ

2 選択ハッシュ法は、 2 選択連鎖法とも呼ばれ、「ハッシュ テーブルの変形で、2 つのハッシュ関数を使用してハッシュすることでキーが追加されます。キーは、衝突するキーの数が少ない配列の位置に配置されます。キーがバケットに保存されていない限り、何らかの衝突解決スキームが必要です。成功した検索の平均コストは で、 はキーの数、は配列のサイズです。衝突が最も多く発生する確率は高いです。」^[1]${\displaystyle O(2+(m-1)/n)}$${\displaystyle m}$${\displaystyle n}$${\displaystyle \log _{2}\ln n+\theta (m/n)}$

2 選択ハッシュ法では、ハッシュ関数が期待されるとおりに機能する 2 つのハッシュ関数h ₁ ( x ) とh ₂ ( x ) を使用します (つまり、整数を全範囲から指定された範囲にマッピングします)。2 つのハッシュ関数は独立しており、相互に相関関係はありません。2 つのハッシュ関数を使用すると、各出力h ₁ ( x ) と h ₂ ( x )の値に基づいて、任意のキーx を最大 2 つの潜在的な場所に格納できます。ハッシュ関数は 2 つありますが、テーブルは 1 つだけであることに注意することが重要です。両方のハッシュ関数は、そのテーブル上の場所にマッピングされます。

この場合のハッシュ実装の最も重要な機能は、挿入と検索です。

• 挿入:挿入時に、挿入するオブジェクトに対して両方のハッシュ関数の値が計算されます。その後、オブジェクトは、オブジェクトの数が少ない方のバケットに配置されます。バケットのサイズが同じ場合、デフォルトの場所はh ₁ ( x ) 値です。
• 検索:効果的な検索は、両方のバケット ( h ₁ ( x ) とh ₂ ( x ) がマッピングされているバケットの場所) で目的の値を検索することによって行われます。

すべてのハッシュ テーブルと同様に、パフォーマンスは最大のバケットに基づいて決まります。値と使用されるハッシュ関数に基づいてバケット サイズが大きくなる場合もありますが、これはまれです。ハッシュ関数が 2 つあるため、1 つの値に対して 2 つの場所が考えられるため、バケットが大きくなる可能性はさらに低くなります。

2 選択ハッシュを使用する場合の予想されるバケット サイズは、θ (log(log( n )))です。この改善は、「2 つの選択の力」と呼ばれるランダム化の概念によるものです。

ハッシュ関数を 2 つ使用すると、1 つのハッシュ関数を使用する場合よりも大きな利点があります。2 つ以上のハッシュ関数を使用した場合、改善はほとんど見られません (期待される順序統計も変わりません)。「ハッシュ関数を追加しても、最大値は一定の割合で減少するだけです。」^[2]

一部のCPUキャッシュでは、 2ウェイスキューアソシアティブキャッシュと呼ばれる2選択ハッシュの一種を推奨する人もいます。^[3]

2左ハッシュ法は、サイズがn /2 のハッシュテーブルを2つ使用し、キーを左ハッシュテーブルに置くことで非対称的に同点を解決するため、衝突が少なく、サイズがnの1つの大きなハッシュテーブルを使用する2選択ハッシュ法よりもパフォーマンスが優れています。^{[4] [全文引用が必要]}

 この記事には、 Paul E. Blackのパブリック ドメイン資料が組み込まれています。「2 選択ハッシュ」。アルゴリズムとデータ構造の辞書。NIST 。

• Azar, Yossi、Broder, Andrei Z.、Karlin, Anna R.、Upfal, Eli (1994 年 5 月 23 ～ 25 日)、「Balanced Allocations (extended abstract)」(PDF)、第 26 回 ACM コンピューティング理論シンポジウム議事録 - STOC '94、モントリオール: Association for Computing Machinery、pp. 593 ～ 602、CiteSeerX  10.1.1.38.5375、doi :10.1145/195058.195412、ISBN 0897916638、S2CID  1014349
• アザール、ヨッシ、ブローダー、アンドレイ Z.、カーリン、アンナ R.、アップファル、エリ (1999)、「バランスのとれた配分」(PDF)、SIAM J. Comput.、29 (1): 180–200、doi :10.1137/S0097539795288490