データ構造におけるユニバーサルハッシュとは？定義と仕組みをわかりやすく解説

ユニバーサルハッシュの背景にある問題

ハッシュ表の設計では、単一のハッシュ関数に頼ること自体に本質的な限界があります。ハッシュ表のサイズ m が、キー全体の集合（ユニバース）U のサイズ u に比べて非常に小さい場合、どんなハッシュ関数 h を選んでも、U の中には必ず同じハッシュ値へ対応づけられる大きな部分集合が存在してしまいます。

つまり、実際に入力されるデータ S がたまたまその「衝突しやすい部分集合」と一致すると、ハッシュ関数の性能は極端に劣化します。しかもこの問題は、事前に悪い入力の内容が分からない限り、回避することができません。

解決策：ハッシュ関数の族（ファミリー）を使う

この問題への有効な対策が、「複数のハッシュ関数からなる集合（族）」を用意し、その中から S に対してうまく機能するものを選ぶという考え方です。族の中の大多数の関数が S にとって良好な性能を示すのであれば、実行時にランダムに1つ選ぶだけで、安定した性能を期待できます。これがユニバーサルハッシュの基本的な発想です。

ユニバーサル（普遍的）なハッシュ関数族の定義

ハッシュ関数の族 ℌ が「ユニバーサル」であるとは、次のように定義されます。U に属する任意のキー x, y ∈ U に対して、h(x) = h(y) を満たすような h ∈ ℌ の個数が、高々 |ℌ|/m であること。

言い換えれば、ℌ からランダムに選んだハッシュ関数 h を用いたとき、互いに異なるキー x と y が衝突する確率は、h(x) と h(y) を集合 {0, 1, …, m − 1} から独立に一様ランダムに選んだ場合の衝突確率 1/m を超えない、ということです。

性能保証：探索・削除の計算量

ユニバーサルな族から選んだハッシュ関数 h を用いて集合 S をハッシュ表に格納した場合、連鎖法などの衝突解消手法と組み合わせることで、探索および削除にかかる期待時間は O(1 + α) となります。ここで α = n/m は、格納要素数 n を表のサイズ m で割った負荷率（ロードファクタ）です。

この保証が重要なのは、特定の入力分布に依存せず成立する点です。どのようなキーの集合が与えられても、期待性能が維持されるため、最悪ケースを狙った入力に対しても強靭という大きな利点があります。

参考：代表的な構成方法

実用上よく知られている構成として、|U| より大きい素数 p を取り、係数 a, b をランダムに選んで

h(x) = ((ax + b) mod p) mod m

とする方式があります。この族（Carter–Wegman 方式）がユニバーサルな性質を持つことは数学的に証明されており、実際のシステムでも広く利用されています。