ダイナミックパーフェクトハッシュとは？定義・特徴・実装の仕組みを解説

ダイナミックパーフェクトハッシュ（Dynamic Perfect Hashing）は、ハッシュテーブルデータ構造において発生する衝突（コリジョン）を解決するためのプログラミング手法として定義されています。

適用場面

この手法は、他のハッシュテーブル方式と比較して多くのメモリを消費するというトレードオフがあります。しかし一方で、大量の要素集合に対して高速な検索（クエリ）、挿入、削除を繰り返し実行する必要がある状況において理想的な選択肢となります。

実装の仕組み

Dietzfelbinger らによって提案された動的辞書アルゴリズムでは、m 個の項目が辞書へ逐次的に追加されていく状況を想定し、次のような性能特性を保証します。

• メンバーシップクエリ（要素の存在確認）は常に定数時間で実行され、最悪計算時間も O(1)
• 必要な総記憶容量は O(m)（線形）
• 挿入・削除の期待償却時間は O(1)（償却定数時間）

衝突発生時の処理

動的なケースでは、キーがハッシュテーブルに挿入される際、対応するサブテーブル内のエントリが既に占有されていると衝突が発生します。この場合、該当するサブテーブルは、新しい総エントリ数とランダムに選択されたハッシュ関数に基づいて再構築されます。

第二レベルテーブルの負荷率（ロードファクタ）は低く保たれているため、再構築が頻繁に起こることはなく、その結果、挿入および削除の償却期待コストは O(1) に抑えられます。

サイズが事前不明な場合への対応

さらに動的なケースでは、トップレベルテーブルや各サブテーブルの最終的なサイズについて事前に知ることができません。テーブル全体の期待記憶容量 O(m) を維持するための代表的な技法として、十分な回数の挿入と削除が行われた時点でテーブル全体の再構築（フルリビルド）を実行する方法があります。

挿入または削除の総回数が、前回の構築時点での要素数を超えない限り、完全な再ハッシュのコストを考慮に入れても、挿入および削除の償却期待コストは O(1) のまま維持されます。