我们先给出之前我看过的腾讯公司的一道笔试题，引出位图BitMap。

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

这个问题怎么解决呢？

1）将40亿数据保存起来（保存在数组、链表、树中），再和该数判断是否相等。

那我们思考一下需要多少内存：

2）借助位图BitMap解决。

位图（BitMap）

是用一个数组中的每个数据的每个二进制位表示一个数是否存在。1表示存在，0表示不存在。

相当于把数组分成很多块的空间，每一块是32个比特位。

原来32个比特位放一个数据，现在一个位就可以放一个数据。16GB/32=0.5GB=512MB。

位图的实现：

#ifndef__BITMAP_H__#define__BITMAP_H__#include<iostream>usingnamespacestd;#include<vector>classBitMap{public:BitMap(size_tsize=0):_size(0){//_a开辟多一个空间，如size=36/32=1,需要两块空间才能放下_a.resize((size>>5)+1);}voidSet(size_tx){//size_tindex=x/32;size_tindex=(x>>5);size_tnum=x%32;//if(!(_a[index]&(1<<num))表示该二进制位不存在，则该位二进制置成1if(!(_a[index]&(1<<num))){_a[index]|=(1<<num);++_size;}}voidReset(size_tx){//size_tindex=x/32;size_tindex=x>>5;size_tnum=x%32;//该位存在则将该位二进制置为0if(_a[index]&(1<<num)){_a[index]&=~(1<<num);--_size;}}boolTest(size_tx){//size_tindex=x/32;size_tindex=x>>5;size_tnum=x%32;if(_a[index]&(1<<num)){returntrue;}returnfalse;}voidResize(size_tsize){_a.resize(size);}private:vector<size_t>_a;size_t_size;};#endif//__BITMAP_H__

布隆过滤器（BloomFilter）

它是由一个很长的二进制向量和一系列随机映射函数组成，布隆过滤器可以用于检索一个元素是否在一个集合中。那我们可以利用哈希函数计算出它具体的存放位置。

它的优点是空间效率和查询时间都远远超过一般的算法，将这40亿的数据内存由16GB变成500MB,可见其强大。

缺点是有一定的误识别率、不便于删除。布隆过滤器会出现：检测存在，而实际中却不存在。而不会出现：实际中不存在，而检测存在。

代码实现（仿函数实现，选取5个位图）：

#define_CRT_SECURE_NO_WARNINGS1#ifndef__COMMON__#define__COMMON__size_t_GetnewSize(size_t_size){staticconstint_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(inti=0;i<_PrimeSize;i++){if(_PrimeList[i]>_size){return_PrimeList[i];}}return_PrimeList[_PrimeSize-1];}template<classT>struct__HashFunc1{size_tBKDRHash(constchar*str){registersize_thash=0;while(size_tch=(size_t)*str++){hash=hash*131+ch;//也可以乘以31、131、1313、13131、131313..}returnhash;}size_toperator()(constT&key){returnBKDRHash(key.c_str());}};template<classT>struct__HashFunc2{size_tSDBMHash(constchar*str){registersize_thash=0;while(size_tch=(size_t)*str++){hash=65599*hash+ch;//hash=(size_t)ch+(hash<<6)+(hash<<16)-hash;}returnhash;}size_toperator()(constT&key){returnSDBMHash(key.c_str());}};template<classT>struct__HashFunc3{size_tRSHash(constchar*str){registersize_thash=0;size_tmagic=63689;while(size_tch=(size_t)*str++){hash=hash*magic+ch;magic*=378551;}returnhash;}size_toperator()(constT&key){returnRSHash(key.c_str());}};template<classT>struct__HashFunc4{size_tJSHash(constchar*str){if(!*str)//这是由本人添加，以保证空字符串返回哈希值0return0;registersize_thash=1315423911;while(size_tch=(size_t)*str++){hash^=((hash<<5)+ch+(hash>>2));}returnhash;}size_toperator()(constT&key){returnJSHash(key.c_str());}};template<classT>struct__HashFunc5{size_tDEKHash(constchar*str){if(!*str)//这是由本人添加，以保证空字符串返回哈希值0return0;registersize_thash=1315423911;while(size_tch=(size_t)*str++){hash=((hash<<5)^(hash>>27))^ch;}returnhash;}size_toperator()(constT&key){returnDEKHash(key.c_str());}};#endif//__COMMON__

布隆过滤器代码实现（借助素数表获取下一个素数，选取合适的容量--》hash函数）：：

#define_CRT_SECURE_NO_WARNINGS1#include<iostream>usingnamespacestd;#include<string>#include"Common.h"#include"BitMap.h"template<classT=string,classHashFunc1=__HashFunc1<T>,classHashFunc2=__HashFunc2<T>,classHashFunc3=__HashFunc3<T>,classHashFunc4=__HashFunc4<T>,classHashFunc5=__HashFunc5<T>>classBloomFilter{public:BloomFilter(size_tcapacity=0){_capacity=_GetnewSize(capacity);_bm.Resize(capacity);}voidSet(constT&key){size_tindex1=HashFunc1()(key);size_tindex2=HashFunc2()(key);size_tindex3=HashFunc3()(key);size_tindex4=HashFunc4()(key);size_tindex5=HashFunc5()(key);_bm.Set(index1%_capacity);_bm.Set(index2%_capacity);_bm.Set(index3%_capacity);_bm.Set(index4%_capacity);_bm.Set(index5%_capacity);}boolTest(constT&key){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;}returntrue;}private:BitMap_bm;size_t_capacity;//布隆过滤器的容量};voidTestBloomFilter(){BloomFilter<>bf(100);bf.Set("JustDoIT!");bf.Set("布隆过滤器");bf.Set("https://mail.google.com/mail/#inbox");cout<<"Isexist?:"<<bf.Test("测试工程师")<<endl;cout<<"Isexist?:"<<bf.Test("开发工程师")<<endl;cout<<"Isexist?:"<<bf.Test("IT")<<endl;cout<<"Isexist?:"<<bf.Test("布隆过滤器")<<endl;cout<<"Isexist?:"<<bf.Test("BloomFilter")<<endl;cout<<"Isexist?:"<<bf.Test("https://mail.google.com/mail/#inbox")<<endl;cout<<"Isexist?:"<<bf.Test("https://mail.google.com/mail/#inbox111111")<<endl;}intmain(){TestBloomFilter();system("pause");return0;}