ハッシュ関数
"hash" という用語は、本来の「切り刻んで混ぜる」という意味からの類推で使われるようになった。実際、合同操作を行う典型的なハッシュ関数は、入力の定義域を多数の部分に「切り刻み」、キーの分布が値域で一様になるように「混ぜた」形で出力する。
ドナルド・クヌースによれば、この用語を最初に使ったのはIBMの Hans Peter Luhn で、1953年1月の社内メモで使っていた。そして、Robert Morris が学会誌 Communications of the ACM に掲載した論文でこの用語を使い、単なるジャーゴンから正式な専門用語に昇格した。
例えば、「ある文書が正確かどうか検証したいが、その文書そのものを記録・比較したくない」場合を考える。ここでもしこの文書を代表する数値(文書の要約)を数学的に作り出すことができれば、この要約だけを記録し、比較すれば良いことになる。このような要約を作る操作がハッシュ化である。
より具体的に、今、ハッシュ関数として、「5字ごとに1字を選択し、その列を並べたものをハッシュ値とする」という操作を選択したとすると、このハッシュ関数によって、元の文書を1/5に短縮することができる。しかしこの方法では、
うまく間に適当な文字を入れて、別の文書を作ることが出来る。
推測から元の文書も復元できてしまう事もある。
短い定型的文章では、異なる文書から同じ要約が出来てしまうこともあり得る(衝突、コリジョン)。
1万字の文章では、要約だけで2000文字になる
という問題がある。そこで、このようなことが確率論的に現実には起こりにくくなるようなハッシュ関数を工夫をする必要がある。
通常は元データのバイナリ表現を使い、それを複雑に操作し数十~数百ビットのハッシュ値を作る。
改竄の検出を行う場合は、単純なハッシュ関数アルゴリズムを用いると、容易に同じハッシュ値を求めることができるため、安全に設計されたハッシュ関数を用いる必要がある。
ハッシュ関数 (ハッシュかんすう、英語: hash function) あるいは要約関数とは、任意のデータから、別の(多くの場合は短い固定長の)値を得るための操作、または、その様な値を得るための関数のこと。ハッシュ関数から得られた値のことを要約値やハッシュ値または単にハッシュという。
ハッシュ関数は、主に検索の高速化やデータ比較処理の高速化、さらには改竄の検出に使われる。例えば、データベース内の項目を探したり、大きなファイル内で重複しているレコードや似ているレコードを検出したり、核酸の並びから類似する配列を探したりといった場合に利用できる。
ハッシュ関数は、チェックサム、チェックディジット、フィンガープリント、誤り訂正符号、暗号学的ハッシュ関数などと関係がある。それぞれ用途が異なり、異なった形で設計・最適化されている。