布隆过滤器(Bloom Filter)入门介绍

布隆过滤器(Bloom Filter)是一个数据结构,由布隆(Burton Howard Bloom)于1970年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。

布隆过滤器可以用于高效的检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远优于一般的算法,缺点是有一定的误识别率,而且难以删除(一般不支持,需要额外的实现)。

布隆过滤器之所以高效,因为它是一个概率数据结构,它能确认元素肯定不在集合中,或者元素可能在集合中。之所以说是可能,是因为它有一定的误识别率,使得无法100%确定元素一定在集合中。

基本原理

布隆过滤器的基本工作原理并不复杂,大致如下:

首先,建立一个二进制向量,并将所有位设置为0。

然后,选定K个散列函数,用于对元素进行K次散列,计算向量的位下标。

添加元素

当添加一个元素到集合中时,通过K个散列函数分别作用于元素,生成K个值作为下标,并对向量的相应位设置为1。

检查元素

如果要检查一个元素是否存在集合中,用同样的散列方法,生成K个下标,并检查向量的相应位是否全部是1。如果全为1,则该元素很可能在集合中;否则(只要有1个或以上的位为0),该元素肯定不在集合中。

这就是布隆过滤器的基本思想。

image

一个简单的例子

假设有一个布隆过滤器,容量是15位,使用2个哈希函数。

image

添加一个字符串a,2次哈希得到下标为4和10,将4和10对应的位由0标记为1。

image

然后添加一个字符串b,2次哈希得到下标为11和11,将11对应的位由0标记为1。

image

再添加一个字符串c,2次哈希得到下标为11和12,将11和12对应的位由0标记为1。

image

最后,添加一个字符串sam,2次哈希得到下标为0和7,将0和7对应的位由0标记为1。

image

上面,我们添加了4个字符串,每个字符串分别进行2次哈希,对应的2个位标记为1,最终被标记为1的共有6位而不是8位。

这说明,不同的元素,哈希后得到的位置是可能出现重叠的。如果元素越多,出现重叠的概率会更高。如果有2个元素出现重叠的位置,我们是无法判断任一元素一定在集合中的。

如果要检查一下元素是否存在集合中,只需要以相同的方法,进行2次哈希,将得到的2个下标在布隆过滤器中的相应位进行查找。如果对应的2位不是全部为1,则该元素肯定不在集合中。如果对应的2位全部为1,则说明该元素可能在集合中,也可能不存在。

例如,检查字符串b是否存在集合中,哈希得到的2个下标都为11。检查发现,11对应的位为1。但是,这并不能说明b一定在集合中。这是因为,字符串c哈希后的下标也包含11,有可能只是字符串c在集合中,而b却不存在,这就是造成了误识别,也称为假阳性。

再检查字符串foo,哈希得到的下标分别为8和13,对应的位都为0。因此,字符串foo肯定不在集合中。

参考

https://en.wikipedia.org/wiki/Bloom_filter

https://zh.wikipedia.org/zh-cn/布隆过滤器

https://llimllib.github.io/bloomfilter-tutorial


---转载本站文章请注明作者和出处 二进制之路(binarylife.icu),请勿用于任何商业用途---

留下评论