• C++ 哈希:HashTable模拟实现(补充)

    目录

    1.引例：两个练习题

    2.定义基本的存储结构

    3.Insert()

    4.Erase()

    5.string为参数的情况

    6.添加类模板 

    7.整体代码

    1.引例：两个练习题

    2.定义基本的存储结构

    1. #pragma once
    2. namespace CloseHash
    3. {
    4. 	template<class K,class V>
    5. 	struct HashData
    6. 	{
    7. 		pair _kv;
    8. 	};
    9.  
    10. 	template<class K,class V>
    11. 	class HashTable
    12. 	{
    13. 	private:
    14. 		HashData* _table;
    15. 		size_t _size;
    16. 		size_t _capacity; //用于增容
    17. 	};
    18. }

    后者直接用vector存储

    1. #pragma once
    2. #include
    3. #include
    4. using namespace std;
    5. namespace CloseHash
    6. {
    7. 	template<class K,class V>
    8. 	struct HashData
    9. 	{
    10. 		pair _kv;
    11. 	};
    12.  
    13. 	template<class K,class V>
    14. 	class HashTable
    15. 	{
    16.     public://待写
    17. 	private:
    18. 		//HashData* _table;
    19. 		//size_t _size;
    20. 		//size_t _capacity; //用于增容
    21. 		vector _table;
    22. 		size_t _n;//存储的有效数据的个数
    23. 	};
    24. }

    3.Insert()

    如何判断一个位置是空还是满？若删除其中一个值，用空值去标识，下一次找后面冲突的值找不到了。前一个冲突的值被删了，导致不连续了，找到空就结束了。

     提供一个状态标识即可

    1.  namespace CloseHash
    2. {
    3. 	enum State//状态
    4. 	{
    5. 		EMPTY,
    6. 		EXITS,
    7. 		DELTE,
    8. 	};
    9. 	template<class K,class V>
    10. 	struct HashData
    11. 	{
    12. 		pair _kv;
    13. 		State _state = EMPTY;//默认状态给空
    14. 	};
    15.  
    16. 	template<class K,class V>
    17. 	class HashTable
    18. 	{
    19. 	public://待写函数
    20. 	private:
    21. 		//HashData* _table;
    22. 		//size_t _size;
    23. 		//size_t _capacity; //用于增容
    24. 		vector _table;
    25. 		size_t _n;//存储的有效数据的个数
    26. 	};
    27. }
    1.  bool Insert(const pair& kv)
    2. {
    3. 	HashData* ret = Find(kv, first);
    4. 	if (ret)
    5. 	{
    6. 		return false;
    7. 	}
    8. 	//判断是否满
    9. 	//计算负载因子，大于0.7就增容
    10. 	//if (_n*10 / _table.size() > 7)
    11. 	if (_tabale.size() == 0)
    12. 	{
    13. 		_table.resize(10);
    14. 	}
    15. 	else if ((double)_n / (double)_table.size() > 0.7)
    16. 	{
    17. 		//方法一，不足之处在于要重复写插入逻辑
    18. 		//vectornewtable;
    19. 		//newtable.resize(_table.size*2);  新表增容，增到旧表的二倍
    20. 		//for (auto& e : _table)
    21. 		//{
    22. 		//	if (e._table == EXITS)
    23. 		//	{
    24. 		//		//重新计算放到newtable中去
    25. 		//		//跟下面插入逻辑类似
    26. 		//	}
    27. 		//}
    28. 		//_table.swap(newtable);
    29.  
    30. 		HashTablenewHT;
    31. 		newHT._table.resize(_table.size() * 2);
    32. 		for (auto& e : _table)
    33. 		{
    34. 			if (e._state == EXITS)
    35. 			{
    36. 				newHT.Insert(e._kv);
    37. 			}
    38. 		}
    39. 		_table.swap(newHT._table);
    40. 	}
    41.  
    42. 	size_t start = kv.first % _table.size();//不能%_table.capacity()
    43. 	size_t index = start;
    44.  
    45. 	//探测后面的位置 -- 线性探测或二次探测
    46. 	size_t i = 1;
    47. 	while (_table[index]._state == EXITS)
    48. 	{
    49. 		index += start + i;//此处的线性探测想改成二次探测将i改为i*i即可
    50. 		index %= _table.size();
    51. 		++i;
    52. 	}
    53.  
    54. 	_table[index]._kv = kv;
    55. 	_table[index]._state = EXITS;
    56. 	++_n;
    57.  
    58. 	return true;
    59. }
    60.  
    61. HashData* Find(const K& key)
    62. {
    63. 	//排除0的情况
    64. 	if (_table.size() == 0)
    65. 	{
    66. 		return nullptr;
    67. 	}
    68. 	size_t start = key % _table.size();
    69. 	size_t index = start;
    70. 	size_t i = 1;
    71. 	while (_table[index]._state != EMPTY)
    72. 	{
    73. 		if (_table[index]._state == EXITS//避免已经删除的元素仍可被寻找的情况
    74. 			&& _table[index]._kv.first == key)
    75. 		{
    76. 			return &_table[index];
    77. 		}
    78. 		inded = start + i;
    79. 		index %= _table.size();
    80. 		++i;
    81. 	}
    82. 	return nullptr;
    83. }

    4.Erase()

    1. bool Erase(const K& key)
    2. {
    3. 	HashData* ret = Find(key);
    4. 	if (ret == nullptr)
    5. 	{
    6. 		return false;
    7. 	}
    8. 	else
    9. 	{
    10. 		ret->_state = DELETE;
    11. 		return true;
    12. 	}
    13. }

    5.string为参数的情况

    若出现下面测试代码的情况，如何更改？

    1. void TestHashTable2()
    2. {
    3. 	string a[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "橘子", "苹果" };
    4. 	HashTableint> ht;
    5. 	for (auto str : a)//string作k的情况
    6. 	{
    7. 		auto ret = ht.Find(str);
    8. 		if (ret)
    9. 		{
    10. 			ret->_kv.second++;
    11. 		}
    12. 		else
    13. 		{
    14. 			ht.Insert(make_pair(str, 1));
    15. 		}
    16. 	}
    17. }

    所有要取模的地方添加仿函数，该仿函数的功能就是将数据转换成整型。

    1. struct IniHashFunc
    2. {
    3. 	int operator()(int i)
    4. 	{
    5. 		return i;
    6. 	}
    7. };

     

    特别的，将字符串转换成整型的仿函数仍存在问题。采用字符串哈希算法的思路改正即可    各种字符串Hash函数 - clq - 博客园

    以此类推，K为不同类型元素的情况写对应的仿函数即可

    思考：

     一个类型去作map/set的Key有什么要求？ 能支持比较大小

    一个类型去作unordered_map/unordered_set的Key有什么要求？  能支持转换成整型+相等比较

    6.添加类模板 

    可以转化成整型的数据采用下面模板，返回值为int

    1. template<class K>
    2. struct Hash
    3. {
    4. 	size_t operator()(const K& key)
    5. 	{
    6. 		return key;
    7. 	}
    8. };

    当K是string时不会走原生的模板，采用特化单独创建一个模板

    1. template<>
    2. struct Hash
    3. {
    4. 	//字符串转成对应的整型，整型才能取模算映射位置
    5. 	//期望->字符串不同，转出的整型值尽量不同
    6. 	size_t operator()(const string& s)
    7. 	{
    8. 		//return s[0];  存在int insert类似首字母相同的情况
    9.  
    10. 		//存在abcd,bcad或abbb.abca的情况(ascii码和相同的情况)
    11. 		size_t value = 0;
    12. 		for (auto ch : s)
    13. 		{
    14. 			value += ch;
    15. 			value *= 131;//采用BKDRHash算法的思想 乘以131
    16. 		}
    17. 		return value;
    18. 	}
    19. };

    使用类模板后不同的数据类型会调用不同类型的仿函数 

     此时可以省略仿函数，参数自动使用隐式类型转换

     

    7.整体代码

    1. #pragma once
    2. #include 
    3. #include 
    4. using namespace std;
    5.  
    6. namespace CloseHash
    7. {
    8. 	enum State
    9. 	{
    10. 		EMPTY,
    11. 		EXITS,
    12. 		DELETE,
    13. 	};
    14.  
    15. 	template<class K, class V>
    16. 	struct HashData
    17. 	{
    18. 		pair _kv;
    19. 		State _state = EMPTY;  // 状态
    20. 	};
    21.  
    22. 	template<class K>
    23. 	struct Hash
    24. 	{
    25. 		size_t operator()(const K& key)
    26. 		{
    27. 			return key;
    28. 		}
    29. 	};
    30.  
    31. 	// 特化
    32. 	template<>
    33. 	struct Hash
    34. 	{
    35. 		// "int"  "insert" 
    36. 		// 字符串转成对应一个整形值，因为整形才能取模算映射位置
    37. 		// 期望->字符串不同，转出的整形值尽量不同
    38. 		// "abcd" "bcad"
    39. 		// "abbb" "abca"
    40. 		size_t operator()(const string& s)
    41. 		{
    42. 			// BKDR Hash
    43. 			size_t value = 0;
    44. 			for (auto ch : s)
    45. 			{
    46. 				value += ch;
    47. 				value *= 131;
    48. 			}
    49.  
    50. 			return value;
    51. 		}
    52. 	};
    53.  
    54. 	template<class K, class V, class HashFunc = Hash>
    55. 	class HashTable
    56. 	{
    57. 	public:
    58. 		bool Insert(const pair& kv)
    59. 		{
    60. 			HashData* ret = Find(kv.first);
    61. 			if (ret)
    62. 			{
    63. 				return false;
    64. 			}
    65.  
    66. 			// 负载因子大于0.7，就增容
    67. 			//if (_n*10 / _table.size() > 7)
    68. 			if (_table.size() == 0)
    69. 			{
    70. 				_table.resize(10);
    71. 			}
    72. 			else if ((double)_n / (double)_table.size() > 0.7)
    73. 			{
    74. 				//vector newtable;
    75. 				// newtable.resize(_table.size*2);
    76. 				//for (auto& e : _table)
    77. 				//{
    78. 				//	if (e._state == EXITS)
    79. 				//	{
    80. 				//		// 重新计算放到newtable
    81. 				//		// ...跟下面插入逻辑类似
    82. 				//	}
    83. 				//}
    84.  
    85. 				//_table.swap(newtable);
    86.  
    87. 				HashTable newHT;
    88. 				newHT._table.resize(_table.size() * 2);
    89. 				for (auto& e : _table)
    90. 				{
    91. 					if (e._state == EXITS)
    92. 					{
    93. 						newHT.Insert(e._kv);
    94. 					}
    95. 				}
    96.  
    97. 				_table.swap(newHT._table);
    98. 			}
    99.  
    100. 			HashFunc hf;
    101. 			size_t start = hf(kv.first) % _table.size();
    102. 			size_t index = start;
    103.  
    104. 			// 探测后面的位置 -- 线性探测 or 二次探测
    105. 			size_t i = 1;
    106. 			while (_table[index]._state == EXITS)
    107. 			{
    108. 				index = start + i;
    109. 				index %= _table.size();
    110. 				++i;
    111. 			}
    112.  
    113. 			_table[index]._kv = kv;
    114. 			_table[index]._state = EXITS;
    115. 			++_n;
    116.  
    117. 			return true;
    118. 		}
    119.  
    120. 		HashData* Find(const K& key)
    121. 		{
    122. 			if (_table.size() == 0)
    123. 			{
    124. 				return nullptr;
    125. 			}
    126.  
    127. 			HashFunc hf;
    128. 			size_t start = hf(key) % _table.size();
    129. 			size_t index = start;
    130. 			size_t i = 1;
    131. 			while (_table[index]._state != EMPTY)
    132. 			{
    133. 				if (_table[index]._state == EXITS 
    134. 					&& _table[index]._kv.first == key)
    135. 				{
    136. 					return &_table[index];
    137. 				}
    138.  
    139. 				index = start + i;
    140. 				index %= _table.size();
    141. 				++i;
    142. 			}
    143.  
    144. 			return nullptr;
    145. 		}
    146.  
    147. 		bool Erase(const K& key)
    148. 		{
    149. 			HashData* ret = Find(key);
    150. 			if (ret == nullptr)
    151. 			{
    152. 				return false;
    153. 			}
    154. 			else
    155. 			{
    156. 				ret->_state = DELETE;
    157. 				return true;
    158. 			}
    159. 		}
    160.  
    161. 	private:
    162. 	/*	HashData* _table;
    163. 		size_t _size;
    164. 		size_t _capacity;*/
    165. 		vector> _table;
    166. 		size_t _n = 0;  // 存储有效数据的个数
    167. 	};
    168.  
    169. 	void TestHashTable1()
    170. 	{
    171. 		int a[] = { 1, 5, 10, 100000, 100, 18, 15, 7, 40};
    172. 		HashTable<int, int> ht;
    173. 		for (auto e : a)
    174. 		{
    175. 			ht.Insert(make_pair(e, e));
    176. 		}
    177.  
    178. 		auto ret = ht.Find(100);
    179. 		if (ret)
    180. 		{
    181. 			cout << "找到了"<
    182. 		}
    183. 		else
    184. 		{
    185. 			cout << "没有找到了" << endl;
    186. 		}
    187.  
    188. 		ht.Erase(100);
    189.  
    190. 		ret = ht.Find(100);
    191. 		if (ret)
    192. 		{
    193. 			cout << "找到了" << endl;
    194. 		}
    195. 		else
    196. 		{
    197. 			cout << "没有找到了" << endl;
    198. 		}
    199. 	}
    200.  
    201. 	struct stringHashFunc
    202. 	{
    203. 		// "int"  "insert" 
    204. 		// 字符串转成对应一个整形值，因为整形才能取模算映射位置
    205. 		// 期望->字符串不同，转出的整形值尽量不同
    206. 		// "abcd" "bcad"
    207. 		// "abbb" "abca"
    208. 		size_t operator()(const string& s)
    209. 		{
    210. 			// BKDR Hash
    211. 			size_t value = 0;
    212. 			for (auto ch : s)
    213. 			{
    214. 				value += ch;
    215. 				value *= 131;
    216. 			}
    217.  
    218. 			return value;
    219. 		}
    220. 	};
    221.  
    222. 	void TestHashTable2()
    223. 	{
    224. 		string a[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "橘子", "苹果" };
    225. 		HashTableint> ht;
    226. 		for (auto str : a)
    227. 		{
    228. 			auto ret = ht.Find(str);
    229. 			if (ret)
    230. 			{
    231. 				ret->_kv.second++;
    232. 			}
    233. 			else
    234. 			{
    235. 				ht.Insert(make_pair(str, 1));
    236. 			}
    237. 		}
    238. 	}
    239.  
    240. 	struct Student
    241. 	{
    242. 		// ...
    243. 	};
    244.  
    245. 	struct StudentHashFunc
    246. 	{
    247. 		size_t operator()(const Student& kv)
    248. 		{
    249. 			// 如果是结构体
    250. 			// 1、比如说结构体中有一个整形，基本是唯一值 - 学号
    251. 			// 2、比如说结构体中有一个字符串，基本是唯一值 - 身份证号
    252. 			// 3、如果没有一项是唯一值，可以考虑多项组合
    253. 			size_t value = 0;
    254. 			// ...
    255. 			return value;
    256. 		}
    257. 	};
    258.  
    259. 	void TestHashTable3()
    260. 	{
    261. 		string a[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "橘子", "苹果" };
    262. 		// 任意类型都可以做key，跟上一个把这个类型对象转换成整形的仿函数即可
    263. 		HashTableint, StudentHashFunc> ht;
    264. 	}
    265.  
    266. 	void TestStringHashFunc()
    267. 	{
    268. 		stringHashFunc hf;
    269. 		cout << hf("insert")<
    270. 		cout << hf("int") << endl<
    271.  
    272. 		cout << hf("abcd") << endl;
    273. 		cout << hf("bacd") << endl << endl;
    274.  
    275. 		cout << hf("abbb") << endl;
    276. 		cout << hf("abca") << endl << endl;
    277. 	}
    278. }
    279.

  • 相关阅读:
    Elasticsearch 入门 索引、分词器
    六大银行数据治理现状盘点：治理架构、数据标准与数据平台
    使用TensorRT 和 Triton 在Jetson NX上的模型部署
    hypermesh 圆周阵列-插件
    竞赛选题 基于机器视觉的停车位识别检测
    从 HTA 中启动应用程序
    大火的4D Radar数据集及基线模型汇总
    业主方怎么管理固定资产
    Markdown 表格
    学会用数据分析汇报工作，升职加薪指日可待
  • 原文地址：https://blog.csdn.net/m0_61548909/article/details/126591355