基本情報技術者 一問一答｜A 第55問

解説

ハッシュ法は、データのキー値にハッシュ関数を適用して格納位置を直接計算する高速な探索手法だが、異なるキーが同じハッシュ値になる「衝突（コリジョン）」が起こり得る。その対処法には、同じハッシュ値のデータを連結リストでつないで管理するチェイン法（チェーニング）と、衝突時に一定の規則で次の空き位置を探して格納するオープンアドレス法（線形探査法など）がある。元データを削除したり検索不可と判定したりするのはデータ管理として成立せず、ハッシュ値を半分にしても衝突が解消する保証はないため誤りである。基本情報技術者試験では衝突発生時の格納位置を実際に計算させる問題や、衝突が少ないほど探索が理想のO(1)に近づくという性質が頻出ポイントである。