• C++--哈希表的实现及unorder_set和unorder_map的封装

    1.什么是哈希表

    哈希表是一种数据结构，用来存放数据的，哈希表存放的数据是无序的，可以实现增删查，当时不能修改数据。可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)。
    unordered_map是存储键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。
    在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
    在内部,unordered_map没有对按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
    unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
    unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
    它的迭代器至少是前向迭代器。

    unorder_set是用来存储的关联式容器，可以用来快速的查找和去重，在内部是按照无序的方式排列的，它的迭代器和unorder_map的使用相同，其他的特性和unorder_map的特性差不多。

    2.哈希冲突

    对于两个数据元素的关键字$k_i$和 $k_j$(i != j)，有$k_i$ != $k_j$，但有：Hash($k_i$) ==
    Hash($k_j$)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

    解决哈希冲突：

    引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
    哈希函数设计原则：
    哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值
    域必须在0到m-1之间；哈希函数计算出来的地址能均匀分布在整个空间中；哈希函数应该比较简单。

    解决哈希冲突两种常见的方法是：闭散列和开散列

    闭散列：

    线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

    通过哈希函数获取待插入元素在哈希表中的位置，如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。

    开散列：

    开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地
    址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链
    接起来，各链表的头结点存储在哈希表中。

    开散列与闭散列比较：
    应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上：
    由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <=
    0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

    3.哈希表的实现

    闭散列的实现：

    1. #include 
    2. #include 
    3. #include 
    4. //usng namespace std;
    5. using std::cout;
    6. using std:: endl;
    7. using std::cin;
    8. //闭散列
    9. namespace open_address
    10. {
    11.  //处理不是整形的字符
    12. 	template<class T>
    13. 	struct DefaultHashFunc
    14. 	{
    15. 		size_t operator()(const T& t)
    16. 		{
    17. 			return size_t(value(t));
    18.  
    19. 		}
    20. 	};
    21.  //特殊化处理字符串
    22. 	template<>
    23. 	struct DefaultHashFunc
    24. 	{
    25. 		const size_t operator()(const string& t)
    26. 		{
    27. 			//KeyofT value;
    28. 			size_t num=1;
    29. 			for (auto e : t)
    30. 			{
    31. 				num *= 131;
    32. 				num +=e;
    33. 			}
    34. 			return num;
    35.  
    36. 		}
    37. 	};
    38.  //枚举三种状态
    39. 	enum State
    40. 	{
    41. 		Empty,
    42. 		Exist,
    43. 		Delete
    44. 	};
    45.  //哈希节点
    46. 	template<class T>
    47. 	struct HashDateNode
    48. 	{
    49. 	private:
    50. 		T _kv;
    51. 		State _state=Empty;
    52. 	};
    53. //哈希表
    54. 	template<class K, class T,class KeyofT,class DefaultHashFunc>
    55. 	class HashTable
    56. 	{
    57. 		typedef HashDateNode Node;
    58. 		HashTable()//初始化，开辟10个空间
    59. 		{
    60. 			_Date.resize(10);
    61. 		}
    62. 		//插入数值
    63. 		bool insert(const T& Date)
    64. 		{
    65.  
    66. 			DefaultHashFunc Func;//处理字符串问题
    67. 			KeyofT value;//处理set和map的数值问题函数
    68. 			//扩容
    69. 			if (n * 10 > _Date.size() * 7)//负载因子
    70. 			{
    71. 				int newsize = _Date.size() * 2;
    72. 				vector newHT;
    73. 				newHT.resize(newsize);//开辟空间
    74. 				for (int i = 0; i < _Date.size(); i++)
    75. 				{
    76. 					if (_Date._state == Exist)//讲旧数据写入新空间中
    77. 					{
    78. 						newHT.insert(KetofT(_Date));
    79. 					}
    80. 					_Date.swap(newHT._Date);//交换数据
    81. 				}
    82. 			}
    83. 			//插入哈希表
    84. 			size_t hashi =Func(value(Date))% _Date.size();
    85. 			while (_Date[hashi]._state == Exist)//存在就++
    86. 			{
    87. 				++hashi;
    88. 				hashi %= _Date.size();
    89. 			}
    90. 			_Date[hashi]._kv = Date;
    91. 			_Date[hashi]._state = Exist;
    92. 			n++;//存放个数加一
    93. 			return true;
    94. 		}
    95. 		//查找函数
    96. 		vector Find(const K& t)
    97. 		{
    98. 			
    99. 			DefaultHashFunc Func;
    100. 			KeyofT value;
    101. 			size_t hashi = Func(value(t)) % _Date.size();
    102. 			while (_Date[hashi]._state != Empty)
    103. 			{
    104. 				if (_Date[hashi]._state == Exist
    105. 					&& value(_Date[hashi]) == t)
    106. 				{
    107. 					return   _Date[hashi];
    108. 				}
    109.  
    110. 				++hashi;
    111. 				hashi %= _Date.size();
    112. 			}
    113.  
    114. 			return nullptr;
    115.  
    116. 		}
    117.  //删除
    118. 		bool erash(const K& key)
    119. 		{
    120. 			
    121. 			vector ret = Find(key);//查找是否存在
    122. 			if (ret)
    123. 			{
    124. 				ret._state= Exist;
    125. 				n--;
    126. 				return true;
    127. 			}
    128. 			return false;
    129. 		}
    130.  
    131. 	private:
    132. 		vector _Date;//数据
    133. 		size_t n;//存储有效个数
    134. 	};
    135. }

    开散列的实现

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5. //处理字符
    6. template<class T>
    7. struct DefaultHashFunc
    8. {
    9. 	size_t operator()(const T& t)
    10. 	{
    11. 		return size_t(t);
    12. 	}
    13. };template<>
    14. struct DefaultHashFunc
    15. {
    16. 	size_t operator()(const string& t)
    17. 	{
    18. 		size_t num = 0;
    19. 		for (auto e : t)
    20. 		{
    21. 			num *= 131;
    22. 			num += e;
    23. 		}
    24. 		return num;
    25. 	}
    26. };
    27. //哈希桶，闭散列
    28. namespace hash_bucket
    29. {
    30. 	template<class T> 
    31. 	struct HashDateNode
    32. 	{
    33. 		T _Date;
    34. 		HashDateNode* _next;
    35.  
    36. 		HashDateNode(const T& Date)
    37. 			:_Date(Date)
    38. 			,_next(nullptr)
    39. 		{}
    40. 	};
    41. 	
    42. 	template<class K, class T, class KeyofT, class HashFunc>
    43. 	class HashDate;//前置声明
    44.  
    45. 	//迭代器
    46. 	//template//旧版
    47. 	template<class K, class T, class Ptr, class Ref, class KeyofT, class HashFunc>//新版
    48. 	struct HashIterator
    49. 	{
    50. 		typedef HashDateNode Node;
    51. 		
    52. 		typedef HashIterator Self;
    53. 		typedef HashIterator iterator;
    54.  
    55. 		Node* _node;
    56. 		const HashDate* _pht; //设置位const ，防止普通类型无法转化为const类型
    57.  
    58. 		//初始化
    59. 		/*const HashIterator(Node* node, HashDate* pht)
    60. 			:_node(node)
    61. 			, _pht(pht)
    62. 		{}*/
    63.  
    64. 		//const初始化
    65. 		HashIterator(Node* node, const HashDate*  pht)
    66. 			:_node(node)
    67. 			, _pht(pht)
    68. 		{}
    69.  
    70.  
    71. 		// 普通迭代器时，他是拷贝构造
    72. 		// const迭代器时，他是构造函数
    73. 		HashIterator(const iterator& it)//防止set类型的const类型与非const类型的转换（模板不同）
    74. 			:_node(it._node)
    75. 			, _pht(it._pht)
    76. 		{}
    77.  
    78.  
    79. 		Ref operator*()
    80. 		{
    81. 			return _node->_Date;
    82. 		}
    83. 		Ptr operator->()
    84. 		{
    85. 			return &_node->_Date;
    86. 		}
    87. 		bool operator!=(const Self& s)
    88. 		{
    89. 			return _node != s._node;
    90. 		}
    91. 		bool operator==(const Self& s)
    92. 		{
    93. 			return _node == s._node;
    94. 		}
    95. 		Self& operator++()
    96. 		{
    97. 			if (_node->_next)
    98. 			{
    99. 				_node = _node->_next;
    100. 			}
    101. 			else
    102. 			{
    103. 				HashFunc Func;
    104. 				KeyofT value;
    105. 				size_t hashi = Func(value(_node->_Date)) % _pht->_table.size(); //该用仿函数
    106. 				//从下一个哈希桶查找
    107. 				hashi++;
    108. 				while (hashi < _pht->_table.size())
    109. 				{
    110. 					if (_pht->_table[hashi])//不为空
    111. 					{
    112. 						_node = _pht->_table[hashi];
    113. 						return *this;
    114. 					}
    115. 					else//为空
    116. 					{
    117. 						++hashi;
    118. 					}
    119. 				}
    120. 				_node = nullptr;
    121. 			}
    122. 			return *this;
    123. 		}
    124.  
    125. 	};
    126.  
    127. 	template<class K, class T, class KeyofT, class HashFunc = DefaultHashFunc>
    128. 	class HashDate
    129. 	{
    130. 		typedef HashDateNode Node;
    131. 		
    132. 		// 
    133. 		//友元
    134. 		template<class K, class T, class Ptr, class Ref, class KeyofT, class HashFunc>
    135. 		friend struct HashIterator;//可以使用迭代器
    136.  
    137. 	public:
    138. 		typedef HashIterator iterator;
    139. 		typedef HashIteratorconst T*, const T&, KeyofT, HashFunc> const_iterator;
    140.  
    141. 		iterator begin()
    142. 		{
    143. 			for (size_t i = 0; i < _table.size(); i++)
    144. 			{
    145. 				Node* cur = _table[i];
    146. 				if (cur)
    147. 				{
    148. 					return iterator(cur,this);
    149. 				}
    150. 			}
    151.  
    152. 			return iterator(nullptr, this);
    153. 		}
    154.  
    155. 		const_iterator begin() const
    156. 		{
    157. 			for (size_t i = 0; i < _table.size(); i++)
    158. 			{
    159. 				Node* cur = _table[i];
    160. 				if (cur)
    161. 				{
    162. 					return iterator(cur, this);
    163. 				}
    164. 			}
    165.  
    166. 			return iterator(nullptr, this);
    167. 		}
    168.  
    169. 		iterator end() 
    170. 		{
    171. 			return iterator(nullptr, this);
    172. 		}
    173.  
    174. 		
    175. 		const_iterator end() const
    176. 		{
    177. 			return iterator(nullptr, this);
    178. 		}
    179. 		HashDate()
    180. 		{
    181. 			_table.resize(10, nullptr);
    182. 		}
    183.  
    184. 		~HashDate()
    185. 		{
    186. 			for (size_t i = 0; i < _table.size(); i++)
    187. 			{
    188. 				Node* cur = _table[i];
    189. 				while (cur)
    190. 				{
    191. 					Node* next = cur->_next;
    192. 					delete cur;
    193. 					cur = next;
    194. 				}
    195.  
    196. 				_table[i] = nullptr;
    197. 			}
    198. 		}
    199.  
    200. 		pairbool> Insert(const T& date)
    201. 		{
    202. 			
    203. 			KeyofT value;
    204. 			HashFunc Func;
    205. 			iterator it = Find(value(date));
    206. 			//it!=end()
    207. 			if(it != end())
    208. 			{
    209. 				return make_pair(it,false);
    210. 			}
    211.  
    212. 			if (n == _table.size())//扩容
    213. 			{
    214. 				int newsize = _table.size() * 2;
    215. 				vector newHash;
    216. 				newHash.resize(newsize);
    217. 				for (size_t i = 0; i < _table.size(); i++)//旧数据
    218. 				{
    219. 					Node* cur = _table[i];
    220. 					while (cur)
    221. 					{
    222. 						Node* next = cur->_next;
    223. 						size_t hashi = Func(value(cur->_Date))% newsize;
    224. 						cur->_next = newHash[hashi];
    225. 						newHash[hashi] = cur;
    226. 						cur = next;
    227. 					}
    228. 					_table[i] = nullptr;
    229. 				}
    230. 				_table.swap(newHash);//交换数据
    231. 			}
    232. 			//插入
    233. 			size_t hashi = Func(value(date))% _table.size();//改变
    234. 			//Node* cur = _table[hashi];
    235. 			//尾插
    236. 			//Node* newNode = new Node(date);
    237. 			//while (cur)
    238. 			//{
    239. 			//	cur = cur->_next;
    240. 			//}
    241. 			//cur = newNode;
    242. 			//头插
    243. 			Node* newNode = new Node(date);//新节点
    244. 			newNode->_next = _table[hashi];//头结点
    245. 			_table[hashi] = newNode;//尾节点
    246. 		
    247. 			n++;
    248. 			return make_pair(iterator(newNode,this),true);
    249. 		}
    250.  
    251.  
    252. 		//查找
    253. 		iterator Find(const K& key)//Find为K类型的只用一个数值，T类型的在map中为pair类型
    254. 		{
    255. 			HashFunc Func;
    256. 			KeyofT value;
    257. 			size_t hashi = Func(key) % _table.size();
    258. 			//size_t hashi = Func(value(key)) % _table.size();//不能使用这个
    259. 			Node* cur = _table[hashi];
    260. 			while (cur)
    261. 			{
    262. 				if (value(cur->_Date) == key)//?
    263. 				{
    264. 					return iterator(cur,this);
    265. 				}
    266. 				cur = cur->_next;
    267. 			}
    268. 			return iterator(nullptr,this);
    269. 		}
    270.  
    271. 		//删除
    272. 		bool Erase(const K& key)
    273. 		{
    274. 			HashFunc Func;
    275. 			KeyofT value;
    276. 			iterator ret=Find(key);
    277. 			if (ret == end())
    278. 				return true;
    279. 			size_t x = Func(value(key))% _table.size();
    280. 			Node* cur = _table[x];
    281. 			Node* prev = nullptr;
    282. 			while (cur)
    283. 			{
    284. 				if (value(cur->_Date) == key)
    285. 				{
    286. 					if (prev == nullptr)
    287. 					{
    288. 						_table[x] = cur->_next;
    289. 					}
    290. 					else
    291. 					{
    292. 						prev->_next = cur->_next;
    293. 					}
    294. 					
    295. 				}
    296. 				prev = cur;
    297. 				cur = cur->_next;
    298. 				delete cur;
    299. 				return true;
    300. 			}
    301. 			return false;
    302. 		}
    303. 		//打印
    304. 		void Print()
    305. 		{
    306. 			for (int i = 10; i < _table.size(); i++)
    307. 			{
    308. 				Node* cur = _table[i];
    309. 				while (cur)
    310. 				{
    311. 					std::cout << cur->_Date.first<<" " << cur->_Date.second <<" " << std::endl;
    312. 					cur = cur->_next;
    313. 				}
    314. 			}
    315. 			std::cout << std::endl;
    316. 		}
    317.  
    318. 	private:
    319. 		vector _table; //存储数据
    320. 		size_t n=0; //记录容器中的个数
    321. 	};
    322. }

    4.Unorderset和Unordermap的实现

    4.1 Unorderset

    1. #pragma once
    2. #include "HashTable.h"
    3. using namespace hash_bucket;
    4. //using namespace open_address;
    5.  
    6.  
    7. template<class K>
    8. class Unorderset
    9. {
    10. 	struct SetKeyofT
    11. 	{
    12. 		const K& operator()(const K& k)
    13. 		{
    14. 			return k;
    15. 		}
    16. 	};
    17. public:
    18. 	typedef typename hash_bucket::HashDate::const_iterator iterator;
    19. 	typedef typename hash_bucket::HashDate::const_iterator const_iterator;
    20.  
    21. 	//typedef typename hash_bucket::HashDate Hash;
    22. public:
    23. 	const_iterator begin() const
    24. 	{
    25. 		return _ht.begin();
    26. 	}
    27. 	const_iterator end() const
    28. 	{
    29. 		return _ht.end();
    30. 	}
    31. 	pairbool> insert(const K& k)
    32. 	{
    33. 		return _ht.Insert(k);
    34. 	}
    35. 	iterator find(const K& kk)
    36. 	{
    37. 		return _ht.Find(kk);
    38. 	}
    39. 	bool erase(const K& kk)
    40. 	{
    41. 		return _ht.Erase(kk);
    42. 	}
    43. private:
    44. 	HashDate _ht;
    45. };

    4.2 Unordermap

    1. #pragma once
    2. #include "HashTable.h"
    3. using namespace hash_bucket;
    4. template<class K,class T>
    5. class Unordermap
    6. {
    7. 	struct MapkeyofT
    8. 	{
    9. 		const K& operator()(const pair<const K, T>& kt)
    10. 		{
    11. 			return kt.first;
    12. 		}
    13. 	};
    14. public:
    15. 	typedef typename hash_bucket::HashDateconst K, T>, MapkeyofT>::iterator iterator;//普通迭代器
    16. 	typedef typename hash_bucket::HashDateconst K, T>, MapkeyofT>::const_iterator const_iterator;//const迭代器
    17. 	//typedef typename hash_bucket::HashDate, MapkeyofT> Hash;
    18. 	iterator begin()
    19. 	{
    20. 		return _ht.begin();
    21. 	}
    22. 	iterator end()
    23. 	{
    24. 		return _ht.end();
    25. 	}
    26. 	const_iterator begin() const
    27. 	{
    28. 		return _ht.begin();
    29. 	}
    30. 	const_iterator end() const
    31. 	{
    32. 		return _ht.end();
    33. 	}
    34. 	//插入
    35. 	pairbool> insert(const pair& kt)
    36. 	{
    37. 		return _ht.Insert(kt);
    38. 	}
    39. 	//查找
    40. 	iterator find(const K& kk)
    41. 	{
    42. 		return _ht.Find(kk);
    43. 	}
    44. 	//重载[]
    45. 	T& operator[](const K& kk)
    46. 	{
    47. 		pairbool> ret = insert(make_pair(kk, T()));
    48. 		return ret.first->second;
    49. 	}
    50. 	//删除
    51. 	bool eraser(const K& kk)
    52. 	{
    53. 		return _ht.Erase(kk);
    54. 	}
    55. private:
    56. 	HashDateconst K, T>, MapkeyofT> _ht;
    57. };

    4.3 完整代码

    Ps:具体实现中建议分开写

    1. #pragma once
    2. #include "HashTable.h"
    3. using namespace hash_bucket;
    4. using namespace open_address;
    5.  
    6. //set实现
    7. template<class K>
    8. class Unorderset
    9. {
    10. 	struct SetKeyofT
    11. 	{
    12. 		const K& operator()(const K& k)
    13. 		{
    14. 			return k;
    15. 		}
    16. 	};
    17. public:
    18. 	typedef typename hash_bucket::HashDate::const_iterator iterator;
    19. 	typedef typename hash_bucket::HashDate::const_iterator const_iterator;
    20.  
    21. 	//typedef typename hash_bucket::HashDate Hash;
    22. public:
    23. 	const_iterator begin() const
    24. 	{
    25. 		return _ht.begin();
    26. 	}
    27. 	const_iterator end() const
    28. 	{
    29. 		return _ht.end();
    30. 	}
    31. 	pairbool> insert(const K& k)
    32. 	{
    33. 		return _ht.Insert(k);
    34. 	}
    35. 	iterator find(const K& kk)
    36. 	{
    37. 		return _ht.Find(kk);
    38. 	}
    39. 	bool erase(const K& kk)
    40. 	{
    41. 		return _ht.Erase(kk);
    42. 	}
    43. private:
    44. 	HashDate _ht;
    45. };
    46.  
    47. //map实现
    48. template<class K,class T>
    49. class Unordermap
    50. {
    51. 	struct MapkeyofT
    52. 	{
    53. 		const K& operator()(const pair<const K, T>& kt)
    54. 		{
    55. 			return kt.first;
    56. 		}
    57. 	};
    58. public:
    59. 	typedef typename hash_bucket::HashDateconst K, T>, MapkeyofT>::iterator iterator;//普通迭代器
    60. 	typedef typename hash_bucket::HashDateconst K, T>, MapkeyofT>::const_iterator const_iterator;//const迭代器
    61. 	//typedef typename hash_bucket::HashDate, MapkeyofT> Hash;
    62. 	iterator begin()
    63. 	{
    64. 		return _ht.begin();
    65. 	}
    66. 	iterator end()
    67. 	{
    68. 		return _ht.end();
    69. 	}
    70. 	const_iterator begin() const
    71. 	{
    72. 		return _ht.begin();
    73. 	}
    74. 	const_iterator end() const
    75. 	{
    76. 		return _ht.end();
    77. 	}
    78. 	//插入
    79. 	pairbool> insert(const pair& kt)
    80. 	{
    81. 		return _ht.Insert(kt);
    82. 	}
    83. 	//查找
    84. 	iterator find(const K& kk)
    85. 	{
    86. 		return _ht.Find(kk);
    87. 	}
    88. 	//重载[]
    89. 	T& operator[](const K& kk)
    90. 	{
    91. 		pairbool> ret = insert(make_pair(kk, T()));
    92. 		return ret.first->second;
    93. 	}
    94. 	//删除
    95. 	bool eraser(const K& kk)
    96. 	{
    97. 		return _ht.Erase(kk);
    98. 	}
    99. private:
    100. 	HashDateconst K, T>, MapkeyofT> _ht;
    101. };
    102. //底层实现
    103. #pragma once//防止头文件重复引用
    104. #include 
    105. #include 
    106. #include 
    107. using namespace std;
    108.  
    109.  
    110.  //处理不是整形的字符
    111. 	template<class T>
    112. 	struct DefaultHashFunc
    113. 	{
    114. 		size_t operator()(const T& t)
    115. 		{
    116. 			return size_t(value(t));
    117.  
    118. 		}
    119. 	};
    120.  //特殊化处理字符串
    121. 	template<>
    122. 	struct DefaultHashFunc
    123. 	{
    124. 		const size_t operator()(const string& t)
    125. 		{
    126. 			//KeyofT value;
    127. 			size_t num=1;
    128. 			for (auto e : t)
    129. 			{
    130. 				num *= 131;
    131. 				num +=e;
    132. 			}
    133. 			return num;
    134.  
    135. 		}
    136. 	};
    137. //开散列
    138. namespace open_address
    139. {
    140.  
    141.  //枚举三种状态
    142. 	enum State
    143. 	{
    144. 		Empty,
    145. 		Exist,
    146. 		Delete
    147. 	};
    148.  //哈希节点
    149. 	template<class T>
    150. 	struct HashDateNode
    151. 	{
    152. 	private:
    153. 		T _kv;
    154. 		State _state=Empty;
    155. 	};
    156. //哈希表
    157. 	template<class K, class T,class KeyofT,class DefaultHashFunc>
    158. 	class HashTable
    159. 	{
    160. 		typedef HashDateNode Node;
    161. 		HashTable()//初始化，开辟10个空间
    162. 		{
    163. 			_Date.resize(10);
    164. 		}
    165. 		//插入数值
    166. 		bool insert(const T& Date)
    167. 		{
    168.  
    169. 			DefaultHashFunc Func;//处理字符串问题
    170. 			KeyofT value;//处理set和map的数值问题函数
    171. 			//扩容
    172. 			if (n * 10 > _Date.size() * 7)//负载因子
    173. 			{
    174. 				int newsize = _Date.size() * 2;
    175. 				vector newHT;
    176. 				newHT.resize(newsize);//开辟空间
    177. 				for (int i = 0; i < _Date.size(); i++)
    178. 				{
    179. 					if (_Date._state == Exist)//讲旧数据写入新空间中
    180. 					{
    181. 						newHT.insert(KetofT(_Date));
    182. 					}
    183. 					_Date.swap(newHT._Date);//交换数据
    184. 				}
    185. 			}
    186. 			//插入哈希表
    187. 			size_t hashi =Func(value(Date))% _Date.size();
    188. 			while (_Date[hashi]._state == Exist)//存在就++
    189. 			{
    190. 				++hashi;
    191. 				hashi %= _Date.size();
    192. 			}
    193. 			_Date[hashi]._kv = Date;
    194. 			_Date[hashi]._state = Exist;
    195. 			n++;//存放个数加一
    196. 			return true;
    197. 		}
    198. 		//查找函数
    199. 		vector Find(const K& t)
    200. 		{
    201. 			
    202. 			DefaultHashFunc Func;
    203. 			KeyofT value;
    204. 			size_t hashi = Func(value(t)) % _Date.size();
    205. 			while (_Date[hashi]._state != Empty)
    206. 			{
    207. 				if (_Date[hashi]._state == Exist
    208. 					&& value(_Date[hashi]) == t)
    209. 				{
    210. 					return   _Date[hashi];
    211. 				}
    212.  
    213. 				++hashi;
    214. 				hashi %= _Date.size();
    215. 			}
    216.  
    217. 			return nullptr;
    218.  
    219. 		}
    220.  //删除
    221. 		bool erash(const K& key)
    222. 		{
    223. 			
    224. 			vector ret = Find(key);//查找是否存在
    225. 			if (ret)
    226. 			{
    227. 				ret._state= Exist;
    228. 				n--;
    229. 				return true;
    230. 			}
    231. 			return false;
    232. 		}
    233.  
    234. 	private:
    235. 		vector _Date;//数据
    236. 		size_t n;//存储有效个数
    237. 	};
    238. }
    239.  
    240. //哈希桶，闭散列
    241. namespace hash_bucket
    242. {
    243. 	template<class T> 
    244. 	struct HashDateNode
    245. 	{
    246. 		T _Date;
    247. 		HashDateNode* _next;
    248.  
    249. 		HashDateNode(const T& Date)
    250. 			:_Date(Date)
    251. 			,_next(nullptr)
    252. 		{}
    253. 	};
    254. 	
    255. 	template<class K, class T, class KeyofT, class HashFunc>
    256. 	class HashDate;//前置声明
    257.  
    258. 	//迭代器
    259. 	//template//旧版
    260. 	template<class K, class T, class Ptr, class Ref, class KeyofT, class HashFunc>//新版
    261. 	struct HashIterator
    262. 	{
    263. 		typedef HashDateNode Node;
    264. 		
    265. 		typedef HashIterator Self;
    266. 		typedef HashIterator iterator;
    267.  
    268. 		Node* _node;
    269. 		const HashDate* _pht; //设置位const ，防止普通类型无法转化为const类型
    270.  
    271. 		//初始化
    272. 		/*const HashIterator(Node* node, HashDate* pht)
    273. 			:_node(node)
    274. 			, _pht(pht)
    275. 		{}*/
    276.  
    277. 		//const初始化
    278. 		HashIterator(Node* node, const HashDate*  pht)
    279. 			:_node(node)
    280. 			, _pht(pht)
    281. 		{}
    282.  
    283.  
    284. 		// 普通迭代器时，他是拷贝构造
    285. 		// const迭代器时，他是构造函数
    286. 		HashIterator(const iterator& it)//防止set类型的const类型与非const类型的转换（模板不同）
    287. 			:_node(it._node)
    288. 			, _pht(it._pht)
    289. 		{}
    290.  
    291.  
    292. 		Ref operator*()
    293. 		{
    294. 			return _node->_Date;
    295. 		}
    296. 		Ptr operator->()
    297. 		{
    298. 			return &_node->_Date;
    299. 		}
    300. 		bool operator!=(const Self& s)
    301. 		{
    302. 			return _node != s._node;
    303. 		}
    304. 		bool operator==(const Self& s)
    305. 		{
    306. 			return _node == s._node;
    307. 		}
    308. 		Self& operator++()
    309. 		{
    310. 			if (_node->_next)
    311. 			{
    312. 				_node = _node->_next;
    313. 			}
    314. 			else
    315. 			{
    316. 				HashFunc Func;
    317. 				KeyofT value;
    318. 				size_t hashi = Func(value(_node->_Date)) % _pht->_table.size(); //该用仿函数
    319. 				//从下一个哈希桶查找
    320. 				hashi++;
    321. 				while (hashi < _pht->_table.size())
    322. 				{
    323. 					if (_pht->_table[hashi])//不为空
    324. 					{
    325. 						_node = _pht->_table[hashi];
    326. 						return *this;
    327. 					}
    328. 					else//为空
    329. 					{
    330. 						++hashi;
    331. 					}
    332. 				}
    333. 				_node = nullptr;
    334. 			}
    335. 			return *this;
    336. 		}
    337.  
    338. 	};
    339.  
    340. 	template<class K, class T, class KeyofT, class HashFunc = DefaultHashFunc>
    341. 	class HashDate
    342. 	{
    343. 		typedef HashDateNode Node;
    344. 		
    345. 		// 
    346. 		//友元
    347. 		template<class K, class T, class Ptr, class Ref, class KeyofT, class HashFunc>
    348. 		friend struct HashIterator;//可以使用迭代器
    349.  
    350. 	public:
    351. 		typedef HashIterator iterator;
    352. 		typedef HashIteratorconst T*, const T&, KeyofT, HashFunc> const_iterator;
    353.  
    354. 		iterator begin()
    355. 		{
    356. 			for (size_t i = 0; i < _table.size(); i++)
    357. 			{
    358. 				Node* cur = _table[i];
    359. 				if (cur)
    360. 				{
    361. 					return iterator(cur,this);
    362. 				}
    363. 			}
    364.  
    365. 			return iterator(nullptr, this);
    366. 		}
    367.  
    368. 		const_iterator begin() const
    369. 		{
    370. 			for (size_t i = 0; i < _table.size(); i++)
    371. 			{
    372. 				Node* cur = _table[i];
    373. 				if (cur)
    374. 				{
    375. 					return iterator(cur, this);
    376. 				}
    377. 			}
    378.  
    379. 			return iterator(nullptr, this);
    380. 		}
    381.  
    382. 		iterator end() 
    383. 		{
    384. 			return iterator(nullptr, this);
    385. 		}
    386.  
    387. 		
    388. 		const_iterator end() const
    389. 		{
    390. 			return iterator(nullptr, this);
    391. 		}
    392. 		HashDate()
    393. 		{
    394. 			_table.resize(10, nullptr);
    395. 		}
    396.  
    397. 		~HashDate()
    398. 		{
    399. 			for (size_t i = 0; i < _table.size(); i++)
    400. 			{
    401. 				Node* cur = _table[i];
    402. 				while (cur)
    403. 				{
    404. 					Node* next = cur->_next;
    405. 					delete cur;
    406. 					cur = next;
    407. 				}
    408.  
    409. 				_table[i] = nullptr;
    410. 			}
    411. 		}
    412.  
    413. 		pairbool> Insert(const T& date)
    414. 		{
    415. 			
    416. 			KeyofT value;
    417. 			HashFunc Func;
    418. 			iterator it = Find(value(date));
    419. 			//it!=end()
    420. 			if(it != end())
    421. 			{
    422. 				return make_pair(it,false);
    423. 			}
    424.  
    425. 			if (n == _table.size())//扩容
    426. 			{
    427. 				int newsize = _table.size() * 2;
    428. 				vector newHash;
    429. 				newHash.resize(newsize);
    430. 				for (size_t i = 0; i < _table.size(); i++)//旧数据
    431. 				{
    432. 					Node* cur = _table[i];
    433. 					while (cur)
    434. 					{
    435. 						Node* next = cur->_next;
    436. 						size_t hashi = Func(value(cur->_Date))% newsize;
    437. 						cur->_next = newHash[hashi];
    438. 						newHash[hashi] = cur;
    439. 						cur = next;
    440. 					}
    441. 					_table[i] = nullptr;
    442. 				}
    443. 				_table.swap(newHash);//交换数据
    444. 			}
    445. 			//插入
    446. 			size_t hashi = Func(value(date))% _table.size();//改变
    447. 			//Node* cur = _table[hashi];
    448. 			//尾插
    449. 			//Node* newNode = new Node(date);
    450. 			//while (cur)
    451. 			//{
    452. 			//	cur = cur->_next;
    453. 			//}
    454. 			//cur = newNode;
    455. 			//头插
    456. 			Node* newNode = new Node(date);//新节点
    457. 			newNode->_next = _table[hashi];//头结点
    458. 			_table[hashi] = newNode;//尾节点
    459. 		
    460. 			n++;
    461. 			return make_pair(iterator(newNode,this),true);
    462. 		}
    463.  
    464.  
    465. 		//查找
    466. 		iterator Find(const K& key)//Find为K类型的只用一个数值，T类型的在map中为pair类型
    467. 		{
    468. 			HashFunc Func;
    469. 			KeyofT value;
    470. 			size_t hashi = Func(key) % _table.size();
    471. 			//size_t hashi = Func(value(key)) % _table.size();//不能使用这个
    472. 			Node* cur = _table[hashi];
    473. 			while (cur)
    474. 			{
    475. 				if (value(cur->_Date) == key)//?
    476. 				{
    477. 					return iterator(cur,this);
    478. 				}
    479. 				cur = cur->_next;
    480. 			}
    481. 			return iterator(nullptr,this);
    482. 		}
    483.  
    484. 		//删除
    485. 		bool Erase(const K& key)
    486. 		{
    487. 			HashFunc Func;
    488. 			KeyofT value;
    489. 			iterator ret=Find(key);
    490. 			if (ret == end())
    491. 				return true;
    492. 			size_t x = Func(value(key))% _table.size();
    493. 			Node* cur = _table[x];
    494. 			Node* prev = nullptr;
    495. 			while (cur)
    496. 			{
    497. 				if (value(cur->_Date) == key)
    498. 				{
    499. 					if (prev == nullptr)
    500. 					{
    501. 						_table[x] = cur->_next;
    502. 					}
    503. 					else
    504. 					{
    505. 						prev->_next = cur->_next;
    506. 					}
    507. 					
    508. 				}
    509. 				prev = cur;
    510. 				cur = cur->_next;
    511. 				delete cur;
    512. 				return true;
    513. 			}
    514. 			return false;
    515. 		}
    516. 		//打印
    517. 		void Print()
    518. 		{
    519. 			for (int i = 10; i < _table.size(); i++)
    520. 			{
    521. 				Node* cur = _table[i];
    522. 				while (cur)
    523. 				{
    524. 					std::cout << cur->_Date.first<<" " << cur->_Date.second <<" " << std::endl;
    525. 					cur = cur->_next;
    526. 				}
    527. 			}
    528. 			std::cout << std::endl;
    529. 		}
    530.  
    531. 	private:
    532. 		vector _table; //存储数据
    533. 		size_t n=0; //记录容器中的个数
    534. 	};
    535. }

  • 相关阅读:
    S波与P波的定义（光波电矢量）（菲涅耳公式）
    写给自己：入职两个月的收获与变化
    新学期，我的FLAG不能倒~
    第一个SpringBoot程序
    IDEA插件Mybatis Log Plugin的安装及其使用教程
    基于视觉AI的管道高后果区预警系统
    wangeditor富文本编辑器使用(详细)
    JavaScript设计模式中的享元模式
    openguass数据库描述指令集合（等保）
    Linux从入门到精通 --- 2.基本命令入门
  • 原文地址：https://blog.csdn.net/weixin_66828150/article/details/133030844