共计 1356 个字符，预计需要花费 4 分钟才能阅读完成。
什么是Bloom Filter？
布隆过滤器本质上是一种高效的数据结构，概率型的数据结构。特点是能够高效的插入和查询，可以告诉你“某个数据一定不存在或者可能存在”，但并不能告诉你一定存在。
相比于传统的List，Set等数据结构，它的占用空间更小，缺点是返回的结果是概率性的，不是确切的。
Bloom Filter实现原理
原理：当一个元素被加入集合时，通过k个散列函数将这个元素映射成一个bit数组中的k个点，把它们置为1。如果这些点有任何一个0，那么被检元素一定不存在；如果都是1，则被检元素就很可能存在。
Bloom Filter实现
布隆过滤器有许多的实现，可以参考Guava中对Bloom Filter的实现。
使用Bloom Filter，设置两个点
- 预估数据量n
- 期望的误判率fpp
实现Bloom Filter，考虑两个点
- hash函数的数量
- bit数组的大小
布隆过滤器数据结构
假设我们需要将“dustin”的值映射到布隆过滤器中，通过3个哈希函数生成3个哈希值，并对每个哈希值指向 bit 位置1，哈希值为1，4，7，如下图
然后我们继续存入一个值“China”，哈希函数返回3，4，8，图变成下图
其中，4这个bit位由于两个值的哈希函数都返回了这个bit为，所以覆盖了。
现在想要查询 “Japan” 这个值，假设返回2，3，4，我们可以发现2这个bit位为0，那么这个值就不存在。而我们查询“dustin”，返回1，4，7，三个bit位都为1，那么“dustin”这个值就可能存在，但是不是一定存在。
为什么呢？因为随着增加的值越来越多，被置为1的bit位也越来越多，这样的话，即使某个值没有被存储过，但是有可能出现他的哈希函数返回的bit位都为1，那么我们的程序还是会判定为存在。
如何选择Bloom Filter的哈希函数个数和数组长度呢？
很显然，很小的布隆过滤器很快就会把所有的bit位都置为1，那么所有的查询结果都是可能存在，就起不到过滤的作用了。
但是数组越大占用内存也越大，哈希函数越多，误判率越低但是效率也越低，所以，还是要做权衡。
k为哈希函数个数，m为布隆过滤器长度，n为插入元素个数，纵坐标p为误判率，至于这个图如何推导，可以上google上查，我们只记住就行。
Bloom Filter使用场景
布隆过滤器的使用可以减少磁盘IO或网络请求，只要判定一个值必然不存在，就可以直接返回，不需要进行后续昂贵的查询请求了。
- 在缓存穿透问题上，使用布隆过滤器判断数据是否存在，不存在直接返回
- 海量数据去重：爬虫系统中对成千上万的url的去重等
- 邮箱系统的垃圾邮件过滤功能
Bloom Filter的缺点
- 存在误判。可以根据业务的容忍度，控制误判率。
- 删除困难。一个放入布隆过滤器的元素映射到bit数组k个位置上都是1，删除的时候不能简单的直接将这些bit位置为0，因为可能会影响到其他元素的判断。可以采用
- 布隆过滤器的不当使用有可能产生大Value，增加redis等的阻塞风险，生产环境建议对体积庞大的布隆过滤器进行拆分。（拆分的大致做法：拆分成多个小bitmap，然后一个key的所有哈希函数必须都落在同一个bitmap上，不要分散在不同的bitmap上即可）
