# 完全ハッシュ関数と最小完全ハッシュ関数 [ハッシュ関数 - Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E9%96%A2%E6%95%B0) ## 完全ハッシュ関数 ハッシュ関数が単射の場合、すなわち正しい入力に対して必ず異なるハッシュ値が対応する場合、これを**完全** (perfect) だという。このような関数を使えば、1つのハッシュテーブルで目的のエントリを直接探すことができ、それ以外の探索の手間が生じない。 完全ハッシュ関数は、入力される範囲が予め分かっていて変化しない場合のみ成立する。例えば英語の月の名前を0から11の整数にマッピングするとか、ある辞書に掲載されている単語にハッシュ値を割り当てるといった場合である。入力の集合を与えられると、それに対応した完全ハッシュ関数を実行する最適化されたサブルーチンを出力する生成器がいくつか存在する（例えば、GNU gperf）。 ## 最小完全ハッシュ関数 $n$ 個のキーに対する完全ハッシュ関数が**最小** (minimal) であるとは、その値域が $n$ 個の連続な整数（通常 $0$ から $n-1$）の場合である。単に参照が単純化されるだけでなく、ハッシュテーブルもコンパクトになり、空きスロットができない。最小完全ハッシュ関数は単なる完全ハッシュ関数よりも求めるのが難しくなる。 ^b525c9 ![[Hash_table_4_1_0_0_0_0_0_LL.svg|400]] ### Knuth's Multiplicative Hash 👉 [[Knuth's Multiplicative Hash]] [[ドナルド・クヌース|ドナルド・クヌース (Donald Ervin Knuth)]] による最小完全ハッシュ関数