ハッシュ表・ハッシュ関数・負荷率

$m$ を正の整数、$T[0..m-1]$ を長さ $m$ の配列（ハッシュ表）、$h : U \to \{0, 1, \ldots, m-1\}$ を関数（ハッシュ関数）とします。キー $k$ はスロット $h(k)$ に関係づけて格納します。相異なるキー $k \ne l$ に対して $h(k) = h(l)$ となることを衝突といいます。格納されているキーの個数を $n$ として、$\alpha = n/m$ を負荷率と呼びます。