function - 在布隆过滤器中使用哪些哈希函数

Question

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

使用哪些功能？

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

我知道这是什么意思(独立且均匀分布)，但是我很难找到论点或讨论，哪些哈希函数满足了这些要求，因此是合适的。在很多文章中，我已经阅读了有关使用 FNV 或 Murmur哈希函数的建议，但不是为什么(或至少没有证明)它们合适。

提前致谢!

Answer 1

在构建Java Bloom筛选器库时，我问了自己同样的问题。有关我对Bloom过滤器的哈希函数分析的详细处理，请参见the Github readme。

我从两个 Angular 研究了这个问题:

计算速度有多快？

输出分布如何均匀？

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

结果是:

使用 Murmur3 可以在速度和均匀性之间取得最佳平衡。不要使用Murmur2，因为对于以小增量变化的输入来说，它不是统一的。

使用诸如SHA-256之类的加密哈希函数可获得最佳一致性。

将Kirsch-Mitzenmacher-Optimization应用于仅计算2而不是k个哈希函数(hash_i = hash1 + i x hash2)。

如果您的实现使用Java，则建议使用我们的Bloom过滤器哈希库。它是有据可查且经过全面测试的。有关详细信息(包括不同哈希函数的基准测试结果以及根据卡方检验得出的不正确性)，请参见 Github readme of the repo。