Bloom过滤器及其多个哈希函数

Question

我正在实现一个简单的布隆过滤器作为练习.

Bloom过滤器需要多个哈希函数,出于实际目的,我没有.

假设我想拥有3个哈希函数,仅仅获取我正在检查成员资格的对象的哈希是否足够,哈希(使用murmur3)然后添加+1,+ 2,+ 3(对于3)不同的哈希)再次哈希之前？

由于murmur3函数具有非常好的雪崩效应(真正展开结果),这对于所有目的都不合理吗？

伪代码:

function generateHashes(obj) {
  long hash = murmur3_hash(obj);
  long hash1 = murmur3_hash(hash+1);
  long hash2 = murmur3_hash(hash+2);
  long hash3 = murmur3_hash(hash+3);
  (hash1, hash2, hash3)
}

如果没有,那么这将是一个简单有用的方法？我希望有一个解决方案,如果需要,我可以轻松扩展更多哈希函数.

谢谢

Answer 1

AFAIK,通常的方法是不实际使用多个哈希函数.相反,哈希一次并将生成的哈希分成2,3或您想要布隆过滤器的部分.因此,例如,创建128位的散列并将其分成每个64位的2个散列.

https://github.com/Claudenw/BloomFilter/wiki/Bloom-Filters----An-overview