布隆过滤器的简易版本实现：
- /*布隆过滤器简易版本 2012.11.10*/
- #include<iostream>
- #include<bitset>
- #include<string>
- #define MAX 2<<24
- using namespace std;
- bitset<MAX> bloomSet; //简化了由n和p生成m的过程
- int seeds[7]={3, 7, 11, 13, 31, 37, 61}; //使用7个hash函数
- int getHashValue(string str,int n) //计算Hash值
- {
- int result=0;
- int i;
- for(i=0;i<str.size();i++)
- {
- result=seeds[n]*result+(int)str[i];
- if(result > 2<<24)
- result%=2<<24;
- }
- return result;
- }
- bool isInBloomSet(string str) //判断是否在布隆过滤器中
- {
- int i;
- for(i=0;i<7;i++)
- {
- int hash=getHashValue(str,i);
- if(bloomSet[hash]==0)
- return false;
- }
- return true;
- }
- void addToBloomSet(string str) //添加元素到布隆过滤器
- {
- int i;
- for(i=0;i<7;i++)
- {
- int hash=getHashValue(str,i);
- bloomSet.set(hash,1);
- }
- }
- void initBloomSet() //初始化布隆过滤器
- {
- addToBloomSet("http://www.baidu.com");
- addToBloomSet("http://www.cnblogs.com");
- addToBloomSet("http://www.google.com");
- }
- int main(int argc, char *argv[])
- {
-
- int n;
- initBloomSet();
- while(scanf("%d",&n)==1)
- {
- string str;
- while(n--)
- {
- cin>>str;
- if(isInBloomSet(str))
- cout<<"yes"<<endl;
- else
- cout<<"no"<<endl;
- }
-
- }
- return 0;
- }
| 
楼主
