テクノロジ系10 / 25問
エンベデッドシステムスペシャリスト試験 令和3年度 秋期 午前II 問10
ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。
選択肢を押すと答え合わせができます。
正解と解説を見る
【正解】エ
ハッシュ表では、探索キーにハッシュ関数を適用して、データを格納している位置を直接求めます。この問題では、異なるデータが同じハッシュ値になる衝突がないため、表内のデータ数が増えても、基本的にハッシュ値の計算と求めた位置の参照だけで探索できます。理論的な探索時間は一定のO（1）であり、横軸のデータ数が増えても縦軸の探索時間が変化しない水平線のグラフであるエが正解です。
アは誤りです。これは、データ数の増加に伴って探索時間の増加幅まで大きくなるグラフです。指数的な増加などを表す形であり、位置を直接求めるハッシュ探索の特性ではありません。
イは誤りです。これは、データ数に比例して探索時間が増えるO（n）のグラフです。先頭から一件ずつ比較する線形探索の特性を表します。
ウは誤りです。これは、データ数が増えるにつれて探索時間は増えるものの、増加の割合が次第に小さくなるO（log n）のグラフです。二分探索や平衡二分探索木の探索に対応する形です。
【ポイント】 代表的な探索時間は、ハッシュ表が平均O（1）、二分探索がO（log n）、線形探索がO（n）です。 実際には衝突処理や表の混雑度によって性能が低下しますが、本問では衝突がないため一定時間として扱います。
出典：令和3年度 秋期 エンベデッドシステムスペシャリスト試験 午前II 問10
※ 解説は SkillStack 編集部が作成したものです。Web 表示のため、図表の配置や表記を一部改めています。
この回の25問を、アプリで通しで解く
- 本番と同じ問題数・制限時間で通し演習（模試モード）
- 間違えた問題は自動で「復習すべき問題」に回る
- 解説で分からない点はAIに質問できる