【1++的数据结构】之哈希（二）

👍作者主页：进击的1++
🤩 专栏链接：【1++的数据结构】

---

一，前言

上一节我们讲解了哈希表，简单的了解了哈希思想，这一节我们对哈希思想进行更深入的了解，对其应用进行学习。大家坐稳了，学习的快车又要发动了！！！

二，位图

1. 位图

什么叫位图呢？
位图就是用每一位来存储一种状态。位是表示信息的最小单位，每一位存储一种状态，那么我们可以将每一位的状态与数据映射。那么便可以用较少的内存去处理海量的数据。通常用其判断某个数据存不存在。
接下来我们进行位图的实现:
来看代码：

template<size_t N>
	class Bit_set
	{
	public:
		Bit_set()
		{
			_bit_table.resize(N / 8 + 1, 0);
		}
		void set(const size_t& key)
		{
			//锁定位置
			size_t i = key / 8;
			size_t j = key % 8;
			//将那一位置为1
			_bit_table[i] |= (1 << j);

		} 

		void reset(const size_t& key)
		{
			//锁定位置
			size_t i = key / 8;
			size_t j = key % 8;
			//将那一位置为0
			_bit_table[i] &= ~(1 << j);
		}

		bool test(const size_t& key)
		{
			//锁定位置
			size_t i = key / 8;
			size_t j = key % 8;
			//检查那一位是否为1
			return _bit_table[i] & (1 << j);
		}
	private:
		vector<char> _bit_table;

	};

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

总的思路就是开一个有N个位大小的空间（N应该比元素集合中的最大值还要大），然后将数据（整型）映射到位图中的位置：即第几个char中的第几位,然后将其进行置1，置0,或是检查那位是否为1。

2. 位图的应用

1. 快速查找某个数据是否在一个集合中
   此题可直接使用位图，进行查找。
2. 排序 + 去重
   由于位图只可以表示其状态（在或不在）因此其天生就有去重的特性，其排序，只需将我位图遍历一遍，便可以得到升序的元素集合。

void test2()
	{
		size_t N = 100;
		Bit_set<100> s1;
		int arr[] = { 1,5,3,7,0,10,9,8,3 };
		for (auto& e : arr)
		{
			s1.set(e);
		}

		for (size_t i = 0; i < N; i++)
		{
			if (s1.test(i))
			{
				cout << i << endl;
			}

		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3. 求两个集合的交集、并集等
   我们只需要创建两个相同大小的对象，然后各自进行set，最后一起遍历。。。。。

void test3()
	{
		size_t N = 100;
		Bit_set<100> s1;
		Bit_set<100> s2;
		int arr1[] = { 1,5,3,7,0,10,9,8,3 };
		int arr2[] = { 1,10,3,7,11,10,2,8,4 };

		for (auto& e : arr1)
		{
			s1.set(e);
		}

		for (auto& e : arr2)
		{
			s2.set(e);
		}

		for (size_t i = 0; i < N; i++)
		{
			if (s1.test(i) && s2.test(i))
			{
				cout << i << 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

4. 找出现两次的元素
   既然一个位只能表示一种状态，那么两个位是不是就能表示四种状态（一次没出现，出现一次，出现两次，出现两次以上）

template<size_t N>
	class two_bit
	{
	public:
		void set(const size_t& key)
		{
			if (_bits1.test(key) == false && _bits2.test(key) == false)
			{
				_bits2.set(key);
				_bits1.reset(key);
			}
			else if (_bits1.test(key) == false && _bits2.test(key) == true)
			{
				_bits1.set(key);
				_bits2.reset(key);
			}
			else 
			{
				_bits1.set(key);
				_bits2.set(key);
			}
			
		}

		bool test(const size_t& key)
		{
				
			return (_bits1.test(key) == true && _bits2.test(key) == false);
		}
	private:
		Bit_set<N> _bits1;
		Bit_set<N> _bits2;

	};


void test3()
	{
		two_bit<100> t1;
		int arr[] = { 1,4,6,2,3,7,9,10,2,6,2 };
		for (auto& e : arr)
		{
			t1.set(e);
		}
		cout<<t1.test(2)<<endl;
		cout << t1.test(6) << endl;
		cout << t1.test(1) << 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

三，布隆过滤器

什么是布隆过滤器？
布隆过滤器是用多个哈希函数，将一个数据元素映射到位图结构中。此方式不仅可以提升效率，也可以节省空间。
以下是布隆过滤器的实现：

template<class K,size_t N>
	class BloomFilter
	{
	public:
		void set(const K& key)
		{
			size_t len = N * 5;
			size_t hash1 = DJBHash()(key) % len;
			size_t hash2 = BKDRHash()(key) % len;
			size_t hash3 = APHash()(key) % len;

			_bitset.set(hash1);
			_bitset.set(hash2);
			_bitset.set(hash3);
		}

		void reset(const K& key)//普通的删除可能会影响其他值

		bool test(const K& key)
		{
			size_t len = N * 5;
			size_t hash1 = DJBHash()(key) % len;
			size_t hash2 = BKDRHash()(key) % len;
			size_t hash3 = APHash()(key) % len;
			if (!_bitset.test(hash1))
				return false;
			if (!_bitset.test(hash2))
				return false;
			if (!_bitset.test(hash3))
				return false;

			return true;

		}
	private:
		Bit_set<N* 5> _bitset;
	};
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

布隆过滤器的优点及其缺陷：

1. 增加和查询元素的时间复杂度位O(K) K为哈希函数的个数。
2. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
3. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
4. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能

缺点：

1. 有误判，能够判定某一元素一定不在，但不能够判定该元素一定在。
2. 一般情况下不能够进行删除
3. 不能够获取元素本身