【SC試験 午前I】ハッシュ探索法の計算量とハッシュ衝突 — アルゴリズムとプログラミング

正解： イ）

解説：

• ア）ハッシュ衝突が発生しない理想的な状況では、ハッシュ値から直接該当データの格納位置を算出できるため、探索の計算量は平均的に O(1)（定数時間）に近づきます。「常にO(n)」は誤りです。
• イ）ハッシュ衝突（異なるキーが同じハッシュ値になること）が発生した場合の対処法として、同じハッシュ値のデータを連結リストでつなげる「チェイン法」や、別の空き位置を探す「オープンアドレス法」が代表的な手法として用いられます。正解です。
• ウ）ハッシュ関数は理想的にはできるだけ一様な分布を目指して設計されますが、実際のデータ分布やハッシュ関数の性質によっては偏りが生じることがあり、「常に完全に一様であることが理論上保証されている」は誤りです。
• エ）ハッシュ表はキーからハッシュ値を計算して格納位置を直接求める仕組みであり、キーの大小関係に基づく比較や整列を前提としません。大小関係を利用するのは二分探索木や二分探索法の特徴であり、誤りです。