布隆过滤器到底是什么东西？它有什么用

一、问题解析

昨天，一个工作了 6 年的粉丝私聊我，说最近面试被问到布隆过滤器没回答出来。然后在网上找了一堆资料也没有说清楚，想让我帮他讲解一下，今天正好有空，给大家分享一下布隆过滤器。

在解释布隆过滤器之前，我先问大家一个问题，如果我想判断一个元素是否存在某个集合里面怎么做？一般的解决方案是先把所有元素保存起来，然后通过循环比较来确定。但是如果我们有几千万甚至上亿的数据的时候｛如图｝，虽然可以通过不同的数据结构来优化数据检索的时间复杂度，但是整体的效率依然很慢，而且会占用非常多的内存空间，这个问题该怎么解决呢？

这个时候，位图就派上了用场｛如图｝BitMap 的基本原理就是用一个 bit 位来存储当前数据是否存在的状态值，也就是把一个数据通过 hash 运算取模后落在 bit 位组成的数组中，通过 1 对该位置进行标记。这种方式适用于大规模数据，但数据状态又不是很多的情况，通常是用来判断某个数据

存不存在的。

对了，我最近整理了一份 80W 字的面试文档，马上就要金三银四了，趁现在可以多花点时间准备一下，找份好工作。布隆过滤器就是在位图的基础上做的一个优化设计｛如图｝。它的原理是，当一个元素被加入集合时，通过 K 个散列函数将这个元素映射成一个位数组中的 K 个点，把它们置为 1。检索的时候，使用同样的方式去映射，只要看到每个映射的位置的值是不是 1，就可以

大概知道该元素是否存在集合中了。如果这些点有任何一个 0，则被检查的元素一定不在；如果都是 1，则被检查的元素很可能存在。