データ構造における二次プロービング（Quadratic Probing）とは？仕組みと具体例を解説

二次プロービング（Quadratic Probing）とは

二次プロービングは、ハッシュ表で衝突が発生した際に対応する手法の一つである「オープンアドレス法（open addressing）」で用いられる衝突解決技術です。

まず、通常のハッシュ関数 h′(x) : U → {0, 1, ..., m − 1} が与えられているものとします。オープンアドレス法では、この基本となるハッシュ関数に別の要素を組み合わせて二次式を構成することで、実際に使用するハッシュ関数 h(x) を作り上げます。

h′(x) = x mod m

h(x, i) = (h′(x) + i²) mod m

ここで使用する二次式は、定数を加えることで別の形に変更することも可能です。

i の値は 0, 1, ..., m − 1 の範囲で変化します。探索は i = 0 から始め、ハッシュ表内の空きスロットが見つかるまで i を順に増やしていきます。最初の i = 0 の時点では、h(x, i) は元のハッシュ関数 h′(x) と同一の値となります。

二次プロービングのポイント

線形プロービングでは、隣接するスロットを順番に調べるため「一次クラスタリング（primary clustering）」と呼ばれる、データが特定の場所に集中する問題が起きやすいという弱点があります。二次プロービングでは探索位置を i² ずつ離すため、このようなデータの偏り（クラスタリング）を大幅に緩和できます。

ただし、同じ初期ハッシュ値を持つ異なるキーは同一の探索順序をたどる「二次クラスタリング（secondary clustering）」が発生する点には注意が必要です。また、表のすべてのスロットを効率よく利用するには、表のサイズ m を素数に設定し、負荷率を0.5以下に抑えることが推奨されます。

具体例

サイズ20（m = 20）のハッシュ表を用意し、次の要素を二次プロービング方式で挿入していきます。

挿入する要素：{96, 48, 63, 29, 87, 77, 48, 65, 69, 94, 61}

各要素に対して h′(x) = x mod 20 を計算し、衝突が発生した場合は h(x, i) = (h′(x) + i²) mod 20 に従って、空きスロットが見つかるまで探索を続けます。たとえば、48 は初回の計算でインデックス8に配置されますが、後から同じハッシュ値を持つもう一つの 48 が挿入される際には衝突が生じるため、i² を加算した位置へと再配置されます。

ハッシュ表