エンベデッドシステムスペシャリスト 2021年 午前2 問10
問題文
ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。
選択肢
ア：
イ：
ウ：
エ：（正解）
🔒 解説は解答すると表示されます
ハッシュ表の探索時間【午前2解説】
正解の理由
ハッシュ表では、探索するデータからハッシュ値を計算し、その値に対応する位置を直接参照します。
問題では、複数のデータが同じハッシュ値になることはないとされています。そのため、データ数が増えても、目的のデータを見つけるまでに必要な操作回数は変わりません。探索時間はデータ数に依存せず一定なので、横軸に沿った水平線で表されるエが正解です。
解法ステップ
- 横軸が「表の中のデータの個数」であることを確認します。
- データ数が増えたとき、探索時間がどう変わるかを考えます。
- ハッシュ値の重複がないため、該当位置を直接参照すれば探索できます。
- 探索時間が一定のグラフを選びます。
選択肢別の誤答解説
- ア：データ数が増えるほど、探索時間の増加が大きくなるグラフです。ハッシュ値の重複がない条件では、このような増え方にはなりません。
- イ：データ数に比例して探索時間が増えるグラフです。先頭から順に調べる線形探索のような場合に当てはまります。
- ウ：データ数が増えるほど探索時間も増えますが、増加の度合いは小さくなっていくグラフです。ハッシュ表の理論的な探索時間を表すものではありません。
- エ：データ数が増えても探索時間が一定です。ハッシュ値から格納位置を直接求めるため、条件に合います。
よくある誤解
- ハッシュ表の探索時間は必ず一定だと思う
理論上は、ハッシュ値の衝突がないなどの前提で一定時間と考えます。実際には衝突が起きると、追加の探索が必要になる場合があります。 - データ数が増えると、どの探索方法でも時間が増えると思う
線形探索ではデータ数に応じて探索時間が増えますが、ハッシュ表はハッシュ値を使って位置を特定する方式です。 - 一定時間なら、データ数に関係なく必ず同じ秒数だと思う
ここでいう一定時間は、データ数の増加に対して計算量が増えないという意味です。実際の処理時間が常に同じになるという意味ではありません。
補足コラム
計算量では、データ数を としたとき、ハッシュ表の探索は衝突がない理想的な条件で と表します。これは、データ数が増えても探索に必要な操作回数が一定であることを示します。
実際のハッシュ表では、異なるデータから同じハッシュ値が計算される「衝突」が起こることがあります。衝突への対処方法や表の使用率によって、実際の探索時間は変わります。
FAQ
Q. ハッシュ値の重複がない条件は、なぜ重要なのですか？
A. 同じハッシュ値を持つデータがあると、目的のデータを特定するために追加の確認が必要になる場合があるためです。この問題では重複がないので、直接参照できると考えられます。
A. 同じハッシュ値を持つデータがあると、目的のデータを特定するために追加の確認が必要になる場合があるためです。この問題では重複がないので、直接参照できると考えられます。
Q. は、データが1個のときと100万個のときで処理時間がまったく同じという意味ですか？
A. 厳密に同じ秒数という意味ではありません。データ数が増えても、探索に必要な操作回数がデータ数に応じて増えないことを表します。
A. 厳密に同じ秒数という意味ではありません。データ数が増えても、探索に必要な操作回数がデータ数に応じて増えないことを表します。
関連キーワード: ハッシュ表、ハッシュ値、探索時間、計算量、
\ せっかくなら /
エンベデッドシステムスペシャリストを
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！