平成30年度 春期 基本情報技術者試験 午前 問7

解説

ハッシュ法は，探索するキーの値からハッシュ関数を使って格納位置を直接計算し，その位置にデータを格納・探索する方式です。計算量がほぼ一定（O(1)）であることが特徴で，表全体の大きさに比例して探索時間が増える線形探索とは異なります。ただし，異なるキーが同じハッシュ値になる衝突（シノニム）が発生することがあり，衝突が全く起きない方式ではありません。

選択肢ごとの解説

• ア誤り。2分木を用いる探索は2分探索木であり，ハッシュ法とは異なる方式です。
• イ誤り。ハッシュ法では異なるキーが同じハッシュ値になる衝突（シノニム）が発生することがあり，衝突が発生しない方式ではありません。
• ウ正しい。ハッシュ法は，キーの値をハッシュ関数によって変換した関数値によって格納場所を決める探索方式です。
• エ誤り。ハッシュ法の探索時間は表の大きさにほとんど依存せず，ほぼ一定時間で探索できる点が特徴です。表全体の大きさに比例するのは線形探索の特徴です。