我家小花儿

这个屌丝很懒，什么也没留下！

热门标签

【C++】手把手教你实现自己的unordered_map 和unordered_set_如何实现std::unordered_map

作者：我家小花儿 | 2024-04-19 14:46:23

踩

如何实现std::unordered_map

1. unordered系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器（map,set等），在查询时效率可达到，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到。

因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，本文中只对unordered_map和unordered_set进行介绍，unordered_multimap和unordered_multiset，其他可查看文档介绍

1.1 unordered_map

1.1.1 unordered_map 简介

unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。

unordered_map 的文档说明

unordered_map的特性：

在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
它的迭代器至少是前向迭代器

1.1.2 unordered_map 接口说明

unordered_map 的文档说明

2. 底层结构

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。

2.1 哈希简介

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( log2 N)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当我们向这种结构中：

插入元素
根据带插入元素的关键码，以此函数计算出该元素的存储位置并按照位置进行存放
搜索元素
对元素的关键码进行同样的计算，把求得的值当做元素存储的位置，在结构中按照此位置取元素比较，若关键码相同，则搜索成功。

这样的方法即为哈希（散列）方法，哈希方法中使用的转换函数成为哈希（散列）函数，构造出来的结构称为哈希表(Hash Table），或者散列表。

例如，对于数组{ 1,7,6,4,5,9};
将哈希函数设置为 hash(key) = key % capacity (其中capacity为存储元素空间的总大小)。
在这里插入图片描述
可以发现，用该方法进行搜索不需要进行多次关键码的比较，因此搜索速度比较快。

2.2 哈希冲突

对于两个数据元素的关键字和 (i != j)，有 != ，但有：Hash( ) == Hash( )，即：不同关键字通过
相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”

2.3 哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单

常见的哈希函数：

直接定制法–(常用)
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀缺点：需要事先知道关键字的分布情况使用场景：适合查找比较小且连续的情况
除留余数法–（常用）
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
平方取中法–(了解)
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况
折叠法–(了解)
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况
随机数法–(了解)
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法
数学分析法–(了解)
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。

数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

2.4 哈希冲突的解决

解决哈希冲突两种常见的方法是：闭散列和开散列

2.4.1 闭散列

2.4.1.1 闭散列简介

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。

“找寻下一个空位置 ”有两种方式：

2.4.1.2 线性探测

线性探测简介

从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止

插入：

通过哈希函数获取待插入元素在哈希表中的位置
如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探
测找到下一个空位置，插入新元素

在这里插入图片描述

删除：

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

比如对于下面的哈希表：
在这里插入图片描述

如果我们直接删除 333,再去查找 14 ,此时会出现什么问题？
在这里插入图片描述
很显然，这个时候会显示14不存在。因为我们的查找规则是如果当前位置被占用，就往后找，直到空位。查找14 ，从下标4开始查找，发现是空位，按照上述规则，14不存在。

所以，直接删除会打乱整个哈希表的对应关系。那么我们如何解决？

此时我们用真正的删除元素，但是要借助其他变量来标记当前位置元素的状态。一个元素有三个状态：空，满，删除。

删除元素的时候，将当前位置由【满】填为【删除】。
插入元素的时候，向位置状态为【空】或者【删除】的位置插入
查找元素的时候，如果发生冲突向后寻找时，只有遇到【空】才停止。

线性探测模拟实现

我们花费了大量的篇幅对哈希表进行了描述，但是仅仅停留在概念上是不够，我们直接通过代码来直观的理解哈希。

哈希表的定义

HashTable 本质上就是一个数组，每个位置上存储了一个pair值（为了结构简单，暂时填写为pair）和状态值。

对于hashTable中的一个存储单元我们该如何定义？

一个键值对结构
一个枚举结构体（表示当前位置元素状态）

    enum Status
	{
		EMPTY,
	    EXITS,
		DELETE
	};
	
	template<class K,class V>
	struct HashData
	{
		pair<K, V>_kv;
		Status _status = EMPTY;
	};
	
	template<class K ,class V,class Hash = HashFunc<K>>
	class HashTable
	{
	public:
	     //接口
	private:
		vector<HashData<K,V>>_tables; 
		size_t _n = 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

插入

根据上面我所说的规则，我们可以写出插入函数：

     // insert 1.0 版本
     bool Insert(const pair<K, V>& kv) {
			
			size_t index = kv.first % _tables.size();
			
			//如果当前位置有元素，就向后找，直到找到空状态位置
			while (_tables[index]._status == EXITS) {
				++index;
				//超出数组大小需要重头开始遍历
				index %= _tables.size(); 
			}
			
			_tables[index]._kv = kv;
			_tables[index]._status = EXITS;
			++_n;//有效元素个数加一
			
			return true;

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

但是，此时这个版本的插入函数是有巨大问题的：

闭散列的扩容问题

闭散列是不能存满的，如果存满，因为查找的结束标准是找到待查找数或者空状态位置。如果该数不存在，那么查找就陷入了死循环。

与此同时，当一个哈希表的大部分空间被填满之后，此时冲突的概率就会明显的增大，插入的效率也下降了，此时我们就需要对哈希表进行扩容。但这个扩容的时机具体是什么呢？

对此，c++对散列表提出来 载荷因子 这一概念：
在这里插入图片描述

除此之外，由于我们使用了vector容器来代替数组，虽然方便了许多，但是vector 的空间大小默认是0，所以我们还需要手动干预一下其初始化以及扩容的大小。

【C++】手把手教你写出自己的vector类

扩容的同时如何保证散列映射规则不变

知道了扩容的重要性之后，如何实现扩容又是另外一回事：

扩容之前，我们的映射公式是_table[i] %10,但是进行一次扩容之后，我们的映射公式变为_table[i]%20 ，如果我们只是单纯的把数据拷贝到一段更大的空间上，那么就是“事倍功半”，原来挤的地方还是拥挤（如下图）。

在这里插入图片描述
扩容之后，映射公式变为_table[i]%20，要重新计算元素位置，正确的分布应该是下图（示意图），这样才达到了减少冲突概率的目的。

所以我们直接开辟一个新表，将现有元素全部重新计算：

     //写法一：
     vector<HashData<K, V>>newTable;
	 newTable.resize(newSize); //newSize 为扩容后的size
	 for (size_t i = 0; i < _tables.size(); i++) {
			f (_tables[i].status == EXITS) {
				size_t index = _tables[i]._kv.first % newTable.size();
			}
	}
1
2
3
4
5
6
7
8

	
	//写法二(现代写法，推荐)：
	HashTable<K, V, Hash>newHT;
	newHT._tables.resize(newSize);
	for (auto& e : _tables) {
			if (EXITS == e._status) {
				newHT.Insert(e._kv);
			}
	}
	_tables.swap(newHT._tables);
1
2
3
4
5
6
7
8
9
10

由此，我们可以写出我们的 insert 2.0版本：

     // insert 2.0 版本
     bool Insert(const pair<K, V>& kv) {
            //避免冗余
            if(Find(kv.first)){
                return false
            }
            //扩容
			if (_tables.size() == 0 || _n*10 / _tables.size()>= 7) {
			
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				
				HashTable<K, V>newHT;
				newHT._tables.resize(newSize);
				for (auto& e : _tables) {
					if (EXITS == e._status) {
						newHT.insert(e._kv);//调用本身，但是 不是递归
					}
				}
				_tables.swap(newHT._tables);
			}
			
			size_t start = key % _tables.size();
			size_t i=0;
			size_t index = start+i; 
			while (_tables[index]._status == EXITS) {
				++i;
				index=start+i;
				index %= _tables.size(); 
			}
			_tables[index]._kv = kv;
			_tables[index]._status = EXITS;
			++_n;
			
			return true;

		}
	};
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

查找

         HashData<K,V>* Find(const K& key) {

			if (_tables.size() == 0) {
				return nullptr;
			}
			
			size_t start = key % _tables.size();
			size_t i=0;
			size_t index = start+i; 
			while (_tables[index]._status != EMPTY) {
				
				if (_tables[index]._kv.first == key
					&&_tables[index]._status== EXITS) {
					
					return &_tables[index];
				}
				else {
					++i;
					index=start+i;
					index %= _tables.size();
				}
			}
			return nullptr;
		}	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

删除

我们的删除实际上是“伪删除”，只是把值状态标记为“DELETE”即可

         bool Erase(const K& key) {

			HashData<K, V>* ret = Find(key);
			if (ret == nullptr) {
				return false;
			}
			else {
				ret->_status = DELETE;
				_n--;
				return true;
			}
	    }		
1
2
3
4
5
6
7
8
9
10
11
12

此时我们的闭散列已经比较完整了，但是还有一个重要的问题： 如果key值是string类型或者其他非int型数据的话，我们是无法取模的，那么我们如何使用散列表存储？

这个时候就要轮到仿函数登场了。
我们在哈希表HashTable的模板参数列表中添加一个仿函数，如果是整数，就是用默认的缺省参数，如果是string,就使用处理string 的仿函数。

template<class K ,class V,class Hash = HashFunc<K>>
1

之后我们在求取start的时候，就可以这样：

Hash hf;
size_t start =  hf(kv.first) % _tables.size();
1
2

默认的HashFunc, 如果key 是一个整数或者说可以隐式转换为整数（比如浮点数）就调用这个函数

    template<class K>
	struct HashFunc {

		size_t operator()(const K& key) {
			return key;
		}
	};
1
2
3
4
5
6
7

针对string类型的 HashFunc

我们将string 填入 HashTable依旧是用某种规则转化为整形，一般是将字符串的每个字符的ascall码之和作为key值。

同样的道理，如果数据是一个结构体类型，我们也是抽取一些特征数据去转化为整形，写成仿函数。

但是，字符串组合是无限的，整数（32位）是有限的，有限的整数不可能表示出无穷的情况。所以任何哈希算法都无法一定避免出现转型后的重复错误。但是，我们是有一些办法来减少这种错误的：
字符串Hash函数对比

简单来说，就是在相加过程中，乘以一个数，来进行打乱，具体的数学原理，不太清除:

 hash = hash * 131 + ch;   // 也可以乘以31、131、1313、13131、131313..  
1

     struct HashFuncString 
     
		size_t operator()(const string & key) {
			//BKDR Hash 思想
			size_t hash = 0;
			for (size_t i = 0; i < key.size(); ++i) {
				hash *= 131;
				hash += key[i];
			}
			return hash;
		}
	};
1
2
3
4
5
6
7
8
9
10
11
12

测试：

void TestHashTable2() {
		HashTable<string, string, HashFuncString>dict;
		dict.insert(make_pair("sort", "排序"));
		dict.insert(make_pair("insert", "插入"));
	}
1
2
3
4
5

但是，string类型的数据是很常见的，每次都要写仿函数会有些麻烦，所以我们可以借助模板的特化。

//特化
	template<>
	struct HashFunc<string> {

		size_t operator()(const string& key) {
			//BKDR Hash 思想
			size_t hash = 0;
			for (size_t i = 0; i < key.size(); ++i) {
				hash *= 131;
				hash += key[i];
			}
			return hash;
		}
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

完整的HashTable.h 代码

#pragma once
namespace close_hash
{
	enum Status
	{
		EMPTY,
	    EXITS,
		DELETE
	};
	template<class K,class V>
	struct HashData
	{
		pair<K, V>_kv;
		Status _status = EMPTY;
	};

	template<class K>
	struct HashFunc {

		size_t operator()(const K& key) {
			return key;
		}
	};

	//特化
	template<>
	struct HashFunc<string> {

		size_t operator()(const string& key) {
			//BKDR Hash 思想
			size_t hash = 0;
			for (size_t i = 0; i < key.size(); ++i) {
				hash *= 131;
				hash += key[i];
			}
			return hash;
		}
	};

	struct HashFuncString {

		size_t operator()(const string & key) {
			//BKDR Hash 思想
			size_t hash = 0;
			for (size_t i = 0; i < key.size(); ++i) {
				hash *= 131;
				hash += key[i];
			}
			return hash;
		}
		
	};

	template<class K ,class V,class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		bool Erase(const K& key) {

			HashData<K, V>* ret = Find(key);
			if (ret == nullptr) {
				return false;
			}
			else {
				ret->_status = DELETE;
				_n--;
				return true;
			}
		}

		HashData<K,V>* Find(const K& key) {

			if (_tables.size() == 0) {
				return nullptr;
			}
			Hash hf;
			size_t start = hf(key) % _tables.size();
			size_t i = 0;
			size_t index = start + i;
			while (_tables[index]._status != EMPTY) {
				
				if (_tables[index]._kv.first == key
					&&_tables[index]._status== EXITS) {

					return &_tables[index];
				}
				else {
					++i;
					index = start + i;
					index %= _tables.size();
				}
			}
			return nullptr;
			
		}

		bool insert(const pair<K, V>& kv) {
			if (Find(kv.first)) {
				return false;
			}
			if (_tables.size() == 0 || _n*10 / _tables.size()>= 7) {
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				/*vector<HashData<K, V>>newTable;
				newTable.resize(newSize);
				for (size_t i = 0; i < _tables.size(); i++) {
					if (_tables[i].status == EXITS) {

						size_t index = _tables[i]._kv.first % newTable.size();
					}
				}*/
				HashTable<K, V, Hash>newHT;
				newHT._tables.resize(newSize);
				for (auto& e : _tables) {
					if (EXITS == e._status) {
						newHT.insert(e._kv);
					}
				}
				_tables.swap(newHT._tables);
			}
			Hash hf;
			size_t start = hf(kv.first) % _tables.size();
			size_t i = 0;
			size_t index = start + i;

			while (_tables[index]._status == EXITS) {
				++i;
				index = start + i;

				index %= _tables.size();
			}
			
			_tables[index]._kv = kv;
			_tables[index]._status = EXITS;
			++_n;
			
			return true;

		}
	private:
		vector<HashData<K,V>>_tables;
		size_t _n = 0; //存储有效数据的个数
	};


	
	void TestHashTable2() {
		HashTable<string, string, HashFuncString>dict;
		dict.insert(make_pair("sort", "排序"));
		dict.insert(make_pair("insert", "插入"));
	}
}
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

2.4.1.3 二次探测

二次探测简介

线性探测虽然实现起来比较简单，但缺点也很明显：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“洪水冲突”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为： = ( H+i^2 )% m,或者： = ( H- i^2 )% m。其中：i = 1,2,3…，是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。对于下图中如果要插入44，产生冲突，使用解决后的情况为：
在这里插入图片描述

二次探测模拟实现

二次查找与线性探测的基本实现几乎一致，只需要在查找和插入的遍历部分做细微的调整即可，这里这届贴出代码：

#pragma once
namespace close_hash
{
	enum Status
	{
		EMPTY,
	    EXITS,
		DELETE
	};
	template<class K,class V>
	struct HashData
	{
		pair<K, V>_kv;
		Status _status = EMPTY;
	};

	template<class K>
	struct HashFunc {

		size_t operator()(const K& key) {
			return key;
		}
	};

	//特化
	template<>
	struct HashFunc<string> {

		size_t operator()(const string& key) {
			//BKDR Hash 思想
			size_t hash = 0;
			for (size_t i = 0; i < key.size(); ++i) {
				hash *= 131;
				hash += key[i];
			}
			return hash;
		}
	};

	struct HashFuncString {

		size_t operator()(const string & key) {
			//BKDR Hash 思想
			size_t hash = 0;
			for (size_t i = 0; i < key.size(); ++i) {
				hash *= 131;
				hash += key[i];
			}
			return hash;
		}
		
	};

	template<class K ,class V,class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		bool Erase(const K& key) {

			HashData<K, V>* ret = Find(key);
			if (ret == nullptr) {
				return false;
			}
			else {
				ret->_status = DELETE;
				_n--;
				return true;
			}
		}

		HashData<K,V>* Find(const K& key) {

			if (_tables.size() == 0) {
				return nullptr;
			}
			Hash hf;
			size_t start = hf(key) % _tables.size();
			size_t i = 0;
			size_t index = start + i;
			while (_tables[index]._status != EMPTY) {
				
				if (_tables[index]._kv.first == key
					&&_tables[index]._status== EXITS) {

					return &_tables[index];
				}
				else {
					++i;
					index = start + i * i;
					index %= _tables.size();
				}
			}
			return nullptr;
			
		}

		bool insert(const pair<K, V>& kv) {
			if (Find(kv.first)) {
				return false;
			}
			if (_tables.size() == 0 || _n*10 / _tables.size()>= 7) {
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				/*vector<HashData<K, V>>newTable;
				newTable.resize(newSize);
				for (size_t i = 0; i < _tables.size(); i++) {
					if (_tables[i].status == EXITS) {

						size_t index = _tables[i]._kv.first % newTable.size();
					}
				}*/
				HashTable<K, V, Hash>newHT;
				newHT._tables.resize(newSize);
				for (auto& e : _tables) {
					if (EXITS == e._status) {
						newHT.insert(e._kv);
					}
				}
				_tables.swap(newHT._tables);
			}
			Hash hf;
			size_t start = hf(kv.first) % _tables.size();
			size_t i = 0;
			size_t index = start + i;

			while (_tables[index]._status == EXITS) {
				++i;
				index = start + i * i;

				index %= _tables.size();
			}
			
			_tables[index]._kv = kv;
			_tables[index]._status = EXITS;
			++_n;
			
			return true;

		}
	private:
		vector<HashData<K,V>>_tables;
		size_t _n = 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
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

2.4.2 开散列

2.4.2.1 开散列简介

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中

在这里插入图片描述
显而易见，开散列的每个桶中存储的都是发生了哈希冲突的元素。

2.4.2.2 开散列模拟实现

开散列的定义

在散列表（即数组）中我们虽然存储了头节点，但是这个头结点不存储数据的，我们把数据同一挂在外面。

template<class K,class V>
	struct HashNode {
		pair<K, V>_kv;
	    HashNode<K,V> * _next;

		HashNode(const pair<K,V>& kv)
			:_kv(kv),
			_next(nullptr)
		{}
	};
	template<class K,class V,class Hash = HashFunc<K>>
	class HashTable {
		typedef HashNode<K, V> Node;
	public:
        //接口
	private:
	    vector<Node*>_tables;
	    int _n;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

插入

bool Insert(const pair<K, V>& kv) {
            Hash hf;
			//当负载因子到1的时候，进行扩容
			if (_n == _tables.size()) {

				size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				vector<Node*>newtables;
				newtables.resize(newsize, nullptr);
				//遍历原表
				for (size_t i = 0; i < _tables.size(); i++) {
					Node* cur = _tables[i];
					while (cur) {
						Node* next = cur->_next;
						size_t index = hf(cur->_kv.first) % newsize;
						cur->_next = newtables[index];
						newtables[index] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				newtables.swap(_tables);

			}

			
			size_t index = hf(kv.first) % _tables.size();
			Node* cur = _tables[index];
			while (cur) {
				if (cur->_kv.first == kv.first) {
					return false;
				}
				else {
					cur = cur->_next;
                 }
			}
			
			Node* newnode = new Node(kv);
			//头插
			newnode->_next = _tables[index];
			_tables[index] = newnode;
			++_n;

			return true;
		}
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

可以看出 Insert的基本思路很简单，这要注意几点：

桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容
扩容的时候，我们通过遍历原表的每一个桶，不需要拷贝，而是直接将节点指针重定向到新表的相应位置上，但是要记得把原表的头指针置空。
插入的时候既可以选择头插，也可以尾插，但是推荐头插，可以减少一个找尾的过程。

拓展
很多文章与数据有一个观点，除留余数法，最好模一个素数，虽然数学证明不太懂，但是这里依旧介绍一下：

我们可以把Insert改进成这样：

我们在扩容的时候将现有的表长传入 GetNextPrime ,获取一个比当前表长大的质数作为 newsize. 同时，我们发现，这样扩容每次也是约等于两倍。

        
        size_t GetNextPrime(size_t prime){
	        const int PRIMECOUNT = 28;
			const size_t primeList[PRIMECOUNT] =
			{
				53ul, 97ul, 193ul, 389ul, 769ul,
				1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
				49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
				1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
				50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
				1610612741ul, 3221225473ul, 4294967291ul
			};

			size_t i = 0;
			for (; i < PRIMECOUNT; ++i)
			{
				if (primeList[i] > primeList[i])
					return primeList[i];
			}
			return primeList[i];
		}
		
        bool Insert(const pair<K, V>& kv) {
             Hash hf;
			//当负载因子到1的时候，进行扩容
			if (_n == _tables.size()) {

				//size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				size_t newSize = GetNextPrime(_tables.size());
				vector<Node*>newtables;
				newtables.resize(newsize, nullptr);
				//遍历原表
				for (size_t i = 0; i < _tables.size(); i++) {
					Node* cur = _tables[i];
					while (cur) {
						Node* next = cur->_next;
						size_t index = hf(cur->_kv.first) % newsize;
						cur->_next = newtables[index];
						newtables[index] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				newtables.swap(_tables);

			}

			
			size_t index = hf(kv.first) % _tables.size();
			Node* cur = _tables[index];
			while (cur) {
				if (cur->_kv.first == kv.first) {
					return false;
				}
				else {
					cur = cur->_next;
                 }
			}
			
			Node* newnode = new Node(kv);
			//头插
			newnode->_next = _tables[index];
			_tables[index] = newnode;
			++_n;

			return true;
		}
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

查找

	     Node* Find(const K& key) {

			if (_tables.size() == 0) {
				return nullptr;
			}
			Hash hf;
			size_t index = hf(key) % _tables.size();
			Node* cur = _tables[index];

			while (cur) {
				if (cur->_kv.first == key) {
					return cur;
				}
				else {
					cur = cur->_next;
				}
			}
			return nullptr;

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

删除

         bool Erase(const K& key) {
			if (_tables.size() == 0) {
				return false;
			}
			Hash hf;
			//素数
			size_t index = hf(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[index];
			while (cur) {
				if (cur->_kv.first == key) {
					// 1. cur是第一个节点
					// 2. cur是非头结点
					if (prev == nullptr) {
						_tables[index] = cur->_next;	
					}
					else {
						prev->_next = cur->next;
					}
                    delete cur;
					--_n;
					return true;
				}
				else {
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;

		}
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

完整代码：

//开散列模拟实现
namespace bucket_hash {

	template<class K,class V>
	struct HashNode {
		pair<K, V>_kv;
	    HashNode<K,V> * _next;

		HashNode(const pair<K,V>& kv)
			:_kv(kv),
			_next(nullptr)
		{}
	};
	template<class K>
	struct HashFunc {

		size_t operator()(const K& key) {
			return key;
		}
	};

	//特化
	template<>
	struct HashFunc<string> {

		size_t operator()(const string& key) {
			//BKDR Hash 思想
			size_t hash = 0;
			for (size_t i = 0; i < key.size(); ++i) {
				hash *= 131;
				hash += key[i];
			}
			return hash;
		}
	};

	struct HashFuncString {

		size_t operator()(const string& key) {
			//BKDR Hash 思想
			size_t hash = 0;
			for (size_t i = 0; i < key.size(); ++i) {
				hash *= 131;
				hash += key[i];
			}
			return hash;
		}

	};

	template<class K,class V, class Hash = HashFunc<K>>
	class HashTable {
		typedef HashNode<K, V> Node;
	public:
		//拷贝构造

		//赋值

		//析构函数：清理桶
		~HashTable() {
			for (size_t i = 0; i < _tables.size(); i++) {
				Node* cur = _tables[i];
				while (cur) {
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}
		
		size_t GetNextPrime(size_t prime)
		{
	        const int PRIMECOUNT = 28;
			const size_t primeList[PRIMECOUNT] =
			{
				53ul, 97ul, 193ul, 389ul, 769ul,
				1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
				49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
				1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
				50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
				1610612741ul, 3221225473ul, 4294967291ul
			};

			size_t i = 0;
			for (; i < PRIMECOUNT; ++i)
			{
				if (primeList[i] > primeList[i])
					return primeList[i];
			}
			return primeList[i];
		}

		bool Erase(const K& key) {
			if (_tables.size() == 0) {
				return false;
			}
			Hash hf;
			//素数
			size_t index = hf(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[index];
			while (cur) {
				if (cur->_kv.first == key) {
					// 1. cur是第一个节点
					// 2. cur是非头结点
					if (prev == nullptr) {
						_tables[index] = cur->_next;	
					}
					else {
						prev->_next = cur->next;
					}
                    delete cur;
					--_n;
					return true;
				}
				else {
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;

		}
		Node* Find(const K& key) {

			if (_tables.size() == 0) {
				return nullptr;
			}
			Hash hf;
			size_t index = hf(key) % _tables.size();
			Node* cur = _tables[index];

			while (cur) {
				if (cur->_kv.first == key) {
					return cur;
				}
				else {
					cur = cur->_next;
				}
			}
			return nullptr;

		}
		bool Insert(const pair<K, V>& kv) {

			//当负载因子到1的时候，进行扩容
			if (_n == _tables.size()) {

				//size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				size_t newSize = GetNextPrime(_tables.size());
				vector<Node*>newtables;
				newtables.resize(newsize, nullptr);
				//遍历原表
				for (size_t i = 0; i < _tables.size(); i++) {
					Node* cur = _tables[i];
					while (cur) {
						Node* next = cur->_next;
						size_t index = cur->_kv.first % newsize;
						cur->_next = newtables[index];
						newtables[index] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				newtables.swap(_tables);

			}

			Hash hf;
			size_t index = hf(kv.first) % _tables.size();
			Node* cur = _tables[index];
			while (cur) {
				if (cur->_kv.first == kv.first) {
					return false;
				}
				else {
					cur = cur->_next;
                 }
			}
			
			Node* newnode = new Node(kv);
			//头插
			newnode->_next = _tables[index];
			_tables[index] = newnode;
			++_n;

			return true;
		}
	private:
		vector<Node*>_tables;
		size_t _n = 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
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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194

3. 模拟实现

3.1 HashMap 的改造与完善

在选择哈希表的时候我们选择使用开散列实现。

当然，我们之前写的哈希表还不能直接用。我们还需要进行改造。

将HashTable的类型改为模板型参数。
给HashMap增加迭代器

//开散列
namespace bucket_hash {

	template<class T>
	struct HashNode {
		T _data;
	    HashNode<T> * _next;

		HashNode(const T& data)
			:_data(data),
			_next(nullptr)
		{}
	};
	template<class K>
	struct HashFunc {

		size_t operator()(const K& key) {
			return key;
		}
	};

	//特化
	template<>
	struct HashFunc<string> {

		size_t operator()(const string& key) {
			//BKDR Hash 思想
			size_t hash = 0;
			for (size_t i = 0; i < key.size(); ++i) {
				hash *= 131;
				hash += key[i];
			}
			return hash;
		}
	};

	struct HashFuncString {

		size_t operator()(const string& key) {
			//BKDR Hash 思想
			size_t hash = 0;
			for (size_t i = 0; i < key.size(); ++i) {
				hash *= 131;
				hash += key[i];
			}
			return hash;
		}

	};
    //前置声明
	template<class K, class T, class Hash, class KeyOfT>
	class HashTable;

	template<class K,class T,class Hash,class KeyOfT>
	struct  HTIterator
	{
		typedef HashNode<T> Node;
		typedef HashTable<K, T, Hash, KeyOfT>HT;
		typedef HTIterator<K, T, Hash, KeyOfT> Self;
		
		Node* _node;
		HT* _ht;

		HTIterator(Node* node,HT* ht)
			:_node(node)
			,_ht(ht)
		{}

		bool operator !=(const Self& s)const {
			return _node != s._node;
		}

		T& operator*() {
			return _node->_data;
		}

		T* operator ->() {
			return &_node->_data;
		}

	    Self  operator++() {
			if (_node->_next) {
				//在当前桶中找
				_node = _node->_next;
			}
			else {
				//找下一个桶
				KeyOfT kot;
				const K& key = kot(_node->_data);
				Hash hf;
				size_t index = hf(key) % _ht->_tables.size();
				++index;
				while (index < _ht->_tables.size()) {

					if (_ht->_tables[index]) {

						_node = _ht->_tables[index];
						break;
					}
					else {
						++index;
					}
				}

				//后面没有桶了
				if (index == _ht->_tables.size()) {
					_node = nullptr;
				}
				
			}
			return *this;
		}
	};



	template<class K,class T, class Hash ,class KeyOfT>
	class HashTable {
		typedef HashNode<T> Node;

		template<class K, class T, class Hash, class KeyOfT>
		friend struct HTIterator;

	public:
		typedef HTIterator<K, T, Hash, KeyOfT> iterator;

		iterator begin() {
			for (size_t i = 0; i < _tables.size(); ++i) {
				if (_tables[i]) {
					return iterator(_tables[i], this);//this是HashTable的指针
				}
			}
			return end();
		}

		iterator end() {
			return iterator(nullptr, this);
		}

		//拷贝构造

		//赋值

		//析构函数：清理桶
		~HashTable() {
			for (size_t i = 0; i < _tables.size(); i++) {
				Node* cur = _tables[i];
				while (cur) {
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}
		
		size_t GetNextPrime(size_t prime)
		{
	        const int PRIMECOUNT = 28;
			static const size_t primeList[PRIMECOUNT] =
			{
				53ul, 97ul, 193ul, 389ul, 769ul,
				1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
				49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
				1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
				50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
				1610612741ul, 3221225473ul, 4294967291ul
			};

			size_t i = 0;
			for (; i < PRIMECOUNT; ++i)
			{
				if (primeList[i] > prime)
					return primeList[i];
			}
			return primeList[i];
		}

		bool Erase(const K& key) {
			if (_tables.size() == 0) {
				return false;
			}
			Hash hf;
			KeyOfT kot;

			//素数
			size_t index = hf(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[index];
			while (cur) {
				if (kot(cur->_data) == key) {
					// 1. cur是第一个节点
					// 2. cur是非头结点
					if (prev == nullptr) {
						_tables[index] = cur->_next;	
					}
					else {
						prev->_next = cur->next;
					}
                    delete cur;
					--_n;
					return true;
				}
				else {
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;

		}
		Node* Find(const K& key) {

			if (_tables.size() == 0) {
				return nullptr;
			}
			Hash hf;
			KeyOfT kot;
			size_t index = hf(key) % _tables.size();
			Node* cur = _tables[index];

			while (cur) {
				if (kot(cur->_data) == key) {
					return cur;
				}
				else {
					cur = cur->_next;
				}
			}
			return nullptr;

		}

		pair<iterator , bool> Insert(const T& data) {
            Hash hf;
			KeyOfT kot;
			//当负载因子到1的时候，进行扩容
			if (_n == _tables.size()) {

				//size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				size_t newsize = GetNextPrime(_tables.size());
				vector<Node*>newtables;
				newtables.resize(newsize, nullptr);
				//遍历原表
				for (size_t i = 0; i < _tables.size(); i++) {
					Node* cur = _tables[i];
					while (cur) {
						Node* next = cur->_next;

						const K& key = kot(cur->_data);
						size_t index = hf(key) % newsize;

						cur->_next = newtables[index];
						newtables[index] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				newtables.swap(_tables);

			}

			const K& key = kot(data);
			size_t index = hf(key) % _tables.size();
			Node* cur = _tables[index];
			while (cur) {
				if (kot(cur->_data) == kot(data)) {
					return make_pair(iterator(cur, this), false);
				}
				else {
					cur = cur->_next;
                 }
			}
			
			Node* newnode = new Node(data);
			//头插
			newnode->_next = _tables[index];
			_tables[index] = newnode;
			++_n;

			return make_pair(iterator(newnode, this), true);
		}
	private:
		vector<Node*>_tables;
		size_t _n = 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
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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290

3.2 unordered_map 的模拟实现

#pragma once
#include"HashTable.h"

namespace yyk {

	template<class K, class V, class Hash = bucket_hash::HashFunc<K>>
	class unordered_map
	{

		struct MapKeyOfT
		{
			const K& operator()(const pair<const  K, V>& kv)const {
				return kv.first;
			}
		};
	public:
		typedef typename bucket_hash::HashTable<K, pair<const K, V>, Hash, MapKeyOfT>::iterator iterator;
		iterator begin() {
			return _ht.begin();
		}

		iterator end() {
			return _ht.end();
		}

		V& operator [](const K& key) {
			pair<iterator, bool>ret = insert(make_pair(key, V()));
			return ret.first->second;
		}

		pair<iterator,bool> insert(const pair<const K, V>& kv) {
			return _ht.Insert(kv);
		}
	private:
		bucket_hash::HashTable<K, pair<const K, V>, Hash, MapKeyOfT>_ht;
	};

	void test_unorderd_map() {
		unordered_map<string, string >dict;
		dict.insert(make_pair("sort", "排序"));
		dict.insert(make_pair("string", "字符串"));
		dict.insert(make_pair("map", "地图"));
		dict["end"] = "结束";
		auto it = dict.begin();
		while (it != dict.end()) {
			cout << it->first << " " << it->second << endl;
			++it;
		}
	}
}
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

3.3 unorderd_set的模拟实现

#pragma once
#include"HashTable.h"

namespace bit {

	template<class K, class Hash = bucket_hash::HashFunc<K>>
	class unordered_set
	{
	public:
		struct SetKeyOfT
		{
			const K& operator()(const K& key)const {
				return key;
			}
		};
	public:
		typedef typename bucket_hash::HashTable<K, K, Hash, SetKeyOfT>::iterator iterator;

		iterator begin() {
			return _ht.begin();
		}
		iterator end() {
			return _ht.end();
		}
		pair<iterator, bool> insert(const K& key) {
			return _ht.Insert(key);
		}
	private:
		bucket_hash::HashTable<K, K, Hash, SetKeyOfT>_ht;
	};

	void test_unordered_set() {

		unordered_set<int>s;
		s.insert(3);
		s.insert(4);
		s.insert(5);
		s.insert(3);
		s.insert(1);
		s.insert(2);
		s.insert(6);
		s.insert(16);
		s.insert(26);
		s.insert(36);

		unordered_set<int>::iterator it = s.begin();
		while (it != s.end()) {
			cout << *it << " ";
			++it;
		}
		cout << 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

4. 哈希的应用

4.1 位图

4.1.1 背景引入

我们先来看一道面试题：

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

我们很容易想到排序(O(nlogN))+二分查找(log N) 的方法,但是，40一个无符号整形大概占有了16GB的空间，显然我们无法申请16GB的数组。那set就更别说了，一个节点不只存有一个整形。

这时候我们只有使用位图：

这里我们不需要真正的存储这些值，只需要知道这些数据是否在容器中。数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。
在这里插入图片描述

我们使用2^32个bit位去映射，那么只需要约0.5GB(512MB)的空间。

4.1.2 位图的使用

c++中提供了bitset库。对于具体的接口可以自行了解。

在这里插入图片描述
其中比较常用的接口有三个：

set

如果我们不传参，默认把所有位置1，如果传n,则把第n位置1；
在这里插入图片描述

reset

如果我们不传参，默认把所有位置0，如果传n,则把第n位置0；

test

查看当前位是1还是0，如果是1，则返回true,反之为0
在这里插入图片描述

4.1.3模拟实现

清楚了bitset的原理我们可以模拟实现一下，我们就将上面的三个接口实现：

template<size_t N>
		class bitset
		{
		public:
	
			bitset() {
				_bits.resize(N / 8 + 1, 0);
			}
	
			//把x映射的比特位设置为1
			void set(size_t x) {
				//计算出它在第i个char对象中
				size_t i = x / 8;
				//计算出它在该char的第j个bit为中
				size_t j = x % 8;
	
				_bits[i] |= 1 << j; //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));
			}
	private:
		vector<char>_bits;
	};
    
    //测试
    void TestBitSet() {
		bitset<10>bs;
		bs.set(4);
		cout << bs.test(4) << endl;
		bs.reset(4);
		cout << bs.test(4) << 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

4.1.4 位图的应用

问题1

给定100亿个整数，设计算法找到只出现一次的整数？

对于这道题我们的思路依旧是使用位图解决，但是会稍有变化，相比于在与不在，“只出现一次”代表着位图中的数据对应了三种情况：不在，一次，多次。那么此时一个bit位来表示三个状态就力不从心了，所以我们使用两个bit位来对应一个整数，00表示不在，01表示出现一次，10表示出现多次。

关于所需的内存大小，也很好估计，虽然有一百一个数，但整形上限是43亿不到，所以预计需要1GB的空间。

如果我们想使用代码实现，又该如何做呢？

按照我们之前实现bitset的思路，我们要将1bit的存储单元改为 2bit，说实话，这样会比较麻烦，所以我们使用另一个思路： 双bitset法

我们使用两个bitset,对应位就可以表示一个整数状态了。
在这里插入图片描述

    template<size_t N>
	class FindOnceValueSet
	{
	public:
		void set(size_t x) {

			bool flag1 = _bs1.test(x);
			bool flag2 = _bs2.test(x);

			//00 -> 01
			if (flag1 == false && flag2 == false) {
				_bs2.set(x);
			}
			//01 ->10
			else if (flag1 == false && flag2 == true) {
				_bs2.set(x);
				_bs2.rset(x);
			}
			//10 -> 10 不处理，表示已经出现多次
			else {

			}
		}
        
		void printf_once_num() {
			for (size_t i = 0; i < N; ++i) {
				if (_bs1.test(i) == false && _bs2.test(i) == true) {
					cout << i << endl;
				}
			}
		}
	private:
		bitset<N>_bs1;
		bitset<N>_bs2;
	};
	
	//测试
	void TestFindOnceValSet() {
		int a[] = { 1,20,30,43,5,4,1,43,43,7,9 };
		FindOnceValueSet<100>fovs;
		for (auto e : a) {
			fovs.set(e);
		}
		fovs.printf_once_num();
	}
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

问题2

给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

我们使用两个 bitset，如果对应位都是1，那么就是相交整数。

问题3

位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

这题和题目1思路相同，只是这题的整数有四个状态，不在（00），一次（01），两次（10），两次以上（11）。

4.2 布隆过滤器

4.2.1 布隆过滤器简介

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

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，这样可以尽量的减少哈希冲突。
虽然我们无论如何都无法保证该元素一定在位图中，但是如果某位为空，那么我们可以说对应的元素一定是不存在于位图上的。所以，布隆过滤器也常用于只需要判断元素一定不在的场景。

在这里插入图片描述

4.2.2 布隆过滤器的模拟实现

插入 Set
我们分别用三个哈希算法（或者更多）将字符串转化为三个整数，再取模，将对应的位设置为1
查找 Test
分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中

#pragma once
#include"bitset.h"

namespace yyk {

	struct HashStr1 {
		size_t operator()(const string& s) {

			//BKDR
			size_t hash = 0;
			for (size_t i = 0; i < s.size(); i++) {
				hash *= 131;
				hash += s[i];
			}
			return hash;
		}
	};
	struct HashStr2 {
		size_t operator()(const string& s) {

			size_t hash = 0;
			for (size_t i = 0; i < s.size(); i++) {
				hash *= 65599;
				hash += s[i];
			}
			return hash;
		}
	};
	struct HashStr3 {
		size_t operator()(const string& s) {

			size_t hash = 0;
			//RSHash
			size_t magic = 63689;
			for (size_t i = 0; i < s.size(); i++) {
				hash *= magic;
				hash += s[i];
				magic *= 378551;
			}
			return hash;
		}
	};
	//N表示最多插多少个值
	template<size_t N, class K = string,
		class Hash1 = HashStr1,
		class Hash2 = HashStr2,
		class Hash3 = HashStr3>
		class BloomFilter
	{
	public:
		bool Test(const K& key) {

			
			size_t index1 = Hash1()(key)%len;
			if (_bs.test(index1) == false) {
				return false;
			}
			size_t index2 = Hash2()(key) % len;
			if (_bs.test(index2) == false) {
				return false;
			}
			size_t index3 = Hash3()(key) % len;
			if (_bs.test(index3) == false) {
				return false;
			}

			return true; //这里是不准确的，可能存有冲突


		}
		bool Set(const K& key) {
			
			size_t index1 = Hash1() % len;
			size_t index2 = Hash2() % len;
			size_t index3 = Hash3() % len;

			_bs.set(index1);
			_bs.set(index2);
			_bs.set(index3);
		}
		//一般情况下不支持删除，可能会导致冲突
		// 如果要实现删除，标记不再使用一个比特位，可以使用多个比特位，进行计数
		//多少个值映射该位置
		//但这种做法对会导致内存消耗加大

		//bool Reset(const K& key) 


	private:
		bit::bitset<6*N>_bs;
		size_t len = 6 * N;
	};


}
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

4.2.3 如何选择哈希函数与布隆过滤器的长度

布隆过滤器的长度太短，容易产生大量冲突，造成大量误判。布隆过滤器的长度太长，又会导致空间的浪费

同时，哈希函数的个数也需要权衡，个数越多布隆过滤器bit位1的速度越慢，布隆过滤器效率越低。反之误报率提高。

我们设 k为哈希函数个数，m为布隆过滤器长度，n为插入元素的个数，p为误报率。

在这里插入图片描述
按照我们之前的模拟实现，k=3, 则大概有 *m=4.2 n

也就是说，布隆过滤器的长度至少是插入元素的最大数目的 4.2倍的时候，我们的误报率才会在一个可接受的范围内。在上面的模拟实现时，我选择了6 作为倍数。

不过这里由于我们选择的m的数据类型是size_t ,上限约为43亿，按照m=6*n,此时可插入的数据个数最多不能超出8亿。所以此时我们可以将m的类型改为unsigned long long ,或者增加一些vector容器，分段存储。

4.2.4 布隆过滤器删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素.

一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作

缺陷：

无法确认元素是否真正在布隆过滤器中
存在计数回绕

4.2.5 布隆过滤器优点

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

4.2.6 布隆过滤器缺陷

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

5. 海量数据处理

5.1 哈希切割

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？与上题条件相同，如何找到top K的IP？

这里我们处理的是字符串，所以位图（只能处理整数）就无能为力了。

这里大文件不能统计次数，要想办法分成小文件，但是不能平均切分，平均切分统计不出字数，这里需要进行哈希切分：

先创建100个小文件，然后读取100G long file,0.txt,1.txt…99.txt。依此获得每一个ip,用一个字符串哈希算法，把ip转化为整形（比如BKDR，size_t num =BKDRHash(ip)%100），然后这个ip就进入 num.txt号小文件,依此对所有ip,进行处理，进入对应的小文件。

依此读取每一个小文件，比如先读取0.txt中的ip,map<string,int >统计次数。这里的ip的次数就是其最终的次数（相同的ip一定在同一个小文件），然后再clear掉map中的值，再读取1.txt，继续统计次数，不断走下去。

要找top K 的ip再建立一个k个数的小堆即可。

此时如果某个小文件过大，可以再次切分，继续统计。

给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法

假设一个query大约20byte,100亿个query 大概2000亿byte,10亿字节约 1G, 所以一个文件总共约大概200G.

依此读取A的文件中的query,然后使用字符创，哈希算法转化为整形，size_t val = HashStr(query);
size_t i = val%200,这个query 就进入Ai.txt 号小文件.

在这里插入图片描述

Ai.txt 读进一个setA，Bi.txt 读进一个setB,setA与setB 中相同的就是把交集。

5.2 位图应用

之前讲过了，就不再重复了。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/452256?site

【C++】手把手教你实现自己的unordered_map 和unordered_set_如何实现std::unordered_map

目录

1. unordered系列关联式容器

1.1 unordered_map

1.1.1 unordered_map 简介

1.1.2 unordered_map 接口说明

1.2 unordered_set

1.2.1 unordered_set 简介

1.2.2 unordered_set 接口说明

2. 底层结构

2.1 哈希简介

2.2 哈希冲突

2.3 哈希函数

2.4 哈希冲突的解决

2.4.1 闭散列

2.4.1.1 闭散列简介

2.4.1.2 线性探测

线性探测简介

线性探测 模拟实现

2.4.1.3 二次探测

二次探测简介

二次探测 模拟实现

2.4.2 开散列

2.4.2.1 开散列简介

2.4.2.2 开散列模拟实现

3. 模拟实现

3.1 HashMap 的改造与完善

3.2 unordered_map 的模拟实现

3.3 unorderd_set的模拟实现

4. 哈希的应用

4.1 位图

4.1.1 背景引入

4.1.2 位图的使用

4.1.3模拟实现

4.1.4 位图的应用

问题1

问题2

问题3

4.2 布隆过滤器

4.2.1 布隆过滤器简介

4.2.2 布隆过滤器 的模拟实现

4.2.3 如何选择哈希函数 与 布隆过滤器的长度

4.2.4 布隆过滤器删除

4.2.5 布隆过滤器优点

4.2.6 布隆过滤器缺陷

5. 海量数据处理

5.1 哈希切割

5.2 位图应用

线性探测模拟实现

二次探测模拟实现

4.2.2 布隆过滤器的模拟实现

4.2.3 如何选择哈希函数与布隆过滤器的长度