Title: 布隆过滤器(BloomFilter)原理 | 亿级数据过滤解决方案

1970 年，布隆先生提出了一种很优秀的过滤器算法，用来判断一个元素是否在集合中

「布隆过滤器算法」

故事开始→_→

先看本故事结构

就当前互联网环境来说，头部的互联网生态越来越往高并发、分布式的形态发展。举例来说，各大网页的黑名单系统，爬虫的重复率判断。这些场景越来越多。

举例来说，实时状态下可能会对超过百亿级别的 URL 需要进行判断是否符合规范或者存在于系统中，能否正常使用。

通常情况下，每个 URL 的大小为 64B（字节），那么就按照100亿的 URL 数量来看，大概需要640GB的内存容量【\(64 \times 100\text{亿}/1024^3\)】，对于当前线上服务器来说，… 这个值依然还是很大的！但如果利用布隆过滤器的优势，在没有失误率的情况下只需要100亿个比特，即：1.2GB，即使为了降低失误率，也不会超过几十GB的空间【失误率后面会谈到】

那么在这种情况下，利用布隆过滤器来解决的确是很优秀，优秀到维基百科这样说「它的优点是空间效率和查询时间都远远超过一般的算法」，空间复杂度和时间复杂度都远超一般的算法，布隆过滤器存储空间和插入/查询时间都是常数O(1)！注意：远超！！

看着来自各方面这么牛B 的吹嘘，咱们把布隆过滤器安排到方方面面，来具体看看它的原理是怎么样的…

维基百科的概念：布隆过滤器实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。基于这个解释，下面从

等方面系统性的说道说道…

【1】

主要作用：判断一个元素是否在集合中

这样的场景会有很多。会去判断，要查询的元素是否存在于集合当中。【该网站是否允许该用户登录、该网站共是否接受这样的 url 请求】

通常在查询的时候，一般会先从 cache 中进行查询，如果没有的话会直接到磁盘或者数据库查询，这样的方式看起来很合理，但是如果在中间再加一层布隆顾虑器，这样就会更加合理了！为什么？

假设要查询的一个元素，而该元素不存在

a. 如果没有 BloomFilter，从cache中查询完就会直接到数据库做查询了，这样带来的现象是“慢”，毕竟从库中查耗时是比较长的，很大程度上对服务的性能产生影响。

b. 中间存在 BloomFilter，从cache中查询完就会首先查询 BloomFilter，就会发现该元素不存在，就可以不往后面进行查询了，而 BloomFilter 的性能是极其优越的。这样，对于机器或者说服务性能避免了很大不必要的消耗。

就上图所示，假设元素不存在，如果没有布隆过滤器，就直接会查询【磁盘/数据库】，这样会带来很大不必要的性能消耗！

既然效率这么高，那到底是什么原因呢？

【2】

数据结构：二进制数组+hash算法

二进制数组

这个是最关键的一个数据结构，会将每一个元素经过 hash 算法映射到每一个二进制数组中去。

开篇讲到在时间复杂度和空间复杂度方面来说，都是在常数级别，这也归功于一个数据结构就是由比特位构成的数组，所以在空间这块是很有优势的。就拿一个URL 64B来说，对应比特位就是1，大概是 64*8:1 这个空间比例。

hash 算法

对于hash算法来说，应该是比较熟悉了，数据元素经过 hash 函数会映射到不同的数组中，如果发生冲突可以使用一些方法进行解决，比如说是拉链法解决。

hash 函数应用在 BloomFilter 中的时候，与一般的 hash 函数处理有区别的地方是：

a. BloomFilter 将值不会映射到一个地址，而是映射到对应的二进制数组位，然后将该数组为置为 1

b. BloomFilter 不会采用 hash 函数中常用的解决地址冲突的方法，而是会将同一个元素，经过几个 hash function 后，将对应二进制数组位置置为 1，后期如果进行查询的时候，只有经过hash函数后，几个位置同时为1，才可以判断该元素存在。

看下图：

按照图例，每个数据元素会经过 3 个不同的 hash function，然后对应到不同的二进制数组位，并且置为 1，这样一方面减小了冲突的概率，另外一方面会减小误差率。

当一个客户端查询过来，对于 URL1、URL2 和 URL3 在BloomFilter 中都是存在的，所以对这三个元素进行查询的时候，一定是可以查到的。

下面咱们试着用 URL1、URL4 和 URL5 进行举例说明：查找成功、查找不存在以及查找失误这三种真实存在的情况。【下图