C++【unordered_map/set的底层实现-哈希表】—含有源代码_unordered_map底层实现

前言

前面讲了STL中的map和set容器以及封装实现，虽然它们的查找效率是O(logN)，但是当红黑树中的节点非常多时，因为红黑树不是严格平衡，树的高度可能变得很大，就是一变高一边低的情况，这会导致查询操作的时间复杂度变为O(N)，所以后面就出现了四个unordered系列的关联式容器，最常用的是unordered_map和unordered_set。

一、unordered_map/unordered_set容器

（1）unordered_map容器介绍及使用

unordered_map容器介绍：
它是以存储<key, value>键值对的方式去存储数据，可以高效地根据单个key值遭到对应的value。key是唯一的，kay和value的类型可以不相同。 另外，它存储元素是没有顺序的，它根据key的哈希值，相同哈希值的键值对放在相同的桶中，所以单个查找很高效，是在常数范围内，但它要查询某一范围内的key值在时要比map效率低，为什么？
因为它内部元素的排列顺序是不稳定的，这使得它的迭代器不能支持对元素子集进行稳定的顺序遍历，或者说它的迭代顺序是不可预测的，比如想遍历所有成绩等于某一值的学生，可以找到，因为它内部的哈希表不支持元素的稳定排序，因此找到的学生的顺序是不可预测的。
unordered_map也实现了直接访问操作符即operator[]，它允许使用key作为参数直接访问value。而且key是不允许被修改，元素值可以被修改。
最重要的一点：它们的值是通过其键的相对位置来找，并不是绝对位置
接口使用：
构造：

构造一个空容器：
unordered_map<string, char> mp1;
拷贝构造一个容器：
unordered_map<string, char> mp2(mp1);
使用迭代器区间构造一个容器：
unordered_map<string, char> mp2(mp1.begin(), mp1.end());

接口函数：

bool empty() const：检测是否为空
size_t size() const：获取有效元素个数
begin：返回unordered_map第一个元素的迭代器位置
end：返回unordered_map最后一个元素下一个位置的迭代器
cbegin：返回unordered_map第一个元素的const迭代器
cend：返回unordered_map最后一个元素下一个位置的const迭代器
iterator find(const K& key)：返回key在哈希桶中的位置
size_t count(const K& key) ：返回哈希桶中关键码为key的键值对的个数
insert：向容器中插入键值对
erase：删除容器中的键值对
void clear ：清空容器中的有效元素个数
void swap(unordered map&)：交换两个容器中的元素

元素访问：

operator[ ] 返回与key对应的value，没有一个默认值

简单介绍一下[ ]的重载，该函数实际调用哈希桶的插入操作，用参数key与V()构造一个默认值向底层哈希桶中插入，后面的哈希桶在后面说。如果key不在哈希桶中，插入成功，返回V()，若key已经在哈希桶中，插入失败，将key对应的value返回。和map实现的[]一样。
接口使用：

begin：获取容器中第一个元素的正向迭代器
end：获取容器中最后一个元素下一个位置的正向迭代器
insert：插入指定元素
erase：删除指定元素
find：查找指定元素
size：获取容器中元素的个数
clear：清空容器
swap：交换两个容器中的数据
count：获取容器中指定元素值的元素个数

（2）unordered_set容器介绍及使用

unordered_set容器：
它不再以键值对方式去存储数据，变成了直接存储，没有重复元素，且不会对内部存储的数据进行排序，平均时间复杂度为常数。unordered_set中元素的值也是唯一标识它的键，键不可改变，所以它里面的元素在容器不能被修改。
同样：它们的值是通过其键的相对位置来找，并不是绝对位置

（3）它们和map/set对比

unordered_map和unordered_set以及map和set，都是不允许插入重复的元素的，当尝试插入一个已经存在于容器中的关键字或元素时，它们都不会插入成功。unordered_map和map可以允许插入多个元素值相同，但键(key)不同的元素。
unordered_map/unordered_set和map/set区别：
1、实现不同：前者底层是用哈希表实现的，后者使用红黑树实现
2、性能不同：前者不按键值排序，插入时间复杂度是O(logN),查找时间复杂度是O(1)，后者按键值排序，插入时间是Olog(logN)，查找时间复杂度是O(logN)

二、容器底层结构

（1）哈希表概念

哈希背景:
前面也提到过，平衡树查找效率一般为O(logN)，红黑树如果发生大两插入有可能退化为O(logN)，而且顺序查找时间复杂度为O(N)，这是因为元素关键码与存储位置之间没有对应关系，因此在查找一个元素时，必须要经过key的多次比较，搜索的效率取决于查找过程中元素的比较次数，现在要使查找效率更高效，找到了一种更优的结构，能一次找到要查找的元素并不经过任何比较，使复杂度为O(1)，而这种结构叫哈希表。
哈希表概:通过某种函数使元素的存储位置与它的关键码之间能够建立一 一映射的关系，那在查找时通过该函数可以很快找到该元素(就像数组一样通过下标找到元素，只不过这里的下标是绝对位置)这种方法叫哈希方法，哈希方法中用的转换函数称为哈希函数或散列函数，构造出来的结构叫哈希表。
哈希本质就上一种映射的算法思想，是一种转换。
unordered系列的关联式容器效率高的原因，是因为其底层使用了哈希结构，哈希表的关键字是通过哈希函数计算得到的，并且哈希函数是将关键字映射到一个桶中，桶中的元素通过链表或其他数据结构连接起来。
**哈希表举例：**例如：数据集合{11，17，16，14，15，19}；
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。如下图：

2种常见的哈希函数：
直接定址法
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点简单、均匀，但去欸但需要事先知道关键字的分布情况，适合查找比较小且连续的情况。
2. 除留余数法
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址。可以节省空间。

（2）哈希冲突

但是对于上面的哈希表，如果要存的元素是1，7就会发生冲突，它们映射到一同个位置，就发生冲突，这种冲突叫哈希冲突或哈希碰撞，含义是不同关键字通过相同哈希哈数计算出相同的哈希地址。

（3）解决哈希冲突

解决哈希冲突的方法有两种方法，分别为闭散列和开散列。
闭散列：
闭散列也叫开放定址法，当有哈希冲突时，如果哈希表未被填满，说明在哈希表中必然还有空位置，这样可以把key存放到冲突位置中的“下一个” 空位置中去，这里下一个带引号，表示并不是相邻的，因为相邻也可能有元素。
也就是说在自己的开放空间去找下一个位置，如果去找？
一种思路叫线性探测，这种方法很暴力，从当前位置往后去找，直到寻找到下一个空位置为止。但是一些相邻聚集位置连续冲突容易形成踩踏，踩踏就是访问别人的位置。可以这样减少踩踏：如果·哈希函数是hash=Key%len，计算出后+i(i>=1,1,2,3…)也可以+i^2(i>=1,1,2,3…)，但是二次探测还是不能解决踩踏。
如果插入的时候，先通过哈希函数获取插入新元素在哈希表中的位置，然后如果该位置中没有元素，就插入新元素，反之发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。如图：

如果删除，在闭散列方法种不能随意删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素17，如果直接删除掉，7查找起来可能会受影响，所以线性探测采用标记的伪删除法来删除一个元素。比如在哈希表给每个空间做个标记，增加一种枚举类型表示三种状态：enum State{EMPTY, EXIST, DELETE};含义：EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除。

开散列：
开散列法又叫链地址法或开链法，这是解决哈希冲突的最优方法，首先对key集合用散列函数计算散列地址，具有相同地址的key归于同一子集合，每一个子集合叫做一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。如下图：

三、闭散列模拟实现

我们先要key和存储位置建立关联关系。我们采用线性探测就是依次找后面的位置存储。

（1）节点

#include<vector>
namespace nza
{
	enum State
	{
		EMPTY,
		EXIST,
		DELETE
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};
	template<class K, class V>
	class HashTable
	{
	private:
		vector<HashData<K,V>>_tables;
		size_t _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

需要enum，每个存储位置的标识符，
再来个结点，存数据的节点和状态，转台初始化为空
我们用vector来存hash节点，这样也方便扩容。
_n 表示存储数据的个数

（2）插入

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> newt;
				newt._tables.resize(newsize);

					for (auto& data : _tables)
					{
						if (data._state == EXIST)
						{
							newt.Insert(data._kv);
						}
					}
					_tables.swap(newt._tables);

			}
			size_t hashi = kv.first % _tables.size();
			size_t i = 1;
			size_t index = hashi;
			while (_tables[index]._state == EXIST)
			{
				index = hash + i;
				index %= _tables.size();
				++i;
			}
			_tables[index]._kv = kv;
			_tables[index]._state = EXIST;
			++_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

开始的newsize是我们要扩容多少，看是否等同于0，如果等于0先给个初始值多少都是可以，

先看最下面的线性探测：我先算起始位置hashi，即存储位置，用hash函数通过key去计算，这里我们要不能用capacity，因为这里会越界，[]会去检查下表小于size，上面说_n是有效数据个数，而_n之外我们不能去访问，所以要%size，然后用while循环判断，如果等于EXIST说明有元素占着，就找下一个位置，如果找出的大于有效数据个数就绕回去，直接取模，找到了就填充元素，并把状态更新为EXIST。
再处理两个问题讲解上面的代码：
1、如果size为0，会崩溃;
哈希表冲突也会受到影响，冲突越多，效率越低，如果都满了，再来一个值冲突的概率极大。这就需要载荷因子α，反映了表满的程度，他表示不是满了才扩容，它等于填入表的元素/表长度，α越大表示冲突的可能型越大。我们设置它在0.7到0.8，如果超过了我们标定的值就扩容，注意一点如果用reserve扩容扩容量capacity的话，size没变而且表为空，扩不了，所以我们先定义一个newsize表示我们要扩容多少，看是否等同于0，如果等于0先给个初始值多少都是可以，否则按2两倍扩。
2、如果表满了，需要扩容，但是size变了映射关系要变。
因为扩容，映射关系变了，原来冲突的值可能不冲突了，原来不冲突的值可能冲突了，这时候需要开一块新的空间，重新建立映射关系，重新定义一个newtables，让然后遍历旧表重新计算，最后交换资源和原来的_tables交换，但是这样太麻烦，代码大量冗余。可以这样解决：可以复用，创建一个哈希表对象HashTable<K, V> newt;，在类里面可以访问私有，把_tables扩容，再遍历旧表，直接插入，插入的时候复用了线性探测那段代码，最后交换资源。这是用新的哈希表对象再调用insert，因为空间开好了直接去走线性探测的代码，这里不是this调，不是直接的递归。
最终返回true，再开始的时候先查找一下key的值在不在，如果为空没有就返回false。

（3）删除

bool Erase(const K& key)
		{
			HashNode<K, V>* ret = find(key);
			if (ret)
			{
				ret->_state = DELETE;
				return true;
			}
			else
			{
				return false;
			}

		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

前面提到过需要标记一种状态，删除某一个位置，需要先通过key找到对应的存储位置去查找，第一次的时候可能不是，然后继续后找，找到后需要把设置为删除(delete)状态，因为查找是从映射位置开始找，直到空结束，如果删除了还是空会提前结束就不到了，所以我们如果成功查找才把它设置为delete状态并啊减减_n，然后返回真，否则返回假。

（4）查找

HashNode<K, V>* Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}
			size_t hashi = key % _tables.size();
			size_t i = 1;
			size_t index = hashi;
			while (_tables[index]._state != EMPTY)
			{
				if (_tables[index]._state==EXIST&&_tables[index]._kv.first == key)
				{
					return &_tables[index];
				}
				index = hashi + i;
				index %= _tables.size();
				++i;
				if (index == hashi)
				{
					break;
				}
			}
			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
25

为了防止除0错误先判断一下有没有有效数据，如果为0直接返回空，接着先计算key的存储位置，如果这个位置不为空，那么就进while循环找，如果找到了返回节点的地址，但是这里还要考虑删除，因为如果之前删除一个数，只是把这个位置标记为DELETE，它还是在的，如果下次去找的时候它还是返回我们已经删除的那个地址，所以if判断里面要加一个状态是不是存在，存在且key找到了然后再返回节点地址，但是如果里面的状态是删除+存在，这样就会在while循环里面一直循环，所以在下面再加一个判断，如果index等于hashi说明走完了一圈没有找到，就break停止。

四、开散列模拟实现

在实践过程种，我们不太期望上面闭散列方式，不管是线性探测还是二次探测都不是很好，我们更喜欢用拉链法或哈希桶实现哈希表。
上面提到拉链法就是把冲突的元素使用链式结构把它们挂起来。

（1）节点

template<class K,class V>
	struct HashNode
	{
		pair<K, V>_kv;
		HashNode<K, V>* _next;
		HashNode(const pair<K,V>& kv)
			:_next(nullptr)
			,_kv(kv)
		{}
	};
	template<class K,class V>
	class HashTable
	{
	public:
	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

一样需要搞个节点，我们不用vecotr加list有些扩容细节不方便，我们用一个节点指针链接下一个节点和键值对存数据。哈希表类的私有成员用vector存节点指针，_n表示有效数据个数。相当于vector挂的是一个链表，里面存的是一个节点指针，有节点就挂起来，没有就是空。

（2）插入

bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;

			if (_n == _tables.size())
			{
				size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				vector<Node*> newtables(newsize,nullptr);
				for (auto& cur : _tables)
				{
					while (cur)
					{
						Node* next = cur->_next;;
						size_t hashi = cur->_kv.first % newtables.size();
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;
						cur = next;
					}
				}
				_tables.swap(newtables);
			}
			size_t hashi = kv.first % _tables.size();
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = 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

先看最下面插入：
还是先计算存储位置hashi，然后我们头插，就是创建一个新节点，然后链接第一个节点，再把新插入的置为第一个节点。再更新_n。
同样也面两个问题：
我们还是要控制负载因子，负载因子越大，冲突概率越高，查找效率越低，空间利用率越高，这里设为1，也就是相等。扩容时和上面的逻辑一样，定义一个newsize表示我们要扩容多少，看是否等同于0，如果等于0先给个初始值多少都是可以，否则按2两倍扩。
因为扩容要解决重新映射的问题，在这里就不需要和上面一样定义一个哈希表对象再复用insert，因为还有优化的空间，因为上面又调了insert创建新节点，而且这里需要注意一点，把每个位置走完桶，过一会还要把原来的表释放掉，因为闭散列不需要写析构函数，它会自动释放，而这里的vecotr也会自动释放，但是不会把里面的指针释放，vector只是把空间释放了，自定义类型要调用自己的析构，开了新表，旧表还要释放。最好的方式是，还是用传统方法，把原表的节点重新计算位置挪动到新表，这里没有申请也没有释放。开一个指针数组，每个位置给空，然后进行挪动，头插需要保存下一个位置，然后重新计算新位置，进行头插并把它更新第一个位置，再把next给cur，继续往下走，遍历完之后旧表时，再交换资源，也就是地址的交换。

（3）查找

	Node* Find(const K& key)
		{
			if (_tables.size() == 0)
				return nullptr;

			size_t hashi = key % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
			cur = cur->_next;
			}
			return nullptr;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

查找先判断有效个数是否等于0，如果等于0直接返回空，再计算存储位置，定义一个指针变量，把刚计算的位置的节点指针赋给它，然后遍历没找到，继续更新节点，如果找到返回指针，否则返回空。

（4）删除

bool Erase(const K& key)
		{
			size_t hashi = key % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;

					}
					delete cur;
					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
32

通过key计算存储位置，这就相当于单链表删除，需要知道它的前面的节点指针再定义一个当前指针，然后如果当前节点不为空进入while循环，如果找到了，再进行判断，如果前面前驱指针等于空，说明要删除的是第一个节点即头，直接把下一个位置赋给第一个节点，否则进行链接，然后再删除，返回真；如果while循环没结束且没找到，继续往下更新前驱指针和当前节点，结束没找到返回假。

（5）完善

一、对key进行完善优化

template<class K>
	struct HashFunc
	{
		size_t operator(const K& key)
		{
			return key;
		}

	};
	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& str)
		{
			size_t hash = 0;
			for (auto& e : str)
			{
				hash += e;
				hash *= 33;
			}
			return hash;
		}

	};
	template<class K,class V,class Hash=HashFunc<K>>
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

如果key时字符串我们改怎么处理，这不能那样计算了，我们不能在代码写死，因为我们写的是一个泛型，我们可以再增加一个模板参数hash，支持一个仿函数，它就是可以把key转换成可以取模的整型，第一种就是本身就是能支持取模的，第二种是字符串里类型，我们需要把他转换成整形，为了减少和其他字符串的存储位置的冲突，我们可以对一个字符串的每一个字符进行先加再乘一个某一个数，据数据表明*31或着131…数字冲突的概率极低，这是字符串到整形的映射。另外我们为了不显示传，直接用了特化，自动匹配相应的类型。接下来在使用key取模的地方，创建一个Hash类型的对象hash，改成hash(key)。如图：

另外哈希表增删查改的平均时间复杂度是O(1)，不看最坏，最坏的是多个数挂了在了相同的位置变成了O(N)，因为有扩容的发生，几乎不会发生，有负载因子的控制如果是1，每个位置平均挂一个，但是没有那么理想，挂2到3个，看的是整体。
我们可以测试一下：
先写一个最大桶的长度函数

size_t MaxBuket()
		{
			size_t  Max= 0;
			for (int i = 0; i < _tables.size(); ++i)
			{
				auto cur = _tables[i];
				size_t count = 0;
				while (cur)
				{
					++count;
					cur = cur->_next;
				}
				if (count > max)
				{
					max = count;
				}
			}
			return max;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

结果我们进行随机测试，大多数情况都是0，1，而最大的是2，如图：

所以极端情况很少出现，有一种方法可以解决单个桶超过一定长度，这个桶可以改成红黑树。

二、接下来是完善的是：对模的这个数进行优化
有些书上建议这个模的这个数也就是表的大小，最好是素数，它只能被1或被自身整除，也是降低冲突的，我们直接看stl标准库的：提供一个素数表，存了28个素数，把当前的素数值传进去，在里面依次在表里遍历找比它大的值。

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

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

			return __stl_prime_list[i];
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

五、源代码

（1）闭散列源代码

ClosedHash.h

#pragma once
#include<utility>
#include<vector>
using namespace std;

namespace nza
{
	enum State
	{
		EMPTY,
		EXIST,
		DELETE
	};

	template<class K, class V>
	struct HashNode
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};

	template<class K, class V>
	class HashTable
	{
	public:
		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> newt;
				newt._tables.resize(newsize);

					for (auto& data : _tables)
					{
						if (data._state == EXIST)
						{
							newt.Insert(data._kv);
						}
					}
					_tables.swap(newt._tables);

			}
			size_t hashi = kv.first % _tables.size();
			size_t i = 1;
			size_t index = hashi;
			while (_tables[index]._state == EXIST)
			{
				index = hashi + i;
				index %= _tables.size();
				++i;
			}
			_tables[index]._kv = kv;
			_tables[index]._state = EXIST;
			++_n;
			return true;
		}
		HashNode<K, V>* Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}
			size_t hashi = key % _tables.size();
			size_t i = 1;
			size_t index = hashi;
			while (_tables[index]._state != EMPTY)
			{
				if (_tables[index]._state==EXIST&&_tables[index]._kv.first == key)
				{
					return &_tables[index];
				}
				index = hashi + i;
				index %= _tables.size();
				++i;
				if (index == hashi)
				{
					break;
				}
			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			HashNode<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_state = DELETE;
				--_n;
				return true;
			}
			else
			{
				return false;
			}

		}


	private:
		vector<HashNode<K, V>> _tables;
		size_t _n = 0; 
	};

	void Test()
	{
		int a[] = { 1, 2, 0, 4, 5, 20, 66 };
		HashTable<int, int> ht;
		for (auto e : a)
		{
			ht.Insert(make_pair(e, e));
		}
		ht.Erase(3);
		ht.Insert(make_pair(80, 90));
	}
}
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

test.cpp

#include"ClosedHash.h"
int main()
{
	nza::Test();
}
1
2
3
4
5

（2）开散列源代码

OpenHash.h

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

namespace nza
{
	template<class K,class V>
	struct HashNode
	{
		pair<K, V>_kv;
		HashNode<K, V>* _next;
		HashNode(const pair<K,V>& kv)
			:_next(nullptr)
			,_kv(kv)
		{}
	};
	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return key;
		}

	};
	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& str)
		{
			size_t hash = 0;
			for (auto& e : str)
			{
				hash += e;
				hash *= 33;
			}
			return hash;
		}

	};
	template<class K,class V,class Hash=HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		~HashTable()
		{
			for (auto& cur : _tables)
			{
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				cur = nullptr;
			}
		}
		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;

			Hash hash;
			if (_n == _tables.size())
			{
				/*size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;*/
				size_t newsize = GetNextPrime(_tables.size());
				vector<Node*> newtables(newsize,nullptr);
				for (auto& cur : _tables)
				{
					while (cur)
					{
						Node* next = cur->_next;;
						size_t hashi = hash(cur->_kv.first) % newtables.size();
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;
						cur = next;
					}
				}
				_tables.swap(newtables);
			}
			size_t hashi = hash(kv.first) % _tables.size();
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return true;
		}
		Node* Find(const K& key)
		{
			if (_tables.size() == 0)
				return nullptr;
			Hash hash;
			size_t hashi = hash(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
			cur = cur->_next;
			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			Hash hash;
			size_t hashi = hash(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;

					}
					delete cur;
					return true;

				}
				else
				{
					prev = cur;
					cur=cur->_next;
				}

			}
			return false;

		}
		size_t MaxBucket()
		{
			size_t  Max= 0;
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				auto cur = _tables[i];
				size_t count = 0;
				while (cur)
				{
					++count;
					cur = cur->_next;
				}
				printf("[%d]->%d\n", i, count);
				if (count > Max)
				{
					Max = count;
				}
			}
			return Max;
		}
		size_t GetNextPrime(size_t prime)
		{
			// SGI
			static const int __stl_num_primes = 28;
			static const unsigned long __stl_prime_list[__stl_num_primes] =
			{
				53, 97, 193, 389, 769,
				1543, 3079, 6151, 12289, 24593,
				49157, 98317, 196613, 393241, 786433,
				1572869, 3145739, 6291469, 12582917, 25165843,
				50331653, 100663319, 201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
			};

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

			return __stl_prime_list[i];
		}

	private:
		vector<Node*> _tables;
		size_t _n = 0;
	};
	void Test()
	{
		int a[] = { 7, 5, 55, 13, 17, 12, 16 };
		HashTable<int, int> h1;
		for (auto e : a)
		{
			h1.Insert(make_pair(e, e));
		}
		h1.Insert(make_pair(22, 22));
		h1.Insert(make_pair(25, 25));
		h1.Insert(make_pair(36, 36));
		h1.Insert(make_pair(65, 65));
		h1.Erase(13);
	
			size_t N = 100000;
			HashTable<int, int> h2;
			srand(time(0));
			for (size_t i = 0; i < N; ++i)
			{
				size_t x = rand() + i;
				h2.Insert(make_pair(x, x));
			}
			cout << h2.MaxBucket() << 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
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

test.cpp

#include"OpenHash.h"

int main()
{
	nza::Test();
	return 0;

}
1
2
3
4
5
6
7
8