全域哈希(Universial Hashing)和完全哈希(Perfect Hashing)

http://blog.csdn.net/qichi_bj/article/details/8469848

1.全域哈希(Universial Hashing)

定义：键集合 U 包含 n 个键，哈希表 T 包含 m 个槽，集合 H 包含一些哈希函数。如果 H 满足：对于任意 x, y ∈ U,  集合 { h | h∈H && h(x) = h(y) } 的元素个数等于 |H|/m，则称 H 为全域哈希；

性质：对全域哈希 H，从 H 中随机选择哈希函数，任意键 x, y 冲突概率等于 1/m；对于全域哈希 H，从中随机选择 h 作为哈希函数，对任意的键 x，与他冲突的键的数目的期望值是 n/m；

构造：构造 H 的一个方法如下：取 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

其中 Ki 为 K 的 m 进制表示的第 i 位即 K = <K0, K1, ..., Kr>；任意随机选择的 A 都对应一个哈希函数，所以 H 的大小为 m^(r+1) 。

2.完全哈希(Perfect Hashing)

定义：给定 n 个键，构造长度为 O(n) 的哈希表，使得键查询在最坏情况下为 O(1) 。构造方法为采用 2 级哈希，在第 1 级，如果有 Ni 个元素映射到第 i 个槽，那么第 Ni 个槽对应的 2 级哈希表采用全域哈希。表的长度取 Mi = Ni^2 。

属性：将 n 个键映射到 n^2 个槽，如果从全域哈希 H 中随机选择 h ，那么期望的冲突次数小于 1/2，不发生冲突的概率大于1/2。