Perfect hash function可以和bloom filter方法结合吗？
2012-01-19 18:03:57   来源：   点击：

1 个答案

• 答案 1：

  假设我们要表示的静态集合X有n个元素，我们针对它可以找到一个perfect hash function，记作h(x) : [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。

  有了h(x)，我们就可以将X映射到n个连续的格子（bucket）中，每个元素对应其中一个格子。下面我们还需要另一个hash function，它针对每个元素完全随机地生成j位长的hash value，然后将hash value作为这个元素的fingerprint存储在对应的格子里。记这个函数为φ: [1…u] → [0…2j-1]。有了h(x)和φ，我们就可以分两步将X映射到一个m = n .j位的内存中，且查找的错误率为1/2j，因为只有在j位fingerprint完全吻合的情况下才会出现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倍。

  所以得出的结论，你能明白了吧！