学习Bloom Filter，处理“海量”数据

今天晚上做了一个在线测评，其中涉及到了一个海量数据处理的问题，下面是这个问题定义及我的解法，其中用到了Bloom Filter，这个东西乍一听让人摸不着头脑，仔细看看，感觉就是Hash+Bitmap的合体，综合了Hash散列定位和Bitmap用位存储的特点。

问题：

已存在20亿个URL，每个URL平均长度为64字节，在2G内存的环境中，设计一个较快的算法去判断一个新的URL是否在那20亿URL中，可以出现一定几率的误判。

思路：

使用Bloom Filter的方法，将这20亿个URL映射到内存中，该内存空间初始化为0，每个URL映射到一个bit位，遍历已有的20亿个URL，并将对应的bit位置为1，检查新的URL所对应的bit位，该位为0则表示新URL不在集合中，该位为1则表示新URL在集合中，映射方法采用哈希算法，理论上2G内存可以处理160亿位，而我使用了40亿位，约占用500M内存空间。

代码：

 1 #include <string.h>
 2 #include <fstream>
 3 #include <iostream>
 4 
 5 using namespace  std;
 6 
 7 unsigned int* build_memory_of_bloomfilter(const unsigned int m)
 8 {
 9     // 建立一个空bitmap
10     // 我这里是用1位表示一条记录，没有查重的功能，如果用2位表示，或者使用双bitmap，则可以实现查重
11     unsigned int* p = new unsigned int[1 + m/(8*sizeof(unsigned int))];
12     memset(p, 0, m/8 + sizeof(unsigned int));
13     return p;
14 }
15 
16 void set_bit(unsigned int* arr, unsigned int n)
17 {
18     unsigned int pos = n/(8*sizeof(unsigned int));
19     unsigned int tmp = n%(8*sizeof(unsigned int));
20     unsigned int msk = (unsigned int)1 << tmp;
21     arr[pos] |= msk;
22 }
23 unsigned int get_bit(unsigned int* arr, unsigned int n)
24 {
25     unsigned int pos = n/(8*sizeof(unsigned int));
26     unsigned int tmp = n%(8*sizeof(unsigned int));
27     unsigned int msk = (unsigned int)1 << tmp;
28     tmp = arr[pos];
29     tmp &= msk;
30     return tmp>0?1:0;
31 }
32 
33 static const int hashtable_length    = 4000000000;
34 unsigned int hash_function(const char* str)
35 {
36     const char* end_of_str = str+strlen(str);
37     unsigned int sum = 0;
38     while (end_of_str - str > 3)
39     {
40         sum ^= *((unsigned int*)str);
41         str += 4;
42     }
43     char tmp[4] = {0};
44     strcpy(tmp, str);
45     sum ^= (unsigned int)*((unsigned int*)tmp);
46     sum %= hashtable_length;
47     memset(tmp, 0, 4);
48 
49     return sum;
50 }
51 int main()
52 {
53 
54     const unsigned int MAX = 4000000000;                        // 设置总位数为40亿，目标是处理20亿URL
55     unsigned int* memory_of_bloomfilter = build_memory_of_bloomfilter(MAX);
56 
57 
58     ifstream input_file;
59     input_file.open("D:/URL.txt");
60     if(!input_file)
61         return -1;
62 
63     char buff[256];
64 
65     // 设置20亿个URL的位
66     while(input_file.getline(buff, 255))
67         set_bit(memory_of_bloomfilter, hash_function(buff));
68 
69     cin>> buff;    // 输入新的URL
70     if(get_bit(memory_of_bloomfilter, hash_function(buff)))
71         cout<< "集合中已经存在！" <<endl;
72     else
73         cout<< "集合中不存在！" <<endl;
74 
75     input_file.close();
76     delete[] buff;
77     delete[] memory_of_bloomfilter;
78     return 0;
79 }

输出结果：

http://s1.hao123img.com/res/images/search_logo/web_png8.png
集合中已经存在！