情報処理安全確保支援士試験 情報処理安全確保支援士試験 令和5年度春期 午前Ⅰ 問6: ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで，複数のデータが同じハッシュ値になることはないものとする。

問題本文

ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで，複数のデータが同じハッシュ値になることはないものとする。

選択肢

• ア.データ1個当たりの探索時間が，表の中のデータの個数の増加に対して指数関数的に増加するグラフ
• イ.データ1個当たりの探索時間が，表の中のデータの個数の増加に対して直線的に増加するグラフ
• ウ.データ1個当たりの探索時間が，表の中のデータの個数の増加に対して対数関数的に増加し，やがて頭打ちになるグラフ
• エ.データ1個当たりの探索時間が，表の中のデータの個数によらず一定であるグラフ

正解

エ. データ1個当たりの探索時間が，表の中のデータの個数によらず一定であるグラフ

解説

ハッシュ表は鍵をハッシュ関数で計算し格納位置を直接特定する。衝突がない理想状態では、データ数によらず計算一回で目的位置に到達できるため探索時間はO(1)で一定。よって個数に依存しないエが正解。実務では平均O(1)の高速検索が連想配列やキャッシュ、重複排除の基盤となるが、衝突対策が現実の性能を左右する。

選択肢ごとの解説

• ア.指数関数的増加はハッシュ表の特性と全く異なり、効率の良い直接アクセスを説明していない。
• イ.直線的増加はO(n)の線形探索の特性で、位置を計算で特定するハッシュ表には当てはまらない。
• ウ.対数関数的増加はO(log n)の二分探索などの特性で、ハッシュ表の理論探索時間ではない。
• エ.衝突がなければ個数に関係なく一回の計算で到達でき、探索時間は一定でO(1)となり正しい。