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

選択肢

• アデータ数が増えると探索時間が指数的に急増するグラフ（下に凸で右肩上がりに急上昇）
• イデータ数に比例して探索時間が直線的に増加するグラフ
• ウデータ数が増えると探索時間が対数的に増加し、やがて頭打ちになるグラフ（上に凸で飽和）
• エデータ数によらず探索時間が一定（水平線）のグラフ

正解と解説

正解：エ データ数によらず探索時間が一定（水平線）のグラフ

ハッシュ表では、キーからハッシュ関数で格納位置を直接計算して1回のアクセスで目的のデータに到達する。衝突が起こらない前提であれば、格納されているデータの個数が増えても1件あたりの探索時間は変わらない。したがってグラフは横軸に平行な水平線となる。

選択肢ごとの解説

• ア探索時間がデータ数に依存して急増する形で、ハッシュ表の性質と合わない。
• イデータ数に比例して増えるのは線形探索の特性である。
• ウ対数的に増えるのは2分探索や平衡木の特性である。
• エデータ数によらず一定であり、衝突がないハッシュ表の理論的性能を表す。

同じ分野の他の問題

• 異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけ…2025年度 秋期 午前 問6
• 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) = x mod n と…2024年度 秋期 午前 問6
• 従業員番号と氏名の対がn件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。この処理における…2023年度 春期 午前 問6
• 自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ571，1168，1566である三つのレコードのキー値を入力…2018年度 秋期 午前 問27
• 探索表の構成法を例とともにa〜cに示す。最も適した探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す…2018年度 秋期 午前 問8