静的パーフェクトハッシュ（FKSハッシング）とは？定義・応用例・実装方法を徹底解説

パーフェクトハッシングの定義

パーフェクトハッシングとは、任意の n 個の要素からなる集合を、それとほぼ同サイズのハッシュテーブルに格納し、すべての検索（ルックアップ）を定数時間 O(1) で実行できるようにするハッシングのモデルです。この手法は1984年にフレッドマン（Fredman）、コムロシュ（Komlós）、セメレディ（Szemerédi）の3名によって考案・発表されたことから、「FKSハッシング」という名称でも広く知られています。

静的ハッシングの定義

静的ハッシングは、確定済みの辞書集合（辞書内のすべての要素が最終状態にあり、以後一切変更されないもの）に対して検索を行うことを前提とした、ハッシング問題のもうひとつの形態です。

静的パーフェクトハッシュの応用例

静的ハッシングでは、データベース本体・そのオブジェクト・参照関係のすべてが不変であることが要求されるため、適用範囲はどうしても限定されます。ただし、更新頻度がきわめて低い情報を扱うデータベースであれば、まれにデータベース全体の再ハッシュを実行するだけで運用できるため、十分に採用候補となります。

具体的な応用例としては、以下のようなものが挙げられます。

• 特定の言語における単語とその定義の集合（辞書データ）
• 組織の人事に関する重要データの集合
• その他、内容がほとんど変わらない固定データの高速検索

実装方法（FKS方式）

静的なケースでは、あらかじめ一意なキーを持つ合計 p 個のエントリからなる集合が与えられます。Fredman、Komlós、Szemerédi の手法では、まずサイズ s = 2(p−1) バケットの第一レベル（トップレベル）ハッシュテーブルを用意します。構築の手順は以下の通りです。

1. トップレベルでの振り分け： p 個のエントリを、上位レベルのハッシュ関数によって q = 2(p−1) 個のバケットへ分配します。
2. 第二レベルテーブルの割り当て： r 個のエントリを含む各バケットに対して、r² スロットを持つ第二レベルのテーブルを確保します。
3. ハッシュ関数の選択： 第二レベルのハッシュ関数は、普遍ハッシュ関数族の中からランダムに選びます。これにより衝突（コリジョン）のないテーブルを実現します。
4. 衝突時のやり直し： もしランダムに選んだハッシュ関数で衝突が生じた場合は、衝突のないテーブルが得られるまで別のハッシュ関数を選び直します。
5. エントリの配置： 最後に、衝突のないハッシュ関数を用いて r 個のエントリを第二レベルのテーブルへ格納します。

この二段階構成により、必要な記憶領域の総量は期待値として入力サイズに比例し、かつすべての検索を定数時間で完了させることが理論的に保証されます。