什么是布隆过滤器

在网络爬虫中，经常需要确认一个网址是否已经访问过，这样可以节约资源，减少不必要的开销。有一个最直接的方法就是将集合中的全部元素存入计算机，每遇到一个新元素，将它和集合中的元素直接比较即可。

把已访问过的url存入哈希表（Hash Table）中，当需要判断当前url是否已经访问时可以访问哈希表，如果存在则表明已经访问过。其优点是快速准确，缺点也显而易见，耗费了大量的存储空间，尤其是当集合规模巨大的时候。

而今天我们要介绍的布隆过滤器（Bloom Filter）就能解决这样的问题。它能够告诉我们“某个url已经访问过或者可能访问过”。这也是布隆过滤器的一个特点，有一定的误识别率。

工作原理

布隆过滤器实际上是一个很长的二进制向量和一些列随机映射函数。比如当前有100个url，先建立一个1000比特的全零向量，对每一个url,分别使用20个hash函数，把这个url 哈希对应的比特位置为1。我们在判断当前url是否已经访问过，可以看该url哈希之后对应的比特位是否全部为1。若全部为1，则说明该url已经访问过或者可能访问过。

误识别问题

布隆过滤器不会判错任何一个确实已经访问过的url，但它也有可能将未访问过的url判成已访问。因为不同url在经过哈希之后，这些对应的比特位可能恰好也都被置为1，即误识别问题。

估算这个误识别的概率（在检验上称之为“假阳性”）并不难。我们可以假定共有n个url,布隆过滤器有m比特，共有k个哈希函数。在经过k次哈希之后，布隆过滤器中某一位比特未被置为1的概率为：

插入n个url后还没有将某一位比特置为1的概率P(A)为

那么被置成1的概率为1-P(A),现在假定这n个url都放入到布隆过滤器中，新插入一个不在集合中的url,该url哈希函数正好命中某个值为1的比特的概率就是1-P(A)。一个不在集合中的url被误判为在集合中，需要所有的哈希函数对应的比特值均为1，其概率为（在m比较大的情况下可以近似）