位图（BitMap）&& 布隆过滤器（BloomFilter）

2024-12-21 技术教程

【面试题】给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。

● 在看到这个题后最先想到的方法是遍历这40亿个数，依次进行判断，但此做法需要的内存很大，大约为15G（4000000000 * 4÷（1024*1024*1024）），可见此算法不可取。

● 如果内存够的话，我们可以通过位图实现，位图一个数组每个数据的每个二进制位表示一个数据，每一位用0，1表示当前这个位置上是否存有值，同样是利用哈希存储的方法。此做法可以大大减少内存，对于此题是一个int类型就可以编程32个位，需要的内存空间从15G降到500M。

具体实现如下：

#pragmaclassBitMap//位图{public:BitMap():_size(0){}BitMap(size_tsize)//size表示多少位，不是数据个数:_size(size){//调整大小为size/32+1即右移5位加1（加1：需要的大小要包含size，例如10%8=1，大小应为2）_a.resize((size>>5)+1);}//位图中，注意1在移位时为左移num不是左移32-num；voidSet(size_tx)//存入x位，置1{size_tindex=x>>5;size_tnum=x%32;//eg:x=35,num=3,则在位图中为_a[1]中设为001++_size;_a[index]|=1<<num;//1左移3位，进行|使_a中对应处为}voidRemove(size_tx)//删除x位，置0{size_tindex=x>>5;size_tnum=x%32;//eg:x=35,num=3,则在位图中为_a[1]中设为110--_size;_a[index]&=(~(1<<num));//1右移3位取反0，进行&使_a中对应处为0}boolTest(size_tx)//判断是否存在{size_tindex=x>>5;size_tnum=x%32;if(_a[index]&(1<<num))//如果当前位为1，则存在{returntrue;}returnfalse;}voidResize(size_tsize)//重置大小{_a.resize((size>>5)+1);}size_tSize()//返回位图的总位数{return_size;}size_tCapacity()//返回int数据个数{return_a.size();}voidPrint(){for(size_ti=0;i<_a.size();i++){cout<<_a[i]<<""<<endl;}cout<<endl;}private:vector<size_t>_a;size_t_size;};voidTestBitMap(){BitMapbm(65);bm.Set(3);bm.Set(4);bm.Set(5);bm.Print();cout<<"is4EXTST?"<<bm.Test(4)<<endl;cout<<"is8EXTST?"<<bm.Test(8)<<endl;bm.Remove(4);cout<<"is4EXTST?"<<bm.Test(4)<<endl;bm.Print();cout<<"size:"<<bm.Size()<<endl;cout<<"capacity:"<<bm.Capacity()<<endl;bm.Resize(100);cout<<"capacity:"<<bm.Capacity()<<endl;}

● Bloom Filter 是一种空间效率很高的随机数据结构，Bloom filter 可以看做是对 bit-map 的扩展, 它的原理是：

当一个元素被加入集合时，通过K个Hash函数将这个元素映射成一个位阵列（Bit array）中的 K 个点，把它们置为1。检索时，只要看看这些点是不是都是 1 就知道集合中有没有它了。

1、如果这些点有任何一个 0，则被检索元素一定不在；

2、如果都是 1，则被检索元素可能在。

用了素数表和6个哈希算法：

#pragmasize_t_GetNextPrime(size_tsize)//素数表：获取下一个素数{constint_PrimeSize=28;staticconstunsignedlong_PrimeList[_PrimeSize]={53ul,97ul,193ul,389ul,769ul,1543ul,3079ul,6151ul,12289ul,24593ul,49157ul,98317ul,196613ul,393241ul,786433ul,1572869ul,3145739ul,6291469ul,12582917ul,25165843ul,50331653ul,100663319ul,201326611ul,402653189ul,805306457ul,1610612741ul,3221225473ul,4294967291ul};for(size_ti=0;i<_PrimeSize;++i){if(_PrimeList[i]>size){return_PrimeList[i];}return_PrimeList[i-1];}return_PrimeList[_PrimeSize];//如果size大于或等于素数表中数据，就返回表中最大数}//6种字符串哈希算法template<classT>size_tBKDRHash(constT*str){registersize_thash=0;while(size_tch=(size_t)*str++){hash=hash*131+ch;//也可以乘以31、131、1313、13131、131313..}returnhash;}template<classT>size_tSDBMHash(constT*str){registersize_thash=0;while(size_tch=(size_t)*str++){hash=65599*hash+ch;//hash=(size_t)ch+(hash<<6)+(hash<<16)-hash;}returnhash;}template<classT>size_tRSHash(constT*str){registersize_thash=0;size_tmagic=63689;while(size_tch=(size_t)*str++){hash=hash*magic+ch;magic*=378551;}returnhash;}template<classT>size_tAPHash(constT*str){registersize_thash=0;size_tch;for(longi=0;ch=(size_t)*str++;i++){if((i&1)==0){hash^=((hash<<7)^ch^(hash>>3));}else{hash^=(~((hash<<11)^ch^(hash>>5)));}}returnhash;}template<classT>size_tJSHash(constT*str){if(!*str)//这是由本人添加，以保证空字符串返回哈希值0return0;registersize_thash=1315423911;while(size_tch=(size_t)*str++){hash^=((hash<<5)+ch+(hash>>2));}returnhash;}template<classT>size_tDEKHash(constT*str){if(!*str)//以保证空字符串返回哈希值0return0;registersize_thash=1315423911;while(size_tch=(size_t)*str++){hash=((hash<<5)^(hash>>27))^ch;}returnhash;}//6个仿函数分别进行6种字符串算法的调用template<classT>struct_HashFunc1{size_toperator()(constT&str){returnBKDRHash(str.c_str());}};template<classT>struct_HashFunc2{size_toperator()(constT&str){returnSDBMHash(str.c_str());}};template<classT>struct_HashFunc3{size_toperator()(constT&str){returnRSHash(str.c_str());}};template<classT>struct_HashFunc4{size_toperator()(constT&str){returnAPHash(str.c_str());}};template<classT>struct_HashFunc5{size_toperator()(constT&str){returnJSHash(str.c_str());}};template<classT>struct_HashFunc6{size_toperator()(constT&str){returnDEKHash(str.c_str());}};

布隆过滤器具体实现如下：

#define_CRT_SECURE_NO_WARNINGS1template<classK=string,classHashFunc1=_HashFunc1<K>,classHashFunc2=_HashFunc2<K>,classHashFunc3=_HashFunc3<K>,classHashFunc4=_HashFunc4<K>,classHashFunc5=_HashFunc5<K>,classHashFunc6=_HashFunc6<K>>classBloomFilter{public:BloomFilter(size_tsize=0){_capacity=_GetNextPrime(size);_bm.Resize(_capacity);//调用BitMap的Resize调整大小}voidSet(constK&key){size_tindex1=HashFunc1()(key);size_tindex2=HashFunc2()(key);size_tindex3=HashFunc3()(key);size_tindex4=HashFunc4()(key);size_tindex5=HashFunc5()(key);size_tindex6=HashFunc6()(key);_bm.Set(index1%_capacity);//设置的位为index1%_capacity，调用BitMap的Set_bm.Set(index2%_capacity);_bm.Set(index3%_capacity);_bm.Set(index4%_capacity);_bm.Set(index5%_capacity);_bm.Set(index6%_capacity);}boolTest(constK&key){//只要存在一个为0就不存在，否则存在size_tindex1=HashFunc1()(key);if(!_bm.Test(index1%_capacity))returnfalse;size_tindex2=HashFunc2()(key);if(!_bm.Test(index2%_capacity))returnfalse;size_tindex3=HashFunc3()(key);if(!_bm.Test(index3%_capacity))returnfalse;size_tindex4=HashFunc4()(key);if(!_bm.Test(index4%_capacity))returnfalse;size_tindex5=HashFunc5()(key);if(!_bm.Test(index5%_capacity))returnfalse;size_tindex6=HashFunc6()(key);if(!_bm.Test(index6%_capacity))returnfalse;returntrue;}private:BitMap_bm;size_t_capacity;};voidTestBloomFilter(){BloomFilter<>bf(50);bf.Set("Scen");bf.Set("斯洛");bf.Set("https://blog.51cto.com/user_index.php?action=addblog_new&job=modify&tid=1773181");cout<<"exist?"<<bf.Test("Scen")<<endl;cout<<"exist?"<<bf.Test("Scenluo")<<endl;cout<<"exist?"<<bf.Test("斯洛")<<endl;cout<<"exist?"<<bf.Test("https://blog.51cto.com/user_index.php?action=addblog_new&job=modify&tid=1773181")<<endl;cout<<"exist?"<<bf.Test("https://blog.51cto.com/user_index.php?action=addblog_new&job=modify&tid=1773131")<<endl;}

布隆过滤器的缺陷：

1、误算率（False Positive）是其中之一。

随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。所以我们用多个哈希表去存储一个数据。那么问题又来了，我们是多用一些呢，还是少用一些。如果多用哈希表的话，如上面的题，一个哈希就需要500M，那么放的越多是不是越占内存啊。如果太少的话是不是误算率就高啊，所以取个适中的。我的程序实现是取了六个哈希表。

2、如果当前位置为0肯定不存在，但是为1不一定存在。

一般布隆过滤器只支持设计，不支持删除。可以通过引用计数，但空间浪费较大。