令和5年度 春期 ITストラテジスト試験 システムアーキテクト試験 ネットワークスペシャリスト試験 ITサービスマネージャ試験 情報処理安全確保支援士試験 午前Ⅰ 問題【共通】 問6

ハッシュ表を用いた探索（ハッシュ探索）では、探索対象のキーの値から ハッシュ関数 を用いて格納位置（インデックス）を直接計算し、その位置のデータを参照します。
問題文にある「複数のデータが同じハッシュ値になることはない（衝突が発生しない）」という条件下では、データ件数 $n$ に関係なく、常に1回の計算とアクセスで目的のデータを見つけることができます。
したがって、理論的な探索時間はデータ件数に依存せず 一定（$O(1)$）となります。
グラフの横軸をデータ件数、縦軸を探索時間とした場合、探索時間が一定であることを示しているのは エ です。

各選択肢の解説

各グラフの形状から推測される代表的な探索・ソートアルゴリズムの計算量は以下の通りです。

• ア：データ件数に比例して探索時間が直線的に増加するグラフであり、線形探索（$O(n)$）などに相当します。
• イ：データ件数が増えても探索時間の増加が緩やかになる対数曲線のグラフであり、二分探索（$O(\log n)$）などに相当します。
• ウ：データ件数の増加に対して探索時間が急激に増加するグラフであり、$O(n^2)$ などの計算量となるアルゴリズム（単純なソートなど）に相当します。
• エ：データ件数に関わらず探索時間が一定であるグラフであり、ハッシュ探索（$O(1)$）に相当します。よってこれが正解です。