データ構造におけるハッシュのオーバーフロー処理：線形探査・二次探査・ランダム探査の徹底解説

新しいペア（キー，要素）を格納すべきホームバケット（home bucket）がすでに満杯になっている状態をオーバーフローと呼びます。ハッシュテーブルを効率的に運用するには、このオーバーフローや衝突（コリジョン）をどのように解決するかが重要な課題となります。

オーバーフローへの主な対処方法

オーバーフローへの対処は、大きく分けて次の2つのアプローチがあります。

1. 空きバケットを体系的に探索する

ハッシュテーブル全体を一定の規則に従って走査し、空いているバケットを見つけて格納する方法です。

• 線形探査（Linear Probing／線形オープンアドレス法）
• 二次探査（Quadratic Probing）
• ランダム探査（Random Probing）

2. 各バケットにリストを持たせる

各バケットが、自分をホームバケットとするすべてのペアをリスト形式で保持することで、オーバーフローそのものを排除する方法です。

• 配列による線形リスト（Array Linear List）
• チェーン（Chain／連結リスト）

オープンアドレス法とは

オープンアドレス法では、すべての要素をハッシュテーブル本体に直接格納することを前提とし、衝突が発生した場合にさまざまな手法で別の格納位置を決定します。

線形探査は、その中でも最も基本的な手法で、衝突が起きたときにテーブル上の次の空きスロットへ順番にデータを配置していくことで衝突を解決します。

線形探査の性能

• 最悪の場合の検索・挿入・削除の計算時間は Θ(m) となります（m はテーブル内のペア数）。
• これは、すべてのペアが同一のクラスタ（占有領域の塊）内に存在する場合に発生します。

線形探査の問題点

• キー（識別子）同士がクラスタ化（塊状化）しやすい
• 隣接するクラスタ同士が合体しやすい
• その結果、探索時間が増大する

二次探査（Quadratic Probing）

二次探査は、増分として i の二次関数を用いることで、線形探査におけるクラスタ化の問題を緩和します。

調査対象となるバケットは次の通りです。

H(x), (H(x) + i²) % b, (H(x) − i²) % b　（1 ≤ i ≤ (b−1)/2）

ここで H(x) は x のハッシュ関数値、b はテーブルサイズです。なお、この方式が正しく機能するためには、b が 4j + 3 の形で表される素数（j は整数）である必要があります。

ランダム探査（Random Probing）

ランダム探査は、乱数列を組み合わせて次の調査位置を決定する手法です。

H(x) := (H′(x) + S[i]) % b

S[i] : サイズ b−1 のテーブル
S[i] : 整数 [1, b−1] のランダムな順列（パーミュテーション）

あらかじめ生成した乱数順列表 S を参照しながら調査位置を飛ばすことで、クラスタの形成を防ぎ、平均的な性能向上を図ります。

まとめ

ハッシュテーブルのオーバーフロー処理には、空きバケットを探索する「線形探査・二次探査・ランダム探査」といったオープンアドレス法と、各バケットにチェーンや配列リストを持たせる方法があります。それぞれに長所・短所があるため、データ量やアクセスパターンに応じて適切な手法を選択することが、高性能なハッシュ構造を実現する鍵となります。