【小姿势】简单的布隆过滤器（C++实现）_内容过滤功能怎么用c++实现

这两天在看redis，看到了布隆过滤器，觉得挺有意思的，随便拿C++写了个mini版本的，可惜C++的bitset不支持自定义长度和resize。
布隆过滤器可以告诉你：某样东西一定不存在或者可能存在
原理就是哈希碰撞，多几个哈希，一个没中就是一定不存在，全中就是很大概率存在，因此正确率依赖bitset的大小，当塞得东西太多时，此时错误率会大幅提高。

#include <iostream>
#include <bitset>
#include <vector>
typedef unsigned long long ull;
using namespace std;

const int MAX_SIZE = 500000;

const vector<int> seeds = { 11, 23, 37, 233 };

ull ha(const string &str, const int &seed) {
    ull ret = 0;
    for (auto& ch : str) {
        ret *= seed;
        ret += ch;
    }
    return ret;
}

struct BloomFilter {
    BloomFilter(int sz) {
        resize(sz);
    }
    void clear() {
        bit_arr.reset();
    }
    int size() const {
        return _size;
    }

    void add(const string &str) {
        for (auto &seed : seeds) {
            ull ret = ha(str, seed);
            int pos = int(ret % _size);
            bit_arr.set(pos);
        }
    }

    bool contains(const string &str)const {
        for (auto &seed : seeds) {
            ull ret = ha(str, seed);
            int pos = int(ret % _size);
            if (!bit_arr[pos]) return false;
        }
        return true;
    }
    void resize(const int &sz) {
        if (sz > MAX_SIZE) {
            cout << "err\n";
            return;
        }
        clear();
        this->_size = sz;
    }
    bitset<MAX_SIZE> bit_arr;
    int _size;
};
int main() {
    BloomFilter b(20);
    vector<string> dict = {"www.baidu.com", "www.7k7k.com", "www.baike.com"};
    vector<string> test = {"www.baidu.com", "github.com", "woshisb"};

    for (auto &it : dict) {
        b.add(it);
    }
    for (auto &it : test) {
        cout << b.contains(it) << endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69