全域哈希和完全哈希——麻省理工算法导论公开课

浏览数：23 / 时间：2015年06月08日

公开课地址：

http://open.163.com/movie/2010/12/3/A/M6UTT5U0I_M6V2TGI3A.html

全域哈希

诞生：

哈希的根本缺陷：对于任意哈希函数而言，都存在一个不好的健集，使得所有的健都会哈希到同一个槽里去，那么如何解决这种情况呢？如何防止对某个键集永远有较差的表现？如何防止竞争对手使用这个键集来降低你的性能表现？一个词解决这个问题 —— random！

全域哈希的方法就是随机选择一个哈希函数H（当然不是每次操作都选择一个哈希函数，而是构建一个哈希表的时候随机选一个，选定之后这个哈希表的所有操作都是基于这个哈希函数，这种方法可以防止竞争对手别有用心的设计一个键集，同时也能避免某些键集永远会导致较差的性能，如果是，那么重新建一个表就行！）

定义：

设U为键的全域，H是哈希的有限集，H里面的每个哈希函数h将集合U映射到哈希表的m个位置上，如果哈希表满足：对于U里面的两个值x,y x≠y {h∈H：h（x）=h（y）}=|H|/m，那么H就是全域的。
|H|的意思是指全域哈希函数的个数，那么从里面任意取一个函数h，这个函数把x和y哈希到同一个位置的概率就是1/m，也就是说，这些函数都是均匀函数。

Hash Function Group构造的一个方法如下：

取 m 为素数，取随机数 A 为 r+1 位 m 进制的数，表示为 <A0,A1,...,Ar> （其中 0 <= Ai <= m-1为随机选择），则哈希函数H[A](K) 定义为：

H[A](K) = sum { Ai * Ki | i =0, 1, ... , m-1 } mod m

证明：

技术分享

定理得证

完全哈希

哈希的基本缺陷，即使构造了全域哈希，还是不一定能解决不好的键集输入的问题，能不能找到一个完美的解决方案呢？
能不能保证在任何情况下查找的复杂度都在Θ（1）呢？而且哈希表还不能太大，必须满足n=O（m）
现在来做做推理，如果我们要求对于哈希表中任意一个数x，发生碰撞的次数的期望，小于1
在均匀哈希的情况下，对于每一个数来说，碰撞的可能性都是1/m,那么
Cn2*1/m=n(n-1)/2m <1 那么m＞n（n-1）/2 也就是说m是n的平方的量级，所以普通的哈希表是不可能完成这种任务的，除非哈希表构造得非常的大。
解决方案是构造一个双层哈希的结构，哈希表的底层用来存放第二层的入口指针和所用的哈希函数，第二层才是存放数据元素，证明略