位图，布隆过滤器的原理和实现

位图

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景，通常是用来判断某个数据是否存在
比方说现在有40亿个未排序的无符号整数，请问如何判断一个数是否存在于这40亿个数中？
这个问题就很适合用位图来解决，题目中说这些数据都是无符号整数而无符号整数最大能取到0xffffffff（约43亿），并且题目只要求我们判断该数据是否存在，因此我们只需要用一个比特位来标识该数值是否存在即可

如上图，插入了1， 3， 7三个数据，我们只要把第1， 3， 7个比特位赋值1即可。

namespace ssj
{
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			// 初始化，因为/向下取整，因此我们分配一个字节即可
			_bits.resize(N / 8 + 1, 0);
		}
		void set(size_t x) // 标记该数存在
		{
			size_t i = x / 8;
			size_t j = x % 8;
			_bits[i] |= (1 << j);
		}
		void reset(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;
			_bits[i] &= (~(1 << j));
		}
		bool test(size_t x) // 检查该数是否存在
		{
			size_t t = x / 8;
			size_t j = x % 8;
			return _bits[i] & (1 << j);
		}

	private:
		std::vector<char> _bits;
	};
}

template<size_t N>
class TwoBitSet
{
public:
	void Set(size_t x)
	{
		if (!bs1.test(x) && !_bs2.test(x))
		{
			_bs2.set(x);
		}
		else if (!_bs1.test(x) && _bs2.test(x))
		{
			_bs1.set(x);
			_bs2.reset(x);
			// 10 表示已经出现2次或以上，不用处理
		}
	}
	void PrintOnceNum()
	{
		for (size_t i = 0; i < N; ++i)
		{
			if (!_bs1.teset(i) && _bs2.test(i))
			{
				cout << i << endl;
			}
		}
	}

private:
	ssj::bitset<N> _bs1;
	ssj::bitset<N> _bs2;
};
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

布隆过滤器

位图固然是一种非常优秀的结构，他不仅节省空间而且效率高，但他也有一个很大的局限性——只能处理整数。对字符串和自定义类型对象位图没办法处理。原因很直观，对整型来讲，不管是长整型还是无符号整型数据，他们的数量终究是有限并且可以很简单的和某个位置一一对应，但是字符串的非常数量非常多，其中字符的增多和减少，或者位置的互换都会形成新的字符串，因此在有限的比特位中若我们想给每个字符串都提供一个比特位，那么必然会造成位置冲突的局面。现在要介绍的布隆过滤器可以比较有效的解决这个问题。

概念

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的一种紧凑型的，比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你“某样东西一定不存在或可能存在”，它是用多个哈希函数，将一个数据映射到 位图结构中，此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

代码

#include 
#include 
#include 

using namespace std;

/*下面三个都是哈希函数，可以自行选择合
适的哈希函数，数量最好控制在3-5个*/
struct BKDRHash
{
	size_t operator()(const string& s)
	{
		// BKDR
		size_t value = 0;
		for (auto ch : s)
		{
			value *= 31;
			value += ch;
		}
		return value;
	}
};

struct APHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (long i = 0; i < s.size(); i++)
		{
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

struct DJBHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};
// X代表我们所给的比特位是数据量的几倍
template <size_t N,
	size_t X = 8,
	class K = string,
	class HashFunc1 = BKDRHash,
	class HashFunc2 = APHash,
	class HashFunc3 = DJBHash>
class BloomFilter
{
public:
	void Set(const K& key)
	{
		size_t len = X * N;
		size_t index1 = HashFunc1()(key) % len;
		size_t index2 = HashFunc2()(key) % len;
		size_t index3 = HashFunc3()(key) % len;

		_bs.set(index1);
		_bs.set(index2);
		_bs.set(index3);
	}
	// 检查该数据是否存在
	bool Test(const K& key)
	{
		size_t len = X * N;
		size_t index1 = HashFunc1()(key) % len;
		if (_bs.test(index1) == false) return false;

		size_t index2 = HashFunc2()(key) % len;
		if (_bs.test(index2) == false) return false;

		size_t index3 = HashFunc3()(key) % len;
		if (_bs.test1(index3) == false) return false;

		return true;
	}

private:
	bitset<X* N> _bs;
};
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

删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。
一种删除方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给计数器加一，删除时减一，通过多占用几倍存储空间的代价来增加删除操作。

布隆过滤器的优点

1. 增加和查询元素的时间复杂度为O(K),(K为哈希函数的个数，一般比较小)，与数据量大小无关
2. 哈希函数相互之间没有关系，方便硬件并行运算
3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有很大的空间优势
5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

布隆过滤器的缺点

1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中（补救方法：再建立一个白名单，存储可能会误判的数据）
2. 不能获取元素本身
3. 一般情况下不能从布隆过滤器中删除元素
4. 如果采用计数方式删除，可能会存在回绕问题