位图定义：

利用位的状态来存放一个数是否存在，其实就是把一个数映射成一个简单的数用以标记他是否存在，一般使用情况为查找一个数是否存在。

数据结构：

1/8=0 1%8=1 1<<1(第二个bit位置1)

2/8=0 2%8=2 1<<2(第3个bit位置1)

3/8=0 3%8=3 1<<3(第4个bit位置1)

4/8=0 ....

查找这个数是否存在：

先算出这个数的存在位置，然后找这个位置是否为1，如果是则存在否则不存在。

缺点：可读性差。

应用：
1、给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中
　　将这40亿个数字存储到bitmap中，然后对于给出的数，判断是否在bitmap中即可。
2、使用位图法判断×××数组是否存在重复
遍历数组，一个一个放入bitmap，并且检查其是否在bitmap中出现过，如果没出现放入，否则即为重复的元素。
3、使用位图法进行×××数组排序
首先遍历数组，得到数组的最大最小值，然后根据这个最大最小值来缩小bitmap的范围。这里需要注意对于int的负数，都要转化为unsigned int来处理，而且取位的时候，数字要减去最小值。

#define_CRT_SECURE_NO_WARNINGS#include<iostream>usingnamespacestd;#include<vector>classBitMap{public:BitMap(size_tsize){_bm.resize(size/32+1);_size=0;}BitMap():_size(0){}voidSet(size_tnum){size_tindex=num>>5;if((_bm[index]&1<<(num%32))==0){_bm[index]|=1<<(num%32);++_size;}}voidReset(size_tnum){size_tindex=num>>5;if((_bm[index]&(1<<(num%32)))==1<<(num%32)){_bm[index]&=~(1<<(num%32));--_size;}}boolTest(size_tnum){size_tindex=num>>5;if((_bm[index]&(1<<(num%32)))==1<<(num%32)){returntrue;}returnfalse;}size_tSize(){return_size;}private:vector<unsignedint>_bm;size_t_size;};////voidtest()//{//BitMapx(100);//x.Set(0);//x.Set(1);//x.Set(2);//x.Set(3);//x.Set(4);//x.Set(5);//x.Reset(1);//x.Reset(3);//intret=x.Test(4);//////}//intmain()//{//test();//system("pause");//return0;//}

利用上述的位图实现布隆过滤器：

仿函数：

就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了。

布隆过滤器：

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

应用场景：

字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断 它是否在已知的字典中）；在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新 元素时，将它和集合中的元素直接比较即可。一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来 了。

优点：

布隆过滤器存储空间和插入/查询时间都是常数。另外, Hash 函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

缺点：

误算率。随着存入的元素数量增加，误算率随之增加。

#define_CRT_SECURE_NO_WARNINGS#include"Map.h"#include<string>

size_t_GetSize(constsize_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};size_ti=0;for(;i<_PrimeSize;i++){if(_PrimeList[i]<=size&&i!=_PrimeSize-1){i++;}else{break;}}return_PrimeList[i];}template<classT>struct__HashFunc1{size_tBKDRHash(constchar*str){registersize_thash=0;while(size_tch=(size_t)*str++){hash=hash*131+ch;}returnhash;}size_toperator()(constT&str){returnBKDRHash(str.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&str){returnSDBMHash(str.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&str){returnRSHash(str.c_str());}};template<classT>struct__HashFunc4{size_tAPHash(constchar*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;}size_toperator()(constT&str){returnAPHash(str.c_str());}};template<classT>struct__HashFunc5{size_tJSHash(constchar*str){registersize_thash=1315423911;while(size_tch=(size_t)*str++){hash^=((hash<<5)+ch+(hash>>2));}returnhash;}size_toperator()(constT&str){returnJSHash(str.c_str());}};template<classK=string,classHashFunc1=__HashFunc1<K>,classHashFunc2=__HashFunc2<K>,classHashFunc3=__HashFunc3<K>,classHashFunc4=__HashFunc4<K>,classHashFunc5=__HashFunc5<K>>classBloomFilter{public:BloomFilter(size_tsize=0):_bitmap(size),_capacity(size){}voidSet(constK&key){size_tindex1=HashFunc1()(key);size_tindex2=HashFunc2()(key);size_tindex3=HashFunc3()(key);size_tindex4=HashFunc4()(key);size_tindex5=HashFunc5()(key);_bitmap.Set(index1%_capacity);_bitmap.Set(index2%_capacity);_bitmap.Set(index3%_capacity);_bitmap.Set(index4%_capacity);_bitmap.Set(index5%_capacity);}boolTest(constK&key){size_tindex1=HashFunc1()(key);if(!(_bitmap.Test(index1%_capacity)))returnfalse;size_tindex2=HashFunc2()(key);if(!(_bitmap.Test(index2%_capacity)))returnfalse;size_tindex3=HashFunc3()(key);if(!(_bitmap.Test(index3%_capacity)))returnfalse;size_tindex4=HashFunc4()(key);if(!(_bitmap.Test(index4%_capacity)))returnfalse;size_tindex5=HashFunc4()(key);if(!(_bitmap.Test(index5%_capacity)))returnfalse;returntrue;}private:BitMap_bitmap;size_t_capacity;};voidtest(){BloomFilter<>bf(50);bf.Set("aaa");bf.Set("bbb");bf.Set("ccc");intret=bf.Test("acc");ret=bf.Test("bbb");ret=bf.Test("aaa");ret=bf.Test("aaa");}intmain(){test();system("pause");return0;}