平成26年度 春期 応用情報技術者試験 午前 問19

解説

ハッシュ表は，キーからハッシュ関数によって格納位置を直接計算できるため，衝突が発生しない理想的な条件下では，表に格納されているデータ数によらず探索時間はほぼ一定になる。したがって，グラフは横軸のデータ個数によらず探索時間が一定な水平のグラフになる。

選択肢ごとの解説

• ア誤り。データ数が増えるにつれて探索時間が急激に増加するグラフであり，最悪の場合の線形探索などの特性に近い。
• イ誤り。データ数に比例して探索時間が増加するグラフであり，線形探索の特性に近い。
• ウ誤り。データ数の増加に伴って探索時間の増加が徐々に頭打ちになるグラフであり，二分探索など対数的な増加傾向を表すものに近い。
• エ正しい。ハッシュ表は衝突がなければキーから格納位置を直接計算できるため，データ数によらず探索時間はほぼ一定（横軸に対して水平）になる。