什么是布隆过滤器
布隆过滤器(Bloom Filter) 是一种以Bitmap为基础的排重算法。由Bitmap和一系列的Hash函数组成。是由Howard Bloom 在 1970 年提出的。
Bloom Filter算法
初始状态
初始状态下，Bloom Filter是一个m位的位数组，且数组被0所填充。定义k个不同的hash函数，每一个hash函数都随机的将每一个输入元素映射到位数组中的一个位上。插入元素
输入元素经过k个hash函数的映射，得到k个索引，把位数组中这k个位置全部置1（不管其中的位之前是0还是1）查询元素
输入元素经过k个hash函数的映射，得到k个索引，如果位数组中这k个索引任意一处是0，那么就说明这个元素不在集合之中；但如果这k个索引处的位都是1，被查询的元素就一定在集合之中吗？答案是不一定，也就是说出现了误报的情况-
例子
例子
在上图中，当插入x、y、z这三个元素之后，再来查询w，会发现w不在集合之中，而如果w经过三个hash函数计算得出的结果所得索引处的位全是1，那么Bloom Filter就会告诉你，w在集合之中，实际上这里是误报，w并不在集合之中。
优缺点
- 优点
插入和查询时间都是常数 - 缺点
有一定的误报率和不能删除，因为多个元素哈希的结果可能在 Bloom filter 结构中占用的是同一个位，如果删除了一个比特位，可能会影响多个元素的检测。
误报率（False Positive Rate）
数学证明较复杂，详细可以参考
https://en.wikipedia.org/wiki/Bloom_filter
减少误报率：
- 增加Bitmap的大小
- 增加Hash函数，一般是8个
- 加上白名单
