【C++ —— 哈希】哈希原理 | 哈希表的模拟实现 | 模拟实现封装unordered_map和unordered_set

---

前言

本文参考文档：https://legacy.cplusplus.com/reference/unordered_map/

---

一、unordered系列关联式容器

1.1 unordered_map

1.unordered_map接口说明

2. unordered_map的容量

3.unordered_map的迭代器(无序set和map的迭代器都是单向迭代器)

4.unordered_map的元素访问

注意：该函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶
中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中，
将key对应的value返回。

5.unordered_map查询

注意：unordered_map中key是不能重复的，因此count函数的返回值最大为1

6. unordered_map的修改操作

7.unordered_map的桶操作

1.2 unordered_set

unordered_set接口根map差不多一样，不过set只存key值且不能修改
这里就不过多赘述了，详情可自行观看文档
set文档资料

二、底层结构

2.1哈希概念（哈希是一种算法思想）

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

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

哈希/散列：映射 一个值和另一个值建立关系。
哈希表/散列表： 映射 关键字和存储位置建立一个关系。

2.2哈希冲突

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突
或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

2.3 解决哈希冲突方法：

1.直接定址法（值和位置关系是唯一关系，每个人都有唯一位置，值很分散，直接定址法会导致空间开很大，资源的浪费）

2.闭散列

2.1 开放地址法/线性探测

当前位置被占用，在开放空间里按某种规则，找一个没有被占用的位置存储

1. 线性探测 hashi + i（i >= 0）
2. 二次探测 hashi + i^2(i >= 0)
   
   多定义一个负载因子，存储有效关键字个数
   当有效关键字个数超过表大小的6~8成就再次扩容，用此种方法可以有效的减少哈希冲突的次数。
   以空间换效率。
   注意：
   负载因子太多：会影响效率。
   负载因子太少：会浪费空间。
   代码实现：

	enum Stutas

	{
		//删除状态的意义：
		//1.再插入，这个位置可以覆盖
		//2.防止后面冲突的值，出现找不到的情况，遇到删除状态还要继续向后寻找
		DELETE,
		EMPTY,
		EXIST

	};
	template<class K,class V>
	struct HashData
	{
		pair<K,V> _kv;
		Stutas _s = EMPTY;
	};


	//开放地址法
	//线性查找，插入
	template<class K>
	struct Hashfunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
	//struct HashfuncString
	//{
	//	//BKDR算法
	//	size_t operator()(const string& key)
	//	{
	//		size_t hash = 0;
	//		//把他们的ascll码值加起来
	//		for (auto e : key)
	//		{
	//			hash += e;
	//		}
	//		return hash;
	//	}
	//};
	template<>
	struct Hashfunc<string>
	{

		size_t operator()(const string& key)
		{
			size_t hash = 0;
			//把他们的ascll码值加起来
			for (auto e : key)
			{
				hash += e;
			}
			return hash;
		}
	};

	template<class K,class V, class Hash = Hashfunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);//resize也直接会开初始化size的大小。reserve之会开capecity的大小

		}
		//提供find解决insert能够插入相同key的问题
		
		HashData<K, V>* Find(const K& key)
		{
			Hash ht;
			size_t hashi = ht(key) % _tables.size();
			while (_tables[hashi]._s != EMPTY)
			{
				if (_tables[hashi]._s == EXIST && _tables[hashi]._kv.first == key)
				{
					//找到return找到位置的地址
					//没找到return空
					return &_tables[hashi];
				}
				hashi++;
				//hashi超出table的size大小就给他%回来
				hashi = hashi % _tables.size();
			}

			return nullptr;
		}

		bool Insert(const pair<K, V>& kv)
		{
			Hash ht;
			if (Find(kv.first))
			{
				return false;
			}
			if ((double)_n / _tables.size() >= 0.7)
			{
				//不能直接扩容size的二倍，还要转移数据，重新映射关系（扩容之后值和空间的位置关系已经乱了）
				//释放旧空间
				size_t newsize = _tables.size() * 2;
				HashTable<K,V,Hash> newHT;
				newHT._tables.resize(newsize);
				//遍历旧表，插入新表
				for ( size_t i= 0; i < _tables.size(); i++)
				{
					if (_tables[i]._s == EXIST)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
				_tables.swap(newHT._tables);

			}
			//size_t hashi = kv.first % _tables.size();//key不一定是整形，如果是string呢？用仿函数把kv.first的值转化整形值
			//先用字符串映射一个整形
			size_t hashi = ht(kv.first) % _tables.size();

			while (_tables[hashi]._s == EXIST)
			{
				hashi++;
				//hashi超出table的size大小就给他%回来
				hashi = hashi % _tables.size();
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._s = EXIST;
			++_n;

		}
		bool Erase(const K& key)
		{
			HashData<K,V>* ret =  Find(key);
			//find找到会返回找到位置的地址
			if (ret)
			{
				ret->_s = DELETE;
				--_n;
				return true;
			}
			return false;
		}
		void Print()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i]._s == EXIST)
				{
					//cout << i << "->";
					cout <<"["<<i<<"]->"<< _tables[i]._kv.first << ":"<< _tables[i]._kv.second << endl;
					/*printf("[%d]->%d\n", i, _tables[i]._kv.first);
					printf("")*/
				}
				else if (_tables[i]._s == EMPTY)
				{
					printf("[%d]->\n", i);
				}
				else 
				{
					printf("[%d]->DELETE\n", i);
				}

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

3.开散列

1. 哈希桶/拉链法

哈希桶的平均时间复杂度为O(1)

思路概念：
我们把每个hashi映射的位置，替换成list，链接每次插入的冲突的新key

可以参考下图：如4位置都是冲突的关键字。

2.字符串映射问题

整形还是可以用除留余数法计算key映射的位置，但是例如string这种字符串呢？
我们可以使用仿函数，实现类型的转换。
例如把字符串的每个字符的ascll码值加起来。
代码实现：

template<class K>
	struct Hashfunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
	struct HashfuncString
	{
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			//把他们的ascll码值加起来
			for (auto e : key)
			{
				hash += e;
			}
			return hash;
		}
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

但是这种转化函数会有一些缺陷，例如abc和acb这两个不同的字符串ascll码值加起来都是相同的，导致了映射位置冲突。
有没有什么办法能解决这类的问题呢？
有大佬专门研究出了很多种算法我们可以参考：
字符串哈希算法
例如：

这类算法会减少字符串转哈希算法的冲突。但是肯定不能完全避免。
我们也可以模仿大佬算法完善我们的代码：

struct HashfuncString
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		//把他们的ascll码值加起来
		for (auto e : key)
		{
			hash *= 31;//在加ascll码值前*31/131
			hash += e;
		}
		return hash;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这种方式也是类似库里面unordered_map的实现方式（要传一个仿函数）

但是库里面其实比我们实现的更好一些，
库里面不用传第三个模板参数直接取模，
库里面的unordered_map用string做key可以直接转化为整型。

std::unordered_map<string,string> dict;
1

我们可以用特化模板参数来模拟实现这总功能。

template<class K>
struct Hashfunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
template<>
struct Hashfunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		//把他们的ascll码值加起来
		for (auto e : key)
		{
			hash += e;
		}
		return hash;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

利用哈希桶实现哈希表代码：

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

		HashNode(const pair<K, V>& kv)
			:_kv(kv)
			,_next(nullptr)
		{}
	};
	template<class K>
	struct Hashfunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
	
	template<>
	struct Hashfunc<string>
	{
		//BKDR算法
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			//把他们的ascll码值加起来
			for (auto e : key)
			{
				hash *= 31;//在加ascll码值之前*31/131...
				hash += e;
			}
			return hash;
		}
	};
	template<class K,class V ,class Hash = Hashfunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		HashTable()
		{
			_tables.resize(10);
		}
		~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;
			}
		}
		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			
			Hash ht;
			//扩容用开放地址法的扩容方法会产生大量的资源浪费
			//可以考虑直接把旧表的数据挪动下来
			if (_n == _tables.size())
			{
				vector<Node*> newtable;
				newtable.resize(_tables.size() * 2, nullptr);
				//遍历旧表
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						//挪动旧表的数据映射到新表
						Node* next = cur->_next;
						size_t hashi = ht(cur->_kv.first) % newtable.size();
						cur->_next = newtable[i];
						newtable[i] = cur;

						//利用cur把节点挪动到新表
						//cur利用next返回到旧表以此循环
						cur = next;

						
					}
					_tables[i] = nullptr;
					//旧表这个桶数据已经被挪动完，记得制空。
					//以防后面析构有问题
				}
				_tables.swap(newtable);

			}
			
			//先算出数据要存入哪个桶
			size_t hashi = ht(kv.first) % _tables.size();
			//头插
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return true;
		}
		Node* Find(const K& key)
		{
			Hash ht;
			size_t hashi = ht(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return NULL;
		}
		bool Erase(const K& key)
		{
			Hash ht;

			size_t hashi = ht(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					return true;
				}
				prev = cur;
				cur = cur->_next;

			}
			return false;
		}
		void Some()
		{
			size_t bucketsize = 0;
			size_t maxbucketlen = 0;
			size_t sumbucketlen = 0;
			double averagebucketlen = 0;
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur == nullptr)
				{
					++bucketsize;
				}
				size_t bucketlen = 0;
				while (cur)
				{
					++bucketlen;
					cur = cur->_next;
				}
				sumbucketlen += bucketlen;
				if (bucketlen > maxbucketlen)
				{
					maxbucketlen = bucketlen;
				}
				

			}
			averagebucketlen = (double)sumbucketlen / (double)bucketsize;
			printf("bucketsize:%d\n", bucketsize);
			printf("maxbucketlen:%d\n", maxbucketlen);
			printf("averagebucketlen:%lf\n", averagebucketlen);
			
		}
		
	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

三、unordered_map和unordered_set封装哈希表模拟实现

1.UnOrdered_map.h

#include"HashTable.h"

namespace goat
{
	template<class K,class V, class Hash = Hash_Bucket::Hashfunc<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K,V>& kv)
			{
				return kv.first;
			}

		};
	public:
		typedef typename Hash_Bucket::HashTable<K, pair<const K, V>, MapKeyOfT , Hash>::iterator iterator;


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

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

	private:

		Hash_Bucket::HashTable<K, pair<const K,V> ,MapKeyOfT ,Hash> _mp;
	};
}
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

2.UnOrdered_set.h

#include"HashTable.h"

namespace goat
{
	template<class K ,class Hash = Hash_Bucket::Hashfunc<K>>
	class unordered_set
	{

		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}

		};
	public:
		typedef typename Hash_Bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;
		typedef typename Hash_Bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;

		/*iterator begin() 
		{
			return _st.begin();
		}
		iterator end() 
		{
			return _st.end();
		}*/

		const_iterator begin() const
		{
			return _st.begin();
		}
		const_iterator end() const
		{
			return _st.end();
		}

		iterator find(const K& key)
		{
			return _st.Find(key);
		}

		bool erase(const K& key)
		{
			_st.Erase(key);
		}


		//返回值pair要实现operator[]再去修改
		pair<iterator, bool> insert(const K& key)
		{
			//return _st.Insert(key);//返回普通迭代器，但是这里insert接受的是const迭代器
								   //正常解决方法1:支持const迭代器转化成普通迭代器，方法二：下一层Insert使用节点的指针返回（指针会产生隐式类型转换为迭代器
								   //但是这里unordered迭代器有三个值不能使用方法二
								   //iterator(cur , this ,hashi)
			//这里用另外一种简单的方法
			auto ret = _st.Insert(key);
			return pair<iterator, bool>(iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);


			
		}

	private:
		
		Hash_Bucket::HashTable<K, K , SetKeyOfT, Hash> _st;
	};
	
}
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

3.HashTable.h

#include<iostream>
#include<vector>
#include<utility>
#include<list>
#include<set>

using namespace std;

namespace Hash_Bucket
{
	template<class T>
	struct HashNode
	{

		HashNode<T>* _next;
		T _data;

		//库里面的unordered是实现插入顺序遍历的
		//要单独维护一个链表
		//HashNode<T>* _linknext;
		//HashNode<T>* _linkprev;
		
		HashNode(const T& data)
			:_data(data)
			,_next(nullptr)
		{}
	};
	template<class K>
	struct Hashfunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
	
	template<>
	struct Hashfunc<string>
	{
		
		size_t operator()(const string& key)
		{
			size_t hash = 0;
		
			for (auto e : key)
			{
				hash *= 31;
				hash += e;
			}
			return hash;
		}
	};
	//解决互相依赖方法一
	//前置声明(不用给缺省参数)
	//因为hashiterator和hashtable是互相依赖的关系

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

	template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
	struct __HashIterator
	{
		typedef HashNode<T> Node;
		typedef __HashIterator<K, T,Ref,Ptr, KeyOfT, Hash> Self;

		Node* _node;
		const HashTable<K, T, KeyOfT, Hash>* _pht;
		//解决互相依赖方法二
		//实际上哈希迭代器需要的是：
		//vector<Node*>* _ptb;


		//1.记录当前桶的所在位置
		size_t _hashi;

		__HashIterator(Node* node,const HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)
			: _node(node)
			, _pht(pht)
			, _hashi(hashi)
		{}
		
		Self& operator++()
		{
			if (_node->_next)
			{
				//桶还有节点，就走下一个节点
				_node = _node->_next;
			}
			else
			{
				//当前桶已经走完了，需要下一个桶的开始
				//传个哈希表过来
				2.直接算出当前所在桶位置
				//KeyOfT kot;
				//Hash hf;
				//size_t hashi = hf(kot(_node->_data)) % _pht._tables.size();
				++_hashi;


				//_tables是私有成员变量
				//可以考虑友元
				while (_hashi < _pht->_tables.size())
				{
					if (_pht->_tables[_hashi])
					{
						_node = _pht->_tables[_hashi];
						break;
					}
					else
					{
						_hashi++;
					}
				}
				if (_hashi == _pht->_tables.size())
				{
					_node = nullptr;
				}
			}
			return *this;
		}
		Ref operator*()
		{
			return _node->_data;
		}
		Ptr operator->()
		{
			return &_node->_data;
		}
		bool operator!=(const Self& s)
		{
			return _node != s._node;

		}
	};
	//unordered_set -> HashTable<K,K>
	//unordered_map -> HashTable<K,pair<K,V>>
	template<class K,class T , class KeyOfT,class Hash = Hashfunc<K>>
	class HashTable
	{

		template<class K, class T,class Ref ,class Ptr ,class KeyOfT, class Hash>
		friend struct __HashIterator;


		typedef HashNode<T> Node;
	public:
		typedef __HashIterator<K, T, T&,T* , KeyOfT, Hash> iterator;
		typedef __HashIterator<K, T, const T&,const T* , KeyOfT, Hash> const_iterator;

		iterator begin()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return iterator(_tables[i] ,this , i);
				}
			}
			return end();
		}
		iterator end()
		{
			return iterator(nullptr, this, -1);
		}
		const_iterator begin() const //const修饰this-> HashTable<K, T, KeyOfT, Hash>* 
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return const_iterator(_tables[i], this, i);
				}
			}
			return end();
		}
		const_iterator end() const
		{
			return const_iterator(nullptr, this, -1);
		}



		HashTable()
		{
			_tables.resize(10);
		}
		~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;
			}
		}
		pair<iterator,bool> Insert(const T& data)
		{
			KeyOfT kot;
			/*if (Find(kot(data)))
			{
				return false;
			}*/
			iterator it = Find(kot(data));
			if(it != end())
			{
				return make_pair(it, false);
			}
			
			Hash ht;
			
			//扩容用开放地址法的扩容方法会产生大量的资源浪费
			//可以考虑直接把旧表的数据挪动下来
			if (_n == _tables.size())
			{
				vector<Node*> newtable;
				newtable.resize(_tables.size() * 2, nullptr);
				//遍历旧表
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						//挪动旧表的数据映射到新表
						Node* next = cur->_next;
						size_t hashi = ht(kot(cur->_data)) % newtable.size();
						cur->_next = newtable[i];
						newtable[i] = cur;

						//利用cur把节点挪动到新表
						//cur利用next返回到旧表以此循环
						cur = next;

						
					}
					_tables[i] = nullptr;
					//旧表这个桶数据已经被挪动完，记得制空。
					//以防后面析构有问题
				}
				_tables.swap(newtable);

			}
			
			//先算出数据要存入哪个桶
			size_t hashi = ht(kot(data)) % _tables.size();
			//头插
			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return make_pair(iterator(newnode,this,hashi),true);
		}
		iterator Find(const K& key)
		{
			Hash ht;
			KeyOfT kot;

			size_t hashi = ht(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return iterator(cur , this ,hashi);
				}
				cur = cur->_next;
			}
			return end();
		}
		bool Erase(const K& key)
		{
			Hash ht;
			KeyOfT kot;

			size_t hashi = ht(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;
				}
				prev = cur;
				cur = cur->_next;

			}
			return false;
		}
		void Some()
		{
			size_t bucketsize = 0;
			size_t maxbucketlen = 0;
			size_t sumbucketlen = 0;
			double averagebucketlen = 0;
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur == nullptr)
				{
					++bucketsize;
				}
				size_t bucketlen = 0;
				while (cur)
				{
					++bucketlen;
					cur = cur->_next;
				}
				sumbucketlen += bucketlen;
				if (bucketlen > maxbucketlen)
				{
					maxbucketlen = bucketlen;
				}
				

			}
			averagebucketlen = (double)sumbucketlen / (double)bucketsize;
			printf("bucketsize:%d\n", bucketsize);
			printf("maxbucketlen:%d\n", maxbucketlen);
			printf("averagebucketlen:%lf\n", averagebucketlen);
			
		}
		
	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
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