令和5年度春期 応用情報技術者試験 午前 問19

正解：エ

AI解説

ハッシュ表は理想的には(衝突がなければ)ハッシュ関数によって格納位置が一意に決まるため、データ件数(表のサイズ)によらずほぼ一定時間(O(1))で探索できる。 ア: 探索時間がデータ件数に比例して増加するグラフは線形探索(O(n))の特性であり、ハッシュ表の理論値ではない。 イ: 探索時間がデータ件数の対数に比例するグラフは2分探索木など(O(log n))の特性であり、ハッシュ表の理論値ではない。 ウ: データ件数の増加に伴い緩やかに増加するグラフは衝突を考慮した現実的な探索時間に近いが、衝突がないという前提の理論値としては誤りである。 エ: 正解。衝突が発生しないという前提の下では、ハッシュ表の探索時間はデータ件数によらずほぼ一定(O(1))となるグラフが理論値を表す。 💡 ハッシュ表の平均探索時間はO(1)だが、これは衝突がない、あるいは衝突対策(オープンアドレス法・チェイン法)が十分機能している場合の理想値である点に注意。実際には衝突が起きると性能は劣化する。