25

我有以下关于为 Bloom 过滤器选择哈希函数的问题：

  • 使用哪些功能？

在几乎所有文档/论文中，您都可以读到Bloom 过滤器中使用的哈希函数应该是独立且均匀分布的。

我知道这是什么意思（独立且均匀分布），但我很难找到一个论据或讨论，哪些散列函数满足这些要求，因此是合适的。在很多帖子中，我读到了有关使用FNV或Murmur 哈希函数的建议，但不知道为什么（或至少没有证明）它们是合适的。

提前致谢！

4

3 回答 3

22

在构建 Java Bloom 过滤器库时，我问过自己同样的问题。请参阅Github 自述文件，详细了解我对 Bloom 过滤器的哈希函数的分析。

我从两个角度看待这个问题：

  • 计算速度有多快？
  • 输出分布有多均匀？

速度可以很容易地通过随机输入的基准来衡量。均匀性有点困难，需要一些统计数据。使用卡方拟合优度测试，我测量了哈希值分布与均匀分布的相似程度。

结果是：

  • 使用Murmur3在速度和均匀性之间取得最佳平衡。不要使用 Murmur2，因为它对于以小增量变化的输入并不统一。
  • 使用 SHA-256 之类的加密哈希函数以获得最佳一致性。
  • 应用Kirsch-Mitzenmacher-Optimization仅计算 2 而不是 k 哈希函数 ( hash_i = hash1 + ix hash2 )。

如果您的实现使用的是 Java，我建议您使用我们的 Bloom 过滤器哈希库。它有据可查并经过全面测试。有关详细信息，包括不同哈希函数的基准结果及其根据卡方测试的不一致性，请参阅repo 的 Github 自述文件。

于 2016-10-31T14:08:20.620 回答
5

哈希函数应该为您提供图形证明，说明为什么 FNV 会是一个糟糕的选择，以及为什么 Murmur2 或Bob Jenkins 的哈希是一个不错的选择。

于 2012-08-21T04:00:01.687 回答
0

我认为一个合理的选择是多个 CRC 哈希。我假设，如果你想要多个 n 位哈希值，那么对于具有布尔域系数的多项式，有多个 n+1 次的素数多项式。但我不知道找到这些多项式的过程。

另一种可能性是使用多个模哈希。布隆过滤器位数组的大小必须是最大模值。但我认为，要使其正常工作，模值必须是大于 10 的素数的乘积，并且彼此互为素数。并且从最小到最大模量值的范围必须尽可能小。我不知道找到这样的值的方法。我已经编写了一些开源 C++ 代码来快速计算余数： https ://github.com/wkaras/C-plus-plus-intrusive-container-templates/blob/master/modulus_hash.h

于 2017-10-19T22:07:19.180 回答