C++ 哈希思想应用 位图 布隆过滤器 海量数据处理_c++中哈希数据量很大怎么办

问题引入

问题：
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。

问题分析：
时间复杂度角度：

1. 直接遍历，时间复杂度O(N)；
2. 以文件为单位进行归并排序(O(NlogN))+二分查找O(logN);
3. 利用位图解决，时间复杂度0(1);
   空间复杂度角度：
4. 如果利用 unordered_set 去建立哈希映射关系，在空间上是不够的 40亿个数如果使用开散列为底层， 那么仅仅是计算所开 结点 的内存大小就为 (16 * 40亿)byte，换算一下约为72GB ，非常不合理。
5. 利用位图解决

位图（附C++模拟实现源码）

什么是位图？
位图，就是用每一bit位来存放某种状态，为1，代表存在，为0
代表不存在适，用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。利用位图处理该问题的思路就是压缩内存成本，是利用哈希思想建立映射的方案可行

位图能解决该问题的大概计算
只粗略计算主干：1 byte 可建立8个数的映射关系(闭散列)，那么40亿个数需要 40亿 / (1024 * 1024* 1024 * 8 ) 约等于0.5GB内存。

位图应用总结

1. 快速查找某个数据是否在一个集合中
2. 排序 + 去重
3. 求两个集合的交集、并集等
4. 操作系统中磁盘块标记（暂时不了解）

位图的模拟实现
注意点：
1.运算符优先级
2.运算逻辑的控制
在.h文件中：

#pragma once
#include<vector>
#include<iostream>
#include<string>
using namespace std;



namespace myBitSet
{
	// 非类型模板参数特化的应用  N的含义为N个bit位的位图
	template<size_t N>
	class bitset
	{
	private:
		 
		//成员变量
		std::vector<char> _bits;

	public:

		bitset()
		{
			// 一个char占8个比特位
			_bits.resize(N / 8 + 1, 0);
		}

		//大概理解为建立映射的功能
		void set(size_t x)
		{
			// x 映射的比特位在第几个char对象
			size_t i = x / 8;

			// x 在char的第几个比特位
			size_t j = x % 8;

			//# 表示可能位0也可能为1
			// 举例j = 3 
			// 原第i个char： ########
			// (1 << j) ：   00001000
			//运算结果：     ####1###
			_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 i = x / 8;
			size_t j = x % 8;
			return _bits[i] & (1 << j);
		}

		//测试方案
		void test_can_do()
		{
			bitset<100> bs;
			bs.set(33);
			bs.set(57);

			cout << bs.test(33) << endl;
			cout << bs.test(57) << endl;

			bs.reset(33);

			cout << bs.test(33) << endl;
			cout << bs.test(57) << 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
70
71
72
73
74
75
76
77
78
79
80

布隆过滤器（附C++模拟实现源码）

位图的缺点？
只能进行整数的海量数据处理。位图为降低空间损耗，建立的映射方案就是数字N的状态用第N个bit位来标识状态。不再需要区花多余的空间去解决哈希冲突，扩容等问题。
什么是布隆过滤器？
布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

布隆过滤器工作原理

布隆过滤器的映射建立与查找

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。
注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。

布隆过滤器删除
布隆过滤器不能直接支持删除工作，因为不同元素在建立映射的时候，多个映射位完全相同的概率很小，但存在相同映射位的概率大，在删除一个元素的映射位时，可能会影响其他元素。

布隆过滤器优点

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

布隆过滤器缺陷

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

布隆过滤器模拟实现
在.文件中：

//布隆过滤器/
#pragma once
#include<vector>
#include<iostream>
#include<bitset>
#include<string>
using namespace std;

	// 将字符串转为可进行整形映射的四种较优方法
	//指效率较优秀
	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;
		}
	};

	struct JSHash
	{
		size_t operator()(const string& s)
		{
			size_t hash = 1315423911;
			for (auto ch : s)
			{
				hash ^= ((hash << 5) + ch + (hash >> 2));
			}
			return hash;
		}
	};
	

	template<size_t M,
	class K = string,
	class HashFunc1 = BKDRHash,
	class HashFunc2= APHash,
	class HashFunc3= DJBHash,
	class HashFunc4= JSHash>
	class BloomFilter       // 关键字: Bloom 布隆过滤器
	{
	private:
		//成员变量
		bitset<M> _bs;
	public:

		void Set(const K& key)
		{
			//如果这样写则会被认为是强制类型转换，类名() 是调用该类构造函数的格式
			//size_t hash1 = HashFunc1(key) % M;

			//所以HashFunc1()是有个匿名对象的
			size_t hash1 = HashFunc1()(key) % M;
			size_t hash2 = HashFunc2()(key) % M;
			size_t hash3 = HashFunc3()(key) % M;
			size_t hash4 = HashFunc4()(key) % M;

			_bs.set(hash1);
			_bs.set(hash2);
			_bs.set(hash3);
			/*_bs.set(hash4);*/
		}

		bool Test(const K& key)
		{

			//这样逐个判断，只要有一个不符合就立马返回结果符合效率最高 
			size_t hash1 = HashFunc1()(key) % M;
			if (_bs.test(hash1) == false)
			{
				return false;
			}

			size_t hash2 = HashFunc2()(key) % M;
			if (_bs.test(hash2) == false)
			{
				return false;
			}

			size_t hash3 = HashFunc3()(key) % M;
			if (_bs.test(hash3) == false)
			{
				return false;
			}

			size_t hash4 = HashFunc4()(key) % M;
			if (_bs.test(hash4) == false)
			{
				return false;
			}

			return true;
			//如果判断为false，即不存在，结果是100%正确的
			//结果为 true 存在误判的可能性 
		}

		//布隆过滤器不存在该选项，因为可能误删其他存在的映射关系
		bool Reset(const K& key);


		void test_can_do()
		{
			BloomFilter<43> bf;

			string a[] = { "苹果", "香蕉", "西瓜", "111111111", "eeeeeffff", "草莓", "休息", "继续", "查找", "set" };

			for (auto& e : a)
			{
				bf.Set(e);
			}

			for (auto& e : a)
			{
				cout << bf.Test(e) << endl;
			}
			cout << endl;

			cout << (bf.Test("芒果")) << endl;
			cout << bf.Test("string") << endl;
			cout << bf.Test("ffffeeeee") << endl;
			cout << bf.Test("31341231") << endl;
			cout << bf.Test("ddddd") << endl;
			cout << bf.Test("3333343") << 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
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165