C++哈希(位图，布隆过滤器，哈希切分)

1.位图

1.1位图的概念

位图结构也是STL中的一种，算是哈希的一种变形，在查找数据的方面效率也比较高。

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

1.遍历：时间复杂度为O(N)。
2.排序(O(NlogN))，然后利用二分查找：logN
3.使用位图来解决：数据是否在给定的整型数组中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制的比特位为，代表存在，为0代表不存在。比如：

所谓位图，就是用每一位来存放某种状态，适用于海量的数据，数据无重复的场景。通常是用来判断某个数据存不存在。
注意，虽然是存放40亿个整数，但是我们要开42亿个空间，因为整数的范围是41亿9千万，要保证每一个整数都有它对应的位图。
由于不能直接开辟比特位的空间，我们使用一个字符的空间来代替(8个比特位)

1.2位图的实现

将要设置的数据除以8得到的是所在的char的位置，再将该数据模8得到的是所在比特位的位置，通过这两个位置我们可以进行置为，重置以及判断。

#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
using namespace std;
template<size_t N>
class bitset
{
private:
	vector<char> _bits;
public:
	bitset()
	{
		_bits.resize(N / 8 + 1);//最多浪费8个比特位，防止空间不够
	}
	void set(size_t x)//将x标记为1
	{
		size_t i = x / 8;//找到所在的char的位置
		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)//判断x是否置位
	{
		size_t i = x / 8;
		size_t j = x % 8;
		return _bits[i] & (1 << j);
	}
};
int main()
{
	bitset<100> bs;
	bs.set(5);
	bs.set(10);
	bs.set(20);
	bs.set(50);
	bs.set(20);
	bs.reset(50);
	bs.reset(5);
	cout << bs.test(5) << endl;
	cout << bs.test(10) << endl;
	cout << bs.test(20) << endl;
	cout << bs.test(50) << endl;
	cout << bs.test(3) << endl;
	return 0;
}
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

1.3一些变形题

1.3.1 问题1

给定100亿个整数，找出只出现一次的整数。
分析有三种状态：出现0次，出现1次，出现2次及以上。
此时我们需要使用两个比特位来表示，即：00表示出现0次，01表示出现1次，10表示出现两次。
一种方式是使用两个比特位表示一个值。

还有一种方式是采用两个位图合起来。分别代表某一个数字的两个比特位，从而可以标定元素的状态。

同理，如果是寻找不超过3次的数据，此时共有5种状态，就可以建立三个位图来接收三个比特位，来表示不同的状态。

1.3.2 问题2

给定两个文件，分别由100亿个数，只有1G内存，如何找到两个文件的交集。

思路一：一个文件中的整数存放在一个位图中，读取第二个文件中的整数，判断是否也在位图中，如果在的话就记录下来。但那时这种方法有一个缺陷，那就是会把重复的值也找出来，还需要想办法来进行去重操作(使用set)。
思路二：读取一个文件整数设置到位图，再把另一个文件中的整数设置到位图，然后两个位图相与即可。

2.布隆过滤器

2.1概念

位图的优势在于节省空间，并且查找的效率高，但是他的局限性在于只能处理整数。而对于字符串类型是无法解决冲突问题的。
因此，我们在位图的基础上引入了布隆过滤器这一概念：
布隆过滤器的本质是(采用不同的哈希算法)让一个字符串映射多个位置。

只有这三个位置都被置位的情况下，才代表该字符串在哈希表中。
但是这种方式仍然不是最准确的，保不准有的字符串的三个映射位置都相同，这种情况称为误判，我们可以通过增加哈希函数，或者增大布隆过滤器的长度来降低该现象发生的概率。但是会增加开销。
因此有人经过大量的比对分析，得到一个函数从而以最小的开销降低误判发生概率：

k=(m/n)*ln2
k：哈希函数个数
m：布隆过滤器长度
n：插入元素个数

2.2 布隆过滤器实现

#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include
#include
using namespace std;
struct BKDRHash
{
	size_t operator()(const string& s)
	{
		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;
	}
};
template<size_t N,class HashFunc1=BKDRHash,class HashFunc2=APHash,class HashFunc3=DJBHash,class K = string>
class BloomFilter
{
public:
	bitset<N> _bs;
public:
	void Set(const K& key)
	{
		size_t index1 = HashFunc1()(key) % N;
		size_t index2 = HashFunc2()(key) % N;
		size_t index3 = HashFunc3()(key) % N;
		cout << index1 << endl;
		cout << index2 << endl;
		cout << index3 << endl;
		cout << endl;
		_bs.set(index1);
		_bs.set(index2);
		_bs.set(index3);
	}
	bool Test(const K& key)
	{
		size_t len =  N;
		size_t index1 = HashFunc1()(key) % len;
		size_t index2 = HashFunc2()(key) % len;
		size_t index3 = HashFunc3()(key) % len;
		if (_bs.test(index1) == false)
		{
			return false;
		}
		else if (_bs.test(index2) == false)
		{
			return false;
		}
		else if(_bs.test(index3)==false)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
};
int main()
{
	BloomFilter<100> bm;
	cout << bm._bs.size() << endl;
	bm.Set("sort");
	bm.Set("left");
	bm.Set("right");
	bm.Set("hello");
	cout << bm.Test("hello") << endl;
	cout << bm.Test("superman") << 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

使用了三种不同的哈希函数来将字符串转化为整型，最终的打印结果为：

2.3 删除操作

一般而言，布隆过滤器是不支持删除的，因为有的字符串的某个位置可能是相同的，一旦将一个位置置为0，就会导致其他有映射到该位置的字符串也同时被删除了，解决这一问题的方法是将每一个比特位扩大成一个整型，以计数器的方式进行插入和删除，但是这就破坏了布隆过滤器的优势。

2.4 布隆过滤器的应用

给定两个文件，分别由100亿个数据，但是只有1G的内存，找到两个文件交集，使用近似算法和精确算法解决：

近似算法：将A的100亿个数据插入到布隆过滤器中，然后读取B中的数据，在布隆过滤器中进行查找即可，但是可能存在误判。
那么如何精确实现呢?这就需要引入哈希切分

3.哈希切分

3.1哈希切分的意义

哈希切分的意义在于：通过映射将相同的元素存放在同一个编号的空间中。

3.2哈希切分的过程

以上题为例，介绍哈希切分的过程：

给定两个文件，分别由100亿个数据，但是只有1G的内存，找到两个文件交集。

将A和B两个文件切分成一个一个的带有编号的小文件，将其中的元素按哈希规则存入到小文件中。
通过这个算法，A和B中相同的字符串一定在相同编号的小文件中，只需要在编号相同的小文件中进行查找即可。可以使用set来进行查找。

3.3 哈希切分的应用

给定100G大小的文件，存放的都是IP地址，设计算法找到出现次数最多的IP地址。

这种查找的情况就很符合哈希切分的特性，只需要在哈希切分之后，统计每一个小文件中相同字符串出现次数最多的即可。

TopK问题解决

使用优先级队列，建立K个数的小堆即可。