本文提到的Perfect Hashing完美哈希不完全等价于完美哈希函数。
假设我们要表示的静态集合X有n个元素,我们针对它可以找到一个perfect hash function,记作hx : [1…u] → [1…n]。所谓perfect hash function,即它针对不同的key能产生不同的hash value,也就是说没有collision。如果针对不同的key产生不同的hash value,且hash value分布在连续的整数区间内,则称之为minimal perfect hash function,或者minimal perfect hashing。所以上面提到的函数hx严格来说是一个minimal perfect hash function。
有了hx,我们就可以将X映射到n个连续的格子(bucket)中,每个元素对应其中一个格子。下面我们还需要另一个hash function,它针对每个元素完全随机地生成j位的hash value,【可以理解为hx用来生成一个随机地址】,然后将hash value作为这个元素的fingerprint存储在对应的格子里。记这个函数为φ: [1…u] → [0…2j-1]。
有了hx和φ,我们就可以分两步将X映射到一个m = n .j位的内存中,且查找的错误率为1/2j【因为完美哈希完成之后fingerprint都是连续存储在m位的内存中,如果此时仅用φ映射查找,则当j位fingerprint完全吻合的情况下才会出现false positive,如果用hx和φ同时查找,则不会出现false positive】。
Bloom Filter的错误率为(1/2)k ≥ (1/2)mln2/n。因此当m = n .j时,Bloom Filter的错误率为(0.6185)j,高于这种基于perfect hashing的方法。如果Bloom Filter要保持1/2j的错误率,必须有m = n .j / ln2,因此所占空间是基于perfect hashing方法的1 / ln2(1.44)倍。