ハッシュ関数
ハッシュ関数は、キーが似ているが全く同一ではない場合のレコード検索にも使える。この場合の入力は1つのキーか、似たようなキーを持つ巨大ファイル内の2つのレコードである。このためには、似たようなキーを与えられたとき、最大でも m しか違わないハッシュ値(m は小さい整数で例えば1か2)を生成するハッシュ関数を必要とする。このようなハッシュ関数を使って全レコードに関するハッシュテーブル T を構築すると、似たようなレコードは同じバケットか近いバケットに格納されることになる。すると各バケット T[i] について、-m から m の範囲の k で表されるバケット T[i+k] に格納されているレコード群を相互に比較すればよい。
この応用として声紋アルゴリズムと呼ばれる技法がある。これを使うと音声ファイルの巨大なコレクションから似たようなエントリを探すことができる(MusicBrainzの楽曲ラベリングサービスで使われている)。この場合のハッシュ関数は、ノイズやタイミングの違いや音量の違いといった差異をなるべく無視できるようなものであることが望ましい。
この原理は、コンピュータグラフィックスや計算幾何学を代表とする様々な分野で、2次元平面や3次元空間でのいわゆる類似性問題を解くのに使われている。例えば、多数の点から最も近い2つの点を探すとか、一連の形状から類似した形状を探すとか、画像データベースから類似する画像を探すなどの用途である。これらの用途では、あらゆる入力は何らかの距離空間にあり、ハッシュ関数はその空間を格子状に分割するものと解釈できる。このときに使用するテーブルは2次元以上の配列であり(グリッドファイルなどと呼ぶ)、ハッシュ関数はその次元数に対応した一連のインデックスを返す。このようなハッシュ技法を幾何学的ハッシュなどと呼ぶ。幾何学的ハッシュは電気通信でのベクトル量子化でも使われており、多次元の信号を符号化し圧縮するために使われている。
巨大なソートされていないファイルから重複したレコードを探す場合、各レコードをハッシュ関数に入力して配列 T のインデックスを得て、各バケット T[i] にハッシュ値が i になった全レコードの番号をリストの形で集める。この配列が完成すると、重複したレコードは必ず同じバケットに存在しているはずである。そこで、リストの要素数が2つ以上のバケット全てについて実際のレコードを求めて比較することで、重複レコードを探すことができる。配列が適切な大きさであれば、この方法が他のどんな方法(ファイルをソートし、隣り合うレコードを比較していく方法など)よりも高速な場合が多い。
Secure Hash Algorithmのような暗号学的ハッシュ関数は、チェックサムやフィンガープリントよりも強力な一様性を保証するので、汎用ハッシュ関数としても最適である。
しかし暗号化などの用途以外では、その計算コストが高いため利点が打ち消されてしまう。しかし、悪意ある者がキーを選んでもハッシュ値が一様に分布するという特性がある。このためDoS攻撃からサービスを保護する助けとなる場合もある。
ハッシュ関数が単射の場合、すなわち正しい入力に対して必ず異なるハッシュ値が対応する場合、これを完全 (perfect) だという。このような関数を使えば、1つのハッシュテーブルで目的のエントリを直接探すことができ、それ以外の探索の手間が生じない。
完全ハッシュ関数は、入力される範囲が予め分かっていて変化しない場合のみ成立する。例えば英語の月の名前を0から11の整数にマッピングするとか、ある辞書に掲載されている単語にハッシュ値を割り当てるといった場合である。入力の集合を与えられると、それに対応した完全ハッシュ関数を実行する最適化されたサブルーチンを出力する生成器がいくつか存在する(例えば、GNU gperf)。