一、哈希桶节点的修改
用哈希桶封装实现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. }
