衝突 (計算機科学)

計算機科学には全く限らず、ハッシュ関数のような種類の関数を使うような場面で、衝突(英: collision)とは、2つの異なるデータからハッシュ関数などで生成したハッシュ値など（チェックサム・フィンガープリント・メッセージダイジェストなど）の値が同じ値（シノニム）になることである。

概要

ほとんどの分野において、衝突は一般に望ましくない結果ではある。ここでは「望ましくなさ」と呼ぶが、その「望ましくなさ」はその応用の目的によって異なる。また鳩の巣原理により、ある集合全体からその集合より小さい集合への写像では必ず衝突が発生するが、メッセージダイジェストなどではその確率が十分に低いかどうかが問題となる。

相同DNA配列や、ほぼ同じ内容の音声ファイルなど、よく似たデータを同一視するためにハッシュ関数とフィンガープリントを使用する場合、ハッシュ関数は似たデータに対して似た結果を出し、あるいは衝突を発生する（確率ができる限り大きくなる）ように設計される。これは一般と逆に必要な場合には衝突が望まれる例である。

ビットの化けや抜けや混入をチェックするチェックサムなどはよく似た入力に対して、可能であれば十分に異なるハッシュ値を生成することが望まれ、衝突を発生させる確率ができる限り小さくなるように設計される。一方で全く異なるデータ間での衝突については通常は意識されない。こういった誤り検出訂正の類はハッシュとは別とすることもある。

ハッシュテーブルにおいて、衝突はルックアップ処理のコストを増加させる。こういった応用には関数の計算量と結果の品質のどちらを重視するか等のトレードオフもある。またハッシュテーブルを実装するいくつかの技法との相性、あるいは入力に現れる値が完全にランダムか何らかの性質があるのか、といった考慮すべき要素もある。入力に現れうる値が予め全て既知なのであれば完全ハッシュ関数といったものもある。

プロキシサーバやファイルのバックアップシステムにおいて不要なファイルの保存や転送を省略するためにはフィンガープリントが使用されるが、ここでの衝突は、単に本来ならば必要なかったはずの転送が必要になったというような結果であれば問題ないが、場合によっては不適切な処理やデータ消失の原因になりうる。暗号学的ハッシュ関数などを使うとかなり低い確率になるかもしれないが、それでもその可能性を考慮すべきかは難しい所である。

暗号分野の応用では衝突が致命的なものもあり、暗号学的ハッシュ関数と呼ばれる特別な一分野としてさかんに研究されている。この分野ではハッシュ関数について「弱衝突耐性」「強衝突耐性」といった術語が定義されており、暗号学的ハッシュ関数はこれらについて、目的に応じて必要な強度を満たしていることが求められる。

ハッシュ関数の結果

あるデータに対して何らかの変換関数（ハッシュ関数という）を適用して、そのデータに対するレコード位置（アドレスなどでもよい）を対応させることにする。このとき、別々のデータに対して同じレコード位置が対応する場合、「シノニムが生じる」などという。

例えば、データ「1,5,7,12,13」があり、データ値に対応するレコード位置を求める関数を「データ値を11で割った余り」ということにする。

データ	レコード位置
1	1
5	5
7	7
12	1
13	2

この例でデータとレコード位置を表にすると上の通りである。

データが1と12のどちらもレコード位置が1になってしまっている。これを「データ1と12で（レコード位置の）シノニムが生じる」などという言い方をする。情報処理においては、シノニムが生じた場合の処理、もしくはシノニムをそもそも発生させない処理方法を予め考えておくことは必須である。