静的ハッシュ

静的ハッシュでは、データベース、そのオブジェクト、および参照が同じままでなければならないため、その適用範囲は限られています。まれに変更される情報を含むデータベースも適しています。これは、まれにデータベース全体を完全に再ハッシュする必要があるためです。その例としては、特定の言語の単語と定義のセット、組織の人員に関する重要なデータのセットなどがあります。^{[ 1 ]}

完全ハッシュはハッシュのモデルであり、任意のセットが${\displaystyle n}$要素は同じサイズのハッシュテーブルに格納でき、定数時間で検索を実行できます。これは特にフレドマン、コムロス、セメレディ（1984）によって発見され議論されたため、「FKSハッシュ」というニックネームが付けられました。^{[ 2 ]}

最上位レベルにはランダムに生成されたハッシュ関数が含まれています。${\displaystyle h(x)}$これは、ユニバーサルハッシュのCarterとWegmanのハッシュ関数の制約内に収まります。そうすることで、最上位レベルには以下が含まれます。${\displaystyle n}$ラベルの貼られたバケツ${\displaystyle k_{1},k_{2},k_{3},...,k_{n}}$このパターンに従って、すべてのバケットにはサイズのハッシュテーブルが格納されます。$s_i$およびそれぞれのハッシュ関数${\displaystyle h_{i}(x)}$ハッシュ関数は、設定によって決定されます。$s_i$に${\displaystyle k_{i}^{2}}$そして、衝突がなくなるまで関数をランダムに順に処理していく。これは定数時間で実行できる。

なぜなら${\displaystyle n \choose 2}$衝突確率が等しい要素のペア${\displaystyle 1/n}$FKSハッシュでは、厳密に以下になることを期待できます。${\displaystyle n/2}$衝突。この事実と各${\displaystyle h(x)}$衝突回数が最大で${\displaystyle n/2}$下階の各テーブルのサイズは以下になります${\displaystyle 2n}$。