三、用开散列解决哈希冲突
1.开散列介绍
开散列也叫拉链法，先对所有key用散列函数计算散列地址，把有相同地址的key每个key都作为一个桶，通过单链表链接在哈希表中。
因此，开散列的每个桶中存放的都是哈希冲突的元素，负载因子较低。当桶超过一定长度时，就把冲突最多的桶就换成红黑树。实际中哈希桶的结构更实用，因为哈希桶空间利用率高，并且在极端情况下还有解决方案。
2.哈希桶的实现
哈希桶作为指针数组，数组的每个元素是一个结点的指针，链表不需要带哨兵位，且头插的效率比较高。
（1）哈希仿函数
在闭散列中，已经实现了Hash仿函数，用来获取哈希表中的元素的key，方便后续计算映射位置
1. #pragma once 2. #include <vector> 3. #include <iostream> 4. using namespace std; 5. namespace OpenHash 6. { 7. template<class K> 8. struct Hash 9. { 10. size_t operator()(const K& key) 11. { 12. return key; 13. } 14. }; 15. }
模板特化：string元素使用频率较高，进行模板特化
1. // 特化 2. template<> 3. struct Hash < string > 4. { 5. //采用BKDR哈希进行计算 6. size_t operator()(const string& s) 7. { 8. // BKDR Hash 9. size_t value = 0; 10. for (auto ch : s) 11. { 12. value += ch; 13. value *= 131; 14. } 15. 16. return value; 17. } 18. };
（2）哈希桶节点
哈希桶只需要2个成员：数据、下一个桶指针
1. template<class T> 2. struct HashNode 3. { 4. HashNode<T>* _next; 5. T _data; 6. 7. HashNode(const T& data) 8. :_next(nullptr) 9. , _data(data) 10. {} 11. };
（3）哈希表
哈希表有两个成员：哈希表、有效数据的个数
1. template<class K,class V,class HashFunc=Hash<K>> 2. class HashTable 3. { 4. typedef HashNode<K, V> Node; 5. private: 6. vector<Node*> _table;//哈希表 7. size_t _n;//有效数据个数 8. };
（4）查找
先计算key在哈希表中的位置，然后后再该位置的哈希桶中遍历查找：
1. //查找 2. Node* Find(const K& key) 3. { 4. //哈希表为空 5. if (_table.size() == 0) 6. { 7. return false; 8. } 9. 10. HashFunc hf; 11. size_t index = hf(key) % _table.size();//计算key在哈希表中的位置 12. Node* cur = _table[index]; 13. 14. while (cur) 15. { 16. if (cur->_kv.first == key)//找到了 17. { 18. return cur; 19. } 20. else//没找到 21. { 22. cur = cur->_next; 23. } 24. } 25. 26. return nullptr; 27. }
（5）插入
①查找key在不在哈希表中
②不在就要先判断哈希表是否满了
③若哈希表满了就要重新开一个新的哈希表，将旧表数据全部头插到新表中
④插入数据
1. //插入 2. bool Insert(const pair<K, V>& kv) 3. { 4. //在哈希表中已存在 5. if (Find(kv)) 6. { 7. return false; 8. } 9. 10. //哈希表负载因子为1时代表哈希表满了，需要重新开新表，重新计算映射位置 11. HashFunc hf; 12. if (_n == _table.size()) 13. { 14. vector<Node*> newHashTable; 15. newHashTable.resize(GetNextPrime(_table.size())); 16. 17. //遍历旧表的所有节点，重新挂到新表中，可能节点映射的位置也发生了变化 18. for (size_t i = 0; i < _table.size(); i++) 19. { 20. if (_table[i]) 21. { 22. Node* cur = _table[i]; 23. while (cur) 24. { 25. Node* next = cur->_next; 26. size_t index = hf(cur->_kv.first) % newHashTable.size(); 27. 28. //由于是头插,因此将旧表_table的每个桶的_next都置为新表计算的新位置的第一个桶，将新表的newHashTable[index]置为cur 29. cur->_next = newHashTable[index]; 30. newHashTable[index] = cur; 31. cur = next; 32. } 33. 34. _table[i] = nullptr; 35. } 36. } 37. _table.swap(newHashTable); 38. } 39. 40. size_t index = hf(kv.first) % _table.size(); 41. Node* newNode = new Node(kv); 42. 43. //不需要增容，直接头插 44. newNode->_next = _table[index]; 45. _table[index] = newNode; 46. _n++; 47. 48. return true; 49. }
（6）删除
①计算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 (cur->_kv.first == key) 11. { 12. if (_table[index] == cur)//要删除的key就是该位置的第一个桶 13. { 14. _table[index] = cur->_next; 15. } 16. else 17. { 18. prev->_next = cur->_next; 19. } 20. 21. --_n; 22. delete cur; 23. return true; 24. 25. } 26. 27. prev = cur; 28. cur = cur->next; 29. 30. return false; 31. } 32. }
（7）完整代码段
HashTable.h
1. namespace OpenHash 2. { 3. template<class K> 4. struct Hash 5. { 6. size_t operator()(const K& key) 7. { 8. return key; 9. } 10. }; 11. 12. //特化 13. template<> 14. struct Hash<string> 15. { 16. size_t operator()(const string& s) 17. { 18. //采用BKDR哈希计算 19. size_t value = 0; 20. for (auto e : s) 21. { 22. value += e; 23. value *= 131; 24. } 25. 26. return value; 27. } 28. }; 29. 30. template<class K, class V> 31. struct HashNode 32. { 33. pair<K, V> _kv; 34. HashNode<K, V>* _next; 35. 36. HashNode(const pair<K, V>& kv) 37. :_kv(kv) 38. , _next(nullptr) 39. {} 40. }; 41. 42. template<class K,class V,class HashFunc=Hash<K>> 43. class HashTable 44. { 45. typedef HashNode<K, V> Node; 46. public: 47. 48. //获取质数 49. size_t GetNextPrime(size_t prime) 50. { 51. const int PRIMECOUNT = 28; 52. static const size_t primeList[PRIMECOUNT] = 53. { 54. 53ul, 97ul, 193ul, 389ul, 769ul, 55. 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, 56. 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 57. 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 58. 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, 59. 1610612741ul, 3221225473ul, 4294967291ul 60. }; 61. 62. size_t i = 0; 63. for (i = 0; i < PRIMECOUNT; i++) 64. { 65. if (primeList[i] > prime) 66. { 67. return primeList[i]; 68. } 69. } 70. 71. return primeList[i]; 72. } 73. 74. bool Insert(const pair<K, V>& kv) 75. { 76. //在哈希表中已存在 77. if (Find(kv)) 78. { 79. return false; 80. } 81. 82. //哈希表负载因子为1时代表哈希表满了，需要重新开新表，重新计算映射位置 83. HashFunc hf; 84. if (_n == _table.size()) 85. { 86. vector<Node*> newHashTable; 87. newHashTable.resize(GetNextPrime(_table.size())); 88. 89. //遍历旧表的所有节点，重新挂到新表中，可能节点映射的位置也发生了变化 90. for (size_t i = 0; i < _table.size(); i++) 91. { 92. if (_table[i]) 93. { 94. Node* cur = _table[i]; 95. while (cur) 96. { 97. Node* next = cur->_next; 98. size_t index = hf(cur->_kv.first) % newHashTable.size(); 99. 100. //由于是头插,因此将旧表_table的每个桶的_next都置为新表计算的新位置的第一个桶，将新表的newHashTable[index]置为cur 101. cur->_next = newHashTable[index]; 102. newHashTable[index] = cur; 103. cur = next; 104. } 105. 106. _table[i] = nullptr; 107. } 108. } 109. _table.swap(newHashTable); 110. } 111. 112. size_t index = hf(kv.first) % _table.size(); 113. Node* newNode = new Node(kv); 114. 115. //不需要增容，直接头插 116. newNode->_next = _table[index]; 117. _table[index] = newNode; 118. _n++; 119. 120. return true; 121. } 122. 123. //查找 124. Node* Find(const K& key) 125. { 126. //哈希表为空 127. if (_table.size() == 0) 128. { 129. return false; 130. } 131. 132. HashFunc hf; 133. size_t index = hf(key) % _table.size();//计算key在哈希表中的位置 134. Node* cur = _table[index]; 135. 136. while (cur) 137. { 138. if (cur->_kv.first == key)//找到了 139. { 140. return cur; 141. } 142. else//没找到 143. { 144. cur = cur->_next; 145. } 146. } 147. 148. return nullptr; 149. } 150. 151. //删除 152. bool Erase(const K& key) 153. { 154. size_t index = hf(key) % _table.size(); 155. Node* prev = nullptr; 156. Node* cur = _table[index]; 157. 158. while (cur) 159. { 160. if (cur->_kv.first == key) 161. { 162. if (_table[index] == cur)//要删除的key就是该位置的第一个桶 163. { 164. _table[index] = cur->_next; 165. } 166. else 167. { 168. prev->_next = cur->_next; 169. } 170. 171. --_n; 172. delete cur; 173. return true; 174. 175. } 176. 177. prev = cur; 178. cur = cur->next; 179. 180. return false; 181. } 182. } 183. private: 184. vector<Node*> _table;//哈希表 185. size_t _n;//有效数据个数 186. }; 187. }
