一、什么是布隆过滤器

在数学之美中，有一章是关于布隆过滤器的讲解，内容如下。

在字处理软件中，一个英语单词是否拼写正确；在FBI中，一个嫌疑人的名字是否在嫌疑名单上；在网络爬虫里，一个网址是否已访问过，等等。最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素之间比较。一般来说，计算机中的集合是用哈希表存储的。好处是快速准确，缺点是耗费存储空间。当集合很小时，这个问题不明显，当集合规模巨大时，哈希表存储效率低的问题就显现出来了。如果使用哈希表存储Email地址，每一亿个Email地址，就需要1.6GB的内存。为了解决哈希表的这个问题，就需要一种叫布隆过滤器的数学工具。所以，布隆过滤器是个数据工具。他的大小只需要哈希表1/8到1/4的大小就能解决同样的问题。

因此，布隆过滤器是一种数学工具。

二、布隆过滤器的原理

布隆过滤器实际上是一个很长的二进制向量和一系列随机映射函数。我们通过电子邮件地址的例子来进行说明。

如果需要存储一亿个电子邮件地址，先建立一个16亿二进制(比特)，即2亿字节的向量，然后将这16亿个二进制位全部清零。再对每一个电子邮件的地址X，用8个不同的随机数产生器(F1, F2, F3 ..., F8)产生8个信息指纹(f1, f2, f3....., f8)。再用一个随机数产生器G把这8个位置的二进制全部设置为1。对这一亿个电子邮件地址都进行这样的处理后，就产生了一个针对布隆过滤器。

当我们需要看一个可疑地址Y是否在黑名单中时，用8个相同的随机数产生器(F1, F2, F3, ..., F8)对这个地址产生8个信息指纹s1, s2, s3, ... s8，然后将这8个指纹对应到布隆过滤器的8个二进制位，分别是t1, t2, ...., t8。如果Y在黑名单中，那么t1, t2, ...., t8对应的8个二进制数肯定是1。

三、布隆过滤器的优缺点

优点： 快速，省空间

缺点： 存在一定的误识别率

四、leveldb中的布隆过滤器

因为还没有实际使用过leveldb，所以，个人在这里觉得，leveldb的布隆过滤器是在数据库查找时，更快，更省空间。后面具体使用leveldb时，再来理解bloom。下面一起来看代码分析

BloomFilterPolicy是继承自FilterPolicy的，关于FilterPolicy在后面的学习中再详述，本节仅讨论Bloom.cc。

1. BloomFilterPolicy类

1.1 BloomFilterPolicy

构造函数，主要是进行初始化，然后确定需要多少个哈希函数

explicitBloomFilterPolicy(intbits_per_key):bits_per_key_(bits_per_key){//Weintentionallyrounddowntoreduceprobingcostalittlebitk_=static_cast<size_t>(bits_per_key*0.69);//0.69=~ln(2)if(k_<1)k_=1;if(k_>30)k_=30;}

1.2 Name

返回bloom过滤器名称

virtualconstchar*Name()const{return"leveldb.BuiltinBloomFilter2";}

1.3CreateFilter

创建BloomFilter，keys是需要存入的key， n是需要存入的个数， dst是BloomFilter的结果

leveldb在最终的BloomFilter上加了一个k_，表示使用了多少个哈希函数，这样在查询时，就可以直接知道用来多少个哈希函数，而不需要重新用一个变量来记录用来多少个哈希函数。

virtualvoidCreateFilter(constSlice*keys,intn,std::string*dst)const{//Computebloomfiltersize(inbothbitsandbytes)size_tbits=n*bits_per_key_;//所有需要创建的key的总位数//Forsmalln,wecanseeaveryhighfalsepositiverate.Fixit//byenforcingaminimumbloomfilterlength.if(bits<64)bits=64;//最小需要64位来保存//这两行主要进行字节对齐size_tbytes=(bits+7)/8;//对所占的内存进行8字节对齐bits=bytes*8;//总共需要的位数constsize_tinit_size=dst->size();dst->resize(init_size+bytes,0);//将所有的位都置为0dst->push_back(static_cast<char>(k_));//Remember#ofprobesinfilter，将总的哈希函数个数存入最后char*array=&(*dst)[init_size];for(inti=0;i<n;i++){//Usedouble-hashingtogenerateasequenceofhashvalues.//Seeanalysisin[Kirsch,Mitzenmacher2006].uint32_th=BloomHash(keys[i]);constuint32_tdelta=(h>>17)|(h<<15);//Rotateright17bitsfor(size_tj=0;j<k_;j++){constuint32_tbitpos=h%bits;//获取第一个数在bits中的位置//将数据存入array中/*bitpos/8计算元素在第几个字节；(1<<(bitpos%8))计算元素在字节的第几位；例如：bitpos的值为3，则元素在第一个字节的第三位上，那么这位上应该赋值为1。bitpos的值为11，则元素在第二个字节的第三位上，那么这位上应该赋值为1。为什么要用|=运算，因为字节位上的值可能为1，那么新值赋值，还需要保留原来的值。*/array[bitpos/8]|=(1<<(bitpos%8));h+=delta;}}}

1.4 KeyMayMatch

查询是否存在函数， key是需要查询的， bloom_filter则是需要使用对比的过滤器

virtualboolKeyMayMatch(constSlice&key,constSlice&bloom_filter)const{constsize_tlen=bloom_filter.size();if(len<2)returnfalse;constchar*array=bloom_filter.data();constsize_tbits=(len-1)*8;//Usetheencodedksothatwecanreadfiltersgeneratedby//bloomfilterscreatedusingdifferentparameters.constsize_tk=array[len-1];//这里是使用过滤器尾部保存的哈希函数个数if(k>30){//保留短布隆过滤器//Reservedforpotentiallynewencodingsforshortbloomfilters.//Consideritamatch.returntrue;}uint32_th=BloomHash(key);constuint32_tdelta=(h>>17)|(h<<15);//Rotateright17bitsfor(size_tj=0;j<k;j++){constuint32_tbitpos=h%bits;//查找if((array[bitpos/8]&(1<<(bitpos%8)))==0)returnfalse;//判断是否存在布隆过滤器中h+=delta;}returntrue;}

以上就是leveldb中bloom的主要代码与分析，可以考虑，以后在自己写代码时，如果存在有大量数据需要查询，读取时，可以先通过布隆过滤器来看是否存在，然后再进行读取。而且布隆过滤器是一种数学方法，从侧面说明了数学与计算机之间的紧密联系，因此，有时间还是需要对数学进行深入学习。

更多分享，尽在交流QQ群：199546072