如何判断一个网页的URL是否存在于包含100亿条数据的黑名单中？该列表现在包含100亿个不安全网页的URL，每个URL的大小高达64B（字节）。请设计系统。要求：系统允许判断错误率小于1/10,000。额外使用的空间不要超过30GB，然后遍历一次就可以判断了。但是，每个URL有64B（字节），黑名单中有100亿个URL。如果要使用数据库或哈希表来存储所有这些数据，则至少需要640GB的空间，这显然不符合要求2（使用不超过30GB的额外空间）。其实这个题目有个明显的暗示，就是错误率是允许的！类似的话题如网页黑名单系统、垃圾邮件过滤系统、爬虫URL判断系统等，一般都允许一定的错误率，但对篇幅要求更严格。话不多说，首先想到的应该是Bloomfilter。简单介绍一下Bloomfilter的基本结构，其实就是一个BitMap（简单点说，其实就是一个数组），BitMap中每一位上的元素都是通过几个hash函数赋值的。Bloomfilter的优点是可以用很少的空间达到很高的准确率（但不可能完全正确）。散列函数（hashfunction）不需要太多，主要有以下节点特点：散列函数一般可以输入任意值，即输入值范围是无限的。当相同的输入值传递给哈希函数时，返回值是相同的。当不同的输入值被传递给哈希函数时，由于哈希冲突的存在，返回值可能相同也可能不同。不同输入值得到的返回值会平均分配。显然，返回值分布越均匀，哈希函数就越好。有兴趣的小伙伴可以了解一下散列函数的一些经典实现，比如MD5、SHA1算法，这里就不详细介绍了。让我们再看看布隆过滤器。假设有一个长度为m的bit（位）类型的数组（即BitMap位图，上一篇介绍过），即数组中每个位置只占一个bit（每个bit只为01)state)：假设总共有k个不同的hash函数，它们的输出域都是>=m。那么对于同一个输入对象（假设是一个URL，字符串），k个哈希函数计算出来的结果也是不同的（当然也有可能相同）。对于每一个计算结果，取m的余数（%m），然后将BitMap上对应的位置设置为1（黑色）：按照上面的方法，我们处理所有的输入对象（黑名单URL中的200亿项），每个对象可能会把BitMap中一些白色的位置涂黑（0的位置为1）。这样就构建了存储黑名单中200亿个URL的布隆过滤器。那么假设此时有一个新的值到来，如何判断这个新值之前是否已经存在呢？（如何判断某个网页的url是否在黑名单？）记录这个网页的url作为input，想查看是否在黑名单（BitMap）中，把input通过同一个khash函数得到k个值，然后继续对k个值取余（%m）同样的方法得到在[0,m-1]范围内的k个值的值，然后检查BitMap上这些位置是否全黑：如果一个不黑，说明输入一定不在这个BitMap中。如果都是黑色，说明这个BitMap中可能有a，也就是说有误判的可能。更具体的解释一下，如果输入确实是之前处理过的URL，那么在生成Bloomfilter的时候，BitMap中对应的k个位置肯定已经被black掉了，所以在checking阶段，input执行相同的操作再次操作，肯定不会有误判。会造成误判的是，输入明明不是之前处理过的输入对象，但是由于哈希冲突的存在，可能会出现这样的巧合，两个不同的输入得到的k个哈希输出是相同的（的当然概率会很小），那么在检查输入的时候，输入对应的k个位置可能是黑色的，从而把输入误认为是输入对象。因此，采用布隆过滤器设计的系统可以总结为：存在于黑名单中的URL必须能够被查出，不存在于黑名单中的URL被误判的可能性相对较小。对于这种误判，其实是有解决办法的，那就是白名单。对于已经发现的误报数据，我们可以建立白名单，防止再次误报。比如已经发现样本www.baidu.com不在Bloomfilter（黑名单）中，但是每次计算的结果都显示在Bloomfilter中，那么这个样本就可以加入到白名单中，以后再输入这个样本时，就不会再进入Bloomfilter的逻辑进行判断了。手写布隆过滤器下面我们用Java实现一个布隆过滤器，参考这篇文章：https://cloud.tencent.com/developer/article/1823271。首先我们当然需要一个位数组，Java提供了一个封装好的位数组BitSet。另外，写一个简单的布隆过滤器需要考虑以下几点：需要指定位数组的大小空间。在其他相同的情况下，位数组越大，哈希冲突的可能性越小。多个哈希函数，为了避免冲突，我们可以使用多个不同的素数作为种子。应该对外提供的方法：主要有两种，一种是给Bloomfilter添加元素，一种是判断Bloomfilter是否包含元素。重点在下图：Hash函数的实现这里不多研究，给出一个比较简单的版本，主要是对hashCode()值的高低位进行异或运算，然后乘以预设种子（seed），然后取BitMap数组大小的余数：
