布隆过滤器及其多重散列函数

Question

我正在实现一个简单的Bloom Filter作为练习。

Bloom filters需要多个哈希函数，但在实际应用中我没有。

假设我想要有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个或多少个部分作为Bloom filter。例如，创建一个128位的散列，并将其分为两个散列，每个散列64位。

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

Answer 2

Bloom filter的散列函数应具有足够的独立性和随机性。murmur hash在这方面做得很好。因此，您的方法是正确的，并且您可以按照自己的方式生成尽可能多的新散列。对于教育目的来说，这是很好的。

但在现实世界中，多次运行散列函数是非常耗时的，因此通常的方法是在不实际计算散列的情况下创建即席散列。

为了纠正@memo，这不是通过将散列分割成多个部分来完成的，因为散列的宽度应该保持不变(并且不能将64位散列分割为超过64个部分;)。方法是获得两个独立的散列并将它们组合在一起。

function generateHashes(obj) {
  // initialization phase
  long h1 = murmur3_hash(obj);
  long h2 = murmur3_hash(h1);

  int k = 3; // number of desired hash functions
  long hash[k];

  // generation phase
  for (int i=0; i<k; i++) {
      hash[i] = h1 + (i*h2);

  return hash;
}

如您所见，以这种方式创建新的散列是一个简单的乘法-加法操作。

Answer 3

这不是一个好的方法。让我试着解释一下。布隆过滤器allows you to test if an element most likely belongs to a set, or if it absolutely doesn’t. In others words, false positives may occur, but false negatives won’t.

参考：https://sc5.io/posts/what-are-bloom-filters-and-why-are-they-useful/

让我们来看一个例子：

您有一个输入字符串'foo‘，我们将其传递给多个散列函数。murmur3散列值提供输出K，对此散列值的后续散列值提供x、y和z

现在假设你有另一个字符串‘murmur3’，碰巧它的bar散列也是K。其余的哈希值呢？它们将是x、y和z，因为在您提出的方法中，后续的散列函数不依赖于输入，而是依赖于第一个散列函数的输出。

long hash1 = murmur3_hash(hash+1);
long hash2 = murmur3_hash(hash+2);
long hash3 = murmur3_hash(hash+3);

正如链接中所解释的，其目的是在集合中执行概率搜索。如果我们搜索“foo”或“bar”，我们会说它们“很可能”都存在。因此，假阳性的百分比将会增加。

换句话说，这个bloom过滤器的行为就像一个简单的散列函数。它的“bloom”方面不会出现，因为只有第一个哈希函数决定了搜索结果。

希望我能解释得够清楚。如果你有更多的后续问题，请在评论中让我知道。很乐意为您效劳。