万能ハッシュ族

定義 5.6（「探索アルゴリズム」§5）

$\mathcal{H}$ を $U$ から $\{0, 1, \ldots, m-1\}$ への関数からなる有限集合とします。任意の相異なる $k, l \in U$ に対して

\Pr_{h \in \mathcal{H}}\left[\, h(k) = h(l) \,\right] \le \frac{1}{m}

が成り立つとき（確率は $\mathcal{H}$ から一様に選ばれる $h$ についてのもの）、 $\mathcal{H}$ を万能（universal）であるといいます。

閉包の状態

定義

定義は閉包の起点です（証明を要しません）。

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