Bloom过滤器中使用哪些哈希函数

Question

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

• 使用哪些功能？

在几乎每篇文档/论文中,您都可以读到Bloom过滤器中使用的散列函数应该是独立且均匀分布的.

我知道这是什么意思(独立和统一分布),但我很难找到论证或讨论,哪些散列函数满足这些要求,因此是合适的.在很多帖子中,我已经阅读了关于使用FNV或Murmur哈希函数的建议,但不是为什么(或者至少没有证明)它们是合适的.

提前致谢!

Answer 1

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

我从两个角度看问题:

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

通过随机输入的基准可以轻松测量速度.统一性有点困难,需要一些统计数据.使用卡方拟合优度检验我测量了散列值的分布与均匀分布的相似程度.

结果是:

• 使用Murmur3在速度和均匀性之间进行最佳平衡.难道不是因为它是不统一的,在小的增量改变投入使用Murmur2.
• 使用SHA-256等加密哈希函数可获得最佳均匀性.
• 应用Kirsch-Mitzenmacher-Optimization仅计算2个而不是k个散列函数(hash_i = hash1 + ix hash2).

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

Answer 2

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