目录

​编辑

一，实现一个可封装的哈希表

1，哈希表的节点

 2，哈希表的成员

 3，哈希表成员方法的实现

 4，迭代器的实现

 5，在哈希表中加入迭代器

二，封装哈希表

1，unorder_map封装

2，unordered_set的封装

 

---

一，实现一个可封装的哈希表

1，哈希表的节点

在哈希表的封装中，分为两类：unordered_map,unordered_set。其中map的元素类型为pair<K,V>类型，set的类型为K类型。

Node实现如下：

   template<class T>struct Node{Node<T>* _next;T val;};

 2，哈希表的成员

哈希表的成员有两个，一个是记录哈希表节点个数的成员_n，一个是成员为Node*类型的vector<Node*>数组。

HashTable实现如下：

template<class T>class HashTables{typedef Node<T> Node;public:private:vector<Node*>_tables;size_t _n;};

 3，哈希表成员方法的实现

（1），Find(V&key)方法

Find方法实现的是在一个哈希表中寻找某个值存不存在。步骤如下：1，找到这个值对应的hashi（在哈希表中的下标）。2，遍历这个下标上挂载的链表上是否有该值。3，有则返回true,没有就返回false.

要找到hashi: 先实现两个方法Getkey()与GetHashi()

Getkey()：

    template <class K,class V>struct Getkey{K operator()(const V& val)//一般的成员直接返回val,遇到特殊pair类型的则返回val.first(先不实现){return val;}};

 GetHashi()：

template <class T>//一般情况下struct GetHashi{size_t operator(T& val){return (size_t)val;}};template<>//模板特化，当这个成员的类型为string类型时struct GetHashi<string>{size_t operator()(string& val){size_t ret = 0;for (int i = 0;i < val.size();i++){ret += ret * 31 + val[i];}return ret;}};

Find():

       bool Find(V& val){size_t hashi = GetHashi(Getkey(val)) % _tables.size();//计算hashiNode* cur = _tables[hashi];//找到对应的位置上的链表while (cur)//开始寻找{if (cur->val == _val) return true;}return false;}

（2），Insert（T&key）

 实现插入函数：(1)，满载时要扩容，扩容逻辑是创建一个新的vector<Node*>temp并且把这个表的大小扩为旧表的二倍。 (2)，将旧表中的元素拆下来头插到新表中。（3），将就表中的值全部变为nullptr,防止二次析构。（4），将新表交换给旧表

Insert函数代码： 

bool Insert(const V& val){if (Find(val)) return false;//存在过则直接返回插入失败if (_n == _tables.size())//检查是否需要扩容{int newsize = 2*(_n == 0? 1 : _n);//新的大小vector<Node*>temp;//开一个临时数组temp.resize(newsize);//扩大为原来哈希表的二倍for (int i = 0;i < _tables.size();i++){Node* cur = _tables[i];Node* next = nullptr;if (cur){while (cur){size_t hashi = GetHashi(Getkey(cur->_val))%_tables.size();//计算新的哈希值//保存下一个值，并更新就哈希表上的值next = cur->_next;_tables[i] = next;//头插到新的哈希表中cur->_next = temp[hashi];temp[hashi] = cur;cur = next;}}}//扩容好后便夺回来for (int i = 0;i < _tables.size();i++){_tables[i] = nullptr;}_tables.swap(temp);}int hashi = GetHashi(Getkey(val))%_tables.size();Node* newNode = new Node(val);//头插newNode->_next = _tables[hashi];_tables[hashi] = newNode;_n++;return true;}

 （3）Erase(V&val)

实现：先找到这个值，再删除。

Erase（V&val）代码：

       bool Erase(const V& val){int hashi = GetHashi(Getkey(val)) % _tables.size();//计算hashiNode* pre = nullptr;//记录hashi前面的指针Node* cur = _tables[hashi];//当前指针while (cur){if (cur->_val == val)//有相同的便开始执行删除逻辑{if(pre)pre->_next = cur->_next;//加上条件防止头删出错delete cur;cur = nullptr;_n--;return true;}pre = cur;cur = cur->_next;}return false;}

 4，迭代器的实现

（1），迭代器的成员

迭代器的成员：1，一个Node*类型的成员_node（因为迭代器就是一种模拟指针的行为所以要有哈希表元素的指针）。2，哈希表的指针和当前的_node对应的位置（主要是为了方便实现++）。

代码如下：

        typedef HTiterator<K, V, ref, ptr, Getkey, GetHashi> self;//迭代器类型typedef Node<V> Node;Node* _node;//哈希表成员的指针typedef HashTables<K, V, Getkey, GetHashi>*  pht;pht _pht;//哈希表的指针size_t _hashi;//迭代器在哈希表中的位置

（2）迭代器++的实现

1，找到下一个不为nullptr的点（这里要用到哈希表的指针和当前指针的位置） 。  2，返回一个迭代器。3，在实现++之前得实现一个迭代器的构造函数。

构造函数代码：

        HTiterator(Node* node,pht Hp,size_t hashi)//构造函数:_node(node),_pht(Hp),_hashi(hashi){}

实现迭代器operator++()代码：

//实现++self operator ++(){if (_node->_next){_node = _node->_next;}else{_hashi++;while (_hashi < _pht->_tables.size()){if (_pht->_tables[_hashi]){_node = _pht->_tables[_hashi];return HTiterator(_node, _pht, _hashi);//找到了直接返回构造的iterator}_hashi++;}_node = nullptr;//找不到就将_node置为nullptr在构造}return  HTiterator(_node, _pht, _hashi);}

（3）实现operator*()，operator->(),operator!=()

*:返回值是_node里面的val。->:返回值是_node->val的地址。！=：比较的是_node

 代码：

        ref operator*(){return _node->_val;}ptr operator->(){return& _node->_val;}bool operator!=(const self& s){return _node != s._node;}

 5，在哈希表中加入迭代器

       typedef HTiterator<K, V, V&, V*> iterator;//定义一个迭代器类型iterator begin()//实现begin(){for (int hashi = 0;hashi < _tables.size();hashi++){if (_tables[hashi]) return iterator(_tables[hashi], this, hashi);}return end();}iterator end()//实现end(){return iterator(nullptr, this, -1);}

二，封装哈希表

1，unorder_map封装

(1)unordered_map的成员

unordered_map的底层便是一个哈希表，所以unordered_map的成员便是一个哈希表。

代码：

cq::HashTables<K,pair<K, V>, Getkey<K,V>> HT;

（2）unordered_map的方法

在实现这些方法之前，先得把哈希表里的Insert()和Find()方法的返回值改一下，改成如下形式：pair<iterator,bool>，方便后面的operator[]的实现。

代码：

pair<iterator,bool> Insert(const V& val)//改成pair<iterator,bool>类型{iterator it = Find(val);if (it != end()) return make_pair(it, false);if (_n == _tables.size())//检查是否需要扩容{int newsize = 2*(_n == 0? 1 : _n);//新的大小vector<Node*>temp;//开一个临时数组temp.resize(newsize);for (int i = 0;i < _tables.size();i++){Node* cur = _tables[i];Node* next = nullptr;if (cur){while (cur){size_t hashi = GetHashi(Getkey(cur->_val))%_tables.size();//计算新的哈希值//保存下一个值，并更新就哈希表上的值next = cur->_next;_tables[i] = next;//头插到新的哈希表中cur->_next = temp[hashi];temp[hashi] = cur;cur = next;}}}//扩容好后便夺回来for (int i = 0;i < _tables.size();i++){_tables[i] = nullptr;}_tables.swap(temp);}size_t hashi = GetHashi(Getkey(val))%_tables.size();Node* newNode = new Node(val);//头插newNode->_next = _tables[hashi];_tables[hashi] = newNode;_n++;return   make_pair(iterator(newNode, this, hashi),true);}

（2） 实现V& operator[](K&key)

operator[]的作用是让我们能够通过key值来访问val值。

代码：

       V& operator[](const K& key){pair<iterator,bool> ret = HT.Insert(make_pair(key,V()));return  ret.first->second;//返回的是一个pair<iterator,bool>,first代表iterator，然后再调用iterator的->找到val值}

（3）unordered_map里其它的成员方法

其它的成员方法都是通过调用哈希表里面实现的方法实现的。

       iterator begin(){return HT.begin();}iterator end(){return HT.end();}pair<iterator, bool> insert(const pair<K,V>& val){return HT.Insert(val);}bool erase(const V& val){return HT.Erase(val);}pair<iterator,bool> Find(const V& val){return HT.Find(val);}

unordered_map封装代码：

	template < class K,class V>struct Getkey{K operator()(const pair<K,V>& val){return val.first;}};template <class K, class V>class my_unordered_map{typedef typename cq::HashTables<K, pair<K,V>, Getkey<K,V>>::iterator iterator;public:iterator begin(){return HT.begin();}iterator end(){return HT.end();}pair<iterator, bool> insert(const pair<K,V>& val){return HT.Insert(val);}bool erase(const V& val){return HT.Erase(val);}pair<iterator,bool> Find(const V& val){return HT.Find(val);}V& operator[](const K& key){pair<iterator,bool> ret = HT.Insert(make_pair(key,V()));return  ret.first->second;}private:cq::HashTables<K,pair<K, V>, Getkey<K,V>> HT;};

 

2，unordered_set的封装

unordered_set的封装与unordered_map的封装类似。但是不用实现operator[]。

 代码如下：

	template < class K>//set的模板参数只要一个struct Getkey{K operator()(const K& val){return val;}};template <class K>class my_unordered_set{typedef typename cq::HashTables<K, K, Getkey<K>>::iterator iterator;public:iterator begin(){return HT.begin();}iterator end(){return HT.end();}pair<iterator, bool> insert(const K& val){return HT.Insert(val);}bool erase(const K& val){return HT.Erase(val);}pair<iterator, bool> Find(const K& val){return HT.Find(val);}private:cq::HashTables<K, K, Getkey<K>> HT;//内部成员哈希表};