×
アルゴリズムとデータ構造
ハッシュ衝突への対策(衝突解決法)には、主に「チェイン法」と「オープンアドレス法」があります。「チェイン法(連鎖法)」では、同じハッシュ値を持つデータを「連結リスト(リンクドリスト)」を用いて数珠つなぎに保存していきます。検索時はリストをたどる必要があるため、衝突が多くなると検索速度が低下します。一方、「オープンアドレス法(開アドレス法)」は、衝突が発生した際に別の空いているハッシュアドレスを探し(再ハッシュなど)、そこにデータを保存する手法です。また、セキュリティ分野において、意図的に同じハッシュ値を持つ異なるデータを生成する攻撃を「衝突攻撃」と呼びます。暗号学的ハッシュ関数(SHA-256など)は、この衝突を実用時間内に見つけることが極めて困難である「衝突耐性(強衝突耐性および弱衝突耐性)」を備えるように設計されています。

試験でのポイント