C++ 实现布隆过滤器(BloomFilter)_内容过滤功能怎么用c++实现

代码如下:

#include <iostream>
#include <vector>
using namespace std;

class BitMap
{
public:

	BitMap(size_t range) :_bit(range / 32 + 1) {}

	void set(const size_t num)
	{
		int idx = num / 32;//idx 数组下标

		int bitIdx = num % 32;

		_bit[idx] |= 1 << bitIdx;
	}

	bool find(const size_t num)
	{
		int idx = num / 32;
		int bitIdx = num % 32;
		return (_bit[idx] >> bitIdx) & 1;
	}

	void reset(const size_t num)
	{
		int idx = num / 32;
		int bitIdx = num % 32;
		_bit[idx] &= ~(1 << bitIdx);
	}


private:
	vector<int>_bit;
};

//哈希函数的个数: k = m/(n*ln(2))，其中m为位图需要的bit的大小，n为元素个数，k为哈希函数的个数


struct HashFun1
{
	size_t operator()(const string & str)
	{
		size_t hash = 0;
		for (const auto & ch : str)
		{
			hash = hash * 131 + ch;
		}
		return hash;
	}
};


struct HashFun2
{
	size_t operator()(const string & str)
	{
		size_t hash = 0;
		for (const auto & ch : str)
		{
			hash = hash * 65599 + ch;
		}
		return hash;
	}
};


struct HashFun3
{
	size_t operator()(const string & str)
	{
		size_t hash = 0;
		for (const auto & ch : str)
		{
			hash = hash * 1313131 + ch;
		}
		return hash;
	}
};

template<typename T, typename HashFun1, typename HashFun2, typename HashFun3>
class BloomFilter
{
public:
	BloomFilter(const size_t num) :_bit(5 * num), _bitCount(5 * num) {}

	void set(const T & val)
	{
		HashFun1 h1;
		HashFun2 h2;
		HashFun3 h3;
		int idx1 = h1(val) % _bitCount;
		int idx2 = h2(val) % _bitCount;
		int idx3 = h3(val) % _bitCount;
		_bit.set(idx1);
		_bit.set(idx2);
		_bit.set(idx3);
	}

	bool find(const T & val)
	{
		HashFun1 h1;
		HashFun2 h2;
		HashFun3 h3;
		int idx1 = h1(val) % _bitCount;
		int idx2 = h2(val) % _bitCount;
		int idx3 = h3(val) % _bitCount;

		if (!_bit.find(idx1)) return false;
		if (!_bit.find(idx2)) return false;
		if (!_bit.find(idx3)) return false;

		return true;//可能存在
	}

private:
	BitMap _bit;
	size_t _bitCount;
};

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122