ハッシュ表による探索で、適切なハッシュ関数を用いて衝突が少ない場合の平均時間計算量と、すべてのキーが同じハッシュ値になった最悪の場合の時間計算量の組合せとして、適切なものはどれか。ここで、衝突はチェイン法で処理し、n はデータ数とする。

解説

正解は「平均 $O(1)$、最悪 $O(n)$」です。ハッシュ表は、キーからハッシュ関数で格納位置を直接計算するため、衝突が少なければデータ数によらず、平均して一定時間で探索できます。一方、すべてのキーが同じ位置に衝突すると、その位置の連結リストを先頭から順にたどることになり、線形探索と同じ $O(n)$ かかります。「平均 $O(\log n)$、最悪 $O(n)$」は、平衡でない2分探索木の計算量です。「平均 $O(1)$、最悪 $O(\log n)$」は、最悪の場合を過小評価しています。「平均 $O(n)$、最悪 $O(n^2)$」は、ハッシュ表の探索ではなく、単純な整列アルゴリズムの計算量に近い値です。