哪个散列函数在布隆过滤器使用

我已经得到了有关选择散列函数布鲁姆过滤以下问题：哪个散列函数在布隆过滤器使用

使用哪些功能？

在几乎每一个文件/文件，你可以读到，在一个布鲁姆使用的散列函数过滤应该是独立的，均匀分布。

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

在此先感谢！

来源

2012-08-14 Torsten

Hash Functions应该为您提供图解证明为什么FNV会是一个不好的选择，为什么Murmur2或Bob Jenkins' Hashes之一会是一个不错的选择。

来源

2012-08-21 04:00:01

构建Java布隆过滤器库时，我问自己同样的问题。请参阅the Github readme以详细了解我对Bloom过滤器的散列函数的分析。

我看着这个问题从两个方面：

的速度有多快的计算？
输出分布的均匀性如何？

速度很容易通过随机输入基准测量。统一性有点困难，需要一些统计数据。使用卡方检验拟合度检验，我测量了散列值分布与统一分布的相似程度。

结果是：

使用Murmur3最佳权衡速度和均匀性。做不是使用Murmur2，因为它是不均匀的输入变化小增量。
使用一个加密散列函数像SHA-256一样是最好的。
应用Kirsch-Mitzenmacher-Optimization仅计算2而不是k个散列函数（hash_i = hash1 + i x hash2）。

如果您的实现使用Java，我会推荐使用我们的Bloom过滤器哈希库。它有据可查，并经过彻底测试。有关详细信息，请参阅Github readme of the repo，其中包括不同散列函数的基准结果以及根据卡方检验的不合格情况。

来源

2016-10-31 14:08:20 DivineTraube

我没有阅读[Kirsch-Mitzenmacher-Optimization]（https://www.eecs.harvard.edu/~michaelm/postscripts/tr -02-05.pdf），但在论文hash_i = hash1 + ix hash2％p中，其中p是一个素数，hash1和hash2在[0，p-1]的范围内，并且该bitset由k * p个位组成。 – cyber4ron 2017-06-06 16:28:55

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

另一种可能性是使用多重模散列。 Bloom Filter位数组的大小必须是最大模数值。但我认为，为了使其运行良好，模数值必须是大于10的素数的乘积，并且相对于彼此素数。而从最小值到最大模值的范围必须尽可能小。我不知道找到这样的价值的方法。我写了一些开源C++代码来快速计算余数：https://github.com/wkaras/C-plus-plus-intrusive-container-templates/blob/master/modulus_hash.h

来源

2017-10-19 22:07:19 WaltK

哪个散列函数在布隆过滤器使用

回答

相关问题