13

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

布隆过滤器需要多个哈希函数，出于实际目的，我没有。

假设我想要 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)
}

如果不是，那将是一种简单、有用的方法吗？我想要一个解决方案，如果需要，我可以轻松扩展更多哈希函数。

谢谢

4

3 回答 3

8

AFAIK，通常的方法是不实际使用多个散列函数。相反，散列一次并将生成的散列分成 2、3 或您想要用于 Bloom 过滤器的部分。因此，例如创建一个 128 位的散列并将其拆分为 2 个 64 位的散列。

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

于 2018-07-27T07:58:17.830 回答
1

布隆过滤器的散列函数应该足够独立和随机。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;
}

如您所见，这种创建新哈希的方法是一个简单的乘加操作。

于 2018-07-30T08:40:15.363 回答
0

这不是一个好方法。让我试着解释一下。布隆过滤器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”，我们将其传递给多个哈希函数。murmur3hash 给出了输出K，随后的 hash 给出了这个 hash 值x，y并且z

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

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

如链接中所述，目的是在集合中执行概率搜索。如果我们搜索“foo”或“bar”，我们会说它们“很可能”都存在。所以误报的百分比会增加。

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

希望我能够充分解释。如果您有更多后续查询，请在评论中告诉我。很乐意提供帮助。

于 2018-07-30T18:10:33.097 回答