布隆过滤器：如何找到k个哈希函数？
布隆过滤器需要 k 个哈希函数，这些函数返回 0 到 m 之间的值（m 是位数组的长度）。 我必须实现这样一个布隆过滤器，并且我已经阅读了一些关于这些过滤器的理论论文（它们如何工作，需要多少个哈希函数，错误如何表现等）
现在我有两个关于哈希函数的问题：
- 我如何找到k 哈希函数 - 我应该使用哪些哈希函数？
- 如何找到返回 0 到 m 之间值的哈希函数？或者，如何将哈希函数的输出映射到 0-m 范围？
A Bloom Filter needs k hash functions, which return a value between 0 and m (m is the length of the bit array).
I have to implement such a bloom filter and I already read some theoretical papers about those filter (how they work, how many hash functions you need, how the error behaves etc.)
Now I have two questions about hash functions:
- How do I find k hash functions - which hash functions should I use?
- How do I find hashs functions which return a value between 0 and m? Alternatively, how can I map the output of a hash function to the range 0-m?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
您可以使用此 - http://en.wikipedia.org/wiki/Universal_hashing
You can use this - http://en.wikipedia.org/wiki/Universal_hashing
您可以使用Kirsch-Mitzenmacher 优化：
其中hash1是32位，hash2是32位。一看你可以使用：
You can use the Kirsch-Mitzenmacher optimization:
Where hash1 is 32 bit, hash2 is 32 bit. In a look you could use:
您可以使用 MD5 或 SHA 等加密哈希函数一次获取一堆哈希值。将加密哈希值分成 N m 位片段，并像处理 N 个普通哈希函数的输出一样对待它们。
You can get a bunch of hash values at one time with a cryptographic hash function like MD5 or SHA. Divide the cryptographic hash value into N m-bit pieces, and treat them just like you would the output of N normal hash functions.
应该使用的k个哈希函数的特点是
维基百科页面上给出：Bloom Filter 并进入
算法描述其中提到 - 设计 k 个不同的独立哈希函数的要求...
有关通用哈希的优秀教程：精彩的麻省理工学院讲座
The characteristics of the k hash functions that should be used are
given on the wikipedia page: Bloom Filter and go in the
algorithm description where it says - The requirement of designing k different independent hash functions...
For good tutorials on universal hashing : Nice MIT lecture
你可以使用任何哈希函数......网络上有许多可用的哈希简单哈希函数。
请参阅 http://en.wikipedia.org/wiki/List_of_hash_functions
使用任何哈希函数来获取哈希值，为了使其在 0-m 范围内，请使用 modulus(%) 运算符。
即位位置 = hash % m;
它可能效率不高，但它有效......
U could use any hash functions....there are many hash simple hash functions available in the net.
Refer http://en.wikipedia.org/wiki/List_of_hash_functions
Use any hash function to get a hash value and in order to get it in the range of 0-m , use the modulus(%) operator.
i.e bitlocation = hash % m;
it might not be efficient ,but it works...