応用情報技術者 2023年 春期 午前2 問19

ハッシュ表の理論的な探索時間を示すグラフ【午前2 解説】

要点まとめ

• 結論：ハッシュ表の理論的な探索時間はデータ数に関係なく一定で、水平直線で表されます。
• 根拠：ハッシュ関数により直接アクセスできるため、探索時間は平均して$O(1)$となり、データ数の増加に影響されません。
• 差がつくポイント：衝突がない理想的な場合の探索時間と、衝突が発生する場合の探索時間の違いを理解し、グラフの形状を正確に把握することが重要です。

正解の理由

よくある誤解

解法ステップ

1. 問題文で「複数のデータが同ハッシュ値になることはない」と確認する。
2. ハッシュ表の理論的な探索時間は$O(1)$で一定であることを思い出す。
3. 探索時間がデータ数に依存しないグラフを探す。
4. 水平直線で表される選択肢エを選択する。

選択肢別の誤答解説

• ア：探索時間がデータ数の増加に伴い急激に増加する凸状の曲線は、線形探索や衝突が多い場合のグラフに近く誤り。
• イ：探索時間が一定の割合で増加する直線は、線形探索やリニアサーチの特徴でありハッシュ表の理論値ではない。
• ウ：探索時間が増加するが増加幅が小さくなる凹状の曲線は、衝突解消のためのチェイン法などで平均探索時間が増加する場合のイメージで誤り。
• エ：探索時間が一定で水平直線を示し、理想的なハッシュ表の理論的探索時間を正しく表現している。

補足コラム

FAQ