目录

数据结构和算法 | 位图和布隆过滤器【高阶】

1. 怎么来的?

假设我们有 1 千万个整数,整数的范围是 1 到 1亿之间。如果给定一个整数,查询其是否在这 1 千万个整数之中?那么我们可以使用顺序查找、二分查找(有序前提下)、跳表查找、散列表查找、红黑树查找等等都可以。但是这些方法的话,都需要将这 1 千万个整数全都存储下来,有没有更加节省内存和时间的查询方法呢?这里其实也可以使用位图的方式,我们申请一个 1 亿个比特位的位图,之后将这 1 千万个数字使用位图来存储,比如针对数字 100,那么,我们就将第 100 个比特位设置为 1,表示 100 这个数字存在。查询时,我们查看第 100 个比特位的位置是否为 1,如果为 1 则表示 100 这个数字存在,否则不存在。通过比较可以发现,位图的使用空间大概在 12MB,而散列表等至少需要 40 MB。

但是,整数的范围如果很大,比如整数的范围在 1 到 10 亿之间,还是有 1 千万个整数,那么位图方式使用的空间会变大,需要大约 120 MB 的内存空间。显然,相比散列表等方式,消耗的内存空间,不降反增。

为了解决这个问题,我们可以使用布隆过滤器。布隆过滤器本身是基于位图的,是对位图的一种改进。布隆过滤器的做法是,仍然使用 1 亿个二进制位大小的位图,通过哈希函数,对数字进行哈希处理,让它落在 1 到 1 亿范围内。比如,我们将哈希函数设计成 f(x)=x%n, 其中 x 表示数字, n 表示位图的大小(1 亿),也就是数字跟位图大小进行取模。

但是,取模的方式肯定存在冲突。比如 1 和 1 亿零 1 这两个数字使用取模的哈希函数的话,是落在位图相同的地方。虽然,采用更复杂点、更随机点的哈希函数,会降低这种冲突的概率,但是也还是会存在冲突。那么布隆过滤器在位图和一个哈希函数的基础之上,多增加几个哈希函数,用多个哈希函数来定位一个数据

2. 怎么做的?

那么布隆过滤器到底是怎么用多个哈希函数来定位一个数据的呢?我们使用 K 个哈希函数,对同一个数字求哈希值,我们会得到 K 个不同的哈希值,分别记为 x1、x2、x3,…,xk。我们把这 K 个数字作为位图中的下标,将对应的 BitMap[x1]、BitMap[x2]、…、BitMap[xk],都设置为 1,也就相当于用 k 个二进制位来表示一个数字的存在。

当查询某个数字是否存在的时候,我们使用同样的 K 个哈希函数,对这个数字求哈希值,得到 y1、y2、…、yk。之后,根据这 K 个哈希值判断位图相应位置的值是否为 1,如果都为 1,那么则表示这个数字存在,如果有一个不为 1 则表示这个数字不存在。

这种方式虽然将冲突的概率降低了,你要想 K 个哈希值都一样的话,这个概率很低很低。但是这种方式容易误判,也就是某个数字经过布隆过滤器之后是存在的,那么这个数字不一定存在;但是某个数字经过布隆过滤器判断之后是不存在的,那么这个数字一定是不存在的。针对,这种情况,我们可以调整哈希函数的个数、位图的大小跟要存储数字的个数之间的比例,从而将这种误判的概率降到非常低。

https://img.dawnguo.cn/All/d0a3326ef0037f64102163209301aa1a.jpg

即使将哈希函数的个数、位图的大小跟要存储数字的个数之间的比例调整得很完美。当往布隆过滤器中不断添加新的数据时,位图中不是 true 的位置将会越来越少,从而也会导致误判率越高(这跟散列表是一个特性的)。因此,我们需要支持自动扩容的功能,当布隆过滤器中,数据个数与位图大小的比例超过某个阈值的时候,我们就重新申请一个位图。

  • 后面来的新数据,会被放到新的位图中。
  • 查询某个数据时,我们可以就需要查看多个位图(效率会有所降低)。

3. 用在哪里?

虽然布隆过滤器存在误判,但是布隆过滤器非常适合那些不需要 100% 准确、允许存在小概率误判的大规模场景。

  • 比如我们使用布隆过滤器来记录已经爬取的网页。那么假设一个网页没有被爬取过,但是却被当成爬取过了,那也不是什么特别大的事情,是可以容忍的。
  • 比如统计一个大型网站的每天的 UV 数,由于每天访问的用户数特别多。因此,也可以使用布隆过滤器对重复访问的用户进行去重。

Java 中的 BitSet 类就是一个位图。Redis 也提供了 BitMap 位图类。Google 的 Guava 工具包也提供了 BloomFilter 布隆过滤器。

bloom filter:False is always false. True is maybe true.

4. 与散列表相比

布隆过滤器用多个哈希函数对同一个网页链接进行处理,CPU 只需要将网页链接从内存中读取一次,进行多次哈希计算,理论上讲这组操作是 CPU 密集型。

而散列表的处理方式中,当将网页链接从内存中读取出来进行比较时,需要比较多个网页链接(存在散列冲突),进行字符串匹配。这个操作涉及到比较多的内存数据的读取,所以是内存密集型的。CPU 的处理速度是比内存访问更快速的,所以理论上来说布隆过滤器的方式更快速。

5. 总结

布隆过滤器是什么?其实就是位图这种数据结构 + 多个哈希函数,组成一种新的数据结构。这种组合方法和散列表的组成方法是类似的。

布隆过滤器存在误判的情况,也就是一个不存在的值可能会被判断为存在了(不存在的会一直判断为不存在)。因此,布隆过滤器适合用于那些对误判存在一定容忍度的场景。

巨人的肩膀

  1. 极客时间-《数据结构与算法》-王争老师