散列函数
一个好的散列函数应满足简单一致散列的假设：每个关键字都等可能的散列到m个槽位的任何一个之中，并与其它的关键字已被散列到哪个槽位无关。
除法散列法
在用来设计散列函数的除法散列法中，通过取k除以m的余数，将关键字k映射到m个槽中的某一个上，即散列函数为:
当应用除法散列法时，要避免选择m的某些值，m常常选择与近2的整数幂的不太接近的素数。
Explain：如果 $m=2^p$，二进制除法相当于右位移>>，例如111010>>3,即除以$2^3$，右移3位变为111，010则作为余数被移除，故在做取余操作时值为010,即为k的p个最低位数字。
乘法散列法
乘法散列法整体包含两步：
- 用关键字k乘上常数
A(0<A<1)，并去除kA的小数部分 - 用m乘以这个值，再取结果的底
floor
公式：h(k)=Math.floor[m(kA mod 1)]
STEP：
- 假设某计算机的字长为 $w$ 位，而 $k$ 正好可容于一个字中（$k<2^w$)
- 现在选取范围$[0，2^w]$内的任意数值 $s$，$k×s$ 即可用$R_1·2^w+R_0$来表示
- 因此$(k·A) mod 1=k·s/2^w$就是将$k×s$整体向右平移 $w$ 位，此时$R_0$即为小数部分
- 再乘以$2^m$相当于左移 $m$ 位，散列值 $h(k)$ 为$R_0$的前m位。
全域散列
如果让某个与你作对的人来选择要散列的关键字，那么他会选择全部散列到同一槽位的n个关键字，使得平均检索时间为O(n)，任何一个特定的散列函数都无法避免这种最坏情况的发生。唯一有效的改进方法是随机的选择散列函数，使之独立于要存储的关键字，这便是全域散列(universal hashing)，无论对手如何选择关键字，平均性态都很好。
步骤
- 选择一个足够大的
质数$p$，使得每个关键字都落在 $[0, p-1]$ 范围内； - 集合$Z_p$ = $\{0,1,…,p-1\}$，集合$Z^*_p$= $\{1,2,…,p-1\}$，对于任何 $a \in Z^*_p$，$b \in Z_p$，定义散列函数 $h_{a,b}$：
假定关键字的范围大于散列表的槽位数，即 $p>m$，对 $a$而言有p种选择，对 $b$ 而言有p-1种可能，所以 $H_{a,b}$有p(p-1)种可能性。当随机的选择关键字$k \not= l$，两者发生碰撞的概率不大于1/m。
Proof：
考虑 $Z_p $ 中两个不同的关键字 $k$ 和 $l$，即 $k \not= l$，对某一给定的随机散列函数$h_{a,b}$
此处必有 $ r\not= s$，因为 $r-s = a(k-l)\ mod\ p$
p为质数，故a和k-l模p均不为0，因此在模p这一层次上，尚不出现冲突。
故对于某个给定的r值，s的可能取值为余下的p-1种，其中满足$s \not= r$且$r \equiv s(mod \ p)$的值的数目至多为$(p-1)/m$，所以s与r发生碰撞的概率至多为 $((p-1)/m)/(p-1)=1/m$
$H_{a,b}$是全域的。
完美哈希
当键值是static(即固定不变)的时候，我们可以涉及方案使得最差情况下的查询性能也很出色，这就是完美哈希。实际上，很多地方都会用到静态关键字集合。比如一种语言的保留字集合，一张CD-ROM里的文件名集合。而完美哈希可以在最坏情况下以O(1)复杂度查找，性能非常出色的。
完美哈希的思想就是采用两级的框架，每一级上都用全域哈希：
完美哈希的结构如上图。具体来说，第一级和带链表的哈希非常的相似，只是第一级发生冲突后后面接的不是链表，而是一个新的哈希表。后面那个哈希结构，我们可以看到前端存储了一些哈希表的基本性质：$m$ 是哈希表槽数；$a,b$ 全域哈希函数要确定的两个值(一般是随机选然后确定下来的)，后面跟着哈希表。
为了保证不冲突，每个二级哈希表的数量是第一级映射到这个槽中元素个数的平方，这样可以保证整个哈希表非常的稀疏。下面给出一个定理，能更清楚的看到设置 $m=n^2$的作用。
定理：设$H$是一类全域哈希函数，哈希表的槽数 $m=n^2$。 那么，如果我们用一个随机函数 $h \in H$把 $n$ 个keys映射到表中。冲突次数的期望最多是1/2.
Proof：根据全域哈希的定义，对任意选出的哈希函数h，表中2个给定keys冲突的概率是 $1/m$,即 $1/n^2$
且总共有$C_2^n$可能的键值对，那么冲突次数的期望就是：
证毕！
