布隆过滤器(Bloom Filter)详解

Bloom Filter算法相似一个hash set,用来判别某个元素(key)是否在某个调集中。
和一般的hash set不同的是,这个算法无需存储key的值,关于每个key,只需求k个比特位,每个存储一个标志,用来判别key是否在调集中。

算法履行进程

1. 首要需求k个hash函数,每个函数能够把key散列成为1个整数
2. 初始化时,需求一个长度为n比特的数组,每个比特位初始化为0
3. 某个key参加调集时,用k个hash函数计算出k个散列值,并把数组中对应的比特方位为1
4. 判别某个key是否在调集时,用k个hash函数计算出k个散列值,并查询数组中对应的比特位,假如一切的比特位都是1,以为在调集中。

长处:

不需求存储key,节约空间

缺陷:

1. 算法判别key在调集中时,有必定的概率key其实不在调集中
2. 无法删去

典型的运用场景:

某些存储体系的规划中,会存在空查询缺陷:当查询一个不存在的key时,需求拜访慢设备,导致功率低下。
比方一个前端页面的缓存体系,或许这样规划:先查询某个页面在本地是否存在,假如存在就直接回来,假如不存在,就从后端获取。可是当频频从缓存体系查询一个页面时,缓存体系将会频频恳求后端,把压力导入后端。

这是只需添加一个Bloom Filter算法的服务,后端刺进一个key时,在这个服务中设置一次
需求查询后端时,先判别key在后端是否存在,这样就能防止后端的压力。



 

 

 

 

布隆过滤器(Bloom Filter)是由布隆(Burton Howard Bloom)在1970年提出的。它实际上是由一个很长的二进制向量和一系列随机映射函数组成,布隆过滤器能够用于检索一个元素是否在一个调集中。它的长处是空间功率和查询时刻都远远超越一般的算法,缺陷是有必定的误辨认率(假正例False positives,即Bloom Filter陈述某一元素存在于某调集中,可是实际上该元素并不在调集中)和删去困难,可是没有辨认过错的景象(即假反例False negatives,假如某个元素确实没有在该调集中,那么Bloom Filter 是不会陈述该元素存在于调集中的,所以不会漏报)。

在日常日子中,包含在规划计算机软件时,咱们常常要判别一个元素是否在一个调集中。比方在字处理软件中,需求查看一个英语单词是否拼写正确(也便是要判别 它是否在已知的字典中);在 FBI,一个嫌疑人的姓名是否已经在嫌疑名单上;在网络爬虫里,一个网址是否被拜访过等等。最直接的办法便是将调集中悉数的元素存在计算机中,遇到一个新 元素时,将它和调集中的元素直接比较即可。一般来讲,计算机中的调集是用哈希表(hash table)来存储的。它的长处是快速精确,缺陷是费存储空间。当调集比较小时,这个问题不显着,可是当调集巨大时,哈希表存储功率低的问题就显现出来 了。比方说,一个象 Yahoo,Hotmail 和 Gmai 那样的大众电子邮件(email)提供商,总是需求过滤来自发送垃圾邮件的人(spamer)的垃圾邮件。一个办法便是记录下那些发垃圾邮件的 email 地址。因为那些发送者不停地在注册新的地址,全世界少说也有几十亿个发垃圾邮件的地址,将他们都存起来则需求许多的网络服务器。假如用哈希表,每存储一亿 个 email 地址, 就需求 1.6GB 的内存(用哈希表完成的具体办法是将每一个 email 地址对应成一个八字节的信息指纹(详见:, 然后将这些信息指纹存入哈希表,因为哈希表的存储功率一般只需 50%,因而一个 email 地址需求占用十六个字节。一亿个地址大约要 1.6GB, 即十六亿字节的内存)。因而存贮几十亿个邮件地址或许需求上百 GB 的内存。除非是超级计算机,一般服务器是无法存储的。

基本概念

假如想判别一个元素是不是在一个调集里,一般想到的是将一切元素保存起来,然后经过比较确认。链表,树等等数据结构都是这种思路. 可是跟着调集中元素的添加,咱们需求的存储空间越来越大,检索速度也越来越慢。不过世界上还有一种叫作散列表(又名哈希表,Hash table)的数据结构。它能够经过一个Hash函数将一个元素映射成一个位阵列(Bit Array)中的一个点。这样一来,咱们只需看看这个点是不是 1 就知道能够调集中有没有它了。这便是布隆过滤器的基本思想。

Hash面对的问题便是抵触。假定 Hash 函数是杰出的,假如咱们的位阵列长度为 m 个点,那么假如咱们想将抵触率降低到例如 1%, 这个散列表就只能包容 m/100 个元素。显着这就不叫空间有用了(Space-efficient)。解决办法也简略,便是运用多个 Hash,假如它们有一个说元素不在调集中,那必定就不在。假如它们都说在,尽管也有必定或许性它们在扯谎,不过直觉上判别这种工作的概率是比较低的。

长处

比较于其它的数据结构,布隆过滤器在空间和时刻方面都有巨大的优势。布隆过滤器存储空间和刺进/查询时刻都是常数。别的, Hash 函数彼此之间没有联系,便利由硬件并行完成。布隆过滤器不需求存储元素自身,在某些对保密要求十分严厉的场合有优势。

布隆过滤器能够标明全集,其它任何数据结构都不能;

k 和 m 相同,运用同一组 Hash 函数的两个布隆过滤器的交并差运算能够运用位操作进行。

缺陷

可是布隆过滤器的缺陷和长处相同显着。误算率(False Positive)是其中之一。跟着存入的元素数量添加,误算率随之添加。可是假如元素数量太少,则运用散列表足矣。

别的,一般状况下不能从布隆过滤器中删去元素. 咱们很简略想到把位列阵变成整数数组,每刺进一个元素相应的计数器加1, 这样删去元素时将计数器减掉就能够了。但是要确保安全的删去元素并非如此简略。首要咱们有必要确保删去的元素确实在布隆过滤器里边. 这一点单凭这个过滤器是无法确保的。别的计数器缭绕也会形成问题。

False positives 概率推导

假定 Hash 函数以等概率条件挑选并设置 Bit Array 中的某一位,m 是该位数组的巨细,k 是 Hash 函数的个数,那么位数组中某一特定的位在进行元素刺进时的 Hash 操作中没有被置位的概率是:

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

假如咱们刺进了 n 个元素,那么某一位依然为 "0" 的概率是:

因而该位为 "1"的概率是:

现在检测某一元素是否在该调集中。标明某个元素是否在调集中所需的 k 个方位都依照如上的办法设置为 "1",可是该办法或许会使算法过错的以为某一本来不在调集中的元素却被检测为在该调集中(False Positives),该概率由以下公式确认:

其实上述结果是在假定由每个 Hash 计算出需求设置的位(bit) 的方位是彼此独立为条件计算出来的,不难看出,跟着 m (位数组巨细)的添加,假正例(False Positives)的概率会下降,一起跟着刺进元素个数 n 的添加,False Positives的概率又会上升,关于给定的m,n,怎么挑选Hash函数个数 k 由以下公式确认:

此刻False Positives的概率为:

而关于给定的False Positives概率 p,怎么挑选最优的位数组巨细 m 呢,

上式标明,位数组的巨细最好与刺进元素的个数成线性联系,关于给定的 m,n,k,假正例概率最大为:

 

下图是布隆过滤器假正例概率 p 与位数组巨细 m 和调集中刺进元素个数 n 的联系图,假定 Hash 函数个数选取最优数目:

 

Bloom Filter 用例

Google 闻名的分布式数据库 Bigtable 运用了布隆过滤器来查找不存在的行或列,以削减磁盘查找的IO次数。

Squid 网页署理缓存服务器在cache digests中运用了也布隆过滤器。

Venti 文档存储体系也采用布隆过滤器来检测从前存储的数据。

SPIN 模型检测器也运用布隆过滤器在大规模验证问题时盯梢可达状况空间。

Google Chrome阅读器运用了布隆过滤器加速安全阅读服务。

在许多Key-Value体系中也运用了布隆过滤器来加速查询进程,如 Hbase,Accumulo,Leveldb,一般来说,Value 保存在磁盘中,拜访磁盘需求花费许多时刻,但是运用布隆过滤器能够快速判别某个Key对应的Value是否存在,因而能够防止许多不必要的磁盘IO操作,仅仅引进布隆过滤器会带来必定的内存耗费,下图是在Key-Value体系中布隆过滤器的典型运用:

上一篇:跟着动画学TCP三次握手和四次挥手
下一篇:最终一页

PythonTab微信大众号:

Python技能交流合作群 ( 请勿加多个群 ):

群1: 87464755

群2: 333646237

群3: 318130924

群4: 385100854