布隆过滤器
布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
布隆过滤器 (Bloom Filter)是一种space efficient的概率型数据结构，在垃圾邮件过滤的黑白名单方法、爬虫(Crawler)的网址判重模块中等等经常被用到。哈希表也能用于判断元素是否在集合中，但是布隆过滤器只需要哈希表的1/8或1/4的空间复杂度就能完成同样的问题。布隆过滤器可以插入元素，但不可以删除已有元素。其中的元素越多，false positive rate(误报率)越大，但是false negative (漏报)是不可能的。
基本概念
如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为 O(n),O(log n),O(n/k)。
布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。
算法描述
-
一个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，但这种情况相对少见。
优点
相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数（O(k)）。另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
布隆过滤器可以表示全集，其它任何数据结构都不能；
缺点
但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。
另外，一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组，每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。
在降低误算率方面，有不少工作，使得出现了很多布隆过滤器的变种。
举例说明布隆过滤器的空间优势
先来一个结论：对于一个有1%误报率和一个最优k值的布隆过滤器来说，无论元素的类型及大小，每个元素只需要9.6 bits来存储。这个优点一部分继承自array的紧凑性，一部分来源于它的概率性。如果你认为1%的误报率太高，那么对每个元素每增加4.8 bits，我们就可将误报率降低为原来的1/10。add和query的时间复杂度都为O(k)，与集合中元素的多少无关，这是其他数据结构都不能完成的。k是hash函数的个数。
举例: 现有1亿个email的黑名单，元素的数量（即email列表）为 108。若采用布隆过滤器，取k=8（k为hash函数个数）。因为n为1亿，所以总共需要8*108。又因为在保证误判率低（后面解释）且k和m选取合适时，空间利用率为50%（后面会解释），所以总空间为
空间优势
所需空间比上述哈希结构或者数组小得多，并且误判率在万分之一以下。为什么可以这样算，可以看下面。
误判概率的证明和计算
该过程的详细说明来自于这个文章http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html，为了看懂求导过程，需要复习数学知识。
对某一特定bit位在一个元素由某特定hash function插入时没有被置位为1的概率为：
则k个hash function中没有一个对其置位的概率为：
现在考虑query阶段，若对应某个待query元素的k bits全部置位为1，则可判定其在集合中。因此将某元素误判的概率为：
，并且1/m 当m很大时趋近于0，所以
现在计算对于给定的m和n，k为何值时可以使得误判率最低。设误判率为k的函数为：
因为等式右边的底数上是函数，指数上也是函数，没有方法求这样组合函数的导数，只能取对数之后，变成乘法。我们有两个函数相乘的求导方法，求导的几个方法可以看参考资料，有很好的视频说明。
下面求最值，
红圈中的等式是把两边看成xln(x)这种形式得到的，和该函数的单调性相关。数学上能不能这么操作我还不太清楚。数学好的大神可以留言解释一下。
时误判率最低，此时误判率为：
可以看出若要使得误判率≤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的一些位数。此时的
从而使得P(error)最小时，我们注意到：
中的
，即
此概率为某bit位在插入n个元素后未被置位的概率。因此，想保持错误率低，布隆过滤器的空间使用率需为50%。
Neo中的布隆过滤器
上面的内容大部分抄袭http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html，原作者写的太好了，我只是加上一些我的理解，方便数学不好的道友理解。下面我们看看Neo中的Bloom Filter。
using System.Collections;
using System.Linq;
namespace Neo.Cryptography
{
public class BloomFilter
{
private readonly uint[] seeds;
private readonly BitArray bits;
public int K => seeds.Length;
public int M => bits.Length;
public uint Tweak { get; private set; }
public BloomFilter(int m, int k, uint nTweak, byte[] elements = null)
{
this.seeds = Enumerable.Range(0, k).Select(p => (uint)p * 0xFBA4C795 + nTweak).ToArray();
this.bits = elements == null ? new BitArray(m) : new BitArray(elements);
this.bits.Length = m;
this.Tweak = nTweak;
}
public void Add(byte[] element)
{
foreach (uint i in seeds.AsParallel().Select(s => element.Murmur32(s)))
bits.Set((int)(i % (uint)bits.Length), true);
}
public bool Check(byte[] element)
{
foreach (uint i in seeds.AsParallel().Select(s => element.Murmur32(s)))
if (!bits.Get((int)(i % (uint)bits.Length)))
return false;
return true;
}
public void GetBits(byte[] newBits)
{
bits.CopyTo(newBits, 0);
}
}
}
前面讲了这么多，代码竟然这么短，分析分析。
- 构造函数传入了m（多少位），k（hash函数种类），这个和我们前面分析根据p（错误率），和n（要插入的元素）来构造的思路不一样。所以Neo的这个版本应该是一个简化版本，输入的数据n应该是有范围的，具体的范围我们后面运行整个区块链的时候在观察，现在不知道n的个数有多大。
- hash函数使用了Murmur32，然后传入不同的seed模拟不同的hash函数，这个是可以的。
- 使用linq，函数式编程代码非常简洁，这也是C#的一个优势啊。
- add，check函数都很容易看懂，确实实现很简洁。
总结
Bloom Filter是牛逼的数据结构，因为有很多数学知识在里面，虽然代码不长，但是能看完这篇文章的人，会感受到代码之美。
参考资料
布隆过滤器
知乎里面关于e的讨论
An Intuitive Guide To Exponential Functions & e
Bloom Filters - the math
布隆过滤器 (Bloom Filter) 详解
What is MurmurHash3 seed parameter?
数学学习资料
各种字符串Hash函数
怎样在 Markdown 中使用数学公式
对数求导公式
导数法求函数最值
网友评论