データ構造の線形探索法（リニアプロービング）とは？仕組みと具体例をわかりやすく解説

線形探索法（リニアプロービング）とは

本記事では、ハッシュテーブルの衝突解決手法の一つであるオープンアドレス法における「線形探索法（リニアプロービング）」について詳しく解説します。

まず、通常のハッシュ関数 h′(x)：U → {0, 1, …, m−1} を考えます。ここで U はキーの全体集合、m はハッシュテーブルのサイズです。

h′(x) = x mod m

オープンアドレス法では、この通常のハッシュ関数 h′(x) に試行回数 i を組み合わせ、次のような線形式として実際のハッシュ関数 h(x, i) を定義します。

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

i は 0, 1, …, m−1 の値を取ります。i = 0 から開始し、空きスロットが見つかるまで 1 ずつ増やしていきます。i = 0 のときは h(x, 0) = h′(x) となるため、最初の挿入位置は通常のハッシュ関数の計算結果と一致します。

動作の流れ

1. キー x に対して h′(x) = x mod m を計算する。
2. 計算結果のスロットが空いていれば、そこにキーを格納する。
3. すでに使用されている場合（衝突が発生した場合）、i を 1 増やして h(x, i) = (h′(x) + i) mod m を再計算する。
4. 空きスロットが見つかるまでこの手順を繰り返す。

具体例：サイズ20のハッシュテーブル

サイズ 20（m = 20）のハッシュテーブルを用意し、次の要素を線形探索法で挿入していきます。

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

ハッシュテーブル 

挿入手順の計算例

各要素の初期配置は以下のように求められます。

• 96 mod 20 = 16 → スロット16へ格納
• 48 mod 20 = 8 → スロット8へ格納
• 63 mod 20 = 3 → スロット3へ格納
• 29 mod 20 = 9 → スロット9へ格納
• 87 mod 20 = 7 → スロット7へ格納
• 77 mod 20 = 17 → スロット17へ格納
• 48 mod 20 = 8 → 衝突発生。スロット9も使用中のため、さらに探索を続けてスロット10へ格納
• 65 mod 20 = 5 → スロット5へ格納
• 69 mod 20 = 9 → 衝突発生。スロット10も使用中のため、スロット11へ格納
• 94 mod 20 = 14 → スロット14へ格納
• 61 mod 20 = 1 → スロット1へ格納

メリットとデメリット

メリット： アルゴリズムが非常にシンプルで実装が容易です。また、メモリ上のデータの局所性が高いため、キャッシュ効率にも優れています。

デメリット： 「一次クラスタリング」と呼ばれる現象が発生しやすい点に注意が必要です。特定の領域にデータが集中すると、空きスロットを見つけるまでの探索距離が長くなり、挿入・検索の性能が低下する可能性があります。