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

【C++】-- STL之用哈希桶模拟实现unordered_set和unordered_map_std中的hash桶

作者：知新_RL | 2024-08-13 06:39:32

赞

踩

std中的hash桶

目录

一、哈希桶节点的修改

二、哈希表

1.构造

2.拷贝构造

3.赋值运算符重载

4.析构

5.迭代器

6.查找

7.插入

8.删除

 三、迭代器

1.operator++( )

2.operator*( )

3.operator->( )

4.operator !=( )

5.operator ==( )

四、封装unordered_set和unordered_map

 1.封装unordered_set

（1）仿函数SetKeyOfT

（2）迭代器

（3）实例

2.封装unordered_map

（1）仿函数MapKeyOfT

（2）迭代器

（3）实例

五、完整代码段

一、哈希桶节点的修改

        用哈希桶封装实现unordered_set和unordered_map，就要考虑到他们传给哈系统的数据元素不同，unordered_set传给哈希桶的是k，unordered_map传给哈希桶的是pair，那么哈希桶面对这两种不同的数据，如何做到统一处理呢？

         面对unordered_set传给哈希桶的是k，unordered_map传给哈希桶的是pair，就把K和V统一封装成T，用T代替pair<K，V>：

  1. 	template<class T>
  2. 	struct HashNode
  3. 	{
  4. 		HashNode<T>* _next;
  5. 		T _data;
  6.  
  7. 		HashNode(const T& data)
  8. 			:_data(data)
  9. 			, _next(nullptr)
  10. 		{}
  11. 	};

二、哈希表

类模板需要修改，模板里面必须包含K，因为要用K来计算数据映射的位置。由于哈希桶的节点类型换成了T ，用T来替代V。KeyOfT仿函数确定上传的是unordered_set还是unordered_map。

  1.     template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
  2. 	class HashTable
  3. 	{
  4. 		typedef HashNode<T> Node;
  5.         
  6.         //哈希桶迭代器
  7. 		template<class K,class T,class KeyOfT,class HashFunc>
  8. 		friend struct __HTIterator;
  9. 	public:
  10. 		typedef __HTIterator<K, T, KeyOfT, HashFunc> iterator;
  11.  
  12.     private:
  13. 		vector<Node*> _table;
  14. 		size_t _n = 0;
  15. 	};

1.构造

使用默认构造函数就可以了，vector自定义类型会调用自己的默认构造函数，size_t作为内置类型编译器不处理：

        HashTable() = default; // 显示指定生成默认构造

2.拷贝构造

_n 直接赋值就可以了。_table的拷贝就需要遍历ht的_table了，并且把ht的_table的每个结点都头插到_table表中：

  1.         //拷贝构造
  2. 		HashTable(const HashTable& ht)
  3. 		{
  4. 			_n = ht._n;//存储有效数据的个数一致
  5. 			_table.resize(ht._table.size());//开同样大小的空间
  6.  
  7. 			//遍历ht，将ht的_table的每个结点都拷贝到_table中
  8. 			for (size_t i = 0; i < ht._table.size(); i++)
  9. 			{
  10. 				Node* cur = ht._table[i];
  11. 				while (cur)
  12. 				{
  13. 					Node* copy = new Node(cur->_data);
  14. 		
  15. 					//头插到新表
  16. 					copy->_next = _table[i];//copy的下一个桶为_table[i]
  17. 					_table[i] = copy;//把copy作为当前位置的第一个桶
  18. 					cur = cur->_next;//cur往下移					
  19. 				}
  20. 			}
  21. 		
  22. 		}

3.赋值运算符重载

只需要交换_table和_n即可：

  1. 		//赋值运算符重载
  2. 		HashTable& operator=(HashTable ht)
  3. 		{
  4. 			_table.swap(ht._table);
  5. 			swap(_n, ht._n);
  6.  
  7. 			return *this;
  8. 		}

4.析构

只需要将_table 的每个结点删除后置空就可以了：

  1. 		//析构
  2. 		~HashTable()
  3. 		{
  4. 			for (size_t i = 0; i < _table.size(); i++)
  5. 			{
  6. 				Node* cur = _table[i];
  7. 				while (cur)
  8. 				{
  9. 					Node* next = cur->_next;
  10. 					delete cur;
  11. 					cur = next;
  12. 				}
  13. 				_table[i] = nullptr;
  14. 			}
  15. 		}

5.迭代器

迭代器的参数包含节点位置和哈希表地址，在下一节迭代器中会讲，为什么都要使用指针：

  1. 		//迭代器开始
  2.         iterator begin()
  3. 		{
  4. 			size_t i = 0;
  5. 			while (i < _table.size())
  6. 			{
  7. 				if (_table[i])
  8. 				{
  9. 					return iterator(_table[i], this);
  10. 				}
  11. 				++i;
  12. 			}
  13. 	
  14. 			return end();
  15. 		}
  16. 		
  17.         //迭代器结束
  18. 		iterator end()
  19. 		{
  20. 			return iterator(nullptr, this);
  21. 		}

6.查找

 这时候就要用到仿函数KeyOfT了，仿函数KeyOfT的对象kot对于unordered_set会取k，对于unordered_map会取作为pair的kv的first作为k和key进行比较：

  1. 		//查找
  2. 		iterator Find(const K& key)
  3. 		{
  4. 			//哈希表为空
  5. 			if (_table.size() == 0)
  6. 			{
  7. 				return end();
  8. 			}
  9. 		
  10. 			KeyOfT kot;
  11. 			HashFunc hf;
  12. 			size_t index = hf(key) % _table.size();//计算在哈希表中的位置
  13. 			
  14. 			//在哈希表当前位置的所有桶中找key
  15. 			Node* cur = _table[index];
  16. 			while (cur)
  17. 			{
  18. 				if (kot(cur->_data) == key)
  19. 				{
  20. 					return iterator(cur,this);
  21. 				}
  22. 				else
  23. 				{
  24. 					cur = cur->_next;
  25. 				}
  26. 			}
  27. 		
  28. 			return end();
  29. 		}

7.插入

①需要先判断data在不在哈希桶中，在就直接返回查找到的位置

②如果不在，需要判断哈希桶需不需要增容，如果不需要增容就计算映射位置头插到哈希表中

③需要增容就要取旧表中的节点一一头插到新表中，并交换旧表和新表

  1. 		//插入
  2. 		pair<iterator,bool> Insert(const T& data)
  3. 		{
  4. 			KeyOfT kot;
  5. 			auto ret = Find(kot(data));
  6. 			if (ret != end())
  7. 			{
  8. 				return make_pair(ret,false);
  9. 			}
  10. 		
  11. 			//仿函数
  12. 			HashFunc hf;
  13. 		
  14. 			//负载因子为1时，进行增容
  15. 			if (_n == _table.size())
  16. 			{
  17. 				vector<Node*> newTable;
  18. 				newTable.resize(GetNextPrime(_table.size()));
  19. 		
  20. 				//取旧表中的结点，重新计算映射到新表中的位置，挂到新表中
  21. 				for (size_t i = 0; i < _table.size(); i++)
  22. 				{
  23. 					if (_table[i])
  24. 					{
  25. 						Node* cur = _table[i];
  26. 						while (cur)
  27. 						{
  28. 							Node* next = cur->_next;//保存下一个结点
  29. 							size_t index = hf(kot(cur->_data)) % newTable.size();//计算结映射到新表中的位置
  30. 		
  31. 							//头插
  32. 							cur->_next = newTable[index];//=nullptr,将cur->_next置空
  33. 							newTable[index] = cur;//将结点插入到新表
  34. 							cur = next;//哈希桶往下挪一个
  35. 						}
  36. 						_table[i] = nullptr;//当前哈希桶的第一个位置置空
  37. 					}
  38. 				}
  39. 				_table.swap(newTable);
  40. 			}
  41. 		
  42. 			//不需要增容时，头插
  43. 			size_t index = hf(kot(data)) % _table.size();
  44. 			Node* newNode = new Node(data);
  45. 		
  46. 			newNode->_next = _table[index];//让新节点newNode的next指向第一个桶
  47. 			_table[index] = newNode;//让新节点newNode做第一个桶
  48. 			++_n;//更新哈希表大小	
  49.  
  50. 			return make_pair(iterator(newNode, this), true);
  51. 		}

8.删除

①删除节点之前要先保留该节点的前一个 节点，否则删除改节点后，让前一个节点要指向下一个，但是又找不到前一个节点了。

②当找到key的映射位置后，要判断找到的节点是不是当前位置的第一个桶，如果是，就让当前位置指向下一个节点；如果不是就直接让前一个节点指向后一个节点。

  1. 		//删除
  2. 		bool Erase(const K& key)
  3. 		{
  4. 			size_t index = hf(key) % _table.size();
  5. 			Node* prev = nullptr;
  6. 			Node* cur = _table[index];
  7. 		
  8. 			while (cur)
  9. 			{
  10. 				if (kot(cur->data) == key)//cur这个桶就是key
  11. 				{
  12. 					if (_table[index] == cur)//cur是第一个桶
  13. 					{
  14. 						_table[index] = cur->_next;
  15. 					}
  16. 					else//cur不是第一个桶
  17. 					{
  18. 						prev->_next = cur->_next;
  19. 					}
  20. 		
  21. 					--_n;//更新表大小
  22. 					delete cur;//删除节点
  23. 					return true;
  24. 				}
  25. 		
  26. 				prev = cur;
  27. 				cur = cur->_next;
  28. 			}
  29. 		
  30. 			return false;
  31. 		}

 三、迭代器

        迭代器需要前置声明HashTable，因为HashTable类中使用了__HTIterator迭代器，且__HTIterator中使用了HashTable类的指针，为什么要用指针呢？
        因为C++编译器自上而下编译源文件的时候，对每一个数据的定义，需要知道定义的数据类型的大小。在预先声明语句class HashTable;之后，编译器已经知道HashTable是一个类，但是其中的数据却是未知的，因此HashTable类型的大小也不知道，这样就造成了编译失败；将__HTIterator中的_node更改为HashTable指针类型之后，由于在特定的平台上，指针所占的空间是一定的（在Win32平台上是4字节，在64位平台上是8字节），这样可以通过编译。
       

迭代器的参数包含哈希节点和哈希表：

  1. 	// 前置声明
  2. 	template<class K, class T, class KeyOfT, class HashFunc>
  3. 	class HashTable;
  4.  
  5. 	// 迭代器
  6. 	template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
  7. 	struct __HTIterator
  8. 	{
  9. 		typedef HashNode<T> Node;//哈希节点
  10. 		typedef __HTIterator<K, T, KeyOfT, HashFunc> Self;//实现++、--
  11. 		typedef HashTable<K, T, KeyOfT, HashFunc> HT;//哈希表
  12. 		Node* _node;
  13. 		HT* _pht;
  14.  
  15. 		__HTIterator(Node* node, HT* pht)
  16. 			:_node(node)//哈希节点
  17. 			, _pht(pht)//哈希表
  18. 		{}
  19.     };

1.operator++( )

如下图，operator++ 分两种情况：

①当前节点不是哈希表当前位置的最后一个节点，如2、53，返回当前节点的next节点

②当前节点是哈希表当前位置的最后一个节点，如852、63，需要返回下一个非空位置的第一个节点

 

  1. 		Self& operator++()
  2. 		{
  3. 			//不是当前位置最后一个节点
  4. 			if (_node->_next)
  5. 			{
  6. 				_node = _node->_next;
  7. 			}
  8. 			else//是当前位置最后一个节点
  9. 			{
  10. 				KeyOfT kot;
  11. 				HashFunc hf;
  12.  
  13. 				size_t index = hf(kot(_node->_data)) % _pht->_table.size();
  14.  
  15. 				//找哈希表中下一个不为空的位置
  16. 				++index;
  17. 				while (index < _pht->_table.size())
  18. 				{
  19. 					if (_pht->_table[index])//不为空
  20. 					{
  21. 						_node = _pht->_table[index];
  22. 						return *this;
  23. 					}
  24. 					else//为空
  25. 					{
  26. 						++index;
  27. 					}
  28. 				}
  29. 				_node = nullptr;//后面的所有位置都为空，_node置空，返回当前位置即可
  30. 			}
  31.  
  32. 			return *this;
  33. 		}

2.operator*( )

取_data即可： 

  1. 		T& operator*()
  2. 		{
  3. 			return _node->_data;
  4. 		}

3.operator->( )

 取_data的地址即可：

  1. 		T* operator->()
  2. 		{
  3. 			return &_node->_data;
  4. 		}

4.operator !=( )

将s的_node和_node进行比较：

  1. 		bool operator != (const Self& s) const
  2. 		{
  3. 			return _node != s._node;
  4. 		}

5.operator ==( )

将s的_node和_node进行比较：

  1. 		bool operator == (const Self& s) const
  2. 		{
  3. 			return _node == s._node;
  4. 		}

四、封装unordered_set和unordered_map

 1.封装unordered_set

unordered_set的成员就是哈希表，不过要传模板参数，SetKeyOfT就是传给哈希表的仿函数

  1. #pragma once
  2. #include "HashTable.h"
  3.  
  4. namespace delia
  5. {
  6. 	template<class K>
  7. 	class unordered_set
  8. 	{
  9.  
  10. 	private:
  11. 		OpenHash::HashTable<K, K, SetKeyOfT> _ht ;
  12.  
  13. 	};
  14. }

（1）仿函数SetKeyOfT

 set直接取k:

  1. 		//set就取k
  2. 		struct SetKeyOfT
  3. 		{
  4. 			const K& operator()(const K& k)
  5. 			{
  6. 				return k;
  7. 			}
  8. 		};

（2）迭代器

        对于unordered_set的迭代器，如果不加typename，类模板里面找迭代器的类型找不到，因为OpenHash::HashTable<K, K, SetKeyOfT>::iterator没有实例化，因此编译器并不知道它是类型还是成员函数或成员变量，编译无法通过。
        用typename表明OpenHash::HashTable<K, K, SetKeyOfT>::iterator是一个类型，不是成员函数或成员变量，不需要等到实例化时才能确定。

        unordered_set的迭代器都调用哈希表的迭代器进行操作：

  1. 	public:
  2. 		typedef typename OpenHash::HashTable<K, K, SetKeyOfT>::iterator iterator;
  3.  
  4. 		iterator begin()
  5. 		{
  6. 			return _ht.begin();
  7. 		}
  8.  
  9. 		iterator end()
  10. 		{
  11. 			return _ht.end();
  12. 		}
  13.  
  14. 		pair<iterator, bool> Insert(const K& k)
  15. 		{
  16. 			return _ht.Insert(k);
  17. 		}

（3）实例

向unordered_set中插入一些数据，并打印：

  1. 	void test_unordered_set1()
  2. 	{
  3. 		unordered_set<int> us;
  4. 		us.Insert(100);
  5. 		us.Insert(5);
  6. 		us.Insert(6);
  7. 		us.Insert(32);
  8. 		us.Insert(8);
  9. 		us.Insert(14);
  10. 		us.Insert(65);
  11. 		us.Insert(27);
  12. 		us.Insert(39);
  13.  
  14. 		unordered_set<int>::iterator it = us.begin();
  15. 		while (it != us.end())
  16. 		{
  17. 			cout << *it << " ";
  18. 			++it;
  19. 		}
  20. 		cout << endl;
  21. 	}

2.封装unordered_map

unordered_map的成员就是哈希表，不过要传模板参数，MapKeyOfT就是传给哈希表的仿函数 :

  1. #pragma once
  2. #include "HashTable.h"
  3.  
  4. namespace delia
  5. {
  6. 	template<class K,class V>
  7. 	class unordered_map
  8.     {
  9.  
  10.     
  11.     private:
  12. 		OpenHash::HashTable<K, pair<K, V>, MapKeyOfT> _ht;
  13.  
  14. 	};

（1）仿函数MapKeyOfT

map就取kv的first: 

  1. 		//map就取kv的first
  2. 		struct MapKeyOfT
  3. 		{
  4. 			const K& operator()(const pair<K,V>& kv)
  5. 			{
  6. 				return kv.first;
  7. 			}
  8. 		};

（2）迭代器

  同unordered_set的迭代器定义一样，前面要加上typename，unordered_map的迭代器都调用哈希表的迭代器进行操作：

  1. 	public:
  2. 		typedef typename OpenHash::HashTable<K, pair<K,V>, MapKeyOfT>::iterator iterator;
  3.  
  4. 		iterator begin()
  5. 		{
  6. 			return _ht.begin();
  7. 		}
  8.  
  9. 		iterator end()
  10. 		{
  11. 			return _ht.end();
  12. 		}
  13.  
  14. 		pair<iterator, bool> Insert(const pair<K,V>& kv)
  15. 		{
  16. 			return _ht.Insert(kv);
  17. 		}
  18.  
  19. 		V& operator[](const K& key)
  20. 		{
  21. 			pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
  22. 			return ret.first->iterator;
  23. 		}

（3）实例

  1. 	void test_unordered_map1()
  2. 	{
  3. 		unordered_map<string,string> um;
  4. 		um.Insert(make_pair("spring", "春天"));
  5. 		um.Insert(make_pair("summer", "夏天"));
  6. 		um.Insert(make_pair("autumn", "秋天"));
  7. 		um.Insert(make_pair("winter", "冬天"));
  8.  
  9. 		unordered_map<string,string>::iterator it = um.begin();
  10. 		while (it != um.end())
  11. 		{
  12. 			cout << it->first << ":" << it->second << endl;
  13. 			++it;
  14. 		}
  15. 	}

五、完整代码段

HashTable.h

  1. #pragma once
  2. #include<vector>
  3. #include<iostream>
  4. using namespace std;
  5.  
  6. namespace OpenHash
  7. {
  8. 	//哈希仿函数
  9. 	template<class K>
  10. 	struct Hash
  11. 	{
  12. 		size_t operator()(const K& key)
  13. 		{
  14. 			return key;
  15. 		}
  16. 	};
  17.  
  18. 	//string仿函数
  19. 	template<>
  20. 	struct Hash<string>//模板特化
  21. 	{
  22. 		size_t operator()(const string& s)
  23. 		{
  24. 			size_t value = 0;
  25. 			for (auto e : s)
  26. 			{
  27. 				value += e;
  28. 				value *= 131;
  29. 			}
  30.  
  31. 			return value;
  32. 		}
  33. 	};
  34.  
  35. 	template<class T>
  36. 	struct HashNode
  37. 	{
  38. 		HashNode<T>* _next;
  39. 		T _data;
  40.  
  41. 		HashNode(const T& data)
  42. 			:_data(data)
  43. 			, _next(nullptr)
  44. 		{}
  45. 	};
  46.  
  47. 	//前置声明HashTable,因为HashTable类中使用了__HTIterator，且__HTIterator中使用了HashTable类的指针，为什么要用指针
  48. 	//C++编译器自上而下编译源文件的时候，对每一个数据的定义，总是需要知道定义的数据类型的大小。在预先声明语句class HashTable;之后，编译器已经知道HashTable是一个类，但是其中的数据却是未知的，因此HashTable类型的大小也不知道，这样就造成了编译失败；将__HTIterator中的_node更改为HashTable指针类型之后，由于在特定的平台上，指针所占的空间是一定的（在Win32平台上是4字节，在64位平台上是8字节），这样可以通过编译
  49. 		// 前置声明
  50. 	template<class K, class T, class KeyOfT, class HashFunc>
  51. 	class HashTable;
  52.  
  53. 	// 迭代器
  54. 	template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
  55. 	struct __HTIterator
  56. 	{
  57. 		typedef HashNode<T> Node;//哈希节点
  58. 		typedef __HTIterator<K, T, KeyOfT, HashFunc> Self;//实现++、--
  59. 		typedef HashTable<K, T, KeyOfT, HashFunc> HT;//哈希表
  60. 		Node* _node;
  61. 		HT* _pht;
  62.  
  63. 		__HTIterator(Node* node, HT* pht)
  64. 			:_node(node)//哈希节点
  65. 			, _pht(pht)//哈希表
  66. 		{}
  67. 	
  68. 		Self& operator++()
  69. 		{
  70. 			//不是当前位置最后一个节点
  71. 			if (_node->_next)
  72. 			{
  73. 				_node = _node->_next;
  74. 			}
  75. 			else//是当前位置最后一个节点
  76. 			{
  77. 				KeyOfT kot;
  78. 				HashFunc hf;
  79.  
  80. 				size_t index = hf(kot(_node->_data)) % _pht->_table.size();
  81.  
  82. 				//找哈希表中下一个不为空的位置
  83. 				++index;
  84. 				while (index < _pht->_table.size())
  85. 				{
  86. 					if (_pht->_table[index])//不为空
  87. 					{
  88. 						_node = _pht->_table[index];
  89. 						return *this;
  90. 					}
  91. 					else//为空
  92. 					{
  93. 						++index;
  94. 					}
  95. 				}
  96. 				_node = nullptr;//后面的所有位置都为空，_node置空，返回当前位置即可
  97. 			}
  98.  
  99. 			return *this;
  100. 		}
  101.  
  102. 		T& operator*()
  103. 		{
  104. 			return _node->_data;
  105. 		}
  106.  
  107. 		T* operator->()
  108. 		{
  109. 			return &_node->_data;
  110. 		}
  111.  
  112. 		bool operator != (const Self& s) const
  113. 		{
  114. 			return _node != s._node;
  115. 		}
  116.  
  117. 		bool operator == (const Self& s) const
  118. 		{
  119. 			return _node == s._node;
  120. 		}
  121. 	};
  122.  
  123. 	template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
  124. 	class HashTable
  125. 	{
  126. 		typedef HashNode<T> Node;
  127.  
  128. 		template<class K,class T,class KeyOfT,class HashFunc>
  129. 		friend struct __HTIterator;
  130. 	public:
  131. 		typedef __HTIterator<K, T, KeyOfT, HashFunc> iterator;
  132. 	
  133. 		//构造函数,default指定生成默认构造函数
  134. 		HashTable() = default;
  135.  
  136. 		//拷贝构造
  137. 		HashTable(const HashTable& ht)
  138. 		{
  139. 			_n = ht._n;//存储有效数据的个数一致
  140. 			_table.resize(ht._table.size());//开同样大小的空间
  141.  
  142. 			//遍历ht，将ht的每个结点都拷贝到_table中
  143. 			for (size_t i = 0; i < ht._table.size(); i++)
  144. 			{
  145. 				Node* cur = ht._table[i];
  146. 				while (cur)
  147. 				{
  148. 					Node* copy = new Node(cur->_data);
  149. 		
  150. 					//头插到新表
  151. 					copy->_next = _table[i];//copy的下一个桶为_table[i]
  152. 					_table[i] = copy;//把copy作为当前位置的第一个桶
  153. 					cur = cur->_next;//cur往下移					
  154. 				}
  155. 			}
  156. 		
  157. 		}
  158.  
  159. 		//赋值运算符重载
  160. 		HashTable& operator=(HashTable ht)
  161. 		{
  162. 			_table.swap(ht._table);
  163. 			swap(_n, ht._n);
  164.  
  165. 			return *this;
  166. 		}
  167.  
  168. 		//析构
  169. 		~HashTable()
  170. 		{
  171. 			for (size_t i = 0; i < _table.size(); i++)
  172. 			{
  173. 				Node* cur = _table[i];
  174. 				while (cur)
  175. 				{
  176. 					Node* next = cur->_next;
  177. 					delete cur;
  178. 					cur = next;
  179. 				}
  180. 				_table[i] = nullptr;
  181. 			}
  182. 		}
  183.  
  184. 		iterator begin()
  185. 		{
  186. 			size_t i = 0;
  187. 			while (i < _table.size())
  188. 			{
  189. 				if (_table[i])
  190. 				{
  191. 					return iterator(_table[i], this);
  192. 				}
  193. 				++i;
  194. 			}
  195. 	
  196. 			return end();
  197. 		}
  198. 		
  199. 		iterator end()
  200. 		{
  201. 			return iterator(nullptr, this);
  202. 		}
  203. 	
  204. 		size_t GetNextPrime(size_t prime)
  205. 		{
  206. 			const int PRIMECOUNT = 28;
  207. 			static const size_t primeList[PRIMECOUNT] =
  208. 			{
  209. 				53ul,97ul,193ul,389ul,769ul,
  210. 				1543ul,3079ul,6151ul,12289ul,24593ul,
  211. 				49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
  212. 				1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
  213. 				50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
  214. 				1610612741ul, 3221225473ul, 4294967291ul
  215. 			};
  216. 	
  217. 			size_t i = 0;
  218. 			for (; i < PRIMECOUNT; i++)
  219. 			{
  220. 				if (primeList[i] > prime)
  221. 				{
  222. 					return primeList[i];
  223. 				}
  224. 			}
  225. 	
  226. 			return primeList[i];
  227. 		}
  228.  
  229. 		//插入
  230. 		pair<iterator,bool> Insert(const T& data)
  231. 		{
  232. 			KeyOfT kot;
  233. 			auto ret = Find(kot(data));
  234. 			if (ret != end())
  235. 			{
  236. 				return make_pair(ret,false);
  237. 			}
  238. 		
  239. 			//仿函数
  240. 			HashFunc hf;
  241. 		
  242. 			//负载因子为1时，进行增容
  243. 			if (_n == _table.size())
  244. 			{
  245. 				vector<Node*> newTable;
  246. 				newTable.resize(GetNextPrime(_table.size()));
  247. 		
  248. 				//取旧表中的结点，重新计算映射到新表中的位置，挂到新表中
  249. 				for (size_t i = 0; i < _table.size(); i++)
  250. 				{
  251. 					if (_table[i])
  252. 					{
  253. 						Node* cur = _table[i];
  254. 						while (cur)
  255. 						{
  256. 							Node* next = cur->_next;//保存下一个结点
  257. 							size_t index = hf(kot(cur->_data)) % newTable.size();//计算结映射到新表中的位置
  258. 		
  259. 							//头插
  260. 							cur->_next = newTable[index];//=nullptr,将cur->_next置空
  261. 							newTable[index] = cur;//将结点插入到新表
  262. 							cur = next;//哈希桶往下挪一个
  263. 						}
  264. 						_table[i] = nullptr;//当前哈希桶的第一个位置置空
  265. 					}
  266. 				}
  267. 				_table.swap(newTable);
  268. 			}
  269. 		
  270. 			//不需要增容时，头插
  271. 			size_t index = hf(kot(data)) % _table.size();
  272. 			Node* newNode = new Node(data);
  273. 		
  274. 			newNode->_next = _table[index];//让新节点newNode的next指向第一个桶
  275. 			_table[index] = newNode;//让新节点newNode做第一个桶
  276. 			++_n;//更新哈希表大小	
  277.  
  278. 			return make_pair(iterator(newNode, this), true);
  279. 		}
  280. 		
  281. 		//查找
  282. 		iterator Find(const K& key)
  283. 		{
  284. 			//哈希表为空
  285. 			if (_table.size() == 0)
  286. 			{
  287. 				return end();
  288. 			}
  289. 		
  290. 			KeyOfT kot;
  291. 			HashFunc hf;
  292. 			size_t index = hf(key) % _table.size();//计算在哈希表中的位置
  293. 			
  294. 			//在哈希表当前位置的所有桶中找key
  295. 			Node* cur = _table[index];
  296. 			while (cur)
  297. 			{
  298. 				if (kot(cur->_data) == key)
  299. 				{
  300. 					return iterator(cur,this);
  301. 				}
  302. 				else
  303. 				{
  304. 					cur = cur->_next;
  305. 				}
  306. 			}
  307. 		
  308. 			return end();
  309. 		}
  310. 		
  311. 		//删除
  312. 		bool Erase(const K& key)
  313. 		{
  314. 			size_t index = hf(key) % _table.size();
  315. 			Node* prev = nullptr;
  316. 			Node* cur = _table[index];
  317. 		
  318. 			while (cur)
  319. 			{
  320. 				if (kot(cur->data) == key)//cur这个桶就是key
  321. 				{
  322. 					if (_table[index] == cur)//cur是第一个桶
  323. 					{
  324. 						_table[index] = cur->_next;
  325. 					}
  326. 					else//cur不是第一个桶
  327. 					{
  328. 						prev->_next = cur->_next;
  329. 					}
  330. 		
  331. 					--_n;//更新表大小
  332. 					delete cur;//删除节点
  333. 					return true;
  334. 				}
  335. 		
  336. 				prev = cur;
  337. 				cur = cur->_next;
  338. 			}
  339. 		
  340. 			return false;
  341. 		}
  342.  
  343. 	private:
  344. 		vector<Node*> _table;
  345. 		size_t _n = 0;
  346. 	};
  347. }

 UnorderedSet.h

  1. #pragma once
  2. #include "HashTable.h"
  3.  
  4. namespace delia
  5. {
  6. 	template<class K>
  7. 	class unordered_set
  8. 	{
  9. 		//set就取k
  10. 		struct SetKeyOfT
  11. 		{
  12. 			const K& operator()(const K& k)
  13. 			{
  14. 				return k;
  15. 			}
  16. 		};
  17.  
  18. 	public:
  19. 		//如果不加typename，类模板里面找迭代器的类型找不到，因为OpenHash::HashTable<K, K, SetKeyOfT>::iterator没有实例化，因此编译器并不知道它是类型还是成员函数或成员变量，编译无法通过
  20. 		//用typename表明OpenHash::HashTable<K, K, SetKeyOfT>::iterator是一个类型，不是成员函数或成员变量，不需要等到实例化时才能确定
  21. 		typedef typename OpenHash::HashTable<K, K, SetKeyOfT>::iterator iterator;
  22.  
  23. 		iterator begin()
  24. 		{
  25. 			return _ht.begin();
  26. 		}
  27.  
  28. 		iterator end()
  29. 		{
  30. 			return _ht.end();
  31. 		}
  32.  
  33. 		pair<iterator, bool> Insert(const K& k)
  34. 		{
  35. 			return _ht.Insert(k);
  36. 		}
  37.  
  38. 	private:
  39. 		OpenHash::HashTable<K, K, SetKeyOfT> _ht ;
  40.  
  41. 	};
  42.  
  43. 	void test_unordered_set1()
  44. 	{
  45. 		unordered_set<int> us;
  46. 		us.Insert(100);
  47. 		us.Insert(5);
  48. 		us.Insert(6);
  49. 		us.Insert(32);
  50. 		us.Insert(8);
  51. 		us.Insert(14);
  52. 		us.Insert(65);
  53. 		us.Insert(27);
  54. 		us.Insert(39);
  55.  
  56. 		unordered_set<int>::iterator it = us.begin();
  57. 		while (it != us.end())
  58. 		{
  59. 			cout << *it << " ";
  60. 			++it;
  61. 		}
  62. 		cout << endl;
  63. 	}
  64. }

UnorderedMap.h

  1. #pragma once
  2. #include "HashTable.h"
  3.  
  4. namespace delia
  5. {
  6. 	template<class K,class V>
  7. 	class unordered_map
  8. 	{
  9. 		//map就取kv的first
  10. 		struct MapKeyOfT
  11. 		{
  12. 			const K& operator()(const pair<K,V>& kv)
  13. 			{
  14. 				return kv.first;
  15. 			}
  16. 		};
  17.  
  18. 	public:
  19. 		typedef typename OpenHash::HashTable<K, pair<K,V>, MapKeyOfT>::iterator iterator;
  20.  
  21. 		iterator begin()
  22. 		{
  23. 			return _ht.begin();
  24. 		}
  25.  
  26. 		iterator end()
  27. 		{
  28. 			return _ht.end();
  29. 		}
  30.  
  31. 		pair<iterator, bool> Insert(const pair<K,V>& kv)
  32. 		{
  33. 			return _ht.Insert(kv);
  34. 		}
  35.  
  36. 		V& operator[](const K& key)
  37. 		{
  38. 			pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
  39. 			return ret.first->iterator;
  40. 		}
  41.  
  42. 	private:
  43. 		OpenHash::HashTable<K, pair<K, V>, MapKeyOfT> _ht;
  44.  
  45. 	};
  46.  
  47. 	void test_unordered_map1()
  48. 	{
  49. 		unordered_map<string,string> um;
  50. 		um.Insert(make_pair("spring", "春天"));
  51. 		um.Insert(make_pair("summer", "夏天"));
  52. 		um.Insert(make_pair("autumn", "秋天"));
  53. 		um.Insert(make_pair("winter", "冬天"));
  54.  
  55. 		unordered_map<string,string>::iterator it = um.begin();
  56. 		while (it != um.end())
  57. 		{
  58. 			cout << it->first << ":" << it->second << endl;
  59. 			++it;
  60. 		}
  61. 	}
  62. }

Test.cpp

  1. #define  _CRT_SECURE_NO_WARNINGS  1
  2. #include "HashTable.h"
  3. #include "UnorderedSet.h"
  4. #include "UnorderedMap.h"
  5.  
  6. int main()
  7. {
  8. 	delia::test_unordered_set1();
  9. 	delia::test_unordered_map1();
  10.  
  11. 	return 0;
  12. }

运行结果：

unordered_set:

由于哈希表的初始大小为primeList中的第一个元素53，因此插入时:

100%53=47，

5%53=5，

6%53=6，

8%53=8，

65%53=12，

14%53=14，

27%53=27，

32%53=32，

39%53=39

且都没有发生冲突，因此排列顺序为5，6，8，65，14，27，32，39，100。

 

unordered_map:

字符串的Hash算法让每个字符*131再求和，再对53取模：

ASCII对照表如下：

97a
98b
99c
100d
101e
102f
103g
104h
105i
106j
107k
108l
109m
110n
111o
112p
113q
114r
115s
116t
117u
118v
119w
120x
121y
122z

spring:(((((((115*131)+112)*131)+114)*131+105)*131+110)*131+103)*131=359074819，中间发生了溢出，所以得到结果359074819，再用359074819对53取模，sunmmer，autumn和winter也都这么计算


 

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

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

  

闽ICP备14008679号