海量数据的插入和查找 bloom filter

时间:2021-07-09 20:52:37

建模:

数据量: n

位数组bit_array: m bits, 初始化清0

独立的哈希函数个数: k

 

插入:

  对于数据x, hash[0 to k-1](x)对应数组bit_array中的位置1。

 

查找:

  对于数据x, 如果hash[0 to k-1](x)对应的k个bit_array中的位都为1, 则x存在。

 

与hash的区别:

  如果只有一个hash函数, 则会有大量的冲突。 所以采用多个hash函数, 用多个位标记一个数据。

 

attention:

  同hash一样, 会出现误判, 关于m, k的选择, 其中有很复杂的数学分析。 hash函数也会影响误判。

 

参考:

http://blog.csdn.net/jiaomeng/article/details/1495500