devbox
Monodyee
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【C++进阶】哈希表的实现_c++ 哈希实现

作者：Monodyee | 2024-05-14 23:07:24

赞

踩

c++ 哈希实现

文章目录

哈希表的概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( l o g 2 N log_2 N log2​N)，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
这篇博客我们简单的介绍一下哈希表，重点是哈希表的实现，下次的博客会为大家详细的介绍一下哈希表。

线性探测哈希表的实现

哈希表的结构

在这里插入图片描述
在这里插入图片描述

哈希表数据的结构

在这里插入图片描述

插入

在这里插入图片描述

查找

在这里插入图片描述

删除

在这里插入图片描述

二次探测哈希表的实现

哈希表的结构

在这里插入图片描述
在这里插入图片描述

哈希表数据的结构

在这里插入图片描述

插入

在这里插入图片描述

查找

在这里插入图片描述

删除

在这里插入图片描述

链式哈希表(哈希桶)的实现

哈希表的结构

在这里插入图片描述

哈希表数据的结构

在这里插入图片描述

插入

在这里插入图片描述

查找

在这里插入图片描述

删除

在这里插入图片描述

整体的代码

#pragma once
#include <vector>
template<class K>
struct Hash
{
	size_t operator()(const K& key)
	{
		return key;
	}
};
template<>
struct Hash<string>
{
	size_t operator()(const string& s)
	{
		size_t value = 0;
		for (auto& ch : s)
		{
			value += ch;
		}
		return value;
	}
};
namespace LinearDetectionHash
{
	enum status
	{
		EMPTY,//空
		EXIST,//存在
		DELETE//删除
	};
	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;//要存的值
		status _status = EMPTY;//状态
	};
	
	template<class K,class V,class HashFunc = Hash<K>>
	class HashTable
	{
		
	public:
		HashTable()
		{}
		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_status = DELETE;
				_size--;
				return true;
				
			}
			else
			{
				return false;
			}
		}
		HashData<K, V>* Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}
			HashFunc hf;
			size_t index = hf(key) % _tables.size();
			while (_tables[index]._status == EXIST)
			{
				if (_tables[index]._kv.first == key && _tables[index]._status == EXIST)
				{
					return &_tables[index];
				}
				index++;
			}

			return nullptr;
		}
		bool Insert(const pair<K,V>& kv)
		{
			HashData<K, V>* ret = Find(kv.first);
			HashFunc hf;
			if (ret)
			{
				return false;
			}
			if (_tables.size() == 0 || _size*10 / _tables.size() > 7)
			{
				size_t newsize = _tables.size() == 0 ? 10 : 2 * _tables.size();
				HashTable<K,V> newHT;
				newHT._tables.resize(newsize);
				for (int i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._status == EXIST)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
				_tables.swap(newHT._tables);

			}
			size_t index = hf(kv.first) % _tables.size();
			while (_tables[index]._status == EXIST)
			{
				index++;
				index %= _tables.size();
			}

			_tables[index]._kv = kv;
			_tables[index]._status = EXIST;
			_size++;
			return true;

		}
	private:
		vector<HashData<K,V>> _tables;
		size_t _size = 0;
	};

	void TestHashTable1()
	{
		HashTable<int, int> kv;
		kv.Insert(make_pair(1, 1));
		kv.Insert(make_pair(2, 2));
		kv.Insert(make_pair(3, 3));
		kv.Insert(make_pair(4, 4));
		kv.Insert(make_pair(14, 14));
		kv.Insert(make_pair(24, 24));
		kv.Insert(make_pair(34, 34));
		kv.Insert(make_pair(11, 11));
		kv.Insert(make_pair(21, 21));
		kv.Insert(make_pair(31, 31));
		kv.Insert(make_pair(32, 32));

		/*cout << kv.Find(1) << endl;
		cout << kv.Find(3) << endl;
		cout << kv.Find(14) << endl;
		cout << kv.Find(32) << endl;
		cout << kv.Find(33) << endl;*/
		
	}
	void TestHashTable2()
	{
		HashTable<string, string> kv;
		kv.Insert(make_pair("sort", "排序"));
		kv.Insert(make_pair("soda", "苏打水"));
		kv.Erase("sort");
		cout << kv.Find("sort") << endl;
		cout << kv.Find("test") << endl;

	}
}
namespace SecondaryDetectionHash
{
	enum status
	{
		EMPTY,
		EXIST,
		DELETE
	};
	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		status _status = EMPTY;
	};

	template<class K, class V, class HashFunc = Hash<K>>
	class HashTable
	{

	public:
		HashTable()
		{}
		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_status = DELETE;
				_size--;
				return true;

			}
			else
			{
				return false;
			}
		}
		HashData<K, V>* Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}
			HashFunc hf;
			size_t i = 0;
			size_t index = hf(key) % _tables.size();
			while (_tables[index]._status == EXIST)
			{
				if (_tables[index]._kv.first == key && _tables[index]._status == EXIST)
				{
					return &_tables[index];
				}
				i++;
				index += i*i;
				index %= _tables.size();
			}

			return nullptr;
		}
		bool Insert(const pair<K, V>& kv)
		{
			HashData<K, V>* ret = Find(kv.first);
			HashFunc hf;
			if (ret)
			{
				return false;
			}
			if (_tables.size() == 0 || _size * 10 / _tables.size() > 7)
			{
				size_t newsize = _tables.size() == 0 ? 10 : 2 * _tables.size();
				HashTable<K, V> newHT;
				newHT._tables.resize(newsize);
				for (int i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._status == EXIST)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
				_tables.swap(newHT._tables);

			}
			size_t i = 0;
			size_t index = hf(kv.first) % _tables.size();
			while (_tables[index]._status == EXIST)
			{
				i++;
				index += i * i;
				index %= _tables.size();
			}

			_tables[index]._kv = kv;
			_tables[index]._status = EXIST;
			_size++;
			return true;

		}
	private:
		vector<HashData<K, V>> _tables;
		size_t _size = 0;
	};

	void TestHashTable1()
	{
		HashTable<int, int> kv;
		kv.Insert(make_pair(1, 1));
		kv.Insert(make_pair(2, 2));
		kv.Insert(make_pair(3, 3));
		kv.Insert(make_pair(4, 4));
		kv.Insert(make_pair(14, 14));
		kv.Insert(make_pair(24, 24));
		kv.Insert(make_pair(34, 34));
		kv.Insert(make_pair(11, 11));
		kv.Insert(make_pair(21, 21));
		kv.Insert(make_pair(31, 31));
		kv.Insert(make_pair(32, 32));

		cout << kv.Find(1) << endl;
		cout << kv.Find(3) << endl;
		cout << kv.Find(14) << endl;
		cout << kv.Find(32) << endl;
		cout << kv.Find(33) << endl;

	}
	void TestHashTable2()
	{
		HashTable<string, string> kv;
		kv.Insert(make_pair("sort", "排序"));
		kv.Insert(make_pair("soda", "苏打水"));
		//kv.Erase("sort");
		cout << kv.Find("sort") << endl;
		cout << kv.Find("test") << endl;

	}
}
namespace LinkHash
{
	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 HashFunc = Hash<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		bool Erase(const K& key)
		{
			if (_size == 0)
			{
				return false;
			}
			HashFunc hf;
			size_t index = hf(key) % _tables.size();
			Node* cur = _tables[index];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					Node* next = cur->next;
					
					if(prev)
						prev->next = next;
					else
						_tables[index] = next;

					delete cur;
					cur = nullptr;
					_size--;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->next;
				}
			}
			return false;
		}
		Node* Find(const K& key)
		{
			if (_size == 0)
			{
				return nullptr;
			}
			HashFunc 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)
		{
			Node* ret = Find(kv.first);
			if (ret)
			{
				return false;
			}
			if (_tables.size() == 0 || _size*10 / _tables.size() == 10)
			{
				size_t newsize = _tables.size() == 0 ? 10 : 2 * _tables.size();
				HashTable<K, V> newHT;
				newHT._tables.resize(newsize);
				HashFunc hf;
				for (int i = 0; i < _tables.size(); i++)
				{
						Node* cur = _tables[i];
						while (cur)
						{
							Node* next = cur->next;
							size_t index = hf(cur->_kv.first) % newHT._tables.size();
							if (newHT._tables[index])
							{
								Node* next = newHT._tables[index];
								newHT._tables[index] = cur;
								cur->next = next;
							}
							else
							{
								newHT._tables[index] = cur;
								newHT._tables[index]->next = nullptr;;
							}
							newHT._size++;
							cur = next;
						}
						_tables[i] = nullptr;	
				}
				_tables.swap(newHT._tables);
			}
			HashFunc hf;
			Node* cur = new Node(kv);
			size_t index = hf(kv.first) % _tables.size();
			if (_tables[index])
			{
				Node* next = _tables[index];
				_tables[index] = cur;
				cur->next = next;
			}
			else
			{
				_tables[index] = cur;
			}
			_size++;
			return true;
		}
	private:
		vector<Node*> _tables;
		size_t _size = 0;
	};
	void TestHashTable1()
	{
		HashTable<int, int> kv;
		kv.Insert(make_pair(1, 1));
		kv.Insert(make_pair(2, 2));
		kv.Insert(make_pair(3, 3));
		kv.Insert(make_pair(4, 4));
		kv.Insert(make_pair(14, 14));
		kv.Insert(make_pair(24, 24));
		kv.Insert(make_pair(34, 34));
		kv.Insert(make_pair(11, 11));
		kv.Insert(make_pair(21, 21));
		kv.Insert(make_pair(31, 31));
		kv.Insert(make_pair(32, 32));
		kv.Insert(make_pair(10, 10));

		cout << kv.Find(1) << endl;
		cout << kv.Find(100) << endl;


	}
	void TestHashTable2()
	{
		HashTable<int, int> kv;
		kv.Insert(make_pair(1, 1));
		kv.Insert(make_pair(11, 11));
		kv.Insert(make_pair(2, 2));
		cout << kv.Erase(4) << endl;
		cout << kv.Erase(11) << endl;
		cout << kv.Erase(2) << endl;
		cout << kv.Erase(1) << endl;


	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 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
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/570473
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号