【C++】unordered_map、unordered_set 模拟实现

作者：从前慢现在也慢 | 2024-04-19 14:59:18

踩

文章目录

概念
框架
实现
源代码

概念

unordered_set 是含有 Key 类型唯一对象集合的关联容器。搜索、插入和移除拥有平均常数时间复杂度。在内部，元素并不以任何特别顺序排序，而是组织进桶中。元素被放进哪个桶完全依赖其值的哈希。这允许对单独元素的快速访问，因为哈希一旦确定，就准确指代元素被放入的桶。不可修改容器元素（即使通过非 const 迭代器），因为修改可能更改元素的哈希，并破坏容器。

unordered_map 是关联容器，含有带唯一键的 “键-值” pair 。搜索、插入和元素移除拥有平均常数时间复杂度。元素在内部不以任何特定顺序排序，而是组织进桶中。元素放进哪个桶完全依赖于其键( Key) 的哈希。这允许对单独元素的快速访问，因为一旦计算哈希，则它准确指代元素所放进的桶。

读上面的两段话会显得非常抽象，但是，如果对模拟实现 Map、Set 有一定了解（不了解可以看一下这篇文章 Map、Set模拟实现），那么就能很快明白，只不过是原本用红黑树作为底层数据结构来实现 Map、Set ，现在使用哈希（拉链法）作为底层数据结构来实现 unordered_map、unordered_set 。既然是使用的哈希，那么存储的数据就无法像红黑树一样具有严格的顺序，但是，换来的确是查找效率的极大提高，提高为 O(1) 的查找效率。

框架

如下图，哈希桶本质上是一个 vector ，容器里面存放的是 HashNode 这个节点的指针，节点是一个结构体，结构体里面存储着下一个 HashNode 结构体的指针 和 当前节点的数据。

哈希桶的实现自然不必多说，不了解的话可以查看这篇文章：C++ 哈希。这里是使用拉链法解决哈希冲突。
在这里插入图片描述

如下，必然要定义一个 HashNode 结构体，HashFunc 是为了根据 Key 来计算出数据的哈希值，以便得知数据存放在哪一个桶里面，至于正反向迭代器自然不必多说，必有的配置，最后就是哈希桶了，其成员变量一个是 _tables ，另一个是用来表示 _tables 中的有效数据个数。


#pragma once
#include<iostream>
#include<vector>

using namespace std;

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

		HashNode(const T& data)
			:_next(nullptr)
			, _data(data)
		{}
	};


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

	// 模板的特化，如果有 string 类型的数据，优先使用特化的模板
	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (auto& a : s)
			{
				hash += a;
				hash *= 31;
			}
			return hash;
		}
	};

	// 前置声明，不需要默认参数
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable;


	template<class K,class T,class Ref,class Ptr,class KeyOfT,class Hash=HashFunc<K>>
	struct Iterator
	{
	public:
		typedef HashNode<T> Node;
		typedef Iterator<K, T, Ref, Ptr, KeyOfT, Hash> self;
		typedef HashTable<K, T, KeyOfT, Hash> HT;
	public:
		Iterator(Node* node = nullptr, HT* tables= nullptr)
			:_node(node)
			,_ht(tables)
		{}

		Iterator(const Iterator<K,T,T&,T*,KeyOfT,Hash>& it)
			:_node(it._node)
			,_ht(it._ht)
		{}

		Node* _node;
		HT* _ht;
	};


	template<class K,class T,class Ref,class Ptr,class KeyOfT,class Hash=HashFunc<K>>
	struct ReverseIterator
	{
		
		typedef HashNode<T> Node;
		typedef ReverseIterator<K, T, Ref, Ptr, KeyOfT, Hash> self;
		typedef HashTable<K, T, KeyOfT, Hash> HT;

		ReverseIterator(Node* node, HT* ht)
		{
			it._node = node;
			it._ht = ht;
		}

		ReverseIterator(const Iterator<K, T,Ref,Ptr,KeyOfT,Hash> rit)
		{
			it._node = rit._node;
			it._ht = rit._ht;
		}

		ReverseIterator(const ReverseIterator<K, T, T&, T*, KeyOfT, Hash>& rit)
		{
			it._node = rit.it._node;
			it._ht = rit.it._ht;
		}


		Iterator<K, T, Ref, Ptr, KeyOfT, Hash> it;
	};

	template<class K, class T, class KeyOfT,class Hash = HashFunc<K>>
	class HashTable
	{
	public:

		typedef HashNode<T> Node;

		typedef Iterator<K, T, T&, T*, KeyOfT, Hash> iterator;
		typedef ReverseIterator<K, T, T&, T*, KeyOfT, Hash> reverse_iterator;

		// 模板类友元，声明不需要默认参数
		template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
		friend struct Iterator;

	public:
		//	成员方法

	private:
		vector<HashNode<T>*> _tables;
		size_t n = 0; // vector 存储有效数据个数
	};

}

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

对于迭代器、HashTable 的模板参数中， KeyOfT 的作用，和模拟实现 Map、Set 一样，就是为了取得数据的 Key 。因为 unordered_map 存储的是 pair<K,V> ，unordered_set 存储的是 K，为了使 HashTable 可以同时支持它们两个容器，所以有了 KeyOfT，该参数的传参是在 unordered_map 和 unordered_set 里面实现的。

如下，在 unordered_map 里面实现了 KeyOfMap，然后将仿函数传入 HashTable 的对应参数，这样在 HashTable 中，用 KeyOfT 实例化出的 kot 对象，实际上就是 struct KeyOfMap 的对象，再使用 kot 调用重载的 () 就可以拿到 pair<K,V> 中的 K 。
unordered_set 同理，不多赘述。

#include"HashTable.h"

namespace simulate_unorderedmap
{
	template<class K, class V,class Hash=HashBucket::HashFunc<K>>
	class unordered_map
	{
	public:

		struct KeyOfMap
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};

	public:
    // 成员函数

	private:
		HashBucket::HashTable<K, pair<const K, V>, KeyOfMap,Hash> _map;
	};

}
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

实现

正反迭代器

这里可以使用包装器的设计模式，实现正向迭代器，然后反向迭代器实际上就是对正向迭代器的封装，反向迭代器的++，就是正向迭代器的–。

如下， Iterator 中有两个成员变量，一个是 HashNode 节点的指针，另一个是 HashTable 的指针。需要 _ht 这个成员变量的原因，其实是进行 ++ 、-- 所需要的。

对于成员函数的介绍主要就在 ++ 、-- 这两个。如下图，我们可以理解为，vector 容器里面装的是一个个桶，桶是链表的结构。进行一次 ++ ，那么迭代器自然是指向链表中下一个节点，此时分为两种情况，下一个节点存在（如下图左边），下一个节点不存在，即当前节点已经是当前桶的最后一个节点（如下图右边）。对于前者，自然很容易，但是，对于后者，就需要找到下一个有数据的桶，然后将 _node 指针指向桶内第一个节点，具体步骤如下。

1、得到 key。 kot(_node->_data)
2、通过 hash 函数得到 hash 值。 hash(kot(_node->_data))
3、得到桶号（一般都为 hash 值对桶数求模）。size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
4、找到下一个有数据的桶。

要进行上面的操作，必须要有当前的 HashTable，但是用一整个 HashTable 当作成员变量，消耗太大，所以用指针。
在这里插入图片描述

operator- - () 也是类似的实现，只不过 - - 要先经过前三步得到桶号，然后判断当前节点的前面有没有节点，可以根据桶的第一个节点是不是当前节点进行判断，不难理解。

同时，无论是 ++ 还是 - - 都要注意边界条件，最后一个哈希桶的最后一个数据，进行 ++ 只能是 nullptr，同样，第一个哈希桶的第一个数据，进行 - - 也只能是 nullptr 。

template<class K, class T, class KeyOfT, class Hash>
	class HashTable;


	template<class K,class T,class Ref,class Ptr,class KeyOfT,class Hash=HashFunc<K>>
	struct Iterator
	{
	public:
		typedef HashNode<T> Node;
		typedef Iterator<K, T, Ref, Ptr, KeyOfT, Hash> self;
		typedef HashTable<K, T, KeyOfT, Hash> HT;
	public:
		Iterator(Node* node = nullptr, HT* tables= nullptr)
			:_node(node)
			,_ht(tables)
		{}

		Iterator(const Iterator<K,T,T&,T*,KeyOfT,Hash>& it)
			:_node(it._node)
			,_ht(it._ht)
		{}

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

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

		bool operator!=(const self& it)
		{
			return _node != it._node;
		}

		self& operator++()
		{
			if (_node->_next)
			{
				_node = _node->_next;
				return *this;
			}

			// 找到下一个有数据的桶
			KeyOfT kot;
			Hash hash;
			size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
			++hashi;
			while (hashi < _ht->_tables.size())
			{
				if (_ht->_tables[hashi])
				{
					_node = _ht->_tables[hashi];
					break;
				}
				else
				{
					++hashi;
				}
			}

			if (hashi >= _ht->_tables.size())
				_node = nullptr;

			return *this;
		}

		self& operator--()
		{
			// 找到当前桶
			KeyOfT kot;
			Hash hash;
			int hashi = hash(kot(_node->_data)) % _ht->_tables.size();
			
			// 桶的第一个就是当前节点构成的迭代器,往前面的桶找
			if (_ht->_tables[hashi] == _node)
			{
				--hashi;
				while (hashi >= 0)
				{
					if (_ht->_tables[hashi] == nullptr)
					{
						--hashi;
					}
					else
					{
						// 找到上一个有数据的桶的最后一个数据
						Node* cur = _ht->_tables[hashi];
						while (cur->_next)
							cur = cur->_next;
						_node = cur;
						break;
					}
				}

				if (hashi < 0)
					_node = nullptr;
			}
			else // 桶的第一个不是当前节点构成的迭代器，在该桶里面找
			{
				Node* cur = _ht->_tables[hashi];
				while (cur->_next != _node)
				{
					cur = cur->_next;
				}
				_node = cur;
			}

			return *this;
		}

		Node* _node;
		HT* _ht;
	};

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

至于反向迭代器，那就是对正向迭代器的封装。

template<class K,class T,class Ref,class Ptr,class KeyOfT,class Hash=HashFunc<K>>
	struct ReverseIterator
	{
		
		typedef HashNode<T> Node;
		typedef ReverseIterator<K, T, Ref, Ptr, KeyOfT, Hash> self;
		typedef HashTable<K, T, KeyOfT, Hash> HT;

		ReverseIterator(Node* node, HT* ht)
		{
			it._node = node;
			it._ht = ht;
		}

		ReverseIterator(const Iterator<K, T,Ref,Ptr,KeyOfT,Hash> rit)
		{
			it._node = rit._node;
			it._ht = rit._ht;
		}

		ReverseIterator(const ReverseIterator<K, T, T&, T*, KeyOfT, Hash>& rit)
		{
			it._node = rit.it._node;
			it._ht = rit.it._ht;
		}

		self operator++()
		{
			return --it;
		}

		self& operator--()
		{
			return ++it;
		}

		Ref operator*()
		{
			return it._node->_data;
		}

		Ptr operator->()
		{
			return it._node->_data;
		}

		bool operator!=(const self& rit)
		{
			return it._node != rit.it._node;
		}

		Iterator<K, T, Ref, Ptr, KeyOfT, Hash> 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
51
52
53

Find()、Insert() 、Erase()

如下是 unordered_map、unordered_set 里面的 Find() 、Erase() 、Insert() 方法，其实就是对 HashTable 的封装。知道了 HashTable 里面的 Find() 、insert() 、Erase() 实现原理即可，并不难，都是和 ++ 类似的思路。

#include"HashTable.h"

namespace simulate_unorderedmap
{
	template<class K, class V,class Hash=HashBucket::HashFunc<K>>
	class unordered_map
	{
	public:

		struct KeyOfMap
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};

	public:
		typedef typename HashBucket::HashNode<pair<const K, V>> Node;

		typedef typename HashBucket::HashTable<K, pair<const K, V>, KeyOfMap, Hash>::iterator iterator;
		typedef typename HashBucket::HashTable<K, pair<const K, V>, KeyOfMap, Hash>::const_iterator const_iterator;
		typedef typename HashBucket::HashTable<K, pair<const K, V>, KeyOfMap, Hash>::reverse_iterator reverse_iterator;
		typedef typename HashBucket::HashTable<K, pair<const K, V>, KeyOfMap, Hash>::const_reverse_iterator const_reverse_iterator;

		iterator begin()
		{
			return _map.begin();
		}

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

		pair<iterator,bool> insert(const pair<const K, V>& kv)
		{
			return _map.insert(kv);
		}

		iterator Find(const K& key)
		{
			Node* cur = _map.Find(key);
			return iterator(cur, &_map);
		}

		bool Erase(const K& key)
		{
			return _map.Erase(key);
		}

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


	private:
		HashBucket::HashTable<K, pair<const K, V>, KeyOfMap,Hash> _map;
	};

}

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

unordered_map 的 operator[ ]

unordered_map 的 [ ] 是兼具插入和查找功能的。unordered_map 里面存储的是 pair<K,V> ，假设有一个 unordered_map< int,int >对象 m，执行 m[10]=1000; —— 如果存储的 pair<K,V> 里面，有 K 类型的数据是 10，那么就将这个键值对的 V 修改成 100；没有则插入 make_pair(10,100);

要完成上面描述的功能，就必须要让 [ ] 的返回值是 V& （V的引用），这样才可以修改 V 类型的数据。可以通过迭代器来实现！！

如下是 unordered_map 里面实现 operator[ ] 的代码，_map 是 HashTable 实例化出来的对象，其 Insert() 返回值是 pair<iterator,bool> ，很明显，返回值包含两个信息：

1.某个节点构成的迭代器。如果插入成功，那么返回插入节点封装成的迭代器。如果插入失败（已经有了 K 类型对应的数据），那么就相当于查找功能，返回找到的节点封装成的迭代器。
2.是否插入成功，插入成功返回 true，否则false。

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

1
2
3
4
5
6

源代码

HashTable.h

#pragma once
#include<iostream>
#include<vector>

using namespace std;

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

		HashNode(const T& data)
			:_next(nullptr)
			, _data(data)
		{}
	};


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

	// 模板的特化，如果有 string 类型的数据，优先使用特化的模板
	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (auto& a : s)
			{
				hash += a;
				hash *= 31;
			}
			return hash;
		}
	};

	// 前置声明，不需要默认参数
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable;


	template<class K,class T,class Ref,class Ptr,class KeyOfT,class Hash=HashFunc<K>>
	struct Iterator
	{
	public:
		typedef HashNode<T> Node;
		typedef Iterator<K, T, Ref, Ptr, KeyOfT, Hash> self;
		typedef HashTable<K, T, KeyOfT, Hash> HT;
	public:
		Iterator(Node* node = nullptr, HT* tables= nullptr)
			:_node(node)
			,_ht(tables)
		{}

		Iterator(const Iterator<K,T,T&,T*,KeyOfT,Hash>& it)
			:_node(it._node)
			,_ht(it._ht)
		{}

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

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

		bool operator!=(const self& it)
		{
			return _node != it._node;
		}

		self& operator++()
		{
			if (_node->_next)
			{
				_node = _node->_next;
				return *this;
			}

			// 找到下一个有数据的桶
			KeyOfT kot;
			Hash hash;
			size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
			++hashi;
			while (hashi < _ht->_tables.size())
			{
				if (_ht->_tables[hashi])
				{
					_node = _ht->_tables[hashi];
					break;
				}
				else
				{
					++hashi;
				}
			}

			if (hashi >= _ht->_tables.size())
				_node = nullptr;

			return *this;
		}

		self& operator--()
		{
			// 找到当前桶
			KeyOfT kot;
			Hash hash;
			int hashi = hash(kot(_node->_data)) % _ht->_tables.size();
			
			// 桶的第一个就是当前节点构成的迭代器,往前面的桶找
			if (_ht->_tables[hashi] == _node)
			{
				--hashi;
				while (hashi >= 0)
				{
					if (_ht->_tables[hashi] == nullptr)
					{
						--hashi;
					}
					else
					{
						// 找到上一个有数据的桶的最后一个数据
						Node* cur = _ht->_tables[hashi];
						while (cur->_next)
							cur = cur->_next;
						_node = cur;
						break;
					}
				}

				if (hashi < 0)
					_node = nullptr;
			}
			else // 桶的第一个不是当前节点构成的迭代器，在该桶里面找
			{
				Node* cur = _ht->_tables[hashi];
				while (cur->_next != _node)
				{
					cur = cur->_next;
				}
				_node = cur;
			}

			return *this;
		}

		Node* _node;
		HT* _ht;
	};


	template<class K,class T,class Ref,class Ptr,class KeyOfT,class Hash=HashFunc<K>>
	struct ReverseIterator
	{
		
		typedef HashNode<T> Node;
		typedef ReverseIterator<K, T, Ref, Ptr, KeyOfT, Hash> self;
		typedef HashTable<K, T, KeyOfT, Hash> HT;

		ReverseIterator(Node* node, HT* ht)
		{
			it._node = node;
			it._ht = ht;
		}

		ReverseIterator(const Iterator<K, T,Ref,Ptr,KeyOfT,Hash> rit)
		{
			it._node = rit._node;
			it._ht = rit._ht;
		}

		ReverseIterator(const ReverseIterator<K, T, T&, T*, KeyOfT, Hash>& rit)
		{
			it._node = rit.it._node;
			it._ht = rit.it._ht;
		}

		self operator++()
		{
			return --it;
		}

		self& operator--()
		{
			return ++it;
		}

		Ref operator*()
		{
			return it._node->_data;
		}

		Ptr operator->()
		{
			return it._node->_data;
		}

		bool operator!=(const self& rit)
		{
			return it._node != rit.it._node;
		}

		Iterator<K, T, Ref, Ptr, KeyOfT, Hash> it;
	};

	template<class K, class T, class KeyOfT,class Hash = HashFunc<K>>
	class HashTable
	{
	public:

		typedef HashNode<T> Node;

		typedef Iterator<K, T, T&, T*, KeyOfT, Hash> iterator;
		typedef Iterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;
		typedef ReverseIterator<K, T, T&, T*, KeyOfT, Hash> reverse_iterator;
		typedef ReverseIterator<K, T, const T&, const T*, KeyOfT, Hash> const_reverse_iterator;

		// 模板类友元，声明不需要默认参数
		template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
		friend struct Iterator;

	public:

		iterator begin()
		{
			Node* cur = nullptr;
			for (int i = 0; i < _tables.size(); i++)
			{
				cur = _tables[i];
				if (cur)
					break;
			}

			return iterator(cur, this);
		}

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

		const_iterator begin()const
		{
			Node* cur = nullptr;
			for (int i = 0; i < _tables.size(); i++)
			{
				cur = _tables[i];
				if (cur)
					break;
			}

			return const_iterator(cur, this);
		}

		const_iterator end()const
		{
			return const_iterator(nullptr, this);
		}


		reverse_iterator rbegin()
		{
			int hashi = _tables.size() - 1;
			while (_tables[hashi] == nullptr && hashi>=0)
			{
				hashi--;
			}
			if (hashi < 0)
				return reverse_iterator(nullptr, this);

			// 最后一个
			Node* cur = _tables[hashi];
			while (cur->_next)
				cur = cur->_next;
			return reverse_iterator(cur, this);
		}

		reverse_iterator rend()
		{
			return reverse_iterator(nullptr, this);
		}


		const_reverse_iterator rbegin()const
		{
			int hashi = _tables.size() - 1;
			while (_tables[hashi] == nullptr && hashi >= 0)
			{
				hashi--;
			}
			if (hashi < 0)
				return const_reverse_iterator(nullptr, this);

			// 最后一个
			Node* cur = _tables[hashi];
			while (cur->_next)
				cur = cur->_next;
			return const_reverse_iterator(cur, this);
		}

		const_reverse_iterator rend()const
		{
			return const_reverse_iterator(nullptr, this);
		}

		bool Erase(const K& key)
		{
			KeyOfT kot;
			Hash hash;
			size_t hashi = hash(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (kot(cur->_data) == 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;
		}

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

			Hash hash;
			KeyOfT kot;
			size_t hashi = hash(key) % _tables.size();

			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
					return cur;
				cur = cur->_next;
			}
			return nullptr;
		}


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

		pair<iterator,bool> insert(const T& data)
		{
			KeyOfT kot;
			Node* findnode = Find(kot(data));
			if (findnode)
				return make_pair(iterator(findnode, this), false);

			Hash hash;

			if (_tables.size() == n)
			{
				//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) // 链表节点全部插入newht
					{
						Node* next = cur->_next;
						size_t newhashi = hash(kot(cur->_data)) % newsize;

						cur->_next = newtables[newhashi];
						newtables[newhashi] = cur;

						cur = next;
					}
				}

				_tables.swap(newtables);
			}

			size_t hashi = hash(kot(data)) % _tables.size();
			Node* tmp = new Node(data);
			tmp->_next = _tables[hashi];
			_tables[hashi] = tmp;

			++n;
			return make_pair(iterator(tmp,this),true);

		}


		size_t MaxBucketSize()
		{
			int size = _tables.size();
			size_t max = 0;
			for (int i = 0; i < size; i++)
			{
				size_t tmp = 0;
				Node* cur = _tables[i];
				while (cur)
				{
					tmp++;
					cur = cur->_next;
				}

				if (tmp > max)
					max = tmp;
			}

			return max;
		}

	private:
		vector<HashNode<T>*> _tables;
		size_t n = 0; // vector 存储有效数据个数
	};

}
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
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466

unordered_map.h

#include"HashTable.h"



namespace simulate_unorderedmap
{
	template<class K, class V,class Hash=HashBucket::HashFunc<K>>
	class unordered_map
	{
	public:

		struct KeyOfMap
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};

	public:
		typedef typename HashBucket::HashNode<pair<const K, V>> Node;

		typedef typename HashBucket::HashTable<K, pair<const K, V>, KeyOfMap, Hash>::iterator iterator;
		typedef typename HashBucket::HashTable<K, pair<const K, V>, KeyOfMap, Hash>::const_iterator const_iterator;
		typedef typename HashBucket::HashTable<K, pair<const K, V>, KeyOfMap, Hash>::reverse_iterator reverse_iterator;
		typedef typename HashBucket::HashTable<K, pair<const K, V>, KeyOfMap, Hash>::const_reverse_iterator const_reverse_iterator;

		iterator begin()
		{
			return _map.begin();
		}

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

		pair<iterator,bool> insert(const pair<const K, V>& kv)
		{
			return _map.insert(kv);
		}

		iterator Find(const K& key)
		{
			Node* cur = _map.Find(key);
			return iterator(cur, &_map);
		}

		bool Erase(const K& key)
		{
			return _map.Erase(key);
		}

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


	private:
		HashBucket::HashTable<K, pair<const K, V>, KeyOfMap,Hash> _map;
	};

}
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

unordered_set.h

#include"HashTable.h"

namespace simulate_unorderedset
{

	template<class K, class Hash = HashBucket::HashFunc<K>>
	class unordered_set
	{
	public:
		typedef typename HashBucket::HashNode<K> Node;
		struct KeyOfSet
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};

	public:

		typedef typename HashBucket::HashTable<K, K, KeyOfSet, Hash>::const_iterator iterator;
		typedef typename HashBucket::HashTable<K, K, KeyOfSet, Hash>::const_iterator const_iterator;
		typedef typename HashBucket::HashTable<K, K, KeyOfSet, Hash>::const_reverse_iterator reverse_iterator;
		typedef typename HashBucket::HashTable<K, K, KeyOfSet, Hash>::const_reverse_iterator const_reverse_iterator;

		pair<iterator,bool> insert(const K& key)
		{
			return _set.insert(key);
		}

		bool Erase(const K& key)
		{
			return _set.Erase(key);
		}

		iterator Find(const K& key)
		{
			Node* cur=_set.Find(key);
			return iterator(cur, &_set);
		}

		iterator begin()
		{
			return _set.begin();
		}

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

		const_iterator begin()const
		{
			return _set.begin();
		}

		const_iterator end()const
		{
			return _set.end();
		}

		reverse_iterator rbegin()
		{
			return _set.rbegin();
		}

		reverse_iterator rend()
		{
			return _set.rend();
		}


	private:
		HashBucket::HashTable<K, K, KeyOfSet,Hash> _set;
	};

}

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

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