令和5年度 春期 応用情報技術者試験 午前 問19

ハッシュ表は、データのキーからハッシュ関数を用いてハッシュ値を計算し、それを配列のインデックスとしてデータを格納・検索するデータ構造です。

問題の条件では「複数のデータが同じハッシュ値になることはない（シノニムが発生しない）」とされています。この場合、目的のデータを検索する際、ハッシュ関数で計算したハッシュ値を使って、データが格納されている場所に直接アクセスすることができます。

したがって、表の中に格納されているデータの個数（$n$）によらず、探索にかかる時間（計算量）は常に一定（$O(1)$）となります。
データの個数が増えても探索時間が増加せず一定であることを示すグラフは、水平な直線である「エ」です。

各選択肢の解説

• ア: 下に凸の右上がりの曲線です。データの個数が増えると探索時間が急激に増加する（例：$O(n^2)$ や $O(2^n)$ のアルゴリズム）ことを示しており、ハッシュ表の探索時間には当てはまりません。
• イ: 右上がりの直線です。データの個数に比例して探索時間が増加する（$O(n)$ のアルゴリズム、例：線形探索）ことを示しており、ハッシュ表の探索時間には当てはまりません。
• ウ: 上に凸の右上がりの曲線です。データの個数が増えると探索時間の増加度合いが緩やかになる（$O(\log n)$ のアルゴリズム、例：2分探索）ことを示しており、ハッシュ表の探索時間には当てはまりません。
• エ: 水平な直線です。データの個数によらず探索時間が常に一定（$O(1)$）であることを示しており、これがシノニムが発生しないハッシュ表の正しい理論的な探索時間です。