布隆过滤器

布隆过滤器是干什么的

假设有这样一个场景：大量请求要访问数据库。我们想要事先过滤一下哪些请求一定在数据库中查不到结果，对于这些请求，我们直接返回而不再查询数据库，以减缓数据库的压力。这时我们就可以用布隆过滤器来过滤出哪些请求一定不能查出记录。

图1 布隆过滤器用于减轻数据库压力

注意：布隆过滤器中查不到的记录，肯定不存在于数据库。但布隆过滤器中能查到的数据并不一定真的在数据库。后面会讲到为什么会这样。

布隆过滤器的数据结构

布隆过滤器由一组hash函数和一个bit数组组成。当我们向布隆过滤器中添加元素时，需要使用一组hash函数求得一组hash值，每个hash值作为index去队形bit数组里的一位，并将这一位的值设置为1。当我们查询某个元素是否存在时，也是用这一组hash函数求得一组hash值，并以hash值作为index去访问bit数组，如果每个hash值所指示的index位置都是1，则表名该元素可能存在，否则该元素一定不存在。

例如我们有一个布隆过滤器：三个hash函数和一个8位的bit数组。下图展示了我们如何将元素“baidu”添加到布隆过滤器中：

图2 布隆过滤器新增元素示意图

那么我们再插入一个元素“tencent”，布隆过滤器的工作原理如下图所示：

图3 再次插入元素后的布隆过滤器

这时候，我们想查询一下元素“alibaba”是否在布隆过滤器里，假设经过计算我们得到：
hash1("alibaba") = 1
hash2("alibaba") = 5
hash3("alibaba") = 6
这时，我们发现这三个位置的值都是1，但是“alibaba”实际上并不存在于布隆过滤器。这就是为什么能够查到的元素也只是“可能存在”的原因。这个问题的原因其实很容易看出来，就是因为hash值之间存在冲突。

图4 布隆过滤器查找过程

布隆过滤器的问题

从上面介绍的布隆过滤器的插入和查询过程可以看出，如果bit数组太小，那么当插入的元素太多时就会使得bit数组的值全部等于1。后面再查询一个元素是否在布隆过滤器中时肯定会返回“可能存在”，那么过滤器就失去了过滤作用。
为了克服这个问题，一方面我们应该增大bit数组的大小；另一方面，还要设计好hash函数使得元素可以均匀的分散到bit数组上，减小冲突。

总结

• 作用：过滤不存在的值
• 结构：一组hash函数和一个足够大的bit数组
• 插入：元素哈希值作为bit数组的index，然后将该位置设置为1
• 查询：元素哈希值作为bit数组的index，全1表示“可能存在”，否则“一定不存在”
• 问题：bit数组太小导致冲突太多