布隆过滤器 (Bloom Filter)是由Burton Howard Bloom于1970年提出，它是⼀种space efficient的概率型数据结构，⽤于判断⼀个元素是否在集合中。在垃圾邮件过滤的⿊⽩名单⽅法、爬⾍(Crawler)的⽹址判重模块中等等经常被⽤到。哈希表也能⽤于判断元素是否在集合中，但是布隆过滤器只需要哈希表的1/8或1/4的空间复杂度就能完成同样的问题。布隆过滤器可以插⼊元素，但不可以删除已有元素。其中的元素越多，false positive rate(误报率)越⼤，但是false negative (漏报)是不可能的。 本⽂将详解布隆过滤器的相关算法和参数设计，在此之前希望⼤家可以先通过⾕歌⿊板报的来得到些基础知识。
⼀. 算法描述
⼀个empty bloom filter是⼀个有m bits的bit array，每⼀个bit位都初始化为0。并且定义有k个不同的hash function，每个都以uniform random distribution将元素hash到m个不同位置中的⼀个。在下⾯的介绍中n为元素数，m为布隆过滤器或哈希表的slot数，k 为布隆过滤器重hash function数。
李瑞海
为了add⼀个元素，⽤k个hash function将它hash得到bloom filter中k个bit位，将这k个bit位置1。
为了query⼀个元素，即判断它是否在集合中，⽤k个hash function将它hash得到k个bit位。若这k bits全
为1，则此元素在集合中；若其中任⼀位不为1，则此元素⽐不在集合中（因为如果在，则在add时已经把对应的k个bits位置为1）。
不允许remove元素，因为那样的话会把相应的k个bits位置为0，⽽其中很有可能有其他元素对应的位。因此remove会引⼊false negative，这是绝对不被允许的。
当k很⼤时，设计k个独⽴的hash function是不现实并且困难的。对于⼀个输出范围很⼤的hash function（例如MD5产⽣的128 bits 数），如果不同bit位的相关性很⼩，则可把此输出分割为k份。或者可将k个不同的初始值（例如0,1,2, … ,k-1）结合元素，feed给⼀个hash function从⽽产⽣k个不同的数。
当add的元素过多时，即n/m过⼤时（n是元素数，m是bloom filter的bits数），会导致false positive过⾼，此时就需要重新组建filter，但这种情况相对少见。
⼆. 时间和空间上的优势
当可以承受⼀些误报时，布隆过滤器⽐其它表⽰集合的数据结构有着很⼤的空间优势。例如self-balance BST, tries, hash table或者array, chain，它们中⼤多数⾄少都要存储元素本⾝，对于⼩整数需要少量的bits，对于字符串则需要任意多的bits（tries是个例外，因为对于有相同prefixes的元素可以共
享存储空间）；⽽chain结构还需要为存储指针付出额外的代价。对于⼀个有1%误报率和⼀个最优k值的布隆过滤器来说，⽆论元素的类型及⼤⼩，每个元素只需要9.6 bits来存储。这个优点⼀部分继承⾃array的紧凑性，⼀部分来源于它的概率性。如果你认为1%的误报率太⾼，那么对每个元素每增加4.8 bits，我们就可将误报率降低为原来的1/10。add和query的时间复杂度都为O(k)，与集合中元素的多少⽆关，这是其他数据结构都不能完成的。
如果可能元素范围不是很⼤，并且⼤多数都在集合中，则使⽤确定性的bit array远远胜过使⽤布隆过滤器。因为bit array对于每个可能的元素空间上只需要1 bit，add和query的时间复杂度只有O(1)。注意到这样⼀个哈希表（bit array）只有在忽略collision并且只存储元素是否在其中的⼆进制信息时，才会获得空间和时间上的优势，⽽在此情况下，它就有效地称为了k=1的布隆过滤器。
⽽当考虑到collision时，对于有m个slot的bit array或者其他哈希表（即k=1的布隆过滤器），如果想要保证1%的误判率，则这个bit array只能存储m/100个元素，因⽽有⼤量的空间被浪费，同时也会使得空间复杂度急剧上升，这显然不是space efficient的。解决的⽅法很简单，使⽤k>1的布隆过滤器，即k个hash function将每个元素改为对应于k个bits，因为误判度会降低很多，并且如果参数k和m选取得好，⼀半的m可被置为为1，这充分说明了布隆过滤器的space efficient性。
辽宁省新闻出版学校三. 举例说明
以垃圾邮件过滤中⿊⽩名单为例：现有1亿个email的⿊名单，每个都拥有8 bytes的指纹信息，则可能的元素范围为 ，对于bit array来说是根本不可能的范围，⽽且元素的数量（即email列表）为 ，相⽐于元素范围过于稀疏，⽽且还没有考虑到哈希表中的collision问题。
若采⽤哈希表，由于⼤多数采⽤open addressing来解决collision，⽽此时的search时间复杂度为 ：
即若哈希表半满(n/m = 1/2)，则每次search需要probe 2次，因此在保证效率的情况下哈希表的存储效率最好不超过50%。此时每个元素占8 bytes，总空间为：
若采⽤Perfect hashing（这⾥可以采⽤Perfect hashing是因为主要操作是search/query，⽽并不是add和remove），虽然保证
worst-case也只有⼀次probe，但是空间利⽤率更低，⼀般情况下为50%，worst-case时有不到⼀半的概率为25%。
若采⽤布隆过滤器，取k=8。因为n为1亿，所以总共需要 被置位为1，⼜因为在保证误判率低且k和m选取合适时，空间利⽤率为
50%（后⾯会解释），所以总空间为：
所需空间⽐上述哈希结构⼩得多，并且误判率在万分之⼀以下。
四. 误判概率的证明和计算
假设布隆过滤器中的hash function满⾜simple uniform hashing假设：每个元素都等概率地hash到m个slot中的任何⼀个，与其它元素被hash到哪个slot⽆关。若m为bit数，则对某⼀特定bit位在⼀个元素由某特定hash function插⼊时没有被置位为1的概率为：
则k个hash function中没有⼀个对其置位的概率为：
如果插⼊了n个元素，但都未将其置位的概率为：
则此位被置位的概率为：
现在考虑query阶段，若对应某个待query元素的k bits全部置位为1，则可判定其在集合中。因此将某元素误判的概率为：
由于 ，并且 当m很⼤时趋近于0，所以
从上式中可以看出，当m增⼤或n减⼩时，都会使得误判率减⼩，这也符合直觉。
现在计算对于给定的m和n，k为何值时可以使得误判率最低。设误判率为k的函数为：
羟甲基丙烯酰胺设 ， 则简化为
，两边取对数
, 两边对k求导
下⾯求最值
因此，即当 时误判率最低，此时误判率为：黄金分割率
可以看出若要使得误判率≤1/2，则：
这说明了若想保持某固定误判率不变，布隆过滤器的bit数m与被add的元素数n应该是线性同步增加的。
五. 设计和应⽤布隆过滤器的⽅法
应⽤时⾸先要先由⽤户决定要add的元素数n和希望的误差率P。这也是⼀个设计完整的布隆过滤器需要⽤户输⼊的仅有的两个参数，之后的所有参数将由系统计算，并由此建⽴布隆过滤器。
系统⾸先要计算需要的内存⼤⼩m bits:
再由m，n得到hash function的个数：
⾄此系统所需的参数已经备齐，接下来add n个元素⾄布隆过滤器中，再进⾏query。
根据公式，当k最优时：
因此可验证当P=1%时，存储每个元素需要9.6 bits：
⽽每当想将误判率降低为原来的1/10，则存储每个元素需要增加4.8 bits：
猴王出世教学设计这⾥需要特别注意的是，9.6 bits/element不仅包含了被置为1的k位，还把包含了没有被置为1的⼀些位数。此时的
才是每个元素对应的为1的bit位数。
从⽽使得P(error)最⼩时，我们注意到：
ising模型中的 ，即
此概率为某bit位在插⼊n个元素后未被置位的概率。因此，想保持错误率低，布隆过滤器的空间使⽤率需为50%。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议