数学之美：布隆过滤器 6月24日 【今日算法】

算法题目

如果一个黑名单网站包含100亿个黑名单网页，每个网页最多占64B，设计一个系统，判断当前的URL是否在这个黑名单当中，要求额外空间不超过30GB，允许误差率为万分之一。

解题思路：布隆过滤器

基础介绍

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量(位图)和一系列随机映射函数（哈希函数）。 布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

实际工程的应用

实际上，布隆过滤器广泛应用于网页黑名单系统、垃圾邮件过滤系统、爬虫网址判重系统等，有人会想，我直接将网页URL存入数据库进行查找不就好了，或者建立一个哈希表进行查找不就OK了。

当数据量小的时候，这么思考是对的，但如果整个网页黑名单系统包含100亿个网页URL，在数据库查找是很费时的，并且如果每个URL空间为64B，那么需要内存为640GB，一般的服务器很难达到这个需求。

那么，在这种内存不够且检索速度慢的情况下，不妨考虑下布隆过滤器，但业务上要可以忍受判断失误率。

位图（bitmap）

布隆过滤器其中重要的实现就是位图的实现，也就是位数组，并且在这个数组中每一个位置只占有1个bit，而每个bit只有0和1两种状态。如上图bitarray所示！bitarray也叫bitmap，大小也就是布隆过滤器的大小。 假设一种有k个哈希函数，且每个哈希函数的输出范围都大于m，接着将输出值对k取余（%m）,就会得到k个[0, m-1]的值，由于每个哈希函数之间相互独立，因此这k个数也相互独立，最后将这k个数对应到bitarray上并标记为1（涂黑）。

等判断时，将输入对象经过这k个哈希函数计算得到k个值，然后判断对应bitarray的k个位置是否都为1（是否标黑），如果有一个不为黑，那么这个输入对象则不在这个集合中，也就不是黑名单了！如果都是黑，那说明在集合中，但有可能会误，由于当输入对象过多，而集合也就是bitarray过小，则会出现大部分为黑的情况，那样就容易发生误判！因此使用布隆过滤器是需要容忍错误率的，即使很低很低！

布隆过滤器重要参数计算

通过上面的描述，我们可以知道，如果输入量过大，而bitarray空间的大小又很小，那么误判率就会上升。那么bitarray空间大小怎么确定呢？不要慌，已经有人通过数据推倒出公式了！！！哈哈，直接用～

假设输入对象个数为n，bitarray大小（也就是布隆过滤器大小）为m，所容忍的误判率p和哈希函数的个数k。计算公式如下：（小数向上取整）

注意：由于我们计算的m和k可能是小数，那么需要经过向上取整，此时需要重新计算误判率p！

假设一个网页黑名单有URL为100亿，每个样本为64B，失误率为0.01%，经过上述公式计算后，需要布隆过滤器大小为25GB，这远远小于使用哈希表的640GB的空间。

并且由于是通过hash进行查找的，所以基本都可以在O(1)的时间完成！

布隆过滤器的测试

测试用例来自GitHub的CPP版的布隆过滤器！

GitHub地址：https://github.com/ArashPartow/bloom

我们关心的主要是Queries列和FPQ列，可以看出，输入对象为1万多个时也会出现错误的访问，当然概率极低的，那么如果我们一直增加Queries的次数，其误判率是怎么样的！

我们可以看到作者一共测试到了1715万次输入，而平均的误判率为0.00023738，充分说明了布隆过滤器的有效性。如果想要了解底层的话，可以去看看源码学习学习！

来源 | 算法工程师之路

作者 | TeddyZhang