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

解説

ハッシュ表は，キーからハッシュ関数によって格納位置を直接計算するため，衝突（複数のキーが同じハッシュ値になること）が発生しない限り，表に格納されているデータの個数に関係なく，常にほぼ一定の時間でデータを探索できます。設問では「複数のデータが同じハッシュ値になることはない」と仮定されているため，データ 1 個当たりの探索時間はデータの個数によらず一定であり，グラフは横軸（データの個数）に対して水平な直線になります。

選択肢ごとの解説

• ア誤り。データの個数が増えるにつれて探索時間が急激に増加するグラフは，衝突が頻発して線形探索に近くなる状況を表すものであり，衝突が発生しないという設問の前提と矛盾します。
• イ誤り。データの個数に比例して探索時間が増加するグラフも，衝突が発生しない場合のハッシュ表の理論的な特性とは一致しません。
• ウ誤り。データの個数の増加に伴い探索時間が徐々に頭打ちになりながら増加するグラフも，衝突が発生しないという前提の下では生じない挙動です。
• エ正しい。衝突が発生しない場合，ハッシュ表の探索時間はデータの個数によらず一定（O(1)）であるため，横軸に対して水平な直線のグラフが理論的な探索時間を表します。