Bloom Filter 的基本原理和实现

导语: Bloom Filter 是由 Burton H. Bloom 在 1970 年提出的二进制向量数据结构,它具有很好的空间和时间效率,被用来检测一个元素是不是集合中的一个成员。

前言

Bloom Filter 是由 Burton H. Bloom 在 1970 年提出的二进制向量数据结构,它具有很好的空间和时间效率,被用来检测一个元素是不是集合中的一个成员。

Bloom Filter 最初的论文发表在ACM,名为《Space/Time Trade-offs in Hash Coding with Allowable Errors》,感兴趣可以下载阅读。本篇主要分享 Bloom Filter 的基本原理、代码实现以及误判率的计算,看过 BitMap 那篇文章的童鞋再看这一篇会十分简单。

Bloom Filter 也就是常说的布隆过滤器,后面就统一称为 BF。

一、原理

BF 可以高效地表示集合数据,它使用长度为 m 的位数组来存储集合信息,同时使用 k 个相互独立的哈希函数将数据映射到位数组空间。

直接上图,根据图来大致梳理一下算法流程。

  1. 初始化一个长度为m的位数组,并将所有元素置为0;
  2. 对于集合 S={a1, a2,…,an} 中的任一元素a,分别使用k个哈希函数对其计算: ,并将位数组中的第 位置为1;
  3. 对S中所有的成员执行同样的操作。

基本的原理就是这么多,看一下图中的例子就能明白了。比如现在要 dantezhao 用 BF 表示,我们会用两个哈希函数分别对 dantezhao 计算,计算结果分别是5和19, 然后对位数组中的第5位和第19位分别置1即可。

当查询 dantezhao 是否在集合的时候,只需使用同样的哈希函数计算,如果对应位数组的位都为1,则说明存在。只要有任意一位为0, 则说明不存在。

二、实现

具体的实现可以直接看代码,用 Python 写的一个简单的版本,总共也就20行左右。代码和 BitMap 的代码实现很接近,不同的是,哈希函数变成了多个。

三、误判率

BF 的基本原理说起来也很简单的,但是还有一些知识点需要关注一下。比如在 BF 中,会出现误判,就是某个成员本来不在集合中,但是会被判断成在集合中。为了把误判率控制在一个可以接受的范围,我们就需要适当地调配能够影响误判率的几个因素:集合大小n、哈希函数个数k和位数组大小m。

这三个影响因素中,m和n对于误判率的影响比较直观。

集合大小n:当其它条件固定的时候,集合大小n越大,则位数组中就会更多比例的位置被置为1,因此误判率会更大。

位数组大小m:同理,当其它条件固定时,位数组大小m的值越大,那么数组中剩余为0的位就会更多,因此误判率就会更小。

哈希函数的个数k:比较难分析,比如将m和n固定,使用的哈希函数越多,则位数组中会有更多比例的位置会被置为1,即增大的误判率,但是在查询时,如果哈希函数个数越多,则被误判的可能就越小。

然后该怎么找到3个因素的最佳取值呢?这里省略推导过程,直接给出结论。

如果给定 m 和 n,当 k 取以下值时,误判率 p 的值最小:

此时误判率 p 等于:

在实际应用中,更常见的需求是,已知集合大小n,并设定好误判率p,需要计算出该给 BF 分配多大内存合适,也就是要确认m的大小,可使用如下公式解决问题:

有了这三个公式,可以在实际应用中灵活地设置各种参数来合理使用BF。

四、 总结

传统 BF 只能添加元素,不能对元素计数,也无法删除元素。如果把底层数组的 bit 换成 int,就可以支持计数和删除动作。每次插入元素时,将对应的 k 个 int 加一;查询时,返回 k 个 int 的最小值;删除时,将对应的 k 个 int 减一。这就是BF的改进版:Couting Bloom Filter,后面再来专门分享。

原创声明,本文系作者授权云+社区-专栏发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

4 条评论
登录 后参与评论

相关文章

来自专栏海说

深入理解计算机系统(3.2)---数据格式、访问信息以及操作数指示符

  本文的内容其实可以成为汇编语言的基础,因为汇编语言大部分时候是在操作一些我们平时开发看不到的东西,因此本文的目的就是搞清楚,汇编语言都是在操作些什么东西。或...

732
来自专栏我的技术专栏

Socket编程实践(1) 基本概念

904
来自专栏PHP技术

PHP 代码规范简洁之道

原文出处: Scholer 1. 统一的编码规范 编码规范往简单说其实就是三个方面: 换行 空格 变量命名 放在 PHP 里面,还有一些附加的地方,比如关键字...

3576
来自专栏LuckQI

Java核心技术讲解学习三

1619
来自专栏進无尽的文章

如何优化冗长的条件语句

【1】尽量少用 else 尽量多用 if reture 的语法方式。 【2】字典的逻辑对应转化作用。 【3】用多态替代条件语句 【4】策略模式,继承重写,...

751
来自专栏小L的魔法馆

新疆大学ACM-ICPC程序设计竞赛五月月赛(同步赛)--B-杨老师的游戏

3929
来自专栏程序员互动联盟

【编程技巧】条条大路通罗马

问题:对于一个字节(8bit)的变量,求其二进制表示中“1”的个数,要求算法的执行效率尽可能地高。 分析与解法 大多数的读者都会有这样的反应:这个题目也太简单了...

35411
来自专栏程序员互动联盟

【答疑释惑】C语言里面栈和堆的区别

很多初学者朋友对C语言里面的堆和栈理解的不是太清楚,模模糊糊。他们到底有哪些区别呢?我认为主要从以下几根方面来了解他们的不同之处: 1,变量位置:栈和堆都是程...

35112
来自专栏更流畅、简洁的软件开发方式

面向对象的本质是什么?

  什么是面向对象的本质呢?   万物皆对象?No   抽象?No   复用?No   那到底是什么呢? 万物皆对象。问了几位网友,这是答复之一。看到了某个...

2609
来自专栏性能与架构

mysql 一个表装入内存需要多少空间?

一个表装入内存所需空间 = 表行数 * 一行的大小 这就是为什么在设计表字段的数据类型时要非常计较 例如 (1)对于固定长度列,应使用char而不是varcha...

2656

扫码关注云+社区