建模:
数据量: 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