令和3年度 秋期 エンベデッドシステムスペシャリスト試験 午前II 問10

グラフの縦軸は「データ1個当たりの探索時間」、横軸は「表の中のデータの個数」を表しています。
ハッシュ表は、データからハッシュ関数を用いてハッシュ値を計算し、それを格納アドレスとして直接データを配置・探索するデータ構造です。

問題文の条件に「複数のデータが同じハッシュ値になることはない」とあるため、データの個数が増えてもハッシュ値の衝突（シノニム）が発生しません。
そのため、データの個数がいくつであっても、ハッシュ関数を1回計算するだけでデータの格納場所を特定できます。
したがって、表の中のデータの個数に関係なく、理論的な探索時間は常に一定（$O(1)$）となります。

探索時間が一定であることを示すグラフは、縦軸の値が変化しない水平な直線となっている エ です。

各選択肢の解説

• ア: データの個数が増加するにつれて、探索時間が急激に増加するグラフです。衝突のないハッシュ表の探索時間としては誤りです。
• イ: データの個数に比例して探索時間が増加するグラフです。これは、データを先頭から順に調べる線形探索の探索時間（$O(n)$）に該当します。
• ウ: データの個数が増加するにつれて、探索時間の増加具合が緩やかになるグラフです。これは、整列済みのデータを対象とする2分探索の探索時間（$O(\log n)$）に該当します。
• エ: 正解です。データの個数に関わらず探索時間が一定（$O(1)$）であることを示しており、衝突が起きない場合のハッシュ表の探索時間と一致します。