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

選択肢

• アデータ1個当たりの探索時間が、表の中のデータの個数の増加とともに指数的に急増するグラフ
• イデータ1個当たりの探索時間が、表の中のデータの個数に比例して直線的に増加するグラフ
• ウデータ1個当たりの探索時間が、表の中のデータの個数の増加とともに対数的に緩やかに増加し頭打ちになるグラフ
• エデータ1個当たりの探索時間が、表の中のデータの個数に関わらず一定（横一直線）のグラフ

正解と解説

正解：エ データ1個当たりの探索時間が、表の中のデータの個数に関わらず一定（横一直線）のグラフ

ハッシュ表は、キーをハッシュ関数で計算して格納位置を直接求める方式なので、格納されているデータの数を1件ずつ調べる必要がない。衝突が起きない前提であれば、1件を探すのに要する時間は表の中の件数に左右されず一定になる。すなわち計算量はO(1)で、グラフは横軸に対して水平になる。

選択肢ごとの解説

• ア件数に対して指数的に悪化する探索は現実的な手法には該当しない。
• イ件数に比例して増えるのは、先頭から順に調べる線形探索の特性である。
• ウ件数の対数に比例して増えるのは、2分探索や2分探索木の特性である。
• エ正しい。ハッシュ計算で位置が直接定まるため、件数によらず一定時間で探索できる。

同じ分野の他の問題

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