整数キーのハッシュテーブル入門：完全ハッシュ関数と誕生日のパラドックス

整数キーを扱うハッシュテーブルとは

ここでは、整数値をキーとして扱うハッシュテーブルについて解説します。キーの値 x は、次のような宇宙（ユニバース）U から取られるものとします。

U = {0, 1, …, u − 2, u − 1}

そして、ハッシュ関数 h の定義域はこの宇宙 U 全体であり、その値域は {0, 1, …, m − 1} の集合です。ここで、m ≤ u という条件が成り立ちます。

つまり、ハッシュ関数 h は、取り得るすべての整数キーを受け取り、それを 0 以上 m − 1 以下の整数に対応付ける役割を果たします。実際に格納するデータ数 m がキー空間のサイズ u より小さいため、複数の異なるキーが同じハッシュ値に衝突する可能性があります。これが「衝突（コリジョン）」と呼ばれる問題であり、ハッシュテーブル設計における中心的な課題となります。

完全ハッシュ関数とは

ある部分集合 S ⊆ U に対して、S 内のすべての要素 x について h(x) の値が互いに重複しない（一意である）とき、ハッシュ関数 h を集合 S に対する完全ハッシュ関数（perfect hash function）と呼びます。

さらに、m = |S| が成り立つ場合、その完全ハッシュ関数 h は最小完全ハッシュ関数（minimal perfect hash function）であるといいます。この場合、h は S から {0, 1, …, m − 1} への全単射（bijection）となり、各キーが配列の各スロットにちょうど一対一で対応します。

最小完全ハッシュ関数が理想的である理由は明らかです。長さ n の単一の配列に S の全要素を余白なく格納できるため、メモリの無駄がなく、検索も O(1) で実行できます。

なぜ完全ハッシュ関数は希少なのか

残念ながら、たとえ m が n より大幅に大きい場合であっても、完全ハッシュ関数は非常に稀です。その直感的な説明には誕生日のパラドックス（birthday paradox）が関係します。

S の各要素が {0, 1, …, m − 1} の中からランダムかつ独立に選ばれた値へ一様にマッピングされると仮定しましょう。このとき、m が n² より十分に小さいならば、誕生日のパラドックスにより、ほぼ確実に S 内のある 2 つの要素が同じハッシュ値を持つことになります。

これは、誕生日のパラドックスにおいて「23 人集まれば誕生日が一致するペアができる確率が 50% を超える」という性質と同じ構造です。つまり、衝突の発生は例外ではなくむしろ必然であり、実用的なハッシュテーブルでは、チェイン法やオープンアドレス法などの衝突対策、あるいは特定のキー集合に合わせて事前に完全ハッシュ関数を構築する手法（静的ハッシュ）が重要になります。

まとめ

• 整数キーのハッシュテーブルでは、キー宇宙 U = {0, 1, …, u − 1} を値域 {0, 1, …, m − 1} へ写像するハッシュ関数 h を用いる。
• S 内の全キーに対してハッシュ値が一意になる関数を完全ハッシュ関数、特に m = |S| の場合を最小完全ハッシュ関数と呼ぶ。
• 最小完全ハッシュ関数があれば、長さ n の配列だけで全要素を効率的に格納できる。
• しかし誕生日のパラドックスにより、m ≪ n² では衝突がほぼ確実に起こるため、完全ハッシュ関数の存在は稀である。