C++语法（22）---- 哈希表的闭散列和开散列_哈里沃克的博客-CSDN博客
https://blog.csdn.net/m0_63488627/article/details/130436178?spm=1001.2014.3001.5501
1.重写HashTable
由于此时我们的实现与map跟set差不多，所以需要进行调整
1.重写节点
节点通过unordered_set和unordered_map传入的东西来构造是Value类型还是pair<K,V>类型
template<class T> struct HashNode {T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){} };
2.重写哈希表
1.首先，一定要通过Key值查找对应的值，那么我们需要设置一个模板为K
2.我们还要传入哈希元素节点，设置模板为T（与上面一致）
3.将T的值进行哈希映射的Hash仿函数，该函数应该在unordered层传入，因为我们也不知道要映射到位置上的是什么
4.还有一个是与map和set实现一样的仿函数，用于区分到底是unordered_map还是unordered_set中的Key值的比较，该模板命名为KeyOfT
template<class K, class T, class Hash, class KeyOfT> class HashTable {typedef HashNode<T> Node; public:HashTable():_n(0){_table.resize(10);}~HashTable(){//省略}bool Insert(const T& data){//需要注意获取哈希映射的方式//需要用到hash转换k为对应的int再进行操作KeyOfT kot;if (Find(kot(data)) != nullptr)return false;if (_n == _table.size()){//省略怎么扩容的}//需要注意获取哈希映射的方式//需要用到上层传来的KeyOfT使得data变成可以被哈希映射的值size_t hashi = kot(data) % _table.size();//省略怎么插入的}Node* Find(const K& k){//需要注意获取哈希映射的方式//需要用到hash转换k为对应的int再进行操作size_t hashi = Hash()(k) % _table.size(); //省略怎么找的}bool Erase(const K& k){//需要注意获取哈希映射的方式//需要用到hash转换k为对应的int再进行操作size_t hashi = Hash()(k) % _table.size(); //省略怎么删除的}private:vector<Node*> _table;size_t _n = 0; };
2.unordered初步实现
1.unordered_set
对于set而言，传入的直接就是Key，那么SetOfT仿函数返回的就是key
namespace MY {template<class K,class Hash = HashFunc<K>>class unordered_set{struct SetOfT{const K& operator()(const K& key){return key;}};private:buckethash::HashTable<K, K, Hash, SetOfT> _ht;}; }2.unordered_map
对于map而言，传入的是pair，那么MapOfT仿函数返回的就是pair的first
namespace MY {template<class K, class V, class Hash = HashFunc<K>>class unordered_map{struct MapOfT{const K& operator()(const pair<const K, V>& key){return key.first;}};private:buckethash::HashTable<K, pair<const K, V>, Hash, MapOfT> _ht;}; }
3. 哈希表的迭代器
template<class K, class T, class Hash, class KeyOfT> struct __HTIterator {typedef HashNode<T> Node;typedef __HTIterator<K, T, Hash, KeyOfT> Self;typedef HashTable<K, T, Hash, KeyOfT> HT;Node* _node;HT* _ht; };我们需要算到开始的位置，所以一定要传入哈希表的地址，随后访问到哈希表的tables。
迭代器的简单函数
__HTIterator(Node* node,HT* ht):_node(node),_ht(ht) {}T operator*() {return _node->_data; }T& operator->() {return &_node->_data; }bool operator != (const Self& s) const {return _node != s._node; }重写++的实现
首先我们找到下一个位置有两种情况
1.指针往下就是下一个数
2.整个桶走完了，我们要找下一个桶有数据的位置
Self& operator++() {if (_node->_next){_node = _node->_next;}else{KeyOfT kot;Hash hash;size_t hashi = hash(kot(_node->_data)) % (_ht->_table.size());hashi++;while (hashi < _ht->_table.size()){if (_ht->_table[hashi]){_node = _ht->_table[hashi];break;}else++hashi;}if (hashi == _ht->_table.size()){_node = nullptr;}}return *this; }因为迭代器用到了哈希表，但是我将迭代器写在了哈希表的前面，所以在此之前还得先定义哈希表的前置声明
//前置声明 template<class K, class T, class Hash, class KeyOfT> class HashTable;
4.哈希表的迭代器形式
1.迭代器怎么才使用_table
由于哈希表中的table是私有对象，而迭代器需要访问table，那么就要将迭代器设置为哈希表的友元。
template<class K, class T, class Hash, class KeyOfT> class HashTable {typedef HashNode<T> Node;template<class K, class T, class Hash, class KeyOfT>friend struct __HTIterator; //友元public:typedef __HTIterator<K, T, Hash, KeyOfT> iterator; private:vector<Node*> _table;size_t _n = 0; };2.哈希表中的迭代器
需要注意的是，在迭代器中，构造函数为：
__HTIterator(Node* node,HT* ht):_node(node),_ht(ht) {}所以哈希表的函数返回包括迭代器内容的，一律需要构造迭代器返回。
_node：就是生成的节点的地址，该地址就是节点的指针，这个好获得
_ht：为哈希表的地址，那么我们在哈希表的类中，本身的对象就是_ht，我们只需要返回this
iterator begin() {for (size_t i = 0; i < _table.size(); i++){if (_table[i] != nullptr)return iterator(_table[i], this);}return iterator(nullptr, this); }iterator end() {return iterator(nullptr, this); }iterator Find(const K& k) {size_t hashi = Hash()(k) % _table.size();Node* cur = _table[hashi];KeyOfT kot;while (cur){if (kot(cur->_data) == k)return iterator(cur, this);elsecur = cur->_next;}return iterator(nullptr,this); }bool Erase(const K& k) {size_t hashi = Hash()(k) % _table.size();Node* cur = _table[hashi];Node* prev = nullptr;while (cur){if (cur->_kv.first == k){if (cur == _table[hashi])_table[hashi] = cur->_next;elseprev->_next = cur->_next;delete cur;_n--;return true;}prev = cur;cur = cur->_next;}return false; }因为需要实现map的operator[]，因此insert的重写是返回一个pair类型，first是迭代器，second是bool。
pair<iterator, bool> Insert(const T& data) {KeyOfT kot;iterator it = Find(kot(data));if (it != end())return make_pair(it, false);if (_n == _table.size()){vector<Node*> newTable;newTable.resize(2 * _table.size(),nullptr);for (int i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){Node* next = cur->_next;size_t hashi = Hash()(kot(cur->_data)) % newTable.size();cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newTable);}size_t hashi = Hash()(kot(data)) % _table.size();Node* newnode = new Node(data);newnode->_next = _table[hashi];_table[hashi] = newnode;_n++;return make_pair(iterator(newnode, this), true); }
5.unordered_map和unordered_set
template<class K, class V, class Hash = HashFunc<K>>class unordered_map{struct MapOfT{const K& operator()(const pair<const K, V>& key){return key.first;}};public:typedef typename buckethash::HashTable<K, pair<const K, V>, Hash, MapOfT>::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}iterator Find(const K& k){return _ht.Find(k);}bool Erase(const K& k){return _ht.Erase(k);}pair<iterator, bool> insert(const pair<const K, V>& data){return _ht.Insert(data);}V& operator[](const K& key){pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));return ret.first->second;}private:buckethash::HashTable<K, pair<const K, V>, Hash, MapOfT> _ht;};template<class K,class Hash = HashFunc<K>>class unordered_set{struct SetOfT{const K& operator()(const K& key){return key;}};public:typedef typename buckethash::HashTable<K, K, Hash, SetOfT>::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}iterator Find(const K& k){return _ht.Find(k);}bool Erase(const K& k){return _ht.Erase(k);}pair<iterator, bool> insert(const K& key){return _ht.Insert(key);}private:buckethash::HashTable<K, K, Hash, SetOfT> _ht;};
