修了試験 2013-01-27実施分 基本情報技術者試験 問6

解説

正解は3です。 ハッシュ法は、キーをハッシュ関数に通して得た値を、そのまま格納場所（アドレス）として使う方法です。 計算一回で格納場所が分かるので、表の大きさに関係なく高速に探索できます。 【選択肢別解説】 1：× 2分木を用いるのは2分探索木による探索です。 ハッシュ法は木構造を使わず、関数の計算で格納場所を決めます。 2：× 異なるキーから同じハッシュ値が得られる衝突（シノニム）は起こり得ます。 そのため、衝突時の処理方法（オープンアドレス法やチェイン法）が必要になります。 3：○ キーをハッシュ関数で変換した値によって格納場所を決めるのが、ハッシュ法の特徴です。 探索時も同じ関数を計算すれば、目的のデータの位置がすぐに分かります。 4：× 表全体の大きさにほぼ比例するのは、先頭から順に調べる線形探索の特徴です。 ハッシュ法は、衝突が少なければ表の大きさにほぼ関係なく一定時間で探索できます。 【ポイント】 探索法の計算量は、線形探索がO(n)、2分探索がO(log n)、ハッシュ法が理想的にはO(1)です。 ハッシュ法では衝突（シノニム）とその解決法がセットで出題されます。