データ構造入門：ダブルハッシュ法の仕組みと計算例をわかりやすく解説

ダブルハッシュ法とは

ダブルハッシュ（Double Hashing）は、ハッシュテーブルの衝突解決手法である「オープンアドレス法」の一種です。基本となるハッシュ関数 h′(x)：U → {0, 1, …, m−1} に対して、挿入先のセルがすでに使用中だった場合に、もう一つのハッシュ関数を組み合わせて新しい格納位置を求めます。

ダブルハッシュでは、次の2つの補助ハッシュ関数を定義します。

第1ハッシュ関数： h₁(x) = x mod m
第2ハッシュ関数： h₂(x) = x mod m′
合成ハッシュ関数： h(x, i) = (h₁(x) + i·h₂(x)) mod m

ここで i は 0, 1, …, m−1 の値を取る試行回数です。i = 0 から探索を開始し、空きセルが見つかるまで i を1ずつ増やしていきます。i = 0 のときは h(x, 0) = h₁(x) となるため、最初は通常のハッシュ関数と同じ位置が調べられます。

ダブルハッシュのメリット

第2ハッシュ関数 h₂(x) がキーごとのステップ幅（探査間隔）を決めるため、線形探査で発生しやすい「一次クラスタリング」や、平方探査で起こりうる「二次クラスタリング」を効果的に抑制できます。また、m′ には m 未満の素数（例では13）を選ぶのが一般的で、これによりテーブル全体をくまなく探索できる可能性が高まります。

計算例

サイズ20（m = 20）のハッシュテーブルを考えます。次の11個の要素をダブルハッシュ法で格納していきます。

{96, 48, 63, 29, 87, 77, 48, 65, 69, 94, 61}

このとき使用するハッシュ関数は以下の通りです。

h₁(x) = x mod 20
h₂(x) = x mod 13
h(x, i) = (h₁(x) + i·h₂(x)) mod 20

挿入手順の例

最初のいくつかの要素を見てみましょう。

・96：96 mod 20 = 16 → セル16は空いているのでそのまま格納。
・48：48 mod 20 = 8 → セル8は空いているのでそのまま格納。
・29：29 mod 20 = 9 → セル9は空いているのでそのまま格納。

一方、衝突が発生した場合は h₂(x) を使って位置をずらします。例えば 69 は 69 mod 20 = 9 でセル9が使用中のため、h₂(69) = 69 mod 13 = 4 を用いて h(69, 1) = (9 + 1×4) mod 20 = 13 となり、空いているセル13へ格納されます。

各要素について h(x, i) = (h₁(x) + i·h₂(x)) mod 20 を計算した結果は、次の表のようになります。

最終的なハッシュテーブル

すべての要素を挿入した後のハッシュテーブルの状態は、次の画像の通りです。