一、基本概念：
布鲁姆过滤器(Bloom Filter )是布鲁姆(Burton Howard Bloom )于1970年提出的。 实际上，它由一个长二进制向量(位向量)和一系列随机映射函数组成，允许使用布隆过滤器查找元素是否位于集合中。 其优点是空间效率和查询时间远远超过一般算法。 缺点是错误识别率(假正例False positives，即Bloom Filter )报告某个要素存在于某个集合中，但实际上该要素不在集合中()，虽然难以删除，但错误的情况)，即假反例False negatives 如果某些元素是确定的，则bloom过滤器不适合“零错误”APP应用程序。 如果Bloom Filter可以接受低错误率的APP应用程序，则Bloom Filter通过少量错误大大节省了存储空间。
如果想确定一个元素是否在一个集合中，人们通常会想到的是保存所有元素，并通过比较来确定。 链表、树等数据结构就是这一思路。 但是，随着集合中元素的增加，所需的存储空间变大，搜索速度也变慢。 但是，世界上也有一种称为哈希表(sydzt表、Hash table )的数据结构。 可以使用Hash函数将元素映射到位数组中的点。 这样的话，只要看这一点是否为1就知道集合中是否有它。 这是布鲁姆过滤器的基本思想。
Hash面临的问题是冲突。 假设散列函数是随机的，如果位数组的长度为m个点，并且希望将冲突率降低到例如1%，则此哈希表只能包含m/100个元素。 这显然不称为空间有效(Space-efficient )。 解决方法也很简单，就是使用多个散列函数。 如果其中任何一个元素都不在集合中，那就一定没有(必须对应的位置都是1 )。 如果说有它们的话，没有那个元素的可能性很低。
bloom过滤器的几个重要参数：
插入集合的要素数n、BloomFilter位数组的长度m、散列函数k
优点
与其他数据结构相比，布隆过滤器在空间和时间方面有很大的优势。 模糊滤波器的存储区域和插入/查询时间都是常数，并且依赖于散列函数的数量k(o(k ) )。 另外，散列函数相互无关，便于并行实现。 布隆过滤器不需要保存元素本身，在对保密要求非常严格的情况下有利。
布隆过滤器可以表示全集，不能有其他任何数据结构；
和k和m一样，使用相同组的散列函数的两个模糊滤波器的交叉差运算可以使用位操作来执行。
缺点
布隆过滤器的缺点和优点一样明显。 误算率(False Positive )是其中之一。 随着进款元素数量的增加，误算率增加。 但是，如果元素数量过少，则使用哈希表就足够了。
此外，一般不能从光晕过滤器中删除元素。 很容易认为只要将位数组设置为整数数组，在每次插入元素时将相应的计数器加1，并在删除元素时减去计数器就可以了。 但是，安全地删除元素并不是那么简单。 首先，必须确保删除的元素位于光晕过滤器中。 这不能只靠这个过滤器来保证。 另外，计数器的倒带也是个问题。
二、算法描述
空bloom过滤器是具有m位的位阵列，每个位初始化为0。 然后，k个不同的散列函数被定义，其中每个随机地将元素散列为m个不同的位置之一。 在以下介绍中，n是元素数，m是布隆过滤器或sydzt表的位数，k是布隆过滤器的散列函数的个数。
为了添加一个元素，用k个混列函数获得bloom滤波器中的k个位，使该k个位位置为1。
为了查询一个元素，即为了确定它是否在集合中，在k个散列函数中得到k个比特的散列。 如果此k bits均为1，则此元素位于集合中； 如果其中一个位不为1，则此元素比不在集合中。 因为如果在add中，则对应的k个bits的位置已经是1。
不允许使用remove元素。 因为这样，对应的k个bits的位置将变为0，其中很可能有与其他元素对应的位。 因此，remove将引入假否定。 这是绝对不允许的。
在k较大的情况下，设计k个独立的散列函数是不现实的，也是困难的。 如果不同比特的相关性相对于输出范围宽的混列函数(例如MD5中产生的128比特的数目)小，则输出可被分成k个。 或者，k个不同的初始值(例如，0、1、2、k-1 )可以被组合在元素中，并且馈送可以给定一个散列函数以生成k个不同的随机数。
add元素过多时，即n/m过大时(n为元素数，m为bloom滤波器的bits数)，成为false positive过高的原因，在这种情况下需要重构滤波器，但这种情况比较少见
e="margin-left:10px;">二. 时间和空间上的优势当可以承受一些误报时，布隆过滤器比其它表示集合的数据结构有着很大的空间优势。例如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)。注意到这样一个sydzt表（bit array）只有在忽略collision并且只存储元素是否在其中的二进制信息时，才会获得空间和时间上的优势，而在此情况下，它就有效地称为了k=1的布隆过滤器。
而当考虑到collision时，对于有m个slot的bit array或者其他sydzt表（即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列表）为 ，相比于元素范围过于稀疏，而且还没有考虑到sydzt表中的collision问题。
若采用sydzt表，由于大多数采用open addressing来解决collision，而此时的search时间复杂度为 ：
即若sydzt表半满(n/m = 1/2)，则每次search需要probe 2次，因此在保证效率的情况下sydzt表的存储效率最好不超过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%（后面会解释），所以总空间为：
所需空间比上述sydzt结构小得多，并且误判率在万分之一以下。
四. 误判概率的证明和计算
假设布隆过滤器中的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)最小时，我们注意到：
中的 ，即
此概率为某bit位在插入n个元素后未被置位的概率。因此，想保持错误率低，布隆过滤器的空间使用率需为50%。
原文：https://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html