ハッシュ関数
n 個のキーに対する完全ハッシュ関数が最小 (minimal) であるとは、その値域が n 個の連続な整数(通常 0 から n-1)の場合である。単に参照が単純化されるだけでなく、ハッシュテーブルもコンパクトになり、空きスロットができない。最小完全ハッシュ関数は単なる完全ハッシュ関数よりも求めるのが難しくなる。
同じ技法は巨大な文字列の集まりから同じ部分か類似する部分を見つけ出すのに応用できる。例えば、文書リポジトリや遺伝子データベースなどに応用できる。この場合、入力文字列群を多数の小さな部分に分割し、それらに対してハッシュ関数を適用して上述してきたような技法で同じ部分や類似の部分を探す。
ラビン-カープ文字列検索アルゴリズムは比較的高速な文字列検索アルゴリズムで、平均でO(n)の時間で動作する。このアルゴリズムは文字列の比較にハッシュ関数を使っている。
第2原像計算困難性(Second Preimage Resistance)とは、与えられた入力値に対して、その入力値をハッシュ関数へ入力したときのハッシュ値と同じハッシュ値を出力する入力値を求めることが困難であるような性質を言う。
データが非常に長い(または可変長の)文字列の場合(人名、URL、電子メールの中身など)、その分布は一様でないことが多く、複雑な依存関係が存在することが多い。例えば、自然言語の文章では文字の分布は全く一様ではないし、文字の並び方にも相関関係があり、その言語に特有の性質を持っている。その場合、ハッシュ関数は文字列内の全文字を何らかの形で使用し、しかもそれぞれの文字を異なった形で使用するのが望ましい。
そのようなデータをハッシュ値に変換する典型的手法は、入力を小さな単位(数ビット、数バイト、数ワードなど)の並び b[1], b[2], ..., b[m] に分割し、それを順に以下のように結合していく。
この手法は、テキストのチェックサムやフィンガープリントのアルゴリズムにも利用されている。状態変数 S は32ビットか64ビットの符号無し整数である。例の場合、S0 は 0 でよいし、G(S,n) は単に S mod n でよい。最適な F の選択は難しい問題で、データの性質にも依存する。データ単位 b[k] が1ビットなら、F(S,b) は例えば次のようになる。
ここで highbit(S) は S の最上位ビットを意味し、'*' 演算子は符号無しの整数の乗算でオーバーフローを無視する操作を表す。'^' はビット単位の排他的論理和演算を表し、P は適当な固定のワードである。