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

選択肢

• ア横軸を表の中のデータの個数、縦軸をデータ1個当たりの探索時間としたとき、データの個数が増えるほど急激に（加速度的に）探索時間が増加するグラフ
• イ横軸を表の中のデータの個数、縦軸をデータ1個当たりの探索時間としたとき、データの個数の増加に比例して探索時間が直線的に増加するグラフ
• ウ横軸を表の中のデータの個数、縦軸をデータ1個当たりの探索時間としたとき、データの個数が増えるにつれ探索時間の増加が徐々に緩やかになり頭打ちになるグラフ
• エ横軸を表の中のデータの個数、縦軸をデータ1個当たりの探索時間としたとき、データの個数によらず探索時間が一定（水平）のグラフ

正解と解説

正解：エ 横軸を表の中のデータの個数、縦軸をデータ1個当たりの探索時間としたとき、データの個数によらず探索時間が一定（水平）のグラフ

ハッシュ表では、キーにハッシュ関数を適用して格納位置を直接計算するため、表を順に走査する必要がない。衝突が起きない前提なら、探索はハッシュ値の計算と1回のアクセスで完了するので、データ件数が増えても1件当たりの探索時間は変わらない。計算量でいえばO(1)であり、グラフは横軸に平行な直線になる。

選択肢ごとの解説

• ア加速度的な増加は計算量が件数の2乗以上になる場合の形で、ハッシュ表には当てはまらない。
• イ件数に比例するのは線形探索の特性。
• ウ対数的に緩やかに増加するのは2分探索や平衡木の特性。
• エ正解。件数によらず探索時間が一定となる。

同じ分野の他の問題

• マイクロサービスアーキテクチャを利用してシステムを構築する利点はどれか。2022年度 秋期 午前II 問20
• 組込みシステムの開発における、ハードウェアとソフトウェアのコデザインを適用した開発手法の説明として、適切なものはどれか。2020年度 10月試験 午前II 問20
• ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。2017年度 春期 午前II 問8
• 組込みシステムにおけるハードウェアとソフトウェアのコデザインの説明として適切なものはどれか。2016年度 春期 午前II 問21
• 銀行の勘定系システムといった特定の分野のシステムに対して、業務知識、再利用部品、ツールなどを体系的に整備し、再利用を促進…2025年度 秋期 午前II 問20