応用情報技術者 2014年 春期 午前2 問19
問題文
ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同ハッシュ値になることはないものとする。
選択肢
ア：
イ：
ウ：
エ：（正解）
ハッシュ表の理論的な探索時間を示すグラフ【午前2 解説】
要点まとめ
- 結論：ハッシュ表の理論的な探索時間はデータ数に関係なく一定であり、グラフは水平な直線となる。
- 根拠：ハッシュ関数によりデータが均等に分散され、衝突がない場合は探索が直接インデックスで行われるため、探索時間はとなる。
- 差がつくポイント：衝突の有無やハッシュ関数の性能を理解し、探索時間の理論値と実際の挙動を区別できることが重要である。
正解の理由
選択肢エは探索時間がデータ数に依存せず一定であることを示す水平線のグラフです。ハッシュ表は理想的には衝突がなく、ハッシュ値から直接データ位置を特定できるため、探索時間は一定時間で完了します。したがって、探索時間がデータ数に比例して増加するアやイ、増加率が変化するウは誤りです。
よくある誤解
ハッシュ表の探索時間は平均的にですが、衝突が多い場合は線形探索に近くなり時間が増加します。理論値と実際の性能を混同しやすい点に注意が必要です。
解法ステップ
- ハッシュ表の基本動作を理解する（ハッシュ関数で直接アクセス）。
- 衝突がない理想状態を想定し、探索時間の計算を考える。
- 探索時間がデータ数に依存しないことから、グラフは水平線になると判断。
- 選択肢のグラフ形状を比較し、水平線のエを選択。
選択肢別の誤答解説
- ア：探索時間が加速度的に増加するため、衝突や線形探索の影響を示すが理論値とは異なる。
- イ：探索時間がデータ数に比例して増加する直線は、線形探索や配列の線形検索に近い。
- ウ：増加率が減少する凹曲線は、二分探索木などの対数時間探索に近い挙動を示す。
- エ：探索時間が一定で、理論的なハッシュ表の探索時間を正確に表している。
補足コラム
ハッシュ表の性能はハッシュ関数の質と衝突解決法に大きく依存します。理想的にはですが、実際は衝突が発生し、チェイン法やオープンアドレス法で処理されるため、平均探索時間はでも最悪はになることがあります。
FAQ
Q: 衝突がある場合の探索時間はどうなるのですか？
A: 衝突があると、チェイン法ではリストの探索、オープンアドレス法では再ハッシュが必要となり、探索時間は平均的にですが最悪はになります。
A: 衝突があると、チェイン法ではリストの探索、オープンアドレス法では再ハッシュが必要となり、探索時間は平均的にですが最悪はになります。
Q: ハッシュ表の探索時間が一定である理由は？
A: ハッシュ関数がデータを均等に分散し、直接アクセスできるため、探索にかかる時間はデータ数に依存しません。
A: ハッシュ関数がデータを均等に分散し、直接アクセスできるため、探索にかかる時間はデータ数に依存しません。
関連キーワード: ハッシュ表、探索時間、ハッシュ関数、衝突解決、時間計算量
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！