<<数学之美>>中23章介绍的布隆过滤器(Bloom filter),以下是一些算法的实现及应用
1.算法应用
在如那件设计中有个最基本的功能是判断某个元素是否在集合当中,比如爬虫中验证一个url是否被收录过,如果用普通的hash来判断那需要的内存容量是惊人的。布隆过滤器的作用就是能够降低内存用量,他只需要hash表的1/8到1/4就能够解决问题。
3.算法实现
3.1生成指纹函数,这里做了一个简化
void make_fingers(const string &url, const vector&fingers){
for (int i=0; i
3.2生成映射,将八个指纹映射到1~MAX中的一个自然数,这里的MAX只取到了10000,实际操作中这个数一般为16亿
void make_map(const vector fingers,bitset&result) {
for(int i=0; i
3.3 验证函数,验证url是否能够匹配到
bool veri_url(const string & url, const bitset result) {
vectorfingers;
make_fingers(url, fingers);
for(int i=; i
3.4 主函数
int main(int argc, char * argv[]) { // 需要hash的字符串 string url = "http://yancey.sinaapp.com"; // 保存指纹信息 vector fingers; // 保存结果的向量,该向量每个比特位的初始值为0 bitset result; result.reset(); // First Step 产生八个指纹信息 make_fingers(url, fingers); // Second Step 将这八个指纹信息用一个hash函数对应到1~MAX中的八个自然数.并将Bit向量中这八位设置为1 make_map(fingers, result); // 验证刚才的url cout << veri_url(url, result) << endl; return 0; };