MIT《算法导论》课程第8课《全域哈希与完全哈希》学习笔记.
哈希的一个根本缺陷
对任意的一个哈希函数，都存在一个不好的键集，其中的所有的键都被映射到同一个槽。
解决方法：随机地选择哈希函数，形成“全域哈希”。
全域哈希 Universal Hashing
令$U$是键的集合，$H$是哈希函数的有限集合，$H$中的哈希函数将$U$映射到${0,1,\dots,m-1}$。如果满足：对所有的两两互异的键$x$和$y$，有$|{h\in H : h(x) = h(y) } | = \frac{|H|}{m}$，则称$H$是全域的。
从另一个角度来看，如果$h$从$H$里随机地选取，则$x$和$y$发生碰撞的概率是$\frac{1}{m}$。
从$H$里随机地选取一个$h$，将$n$个键映射到$m$个槽，对于给定的键$x$，期望的碰撞次数$\lt \frac{n}{m} = \alpha$。 证明如下。
设$C_x$为随机变量，用来表示哈希表$T$中与$x$发生碰撞的总次数。它实际上是指示器随机变量之和。
令
$$
C_{x,y}
\begin{cases}
1,& 如果h(x)=h(y) \
0,& 其他
\end{cases}
$$
则
$$
E[C_{x,y}] = \frac{1}{m}
$$
$$
C_x=\sum\limits_{y \in T - {x}} C_{x,y}
$$
$$
\begin{align}
E[C_x] &= E\left[\sum\limits_{y \in T - {x}} C_{x,y}\right] \
&= \sum\limits_{y \in T - {x}} E[C_{x, y}] \
&= \sum\limits_{y \in T - {x}} \frac{1}{m} \
&=\frac{n-1}{m} \
& \lt frac{n}{m} \
&= \alpha
\end{align}
$$
证毕.
构建一个全域哈希
令槽数$m$为质数。将全域里的任意键$k$分解成$r+1$位的$m$进制表示，即：
$$
k = <k_0,k_1,\dots,k_r>,0 \le k_i \le m - 1
$$
随机地选择一个数$a = <a_0, a_1, \dots, a_r>$，其中每一个$a_i$都随机地从${0, 1, \dots, m - 1}$中选取。
定义哈希函数$h_a(k) = \left( \sum \limits_{l = 0} \limits^r a_ik_i \right) \pmod m$。
函数集$H = {h_a}$，其大小$|H| = m ^ {r +1}$，此时的$H$是全域的，证明如下。
令$x = <x_0, x_1, \dots, x_r>, y = <y_0, y_1, \dots, y_r>$位两个互异的键，则$x$和$y$至少有以为不同，不妨设它们在第$0$位不相同，即$x_0 \ne y_0$.
设$H$中存在函数$h_a$使得$x$和$y$发生碰撞.
于是有：
$$
\begin{align}
& h_a(x) = h_a(y) \
\Rightarrow & \sum\limits_{i = 0}\limits^r a_ix_i \equiv \sum\limits_{i=0}\limits^r a_iy_i \pmod m \
\Rightarrow & \sum\limits_{i=0}\limits^r a_i(x_i - y_i) \equiv 0 \pmod m \
\Rightarrow & a_0(x_0-y_0) + \sum\limits_{i=1}\limits^r a_i(x_i-y_i) \equiv 0 \pmod m \
\Rightarrow & a_0(x_0-y_0) \equiv - \sum\limits_{i=1}\limits^r a_i(x_i-y_i) \pmod m
\end{align}
$$
Number Theory Fact
令$m$为质数，对任意的$z \in Z_m$（除$m$取余的整数）且$z \neq 0 \pmod m$，存在唯一的$z^{-1} \in Z_m$使得$z \cdot z^{-1} \equiv 1 \pmod m$。如$m=7$，有：
| $z$ | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| $z^{-1}$ | 1 | 4 | 5 | 2 | 3 | 6 |
由于$x_0 \ne y_0$，故而$\exists (x_0 - y_0) ^ {-1}$.
$$
\Rightarrow a_0 \equiv \left(-\sum\limits_{i=0}\limits^r a_i(x_i-y_i)\right)\cdot (x_0-y_0)^{-1} \pmod m
$$
因此，对于任意选定的$a_0,a_1,\dots,a_r$，在$a_0$的所有$m$种选择中，有且只有一种选择导致发生碰撞，其余的$m-1$种选择不会导致碰撞。
因此，导致$x$和$y$碰撞的$h_a$的数目为：
$$
\begin{align}
& m \cdot m \cdot \dots \cdot 1 \
=& m^r \
=& \frac{|H|}{m}
\end{align}
$$
完全哈希 Perfect Hashing
给定$n$个键，创建一个静态的哈希表，其大小$m=O(n)$，使得在最坏情况下，查找的时间为$O(1)$。
关键在于使用一个双级结构，并且每一级都使用全域哈希。通过这种方法，我们可以做到在第二级哈希表没有碰撞。
如果有$n_i$个项被同时哈希到第1级的槽$i$，那么有$m_i=n_i^2$个槽在第二级的哈希表中。
对第二级的分析
如果我们把$n$个键映射到$m=n^2$个槽中，使用的哈希函数$h$是从全域集合$H$中随机挑选的，那么期望的碰撞次数小于$\frac{1}{2}$。证明如下。
对于两个给定的键，经过$h \in H$哈希后，碰撞的概率为$\frac{1}{m} = \frac{1}{n^2}$。而一共有$C_2^n$对键。
因此，
$$
\begin{align}
E[碰撞次数] &= C^n_2 \cdot \frac{1}{n^2} \
&= \frac{n(n-1)}{2} \cdot \frac{1}{n^2} \
& \lt \frac{1}{2}
\end{align}
$$
证毕.
引理：马尔科夫不等式
对下界为$0$的随机变量$x$，
$$
P(x \ge t) \le \frac{E[x]}{t}
$$
证明如下。
$$
\begin{align}
E[x] &= \sum\limits_{x=0}\limits^\infty x \cdot P(X=x) \
& \ge \sum\limits_{x=t}\limits^\infty x \cdot P(X=x) \
& \ge \sum\limits_{x=t}\limits^\infty t \cdot P(X=x) \
&= t \cdot P(X\ge x)
\end{align}
$$
引理证毕.
于是，$P(没有碰撞)\ge \frac{1}{2}$.证明如下.
$$
\begin{align}
P(至少1个碰撞) & \le \frac{E[碰撞次数]} {1} \
& \le \frac{1}{2}
\end{align}
$$
证毕.
为找到良好的第2级的哈希函数，只需要随机测试几个，因为至少有一半的哈长局势都能保证不会发生碰撞。
空间复杂度分析
整个二级表的空间复杂度为$\Theta(n)$.证明如下.
对于第1级，选择$m=n$.令$n_i$作为被哈希到槽$i$里的键的数量。
对于第2级的每个哈希表$S_i$，选择$m_i=n_i^2$.
于是：
$$
\begin{align}
E[总的存储空间]&=n+E\left[\sum\limits_{i=0}\limits^{m-1} \Theta(n_i^2)\right] \
&=\Theta(n)(由桶排序分析可得)
\end{align}
$$
证毕.