ハッシュテーブルの検索に失敗したのはなぜ時間複雑度Θ（1 +α）ですか？

Question

私はΘ（1）の部分がハッシュテーブルを計算するのに使う時間ですが、私はΘ（α）の部分を理解していません。

私の見解では、時間の複雑さはΘ（n）です。 αが期待される長さであり、テーブルがm個のスロットを有すると仮定する。キーがテーブル内にないことを保証するために、各スロットを探索する必要があり、各スロットは長さを除いてαを有するので、合計時間はα倍mであるので、Θ（n）である。

誰かが私が正しく理解しなかった部分を教えてもらえますか？

Answer 1

特定のキーがハッシュテーブルに含まれているかどうかのテストでは、すべてのスロットをテストする必要はありません。指定したキー（1）のハッシュ値を計算するだけです。このハッシュ値は、ハッシュテーブル内にある場合、キーがどのスロットにあるかを識別します。したがって、そのスロット内のすべてのエントリ（α）を指定されたキーと比較するだけで、Θ（1 +α）が得られます。他のスロットにキーを格納できないため、他のスロットを見る必要はありません。