チェイン法の期待計算量

$m$ スロットのハッシュ表に $n$ 個のキーをチェイン法で格納し、$\alpha = n/m$ とします。次の仮定を置きます。

• 単純一様ハッシュの仮定：格納される各キーは、他のキーと独立に、$m$ 個のスロットのそれぞれに確率 $1/m$ で写る。
• ハッシュ関数 $h$ の計算は $O(1)$ 時間でできる。
• 新しいキーはリストの先頭に挿入する。

このとき次が成り立ちます。

1. 表に格納されていないキー $x$（その $h(x)$ もまた $m$ 個のスロット上の一様分布に従い、格納済みのキーとは独立とする）を探索するとき、走査されるリスト要素数の期待値は $\alpha$ であり、探索時間の期待値は $\Theta(1 + \alpha)$ です。
2. 格納されている $n$ 個のキーのどれを探すかが等確率であるとき、走査されるリスト要素数の期待値は $1 + \dfrac{\alpha}{2} - \dfrac{\alpha}{2n}$ であり、探索時間の期待値は $\Theta(1 + \alpha)$ です。