点击蓝色“五分钟学算法”关注我哟

加个“星标”,天天中午 12:15,一起学算法

五分钟小知识:布隆过滤器原理和应用分析

作者 | P.yh

来源 | 五分钟学算法

布隆过滤器出现的背景和要解决的问题

Wikipedia 上面提到布隆过滤器早在 1970 年就被提出来,很难想象在当时那个年代它的主要用途是什么,估计当时提出也是一个数据模型吧。

在互联网时代,每天会产生大量的数据,而且很多数据不是人产生的,而是机器产生的,就比如说是爬虫,每个网页被实际浏览的次数当中有一大半都是爬虫所致,那么这些数据怎么存储就是一个问题,有没有一个数据结构能够以很小的实际内存开销来存储这些数据呢?

这也就是布隆过滤器要来解决的问题,要用尽量小的存储空间存储数据,还要使数据的获取更加快速、便捷。

位图的概念

在说布隆过滤器之前还是讲讲位图,BitMap,这个东西,先来回答这么一个问题,如果这个时候你需要判断一个整数是否在一堆整数当中,你会使用什么数据结构?散列表吗?这个当然是可行的,但是好不好呢?

这里我的问题是只需要判断一个数在不在这一堆数里面,注意这里我要的结果其实只有两个,“在” 和 “不在”,如果说用散列把这些实际的数字全部存起来显然不是最理想的做法,我们只需要标记这个些数字存在即可,你可能会想到用 boolean 数组来做存储,还能不能继续优化?既然是 Binary 问题,那么一个 bit 是不是就够了,0 用来表示 false,1 用来表示 true,一个整数 4 个字节,32 bits,我们用一个 bit 就解决了,这样我们就把存储空间缩小了 32 倍。

这个就是位图的概念,其就是用 bit 来作为存储数据的单位,数据量小的话,其优势可能并不明显,但是对于海量数据优势就很明显了。

BitMap 其实就是一个整型数组,你也可以把其想象成 n * 32 的二维 bit 数组,但是这里还是有一个问题,上面我们讨论的仅仅是针对整数的存储是这样子,现实生活中,我们常常接触的会是字符串这类的数据,那这个该如何存储,我们该如何从字符串对应到实际的数组 index,这就要说到布隆过滤器了。

布隆过滤器原理

如果说要存储 1 亿个网站的 URL,你会使用什么样的数据结构?

我们需要方便对应查找,因此 query 的时间复杂度不能过高,在正常的,我们经常接触的数据结构中,你可能会想到的是散列表、平衡二叉树、跳表等数据结构。

我们来看看散列表,时间的话平均时间复杂度是 O(1),注意我这里说的是平均时间复杂度,哈希是会存在冲突的情况,这是你就要对比两个字符串上面的每个字符,完全符合条件才行,不符合还和继续找,继续对比;另外就是散列的存储空间,假如一个 URL 是 64 Bytes,那么 1 亿个 URL 大概是 6GB 的样子,但是对于散列来说的话这还没完,如果要尽量减少冲突的话,散列的实际 size 要比实际存储的数据的 size 要大,散列是这样,其他的数据结构,二叉树,跳表也都会有一些额外的开销,这些额外的开销都会导致实际存储当中不可避免的资源消耗。

上面讲到的散列表其实就是数组,我们之前提到的位图也是数组,但是我们说到了字符串如何存储的问题,这时我们就需要借助哈希函数了,哈希函数会根据输入参数的特性返回一个数组 index,我们直接去这个 index 上查看即可。

但是结合实际情况,我们有必要直接将整个 URL 存储起来吗?和位图的功能类似,布隆过滤器也仅仅是需要判断这个 URL 是不是在内存中,我们需要的答案是 “是” 或者 “不是”。

但是这里有个问题,只要是哈希函数都会有冲突的问题,假如说我们之前标记了一个 URL 存在,但是这个时候冲突产生了,一个本身不存在的 URL 我们通过哈希函数发现其存在,这个时候就会产生误判,但是你要知道的是,这个误判也只是单向的,对于不同的 URL,哈希函数可能返回相同的值,但是如果说返回的这个值是不存在 的话,那么表示一定是不存在的,如果是存在的话,可能是存在,因为这时有可能是相同哈希值的 URL 存在,并不是当前的 URL 存在,这是就是我们说的误判的情况,简而言之就是 “false always false,true maybe true”。

改进方法

上面我们提到布隆过滤器会存在一定的误判率,这个时候我们需要做的就是尽量降低这个误判率。我们主要从两个方向进行优化,一个是布隆过滤器的 size,还有一个就是哈希函数。

和散列表类似,这里也有一个装载因子的东西,它来保证实际的数据使用空间要低于总空间,这样的话才能使得冲突尽量的小;当然布隆过滤器是基于位图的,其占用的空间相比散列还是小的多的,一般实际空间和总空间 1:10 其实都不为过,这个比例绝大多数散列表是做不到的,特别是对于海量存储来说。因此这也就保证布隆过滤器的冲突发生几率要比散列表更加的小。

另外一个影响冲突的因素是哈希函数,其实仅仅通过一个哈希函数来判断的话误判率确实会有点高,我们可以用多个哈希函数判断,这就好像有了多层保障,你必须保证满足条件1,条件2,条件3,…,才能被判定是 true,虽然说略微增加了时间的消耗,但是这些消耗往往都是常数级别的,误判率得到了有效的降低。

所以,总的来说,增加布隆过滤器的大小,增加判断的哈希函数能够有效的降低误判率

实际应用

说了这么多,你可能会好奇布隆过滤器有啥用,只能返回一个 boolean 的值,有时还会出问题,在实际当中真的有用吗?

在工程当中我们往往不会追求一个完美的结果,我们仅仅需要的是一个近似解,这就给布隆过滤器的应用提供了很大的空间

在爬虫当中,机器需要知道这个网站是否被爬过,这里有上亿个网站,少爬一个其实没有多大区别,另外我们记录有多少用户访问了自己的 blog,这里也是近似,1000 个用户访问和 1002 个用户访问对我们影响并不大,我们只是看看这个大概的结果就行。

对于海量数据来说,布隆过滤器的用途还是真的挺广泛的,它不需要特别大的存储空间就可以让计算机去做几乎正确的事情,这也是其它的传统的数据结构所不能达到的

详细版介绍:

拜托,面试官别问我「布隆」了(修订补充版)

五分钟小知识:布隆过滤器原理和应用分析

有热门推荐?

1.程序员我们就必须承认:这个世界上,有很多问题,就是无解的

2.【GitHub我在 GitHub 上看到了一个丧心病狂的开源项目!

3.【算法动画:七分钟理解什么是KMP算法

4.【数据结构十大经典排序算法动画与解析,看我就够了!

五分钟小知识:布隆过滤器原理和应用分析

▼ 点击『阅读原文』解锁更多图解 LeetCode 题目