ハッシュ関数
ハッシュ対象のデータが十分に小さいなら、入力データそのものをハッシュ値として使うこともできる(何らかのバイナリを整数として再解釈する)。このような自明なハッシュ関数(恒等関数)の計算コストは事実上ゼロである。
「十分に小さい」の意味は、ハッシュテーブルに割り当てられるメモリ量に依存する。2008年現在、典型的なPCでは1GB程度のメモリが利用可能で、30ビット程度のハッシュ値なら扱える。ただし、多くの場合そこまで大きなハッシュテーブルは必要としない。例えば、英文の文字列の大文字/小文字の変換をするとき、各文字をバイナリ符号化したものを使い、その文字符号を整数のインデックスとしてテーブルを参照すると対応する変換後の文字符号が得られるようにするという方法が考えられる(例えば、'A' には 'a'、'8' には '8' を返すなど)。それぞれの文字が8ビットで表されていれば(ASCIIまたはISO Latin 1)、テーブルのエントリ数は 2 = 256 個だけとなるし、Unicodeの場合でも 17×2 = 1114112 エントリである。
同じ技法は 'us' とか 'ja' のような2文字国名コードを実際の国名にマッピングする場合(26=676 エントリ)、アメリカの5桁の郵便番号を地名にマッピングする場合(10万エントリ)などに利用できる。不正なデータ値(例えば国名コードなら 'xx'、ZIPコードなら 00000)に対応するエントリは未定義とされたり、何らかの 'null' 値にマッピングすることになるだろう。
ハッシュ関数は、低速な記憶媒体に格納された巨大なデータセットのためのキャッシュを構築するのに使うことがある。ハッシュテーブルと似ているが、キャッシュであるため、衝突が発生しても古い方のアイテムを消去するか本来の媒体に書き戻せばよいという特徴がある。
ハッシュ関数に衝突が多い場合、原像計算困難性を満たさないハッシュ関数では、任意の入力値からハッシュ値を得られるため、第2原像計算困難性を満たさない。また、第2原像計算困難性を満たさないハッシュ関数では、衝突困難性を満たさない。すなわち、
原像計算困難 ⊃ 第2原像計算困難 ⊃ 衝突困難
である。
ハッシュ関数の入力を「キー (key)」と呼ぶ。得られるハッシュ値は、2つ以上のキーから同じ値が得られることがある。これを衝突という。多くの場合、衝突の発生は最小限に抑えるのが望ましい。そのため、ハッシュ値の出現頻度は一様になるように設計しなければならない。
(等しいデータではなく)類似するデータを探索する用途では、ハッシュ関数は可能な限り連続となっているべきである。少しだけ異なる入力に対しては、同じハッシュ値かごく近いハッシュ値を生成すべきである。
なお、連続性はチェックサムや暗号学的ハッシュ関数などにとっては不適切な特性である。ハッシュ関数に連続性が必要となる用途は、線型探索を使うハッシュテーブルなどの用途である。