基本情報技術者試験 ap-2023r05h-a 午前 問19: ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで，複数のデータが同じハッシュ値になることはないものとする。

問題本文

ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで，複数のデータが同じハッシュ値になることはないものとする。

選択肢

• ア.横軸を表の中のデータの個数，縦軸をデータ1個当たりの探索時間としたとき，データの個数の増加に対して探索時間が加速度的に増加するグラフ
• イ.横軸を表の中のデータの個数，縦軸をデータ1個当たりの探索時間としたとき，データの個数の増加に対して探索時間が直線的に増加するグラフ
• ウ.横軸を表の中のデータの個数，縦軸をデータ1個当たりの探索時間としたとき，データの個数の増加に対して探索時間が増加した後，次第に一定値へ近づくグラフ
• エ.横軸を表の中のデータの個数，縦軸をデータ1個当たりの探索時間としたとき，データの個数にかかわらず探索時間が一定であるグラフ

正解

エ. 横軸を表の中のデータの個数，縦軸をデータ1個当たりの探索時間としたとき，データの個数にかかわらず探索時間が一定であるグラフ

解説

ハッシュ表探索は、ハッシュ関数でキーから格納位置(ハッシュ値)を1回計算するだけで目的データの位置が直接求まる探索法である。本問は「複数のデータが同じハッシュ値にならない」(衝突=シノニムが起きない)前提なので、表に格納されたデータ個数が何件であっても1回の計算で位置が定まり、探索時間はデータ個数に依存せず一定である。これは計算量 O(1) を意味し、横軸のデータ個数にかかわらず縦軸の探索時間が一定(水平)となるエが正解である。

選択肢ごとの解説

• ア.データ個数の増加に対し探索時間が加速度的に増加するグラフは O(n^2) 相当の振る舞いで、ハッシュ表探索には当てはまらない。
• イ.探索時間がデータ個数に直線的に比例して増加するグラフは O(n) であり、先頭から順に調べる線形探索の特性である。ハッシュ表探索ではない。
• ウ.増加後に一定値へ漸近するグラフはハッシュ表探索の理論特性とは異なる。衝突がない前提では最初からデータ個数に依存しないため、増加してから頭打ちになる形にはならない。
• エ.ハッシュ値の計算1回で位置が決まるため探索時間はデータ個数によらず一定(O(1))であり、水平な直線グラフが正しい。