本质上Bloom filter是一种数据结构，一种巧妙的概率数据结构，特点是高效的插入和查询，可以用来告诉你‘某个东西一定不存在或者可能存在’。 　　

　　与传统的链表、集合和映射等数据结构相比，它效率更高，占用空间更少，但其缺点是返回的结果是概率性的，而不是精确的。 　　

　　实现原理HashMap的问题在讲述Bloom Filter的原理之前，我们先思考一下。你通常用什么来判断一个元素是否存在？应该有相当一部分人回答HashMap。确实可以将值映射到HashMap的键，然后在O(1)的时间复杂度内返回结果，效率极高。但是HashMap的实现也有缺点，比如存储容量大。考虑到负载系数的存在，通常空间用不完。一旦你的值很多，比如几亿，HashMap占用的内存就变得相当可观。 　　

　　比如，当你的数据集存储在远程服务器上，本地服务接受输入，数据集太大，无法一次性读入内存构建HashMap，也会出现问题。 　　

　　Bloom filter数据结构Bloom filter是一个位向量或位数组，看起来像这样： 　　

　　如果要将一个值映射到Bloom filter，需要使用多个不同的hash函数生成多个hash值，为每个生成的hash值所指向的位位置生成hash值1、4、7，例如，为值' baidu '和三个不同的hash函数，那么上图就转化为： 　　

　　好了，我们现在来拯救另一个价值‘腾讯’。如果哈希函数返回3、4和8，图形将继续变为： 　　

　　值得注意的是，4位被覆盖，因为两个值的散列函数都返回该位。现在，如果我们要查询' dianping '的值是否存在，哈希函数返回1、5和8三个值。结果我们发现第5位的值是0，说明没有一个值映射到这个位，所以我们可以肯定地说‘dianping’的值不存在。而当我们需要查询'百度'的值是否存在时，那么哈希函数必然会返回1、4、7，然后我们检查这三位的值都是1，那么我们能说'百度'存在吗？答案是否定的，只有‘百度’这个值可能存在。 　　

　　这是为什么呢？答案很简单，因为随着加入越来越多的值，会有越来越多的位被设置为1，这样即使某个值‘淘宝’还没有被存储，如果哈希函数返回的三位都被其他值设置为1，程序仍然会判断值‘淘宝’存在。 　　

　　你支持删除吗？目前我们知道Bloom filter可以支持add和isExist操作，那么可以删除操作吗？答案是否定的。比如上图中的bit 4，如果被两个值一起覆盖，一旦你删除了其中一个值，比如'腾讯'，并设置为0，下次你判断另一个值，比如'百度'是否存在，会直接返回false，而实际上你并没有删除它。 　　

　　如何解决这个问题，答案是计数删除。但是计数删除需要存储一个数值而不是原来的位，这样会增加占用的内存大小。在这种情况下，加一个值意味着在对应索引槽中存储的值上加一，删除意味着减一，判断是否存在取决于该值是否大于0。 　　

　　如何选择哈希函数的个数和布隆过滤器的长度？显然，如果Bloom filter太小，很快所有的位都将是1，那么查询的任何值都将返回‘可能存在’，这将达不到过滤的目的。布隆过滤器的长度会直接影响虚警率，布隆过滤器越长，虚警率越小。 　　

　　此外，哈希函数的数量也需要权衡。数字越多，布隆过滤器的比特位1越快，布隆过滤器的效率越低。但是如果太少，那么我们的误报率就会变高。 　　

　　k是哈希函数的数量，m是布隆过滤器的长度，n是插入元素的数量，p是虚警率。至于这个公式怎么推导，我在知乎上发表的文章有涉及。有兴趣的可以看看。如果不感兴趣，只要记住上面的公式就可以了。 　　

　　最佳实践的常见应用是使用Bloom filter来减少磁盘IO或网络请求，因为一旦某个值必须不存在，我们就可以避免后续昂贵的查询请求。 　　

　　另外，既然你使用Bloom filter来加快搜索速度，判断是否存在，那么性能不高的hash函数并不是一个好的选择。推荐MurmurHash和Fnv。 　　

　　值分裂Redis由于支持setbit和getbit操作，具有较高的纯内存性能，自然可以作为Bloom filter使用。但Bloom filter使用不当，容易导致数值较大，增加Redis阻塞的风险，建议在生成环境中拆分庞大的Bloom filter。 　　

　　拆分的形式化方法有很多种，但本质是Hash(Key)后的请求不应该分散在多个节点的多个小位图上。而是拆分成多个小位图后，一个键的所有哈希函数都落在这个小位图上。 　　

　　参考概率数据结构：布隆过滤器。 　　

　　布鲁姆过滤器 　　

　　本文遵循CC BY-NC-SA 3.0创意分享协议。