布隆过滤器

背景

之前读吴军《数学之美》的时候提到布隆过滤器,觉得蛮有意思的,所以总结一下。 在计算机中,判断一个元素是不是在一个集合中,通常是用hash来解决,这在数据量不大的时候是可以的,但是当数据量很大的时候存储空间就会爆炸。

一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件(email)提供商,总是需要过滤来自发送垃圾邮件的人(spamer)的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址,全世界少说也有几十亿个发垃圾邮件的地址,将他们都存起来则需要大量的网络服务器。如果用哈希表,每存储一亿个 email 地址, 就需要 1.6GB 的内存(用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹 googlechinablog.com/2006/08/blog-post.html,然后将这些信息指纹存入哈希表,由于哈希表的存储效率一般只有 50%,因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB, 即十六亿字节的内存)。因此存贮几十亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机,一般服务器是无法存储的。

解决的问题

大数据量的时候, 判断一个元素是否在一个集合中。

实现原理

布隆过滤器(Bloom Filter)的核心实现是一个超大的位数组和几个哈希函数。假设位数组的长度为m,哈希函数的个数为k

布隆过滤器 以上图为例,具体的操作流程:假设集合里面有3个元素{x, y, z},哈希函数的个数为3。首先将位数组进行初始化,将里面每个位都设置位0。

添加元素

对于集合里面的每一个元素,将元素依次通过3个哈希函数进行映射,每次映射都会产生一个哈希值,这个值对应位数组上面的一个点,然后将位数组对应的位置标记为1。

查询元素

查询W元素是否存在集合中的时候,同样的方法将W通过哈希映射到位数组上的3个点。如果3个点的其中有一个点不为1,则可以判断该元素一定不存在集合中。反之,如果3个点都为1,则该元素可能存在集合中。注意:此处不能判断该元素是否一定存在集合中,可能存在一定的误判率。可以从图中可以看到:假设某个元素通过映射对应下标为4,5,6这3个点。虽然这3个点都为1,但是很明显这3个点是不同元素经过哈希得到的位置,因此这种情况说明元素虽然不在集合中,也可能对应的都是1,这是误判率存在的原因。

移除集合中的元素

这个在布隆过滤器中是不允许的,理解原理我们就知道,如果将是1的位置重置成0会影响其他元素是不是在集合中的判断。对于关小黑屋再放出来这种需求,我们可以换一个思路,再加一个布隆过滤器————“被移除的元素”,当然现在公司都比较土豪,直接用redis存一个过期时间就可以,那就不在我们讨论之列了,布隆过滤器的初衷是用少许的误判来极大的节省空间。

错误率

假设 Hash 函数以等概率条件选择并设置 Bit Array 中的某一位,假定由每个 Hash 计算出需要设置的位(bit) 的位置是相互独立, m 是该位数组的大小,k 是 Hash 函数的个数. 位数组中某一特定的位在进行元素插入时的 Hash 操作中没有被置位的概率是:

在所有 k 次 Hash 操作后该位都没有被置 "1" 的概率是:

如果我们插入了 n 个元素,那么某一位仍然为 "0" 的概率是:

该位为 "1"的概率是:

检测某一元素是否在该集合中。标明某个元素是否在集合中所需的 k 个位置都按照如上的方法设置为 "1",但是该方法可能会使算法错误的认为某一原本不在集合中的元素却被检测为在该集合中(False Positives),该概率由以下公式确定:

如何使得错误率最小,对于给定的m和n,当 k=m/n * ln2 的时候取值最小。关系如下图所示:

应用

  • HBASE、Cassandra数据库中用来判断数据是不是在磁盘上
  • chrome用它来做钓鱼网站监测
  • 在比特币中用来判断是不是属于钱包
  • 垃圾邮件监测

参考资料

https://en.wikipedia.org/wiki/Bloom_filter http://blog.jobbole.com/113396/

原文发布于微信公众号 - Leetcode名企之路(DailyLeetCode)

原文发表时间:2018-10-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏蘑菇先生的技术笔记

探索c#之跳跃表(SkipList)

2878
来自专栏C/C++基础

认识UML类关系——依赖、关联、聚合、组合、泛化

在学习面向对象设计时,类关系涉及依赖、关联、聚合、组合和泛化这五种关系,耦合度依次递增。关于耦合度,可以简单地理解为当一个类发生变更时,对其他类造成的影响程度,...

1392
来自专栏小樱的经验随笔

深入理解树状数组

树状数组(Binary Indexed Tree(BIT), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之...

2687
来自专栏技术翻译

与机器学习算法相关的数据结构

我不认为机器学习中使用的数据结构与在软件开发的其他领域中使用的数据结构有很大的不同。然而,由于许多问题的规模和难度,掌握基本知识是必不可少的。

1943
来自专栏小红豆的数据分析

小蛇学python(18)pandas的数据聚合与分组计算

对数据集进行分组并对各组应用一个函数,这是数据分析工作的重要环节。在将数据集准备好之后,通常的任务就是计算分组统计或生成透视表。pandas提供了一个高效的gr...

2802
来自专栏生信技能树

(11)仿写bowtie-生信菜鸟团博客2周年精选文章集

然后仿写了bowtie,对我的编程技术提高非常有帮助。目录如下: 自己动手写bowtie第一讲:BWT算法详解并建立索引 自己动手写bowtie第二讲:优化索引...

3476
来自专栏大数据风控

R中的数据结构(Array,Factor,List,DataFrame)

1、R中的数据结构-Array #一维数组 x1 <- 1:5; x2 <- c(1,3,5,7,9) x3 <- array(c(2, 4, 6, 8, 10...

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

【专业技术】Android平台下使用OpenGL

存在问题: 安卓平台下如何使用opengl? 解决方案: 1、GLSurfaceView GLSurfaceView是Android应用程序中实现OpenGl画...

3926
来自专栏数据结构与算法

BZOJ4810: [Ynoi2017]由乃的玉米田(莫队+bitset)

Description 由乃在自己的农田边散步,她突然发现田里的一排玉米非常的不美。这排玉米一共有N株,它们的高度参差不齐。 由乃认为玉米田不美,所以她决定出...

3358
来自专栏吴伟祥

UML 类图介绍 转

Unified Modeling Language (UML)又称统一建模语言或标准建模语言,是始于1997年一个OMG标准,它是一个支持模型化和软件系统开发的...

871

扫码关注云+社区

领取腾讯云代金券