正答4
解説
正解は4です。
ハッシュ表は、データのキーからハッシュ関数で格納位置を直接計算して探索する方法です。
問題文の条件により、異なるデータが同じハッシュ値になる衝突は起こりません。
【選択肢別解説】
1：× 図のアは、データの個数が増えるほど探索時間が急に増える曲線です。
衝突がないハッシュ表では、データが増えても探索時間は増えません。
2：× 図のイは、データの個数に比例して探索時間が直線的に増えるグラフです。
これは線形探索の特徴です。
3：× 図のウは、初めは増え方が大きく、しだいに増え方が小さくなる曲線です。
これはデータ数の対数に比例する2分探索に近い特徴です。
4：○ 図のエは、データの個数にかかわらず探索時間が一定の水平な直線です。
衝突がなければハッシュ値の計算1回で格納位置が決まるため、探索時間はデータ数によらず一定になります。
【ポイント】
探索時間の目安は、線形探索がn、2分探索がlog n、衝突のないハッシュ表が一定です。
実際のハッシュ表では、データが増えて衝突が起こると探索時間が増えていきます。