MIT算法导论八 全域哈希和完全哈希

- 全域哈希
- 完全哈希

普通哈希的一个缺点：
对任意的hash函数h，总存在一组keys，让他们都映射到同一个槽里面，这样效率，就跟离链表差不多了

解决的思想就是：
独立于键值，随机的选择hash 函数。这就跟快排中为避免最差情况时随机化版本差不多。但是选取hash function的全局域是不能乱定的，否则也打不到理想的性能。

---

全域哈希

设U是key的全局域， 设H是哈希函数的有限集合，H函数将U映射到{0,1,..,m-1}，即table的槽内。 如果对所有不等的键值对x,y∈U，将他们映射到同一个位置的概率是H/m
从另一个角度看，如果函数h是从H中随机选出的，x和y发生碰撞的概率是1/m

用一张图来理解，当我随机选一个哈希函数时，就像在上图区域乱扔一个飞镖，落在下面红色区域中就会发生冲突，这个概率是1/m

下面给一个定理，说明为什么全域函数就是好的
设h是从哈希函数全域集H中随机选出的函数h，h被用作把任意n个键映射到表T的m个槽中，对给定键值x，E[#collision with x]<n/m | 发生碰撞的期望次数小于n/m，即装载因子α

证明
设Cx是表示与key x冲突的键值数量的随机变量，设Cxy是指示变量
Cxy = 1 if h(x) = h(y) and 0 otherwise
根据定理 E[Cxy]=1/m  
Cx=∑Cxy | y∈T−{x}
=》 E[Cx] = E[ ∑Cxy ]   | y∈T−{x}
          = ∑ E[Cxy] | y∈T−{x}
          = ∑ 1/m | y∈T−{x} 
          = n-1 / m

这个定理想要说明的是，这种全域哈希的随机化选择可以达到哈希表理想的效果

构造一个全域哈希

首先选择一个足够大的质数m，把key k分解为r+1位，可以把k=<k_0、k_1 ...k_r> | k_i > 0，即把k转换成m进制数
然后引入随机化策略，随机的选择一个数a，a=<a_0、a_1 ...a_r>，a同样是m进制数，a_i∈[0, m-1]，对于a的每一位，对应一个不同的哈希函数，用随机数a表示随机哈希函数
最后定义哈希函数，ha(k) = ∑ ai·ki mod m | i = 0 <- r

书上给出的全域哈希
首先选择一个足够大的质数p,使得所有的键值都在0-p-1之间
Zp={0,1,...,p-1}，Z∗p={1,2,..,p-1}
对于任意的a∈Zp*和b∈Zp，定义散列函数
Ha,b(k) = ((ak + b) mod p) mod m
所有这样的哈希函数构成的函数集
Hp.m={ha,b | a∈Zp*,b∈Zp}，共p(p-1)个散列函数

现有p=17，m=6 计算h3,4(8)=5

---

完全哈希

当键值是static(即固定不变)的时候，我们可以涉及方案使得最差情况下的查询性能也很出色，这就是完美哈希

完全哈希可以在最坏情况下以O(1)复杂度查找，性能非常出色的。完美哈希的思想就是采用两级的框架，每一级上都用全域哈希

完全哈希的结构如图

完全哈希

第一级和带链表的哈希非常的相似，只是第一级发生冲突后后面接
的不是链表，而是一个新的哈希表。后面那个哈希结构，我们可以看到前端存储了一些哈希表的基本性质：m 哈希表槽数；a,b 全域哈希函数要确定的两个值(一般是随机选然后确定下来的)，后面跟着哈希表。新的哈希表通过选取哈希函数却表二次哈希不出现碰撞

为了保证不冲突，每个二级哈希表的数量是第一级映射到这个槽中元素个数的平方，这样可以保证整个哈希表非常的稀疏。下面给出一个定理，能更清楚的看到设置m=n²的作用

设H是一类全域哈希函数，哈希表的槽数m=n². 那么，如果我们用一个随机函数h∈H把n个keys映射到表中。冲突次数的期望最多是1/2