c - C中布隆过滤器的通用哈希函数实现

Question

我使用布隆过滤器模拟集合交集近似。我尝试了很多简单的散列函数来将值散列到过滤器。但它不擅长避免碰撞。所以有人建议了一个通用的哈希函数。但我不确定它是如何工作的。我的程序旨在仅将密钥传递给散列函数，散列函数返回散列。谁能帮我写代码？谢谢

Answer 1

don't worry about collision of hash functions when used with bloom filters. you don't have to handle collision in this case. just get k different has functions which set k bits in an array of m-bits when you are inserting an element. at the time of query, you again use all k hash functions to check all the k-bits; if any one of them is not set then the search is false. if all of them is set, you can't conclude anything (false positive results). This is clearly explained in wiki:

http://en.wikipedia.org/wiki/Bloom_filter