解説

ハッシュ表（ハッシュテーブル）の探索時間の特性を問う問題です。条件として「複数のデータが同じハッシュ値になることはない（衝突なし）」とあります。この条件下では、ハッシュ関数によってデータの格納位置を直接計算できるため、データ件数 n に依存せず、常に O(1)（定数時間）で探索が完了します。グラフで言えば、横軸がデータ件数 n であっても、探索時間が常に一定の水平線（定数）を示すグラフが正解です。選択肢 d は探索時間が定数（n によらず一定）を示すグラフです。二分探索は O(log n)、線形探索は O(n) と区別して覚えておきましょう。

なぜ他の選択肢は違うのか

選択肢 ア

選択肢アは右上がりの直線（O(n)）のグラフです。これは線形探索（順探索）の探索時間特性であり、データ件数に比例して時間が増加します。

選択肢 イ

選択肢イは対数曲線（O(log n)）のグラフです。これは二分探索（バイナリサーチ）の探索時間特性です。データ件数が増えても増加は緩やかです。

選択肢 ウ

選択肢ウは右上がりの曲線（O(n^2) やその他）です。ハッシュ探索でも衝突がある場合はチェーン法などで最悪 O(n) になることがありますが、設問の条件「衝突なし」の下では当てはまりません。

解くときのポイント

探索アルゴリズムの計算量：ハッシュ探索（衝突なし）＝O(1)（定数）、二分探索＝O(log n)、線形探索＝O(n)。ハッシュ表の特長は「インデックス直接計算による O(1) 探索」。衝突が発生すると最悪 O(n) に悪化する点も押さえる。