エンベデッドシステムスペシャリスト 2017年 午前2 問08
問題文
ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。
選択肢
ア：
イ：
ウ：
エ：（正解）
🔒 解説は解答すると表示されます
ハッシュ表の探索時間【午前2解説】
正解の理由
ハッシュ表では、探索したいデータのキーからハッシュ値を計算し、その値に対応する位置を直接調べます。
問題では「複数のデータが同じハッシュ値になることはない」とされています。そのため、衝突への対処や複数の候補の確認が不要で、データの個数が増えても探索にかかる時間は理論上一定です。したがって、探索時間を横向きに示すグラフであるエが適切です。
データ数を とすると、探索時間は （定数時間）です。
解法ステップ
- ハッシュ表では、キーからハッシュ値を求め、対応する位置を調べると確認します。
- 問題の条件から、異なるデータが同じハッシュ値になる「衝突」は起きないと読み取ります。
- データ数が増えても、調べる位置は基本的に一つです。
- 探索時間が一定であるエを選びます。
選択肢別の誤答解説
- ア：データ数の増加に伴い、探索時間の増え方も大きくなるグラフです。ハッシュ表の理論的な探索時間は、衝突がない条件ではこのように増加しません。
- イ：データ数に比例して探索時間が増えるグラフです。先頭から順に調べる線形探索などに相当し、ハッシュ表の探索とは異なります。
- ウ：探索時間は増加しますが、次第に増えにくくなるグラフです。衝突がないハッシュ表の理論的な探索時間は増加しないため、適切ではありません。
- エ：データ数が増えても探索時間が一定のグラフです。衝突がない場合のハッシュ表の理論的な探索時間を表しています。
よくある誤解
- データ数が増えれば、どの探索方法でも時間が増える
そうとは限りません。ハッシュ表では、キーから格納位置を直接求めるため、衝突がなければ探索時間は一定です。 - 「一定時間」は、実際の処理時間が常にまったく同じという意味
ここでは、データ数の増加に対して探索時間が増えないという計算量上の性質を指します。 - ハッシュ値が同じになるデータがあっても、探索時間は必ず一定
衝突がある場合は、衝突を解消するために追加の確認が必要になり、探索時間が増えることがあります。
補足コラム
ハッシュ表の探索は、衝突がないという理想的な条件では です。実際には衝突が起きる可能性があるため、ハッシュ関数の設計や表の使用率、衝突解消方法などが性能に影響します。この問題では衝突がないと明示されているため、理想的な一定時間として考えます。
FAQ
Q. とは、探索に必ず1回しか処理が必要ないという意味ですか？
A. いいえ。処理回数が厳密に1回という意味ではなく、データ数が増えても処理時間が増加しないことを表します。
A. いいえ。処理回数が厳密に1回という意味ではなく、データ数が増えても処理時間が増加しないことを表します。
Q. ハッシュ表では、データ数が非常に多くても探索時間は一定ですか？
A. 理論上、衝突がない条件では一定時間です。実際のシステムでは、衝突やメモリの状態などによって時間が変わることがあります。
A. 理論上、衝突がない条件では一定時間です。実際のシステムでは、衝突やメモリの状態などによって時間が変わることがあります。
関連キーワード: ハッシュ表、ハッシュ値、衝突、探索時間、計算量、
\ せっかくなら /
エンベデッドシステムスペシャリストを
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！