データ構造とアルゴリズム
ハッシュテーブル(ハッシュ表)における衝突(コリジョン)の説明として正しいものはどれか。
- Aハッシュ値から元のキーが求められてしまうこと
- B異なるキーから同じハッシュ値(格納する位置)が求まること
- C同じキーから、実行するたびに違うハッシュ値が求まること
答えと解説を見る
正解：B. 異なるキーから同じハッシュ値(格納する位置)が求まること
ハッシュテーブルは、キーからハッシュ関数で格納する位置を計算し、平均 O(1) で探索・挿入・削除ができるデータ構造です。キーの種類は表の大きさよりはるかに多いので、異なるキーが同じ位置になること(衝突)は避けられません。そのため、同じ位置の要素をリストにつなぐチェイン法や、空いている別の位置を探すオープンアドレス法などで衝突を処理します。同じキーからは必ず同じハッシュ値が求まらなければ探索ができず、ハッシュ値から元のキーが分かるかどうかは暗号に使う場合の性質で、衝突とは別の話です。
- A. 元の値が求められないこと(一方向性)は暗号に使うハッシュ関数の性質で、衝突とは別の話です。
- B. 正しい。異なるキーが同じ位置になることを衝突といい、必ず何らかの方法で処理します。
- C. 同じキーから違う値が出るとデータを探せなくなるので、ハッシュ関数はそうならないように作ります。