• 【哈希表完整代码】模拟实现哈希表和unordered_set与unordered_map

    目录

    HashTable.h:

    Test.cpp:

    MyUnorderedSet.h:

    HashTable.h:

    1. #pragma once
    2. #include
    3. #include
    4. #include//pair头文件
    5. #include
    6. #include
    7.  
    8. using namespace std;
    9.  
    10. namespace CLOSEHASH
    11. {
    12. 	enum State
    13. 	{
    14. 		EMPTY, //空
    15. 		EXIST, //存在
    16. 		DELETE //删除
    17. 	};
    18.  
    19. 	template<class T>
    20. 	struct HashData
    21. 	{
    22. 		T _data;
    23. 		State _state; //代表数据状态
    24.  
    25. 		HashData()
    26. 			:_state(EMPTY)
    27. 			,_data(0)
    28. 		{}
    29. 	};
    30.  
    31. 	template<class K, class T, class KeyOfT>
    32. 	class HashTable
    33. 	{
    34. 		typedef HashData HashData;
    35. 	public:
    36. 		bool Insert(const T& data)
    37. 		{
    38. 			KeyOfT koft;
    39. 			//1、增容：第一次插入或者负载因子>=0.7就要增容
    40. 			if (_tables.capacity() == 0 || _num * 10 / _tables.capacity() == 7)
    41. 			{
    42. 				//A、增容——传统思路
    43. 				//vector newtables;
    44. 				//size_t newcapacity = _tables.capacity() == 0 ? 10 : _tables.capacity() * 2;
    45. 				//newtables.resize(newcapacity);//开空间+自动初始化为0
    46. 				把旧空间数据拷贝到新空间中
    47. 				//for (size_t i = 0; i < _tables.capacity(); ++i)
    48. 				//{
    49. 				//	if (_tables[i]._state == EXIST)
    50. 				//	{
    51. 				//		size_t index = koft(_tables[i]._data) % newtables.capacity();
    52. 				//		while (newtables[index]._state == EXIST)
    53. 				//		{
    54. 				//			index++;
    55.  
    56. 				//			if (index == newtables.capacity())
    57. 				//			{
    58. 				//				index = 0;//走到尾了就要返回头找位置
    59. 				//			}
    60. 				//		}
    61. 				//		newtables[index] = _tables[i];
    62. 				//	}
    63. 				//}
    64.  
    65. 				//_tables.swap(newtables);
    66.  
    67. 				//B、增容——简便思路
    68. 				HashTable newht;
    69. 				size_t newcapacity = _tables.capacity() == 0 ? 10 : _tables.capacity() * 2;
    70. 				newht._tables.resize(newcapacity);
    71.  
    72. 				for (size_t i = 0; i < _tables.capacity(); ++i)
    73. 				{
    74. 					if (_tables[i]._state == EXIST)
    75. 					{
    76. 						newht.Insert(_tables[i]._data);//把原哈希表中每个数据利用Insert都插入到新哈希表中
    77. 					}
    78. 				}
    79.  
    80. 				_tables.swap(newht._tables);//交换两者的vector
    81. 			}
    82.  
    83. 			//1、线性探测
    84. 			//size_t index = koft(data) % _tables.capacity();//计算出要映射的位置
    85. 			//while (_tables[index]._state == EXIST)
    86. 			//{
    87. 			//	if (koft(_tables[index]._data) == koft(data))
    88. 			//	{
    89. 			//		return false;//如果存在相同的数据
    90. 			//	}
    91.  
    92. 			//	++index;
    93. 			//	if (index == _tables.capacity())
    94. 			//	{
    95. 			//		index = 0;
    96. 			//	}
    97. 			//}
    98.  
    99. 			//2、二次探测
    100. 			size_t start = koft(data) % _tables.capacity();
    101. 			size_t index = start;
    102. 			int i = 1;
    103. 			while (_tables[index]._state == EXIST)
    104. 			{
    105. 				if (koft(_tables[index]._data) == koft(data))
    106. 				{
    107. 					return false;
    108. 				}
    109.  
    110. 				index = start + i * i;
    111. 				++i;
    112. 				index %= _tables.capacity();
    113. 			}
    114.  
    115. 			//插入数据
    116. 			_tables[index]._data = data;
    117. 			_tables[index]._state = EXIST;
    118. 			++_num;		//有效数据个数++
    119. 			
    120. 			return true;
    121. 		}
    122.  
    123. 		HashData* Find(const K& key)
    124. 		{
    125. 			KeyOfT koft;
    126. 			size_t index = key % _tables.capacity();
    127. 			while(_tables[index]._state != EMPTY)
    128. 			{//只要是存在和删除状态就要持续往下找
    129. 				if (koft(_tables[index]._data) == key)
    130. 				{
    131. 					if (_tables[index]._state == EXIST)
    132. 						return &_tables[index];//值相等且为存在状态
    133. 					else
    134. 						return nullptr;//值相等但为删除状态，说明被删除了
    135. 				}
    136.  
    137. 				++index;//没找到继续往后找
    138. 				index %= _tables.capacity();
    139. 			}
    140.  
    141. 			return nullptr;
    142. 		}
    143.  
    144. 		bool Erase(const K& key)
    145. 		{
    146. 			HashData* ret = Find(key);
    147. 			if (ret)
    148. 			{
    149. 				ret->_state = DELETE;//用状态代表删除状态
    150. 				--_num; //--有效元素个数
    151. 				return true;
    152. 			}
    153. 			else
    154. 			{
    155. 				return false;
    156. 			}
    157. 		}
    158.  
    159. 	private:
    160. 		vector _tables;
    161. 		size_t _num = 0;	//表中存了多少个有效个数，不等于容量
    162. 	};
    163. }
    164.  
    165. namespace OPENHASH
    166. {
    167. 	template<class T>
    168. 	struct HashNode
    169. 	{
    170. 		T _data;
    171. 		HashNode* _next;
    172.  
    173. 		HashNode(const T& data)
    174. 			:_data(data)
    175. 			, _next(nullptr)
    176. 		{}
    177. 	};
    178.  
    179. 	//前置声明：为了让哈希表的迭代器能用哈希表
    180. 	template<class K, class T, class KeyOfT, class Hash>
    181. 	class HashTable;		
    182.  
    183. 	template<class K, class T, class KeyOfT, class Hash>
    184. 	struct __HashTableIterator
    185. 	{
    186. 		typedef __HashTableIterator Self;
    187. 		typedef HashTable HT;
    188. 		typedef HashNode Node;
    189. 		Node* _node;//迭代器中存的是节点指针
    190. 		HT* _pht;//对象的指针
    191.  
    192. 		__HashTableIterator(Node* node, HT* pht)
    193. 			:_node(node)
    194. 			,_pht(pht)
    195. 		{}
    196.  
    197. 		T& operator*()
    198. 		{
    199. 			return _node->_data;
    200. 		}
    201.  
    202. 		T* operator->()
    203. 		{
    204. 			return &_node->_data;
    205. 		}
    206.  
    207. 		Self operator++()
    208. 		{
    209. 			if (_node->_next)
    210. 			{
    211. 				_node = _node->_next;
    212. 			}
    213. 			else
    214. 			{
    215. 				// 如果一个桶走完了，要往下找到下一个桶继续遍历
    216. 				KeyOfT koft;
    217. 				//先计算我当前是在哪个桶
    218. 				size_t i = _pht->HashFunc(koft(_node->_data)) % _pht->_tables.capacity();
    219. 				++i;//下一个桶
    220. 				for (; i < _pht->_tables.capacity(); ++i)
    221. 				{	//找不为空的桶
    222. 					Node* cur = _pht->_tables[i];
    223. 					if (cur)
    224. 					{	//如果这个桶不为空
    225. 						_node = cur;
    226. 						return *this;
    227. 					}
    228. 				}
    229.  
    230. 				_node = nullptr;//如果没有找到有数据的桶，则指针置为空,与end()相符
    231. 				return *this;
    232. 			}
    233. 		}
    234.  
    235. 		bool operator!=(const Self& s)
    236. 		{
    237. 			return _node != s._node;
    238. 		}
    239. 	};
    240.  
    241. 	template<class K>
    242. 	struct _Hash
    243. 	{
    244. 		const K& operator()(const K& key)
    245. 		{
    246. 			return key;//可以取模的直接返回即可
    247. 		}
    248. 	};
    249.  
    250. 	//特化
    251. 	template<>
    252. 	struct _Hash
    253. 	{
    254. 		size_t operator()(const string& key)
    255. 		{
    256. 			//运用BKDR Hash算法
    257. 			size_t hash = 0;
    258. 			for (size_t i = 0; i < key.size(); ++i)
    259. 			{
    260. 				hash *= 131; //BKDR
    261. 				hash += key[i];//字符串中每个字母ASCII码值相加
    262. 			}
    263.  
    264. 			return hash;
    265. 		}
    266. 	};
    267.  
    268. 	template<class K, class T, class KeyOfT, class Hash>
    269. 	class HashTable
    270. 	{
    271. 		typedef HashNode Node;
    272. 	public:
    273. 		friend struct __HashTableIterator;//因为迭代器要访问哈希表的私有成员_tables
    274. 		typedef __HashTableIterator iterator;
    275.  
    276. 		//begin()返回第一个不为空的桶的第一个节点
    277. 		iterator begin()
    278. 		{
    279. 			for (size_t i = 0; i < _tables.capacity(); ++i)
    280. 			{
    281. 				if (_tables[i])
    282. 				{
    283. 					return iterator(_tables[i], this);//找到了则构造匿名对象返回
    284. 				}
    285. 			}
    286.  
    287. 			return end();//每个桶中都没找到则返回end()
    288. 		}
    289.  
    290. 		iterator end()
    291. 		{
    292. 			return iterator(nullptr, this);
    293. 		}
    294.  
    295. 		size_t HashFunc(const K& key)
    296. 		{
    297. 			Hash hash;
    298. 			return hash(key);//利用仿函数把key值转为整形
    299. 		}
    300.  
    301. 		size_t GetNextPrime(size_t num)
    302. 		{
    303. 			const int PRIMECOUNT = 28;
    304. 			static const size_t primeList[PRIMECOUNT] =
    305. 			{
    306. 			53ul, 97ul, 193ul, 389ul, 769ul,1543ul, 3079ul, 6151ul,
    307. 			12289ul, 24593ul,49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    308. 			1572869ul, 3145739ul, 6291469ul, 12582917ul,25165843ul,50331653ul,
    309. 			100663319ul, 201326611ul, 402653189ul,805306457ul,1610612741ul, 
    310. 			3221225473ul, 4294967291ul
    311. 			};
    312. 			
    313. 			for (size_t i = 0;; i < PRIMECOUNT; ++i)
    314. 			{
    315. 				if (primeList[i] > num)
    316. 					return primeList[i];
    317. 			}
    318.  
    319. 			return primeList[PRIMECOUNT - 1];//如果num比我表中所有数据都大，默认返回表中最后一个
    320. 		}
    321.  
    322. 		pairbool> Insert(const T& data)
    323. 		{
    324. 			KeyOfT koft;
    325. 			//1、判断是否增容
    326. 			if (_tables.capacity() == _num)
    327. 			{	//开散列的实现平衡因子为1就增容且第一次插入也会增容
    328. 				//size_t newcapacity = _tables.capacity() == 0 ? 10 : _tables.capacity() * 2;
    329. 				size_t newcapacity = GetNextPrime(_tables.capacity());
    330. 				vector newtables;
    331. 				newtables.resize(newcapacity, nullptr);//给新的vector开新空间+初始化
    332. 				//重新计算旧表的数据在新表中的映射位置
    333. 				for (size_t i = 0; i < _tables.capacity(); ++i)
    334. 				{	//如果是第一次的增容不会进for循环的，故不用担忧表的初始数据是否为nullptr
    335. 					//哈希表中每一个桶都是一个单链表，故考察单链表的头插
    336. 					Node* cur = _tables[i];
    337. 					while (cur)
    338. 					{
    339. 						Node* next = cur->_next;
    340. 						size_t index = HashFunc(koft(cur->_data)) % newtables.capacity();//重新计算映射位置
    341. 						//头插
    342. 						cur->_next = newtables[index];
    343. 						newtables[index] = cur;
    344. 						 
    345. 						cur = next;
    346. 					}
    347. 					_tables[i] = nullptr;//映射到新表后置为空
    348. 				}
    349.  
    350. 				_tables.swap(newtables);//新旧表的vector交换
    351.  
    352. 			}
    353.  
    354. 			size_t index = HashFunc(koft(data)) % _tables.capacity();//计算新的映射位置
    355.  
    356. 			//1、先查找这个元素是否在哈希表中
    357. 			Node* cur = _tables[index];//知道映射位置就能确定是哪个桶
    358. 			while (cur)
    359. 			{
    360. 				if (koft(cur->_data) == koft(data))
    361. 					return make_pair(iterator(cur, this), false);//找到相同数据则插入失败
    362. 				else
    363. 					cur = cur->_next;
    364. 			}
    365.  
    366. 			//2、头插到这个桶中
    367. 			Node* newnode = new Node(data);//开辟新节点
    368. 			//头插
    369. 			newnode->_next = _tables[index];
    370. 			_tables[index] = newnode;
    371.  
    372. 			++_num;//哈希表中有效元素个数++
    373. 			return make_pair(iterator(newnode, this), false);
    374. 		}
    375.  
    376.  
    377. 		Node* Find(const K& key)
    378. 		{
    379. 			KeyOfT koft;
    380. 			size_t index = HashFunc(key) % _tables.capacity();//先计算映射位置
    381. 			Node* cur = _tables[index];
    382. 			while (cur)
    383. 			{
    384. 				if (koft(cur->_data) == key)
    385. 					return cur;
    386. 				else
    387. 					cur = cur->_next;
    388. 			}
    389.  
    390. 			return nullptr;//走遍桶都没找到则返回空
    391. 		}
    392.  
    393. 		bool Erase(const K& key)
    394. 		{
    395. 			assert(_tables.capacity() > 0);//有空间才能删
    396.  
    397. 			KeyOfT koft;
    398. 			size_t index = HashFunc(key) % _tables.capacity();
    399. 			Node* cur = _tables[index];
    400. 			Node* prev = nullptr;//记录cur的前一位置
    401.  
    402. 			while (cur)
    403. 			{
    404. 				if (koft(cur->_data) == key)
    405. 				{
    406. 					if (prev == nullptr)
    407. 					{	//如果是头删
    408. 						_tables[index] = cur->_next;
    409. 					}
    410. 					else
    411. 					{
    412. 						prev->_next = cur->_next;
    413. 					}
    414. 					delete cur;
    415. 					--_num;
    416.  
    417. 					return true;
    418. 				}
    419. 				else
    420. 				{
    421. 					prev = cur;
    422. 					cur = cur->_next;
    423. 				}
    424. 			}
    425.  
    426. 			return false;//要删除数据根本不存在
    427. 		}
    428.  
    429. 		~HashTable()
    430. 		{
    431. 			Clear();
    432. 			//vector不用我们释放，因为它是自定义类型，哈希表要清理时，vector也会自动清理
    433. 		}
    434.  
    435. 		void Clear()
    436. 		{
    437. 			for (size_t i = 0; i < _tables.capacity(); ++i)
    438. 			{
    439. 				Node* cur = _tables[i];
    440. 				while (cur)
    441. 				{
    442. 					Node* next = cur->_next;
    443. 					delete cur;
    444. 					cur = next;
    445. 				}
    446.  
    447. 				_tables[i] = nullptr;//清空完数据后置为nullptr
    448. 			}
    449. 		}
    450.  
    451. 	private:
    452. 		vector _tables; //使用vector一定要包含std库，不然使用不了
    453. 		size_t _num = 0;      //有效元素的个数，不是容量
    454. 	};
    455.  
    456. }
    457.

    Test.cpp:

    1. #include"HashTable.h"
    2. #include"MyUnorderedMap.h"
    3. #include"MyUnorderedSet.h"
    4.  
    5. template<class K>
    6. struct SetKeyOfT
    7. {
    8. 	const K& operator()(const K& key)
    9. 	{
    10. 		return key;
    11. 	}
    12. };
    13.  
    14. void TestCloseHash()
    15. {
    16. 	CLOSEHASH::HashTable<int, int, SetKeyOfT<int>> ht;
    17. 	//CLOSEHASH::HashTable> ht2;
    18.  
    19. 	ht.Insert(2);
    20. 	ht.Insert(4);
    21. 	ht.Insert(14);
    22. 	ht.Insert(24);
    23. 	ht.Insert(26);
    24. 	ht.Insert(16);
    25.  
    26. 	ht.Erase(14);
    27. 	ht.Erase(2);
    28.  
    29. 	CLOSEHASH::HashData<int>* data = ht.Find(4);
    30. }
    31.  
    32. void TestOpenHash1()
    33. {
    34. 	using OPENHASH::_Hash;
    35.  
    36. 	OPENHASH::HashTable<int, int, SetKeyOfT<int>, _Hash<int>> ht;
    37. 	//OPENHASH::HashTable> ht2;
    38.  
    39. 	ht.Insert(2);
    40. 	ht.Insert(4);
    41. 	ht.Insert(14);
    42. 	ht.Insert(24);
    43. 	ht.Insert(26);
    44. 	ht.Insert(16);
    45.  
    46. 	ht.Erase(14);
    47. 	ht.Erase(2);
    48.  
    49. 	OPENHASH::HashNode<int>* Node = ht.Find(4);
    50.  
    51. 	/*ht2.Insert(make_pair(1,1));
    52. 	ht2.Insert(4);
    53. 	ht2.Insert(14);
    54. 	ht2.Insert(24);
    55. 	ht2.Insert(26);
    56. 	ht2.Insert(16);
    58. 	ht2.Erase(14);
    59. 	ht2.Erase(2);
    61. 	HashNode* Node2 = ht2.Find(4);*/
    62.  
    63. }
    64.  
    65. void TestOpenHash2()
    66. {
    67. 	using OPENHASH::_Hash;
    68.  
    69. 	OPENHASH::HashTable,_Hash> ht;
    70. 	ht.Insert("sort");
    71. 	ht.Insert("futile");
    72. 	ht.Insert("plight");
    73.  
    74. 	cout << ht.HashFunc("abcd") << endl;
    75. 	cout << ht.HashFunc("aadd") << endl;
    76.  
    77. }
    78.  
    79. int main()
    80. {
    81. 	//TestCloseHash();
    82. 	//TestOpenHash1();
    83. 	//TestOpenHash2();
    84. 	//mz::test_unordered_set();
    85. 	mz::test_unordered_map();
    86.  
    87.  
    88. 	return 0;
    89. }

    MyUnorderedSet.h:

    1. #pragma once
    2. #include"HashTable.h"
    3. using namespace OPENHASH;
    4.  
    5. namespace mz
    6. {
    7. 	using OPENHASH::_Hash;
    8. 	template<class K, class Hash = _Hash>
    9. 	class unordered_set
    10. 	{
    11. 		struct SetKOfT
    12. 		{
    13. 			const K& operator()(const K& k)
    14. 			{
    15. 				return k;
    16. 			}
    17. 		};
    18.  
    19. 	public:
    20. 		//加typename是告诉编译器这是个类型，你先让我过，等实例化了再去找
    21. 		//因为模板没实例化它是不接受你用模板里面的一个类型，故要用typename 
    22.  
    23. 		typedef typename HashTable::iterator iterator;
    24. 		iterator begin()
    25. 		{
    26. 			return _ht.begin();
    27. 		}
    28.  
    29. 		iterator end()
    30. 		{
    31. 			return _ht.end();
    32. 		}
    33. 		pairbool> insert(const K& k)
    34. 		{
    35. 			return _ht.Insert(k);
    36. 		}
    37. 	private:
    38. 		HashTable _ht;
    39. 	};
    40.  
    41. 	void test_unordered_set()
    42. 	{
    43. 		unordered_set<int> s;
    44. 		s.insert(1);
    45. 		s.insert(5);
    46. 		s.insert(4);
    47. 		s.insert(2);
    48.  
    49. 		unordered_set<int>::iterator it = s.begin();
    50. 		while (it != s.end())
    51. 		{
    52. 			cout << *it << " ";
    53. 			++it;
    54. 		}
    55. 		cout << endl;
    56. 	}
    57. }

    MyUnorderedMap.h:

    1. #pragma once
    2. #include"HashTable.h"
    3. using namespace OPENHASH;
    4.  
    5. namespace mz
    6. {
    7. 	using OPENHASH::_Hash;
    8. 	template<class K, class V, class Hash = _Hash>//一般模板参数都是由上一层来控制的
    9. 	class unordered_map
    10. 	{
    11. 		struct MapKOfT 
    12. 		{
    13. 			const K& operator()(const pair& kv)
    14. 			{
    15. 				return kv.first;
    16. 			}
    17. 		};
    18.  
    19. 	public:
    20.  
    21. 		typedef typename HashTable, MapKOfT, Hash>::iterator iterator;
    22. 		iterator begin()
    23. 		{
    24. 			return _ht.begin();
    25. 		}
    26. 		
    27. 		iterator end()
    28. 		{
    29. 			return _ht.end();
    30. 		}
    31.  
    32. 		pairbool> insert(const pair& kv)
    33. 		{
    34. 			return _ht.Insert(kv);
    35. 		}
    36.  
    37. 		V& operator[](const K& key)
    38. 		{
    39. 			pairbool> ret = _ht.Insert(make_pair(key, V()));
    40. 			return ret.first->second;
    41. 		}
    42.  
    43. 	private:
    44. 		HashTable, MapKOfT, Hash> _ht;//底层是个哈希表
    45. 	};
    46.  
    47. 	void test_unordered_map()
    48. 	{
    49. 		unordered_map dict;
    50. 		dict.insert(make_pair("factual", "真实的"));
    51. 		dict.insert(make_pair("fringe", "侵犯"));
    52. 		dict.insert(make_pair("intermittent", "间歇的"));
    53. 		dict["prerequisite"] = "先决条件";
    54. 		dict["reduce to"] = "处于";
    55.  
    56. 		//unordered_map::iterator it = dict.begin();
    57. 		auto it = dict.begin();
    58. 		while (it != dict.end())
    59. 		{
    60. 			cout << it->first << ":" << it->second << endl;
    61. 			++it;
    62. 		}
    63. 		cout << endl;
    64.  
    65. 	}
    66. }

  • 相关阅读:
    数据结构之二叉搜索树
    Unity Shader顶点数据疑问
    ElasticSearch：实现高效数据搜索与分析的利器！项目中如何应用落地，让我带你实操指南。
    融云云盘，不止于存储
    【Vue】搭建vuex环境
    Git 详细安装教程（详解 Git 安装过程的每一个步骤）
    比Tensorflow还强？
    解决uniapp打包过大问题的实用方法
    ES5中实现继承
    CatFly【汇编代码还原】
  • 原文地址：https://blog.csdn.net/m0_74044018/article/details/133973253