オープンアドレス法の期待探査回数

定理 6.3（「探索アルゴリズム」§6）・ ※主張のみ

一様ハッシュの仮定、すなわち各キーの探査列が $\{0, 1, \ldots, m-1\}$ の $m!$ 通りの並べ替えから一様ランダムに、他のキーと独立に選ばれると仮定します。表に $n$ 個のキーが格納されており $\alpha = n/m < 1$ とすると、

不成功探索の探査回数の期待値は $\dfrac{1}{1-\alpha}$ 以下です。
表にあるキーの探索（どのキーを探すかは等確率）の探査回数の期待値は $\dfrac{1}{\alpha}\ln\dfrac{1}{1-\alpha}$ 以下です。

閉包の状態

※ 主張のみ

この分野（情報科学・コラム）は閉包の検査の対象外で、証明を載せていない定理です。出典は本文を見てください。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

主張のみなので、Rikai の中で証明が使う前提はありません。

証明で明示的に参照している定理は、まだありません。