令和5年度 春期 午前 問19

✓ これが正解エ横軸が表の中のデータの個数，縦軸がデータ 1 個当たりの探索時間。個数によらず高さが変わらない水平な直線

解説

件数によらない水平な直線です。

設問は、ハッシュ表の理論的な探索時間を示すグラフを四つから選ばせています。どの選択肢も横軸が表の中のデータの個数、縦軸がデータ1個当たりの探索時間ですから、見分けの軸は、個数が増えたときに時間が伸びるかどうか、という一点になります。ハッシュ表は、キーをハッシュ関数に入れて添字を計算し、その添字の場所を直接見る、という二手で値を引きます。表の中に何件入っていても、この二手の回数は変わりません。したがって探索時間はデータの個数に依存せず、グラフは個数によらず高さが変わらない水平な直線になります。設問が、複数のデータが同じハッシュ値になることはないと断っているのが効いています。同じ場所に複数のキーが来ると、そこから順に見ていく手間が加わって件数の影響を受けるからです。その要素を消したうえで、理論上の形だけを問うています。なお速さと引き換えに、表の大きさをあらかじめ確保する必要があり、キーの順に取り出すこともできません。

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

• ア横軸が表の中のデータの個数，縦軸がデータ…：右へ行くほど急に立ち上がる曲線です。個数が増えると時間が加速して伸びる形で、総当たりで組合せを調べるような処理の増え方にあたり、計算で場所が一度に定まる引き方の形ではありません。
• イ横軸が表の中のデータの個数，縦軸がデータ…：右上がりの直線です。個数が2倍になれば時間も2倍という増え方で、表を先頭から順に見ていく探索の形にあたります。添字を計算して直接見る方法では、この比例の関係は生じません。
• ウ横軸が表の中のデータの個数，縦軸がデータ…：右へ行くほど傾きが緩み、やがて一定値に近づく曲線です。伸び方は緩やかでも個数が増えるほど時間が伸びる形なので、個数によらず高さの変わらない形とは別のものです。