哈希表的完善及unordered_map/unordered_set封装

1.哈希表的完善

1.1 优化：哈希函数

在实际使用中，往往需要以字符串作为存储依据(键值)，比如姓名与快递信息、商品名称与价格、中文单词与英文释义等。
而在上一篇文章中，我们实现的哈希表只考虑了整型的存储情况，即直接用key%capacity计算哈希值，如果把整型换成字符串是无法进行计算的。如下图所示。

为了解决这个问题，我们可用将获取key值单独封装为一个仿函数，再利用模板特化，使其既能支持整型也能支持字符串。

//特化
template<>
struct _Hash<string>
{size_t operator()(const string& key){size_t hash = 0;for (size_t i = 0; i < key.size(); ++i){hash += key[i];}return hash;}
};

利用以上模板函数，sort、left、right三个字符串计算出的值分别为456、427、542，可以看出假如字符串比较短或者字符串较为接近，字符串的每个字符的ASCII码值加起来的和比较接近，或者可能是相同的值，这会导致哈希冲突。因此，单纯的累加每个字符的ASCII码值显得不够专业。有人专门对字符串进行了研究，搞出了各种各样的重复率较底的字符串哈希算法。具体可以参考该文章，字符串哈希算法。
在众多字符串哈希算法中，BKDRHash在各方面都很优秀。因此，本文选择BKDRHash算法作为计算字符串值的函数。

BKDRHash的核心就是在原来值的基础上*131，再加上字符的ASCII码值。这样计算出来的值更为分散，更加符合我们的需求。

//特化
template<>
struct _Hash<string>
{size_t operator()(const string& key){size_t hash = 0;for (size_t i = 0; i < key.size(); ++i){hash *= 131;hash += key[i];}return hash;}
};

1.2 优化：素数大小

使用除留余数法时，哈希表的大小最好是素数，这样能够减少哈希冲突产生的次数。SGI版STL中，哈希表在扩容时就使用了这一技巧。
简单来说，就是当我们进行扩容时，按照下一个素数值的大小进行扩容，这些素数都是近似2倍的大小关系，在确保不会频繁扩容的同时，尽可能减少哈希冲突，所以需要这样一个函数。

size_t GetNextPrime(size_t num)
{const int PRIMECOUNT = 28;static const size_t primeList[PRIMECOUNT] ={53ul, 97ul, 193ul, 389ul, 769ul,1543ul, 3079ul, 6151ul, 12289ul, 24593ul,49157ul, 98317ul, 196613ul, 393241ul, 786433ul,1572869ul, 3145739ul, 6291469ul, 12582917ul,25165843ul,50331653ul, 100663319ul, 201326611ul, 402653189ul,805306457ul,1610612741ul, 3221225473ul, 4294967291ul};for (size_t i = 0; i < PRIMECOUNT; ++i){if (primeList[i] > num){return primeList[i];}}return primeList[PRIMECOUNT - 1];
}

同样的，需要对扩容的地方进行改造。改造之后，哈希表的初始大小变为53。

2 新增迭代器类

2.1 设计背景

哈希表的数据存储分散在多个桶（bucket）中，每个桶可能是一个链表，存储若干个节点。因此，迭代器的实现不仅需要遍历链表中的节点，还需要跳跃到下一个非空桶继续遍历。为了实现这一功能，需要一个特殊的迭代器。因为哈希桶是一个单链表，只能往前走访问链表，不能往回走。因此我们的迭代器要设计为单向迭代器（只支持++）。如下代码所示：

//前置声明
template<class K, class T, class KeyOfT, class Hash>
class HashTable;template<class K, class T, class KeyOfT, class Hash>
struct __HashTableIterator
{KeyOfT keyoft;typedef __HashTableIterator<K, T, KeyOfT, Hash> Self;typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;Node* _node;HT* _pHashTable;//指向哈希表的指针__HashTableIterator(Node* node, HT* pHashTable):_node(node), _pHashTable(pHashTable){}//基本功能
};

2.2 为什么需要存储哈希表指针

迭代器的移动逻辑是：如果当前所在的桶中还有数据，迭代器直接移动到下一个节点即可。如果已经移动到了当前桶中最后一个元素，此时迭代器还需要继续往后移动，迭代器就需要移动至当前哈希表中下一个有数据的桶中。这里显然需要用到哈希表，并且是同一个哈希表。解决办法：构造迭代器__HashTableIterator时，迭代器除了保存指向当前节点的指针_node，还需要保存一个指向哈希表对象的指针_pHashTable，主要原因是为了跨桶查找下一个节点。

那么迭代器如何在哈希表中移动呢？首要问题是确定当前迭代器位于哈希表中的哪个位置，可以通过代码size_t index = HashFunc(koft(cur->_data)) % newtales.size();求出该位置。确定位置后，迭代器往后移动，直到移动至一个不为空的位置，返回即可。

1、桶定位需要哈希表结构：
当遍历完当前桶后，operator++需要从当前桶的索引位置开始，查找下一个不为空的桶；这些桶存储在哈希表的_tables成员中，迭代器需要通过指针_pHashTable访问它。

2、简化设计：
（1）如果不存储哈希表的指针，迭代器__HashTableIterator无法跨桶查找下一个节点，导致实现复杂且效率低下。
（2）存储_pHashTable后，可以直接使用哈希表的结构信息（如桶的数量和内容）进行遍历。

3、提升代码的灵活性：
_pHashTable提供了迭代器与哈希表的关联性，使得__HashTableIterator能够独立于具体的哈希表实现，在其他类似结构中复用。

现在能通过_pHashTable访问一个哈希表。
一个细节：需要对哈希表进行前置声明才能正常使用；

2.3 operator++()的逻辑

operator++的核心任务是移动迭代器到下一个可访问的节点，分为两种情况。

1、当前桶的链表还剩余有节点：
如果当前节点有_next指针，直接移动到链表中的下一个节点。

2、当前桶已经被遍历完：
获取当前桶的索引：根据当前节点的数据，通过哈希函数计算出当前桶的索引。
查找下一个非空桶：
（1）从当前桶的下一个位置开始遍历_tables。
（2）找到第一个不为空的桶后，将_node指向该桶的第一个节点。
（3）如果遍历到表尾仍未找到，将_node设置为nullptr，表示迭代结束。

再次理解为什么要存储哈希表指针，如下图代码所示，我们需要表的数据记录hashi以及_size。

Self operator++()
{//当前桶还未遍历结束if (_node->_next){_node = _node->_next;}else{//此时，当前的桶已经遍历完了，需要对下一个桶进行遍历//1、计算当前桶的哈希值size_t hashi = _pHashTable->HashFunc(keyoft(_node->_data)) % _pHashTable->_tables.size();++hashi;//++i进入到下一个哈希桶for (; hashi < _pHashTable->_tables.size(); ++hashi){Node* cur = _pHashTable->_tables[hashi];if (cur){_node = cur;return *this;}}_node = nullptr;}return *this;
}

在该重载函数中，访问了哈希表类中的私有成员_tables，这种操作是不行的，为了让其能够成功访问哈希表类中的私有成员_tables，可以把迭代器类设为哈希表类的友元类。

class HashTable
{typedef HashNode<T> Node;friend struct __HashTableIterator<K, T, KeyOfT, Hash>;
public:typedef __HashTableIterator<K, T, KeyOfT, Hash> iterator;//各类功能
}

再次理解为什么要存储哈希表指针，如下图代码所示，我们需要表的数据记录hashi和_size。

2.4 begin()和end()的实现

1、begin()

• 从第一个桶开始查找，找到第一个非空桶，返回其第一个节点对应的迭代器。
• 如果所有的桶都为空，返回迭代器iterator(nullptr,this)。

2、end()

• 返回一个空迭代器iterator(nullptr,this)，用于标志迭代结束。

iterator begin()
{for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]){return iterator(_tables[i], this);}}return end();
}iterator end()
{return iterator(nullptr, this);
}

2.5 友元和前置声明的作用

1、前置声明：

• __HashTableIterator的定义在HashTable之前，且依赖于HashTable的定义，HashTable的接口（如begin()、end()）需要返回__HashTableIterator。
• 前置声明解决了这种相互依赖的问题，确保了在定义HashTable时能够使用__HashTableIterator。

2、友元

• __HashTableIterator需要访问HashTable的私有成员_tables和_tables.size()，这是其实现operator++所必须的。
• 通过友元声明，使__HashTableIterator可以直接访问HashTable的私有成员，简化了代码设计。

2.6 迭代器和哈希表实现的完整代码

#pragma once
#include<iostream>
#include<vector>
#include<string>
using namespace std;template<class T>
struct HashNode
{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data),_next(nullptr){}
};//前置声明
template<class K, class T, class KeyOfT, class Hash>
class HashTable;template<class K, class T, class KeyOfT, class Hash>
struct __HashTableIterator
{KeyOfT keyoft;typedef __HashTableIterator<K, T, KeyOfT, Hash> Self;typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;Node* _node;HT* _pHashTable;//指向哈希表的指针__HashTableIterator(Node* node, HT* pHashTable):_node(node), _pHashTable(pHashTable){}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}Self operator++(){//当前桶还未遍历结束if (_node->_next){_node = _node->_next;}else{//此时，当前的桶已经遍历完了，需要对下一个桶进行遍历//1、计算当前桶的哈希值size_t hashi = _pHashTable->HashFunc(keyoft(_node->_data)) % _pHashTable->_tables.size();++hashi;//++i进入到下一个哈希桶for (; hashi < _pHashTable->_tables.size(); ++hashi){Node* cur = _pHashTable->_tables[hashi];if (cur){_node = cur;return *this;}}_node = nullptr;}return *this;}bool operator!=(const Self& s){return _node != s._node;}
};//如果K是一个整型，则直接返回该数据
template<class K>
struct _Hash
{const K& operator()(const K& key){return key;}
};//特化
template<>
struct _Hash<string>
{size_t operator()(const string& key){size_t hash = 0;for (size_t i = 0; i < key.size(); ++i){hash *= 131;hash += key[i];}return hash;}
};template<class K,class T ,class KeyOfT,class Hash>
class HashTable
{typedef HashNode<T> Node;friend struct __HashTableIterator<K, T, KeyOfT, Hash>;
public:typedef __HashTableIterator<K, T, KeyOfT, Hash> iterator;iterator begin(){for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]){return iterator(_tables[i], this);}}return end();}iterator end(){return iterator(nullptr, this);}//析构函数~HashTable(){Clear();}void Clear(){for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}size_t HashFunc(const K& key){Hash hash;return hash(key);}size_t GetNextPrime(size_t num){const int PRIMECOUNT = 28;static const size_t primeList[PRIMECOUNT] ={53ul, 97ul, 193ul, 389ul, 769ul,1543ul, 3079ul, 6151ul, 12289ul, 24593ul,49157ul, 98317ul, 196613ul, 393241ul, 786433ul,1572869ul, 3145739ul, 6291469ul, 12582917ul,25165843ul,50331653ul, 100663319ul, 201326611ul, 402653189ul,805306457ul,1610612741ul, 3221225473ul, 4294967291ul};for (size_t i = 0; i < PRIMECOUNT; ++i){if (primeList[i] > num){return primeList[i];}}return primeList[PRIMECOUNT - 1];}bool Insert(const T& data){KeyOfT keyoft;if (Find(keyoft(data)) != nullptr)return false;if (_num == _tables.size()){//创建一个新表，并扩容vector<Node*> newtables;//size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;size_t newsize = GetNextPrime(_tables.size());newtables.resize(newsize);//将旧表中的数据拷贝到新表中for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){size_t index = HashFunc(keyoft(data)) % newtables.size();Node* next = cur->_next;cur->_next = newtables[index];newtables[index] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtables);}//正常先查看该数据在不在表中，如果在就返回false，代码前面已经查找过了，//这里就不再查询了。 //计算数据在表中映射的位置size_t index = HashFunc(keyoft(data)) % _tables.size();//将该数据头查到链表中Node* newnode = new Node(data);newnode->_next = _tables[index];_tables[index] = newnode;++_num;return false;}Node* Find(const K& key){if (_tables.size() == 0)return nullptr;KeyOfT keyoft;size_t index = HashFunc(key) % _tables.size();Node* cur = _tables[index];while (cur){if (keyoft(cur->_data) == key){return cur;}else{cur = cur->_next;}}return nullptr;}bool Erase(const K& key){if (Find(key) == nullptr)return false;KeyOfT keyoft;size_t index = HashFunc(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[index];while (cur){if (keyoft(cur->_data) == key){if (prev == nullptr){//此时，说明要删除的节点就是链表的第一个节点_tables[index] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return nullptr;}private:vector<Node*> _tables;size_t _num;//记录哈希表中存储的数据的个数
};

3 迭代器map与set的复用

3.1 map的复用，数据pair<K,V>

#include"HashTable.h"template<class K, class V, class Hash=_Hash<K>>
class MyUnorderedMap
{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename HashTable<K, pair<K, V>, MapKeyOfT, Hash>::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}bool Insert(const pair<K, V>& kv){return _ht.Insert(kv);}private:HashTable<K, pair<K, V>, MapKeyOfT, Hash> _ht;
};

3.2 Set的复用，数据Key

#include"HashTable.h"template<class K, class Hash = _Hash<K>>
class MyUnorderedSet
{struct MapKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename HashTable<K, K, MapKeyOfT, Hash>::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}bool Insert(const K& key){return _ht.Insert(key);}private:HashTable<K, K, MapKeyOfT, Hash> _ht;
};

4.const迭代器--增加Ref与Ptr模板参数

const迭代器复用普通迭代器的代码，唯一不同的是operator*与operator->的返回值，const迭代器返回的是const T*与const T& ，因此加入两个模板参数Ref与Ptr，实例化时就可以获得两种模式的迭代器。

Ref operator*()
{return _node->_data;
}Ptr operator->()
{return &_node->_data;
}

根据以上代码可以实例化出两种模式的迭代器：普通迭代器和const迭代器。

typedef __HashTableIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
typedef __HashTableIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;iterator begin()
{for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]){return iterator(_tables[i], this);}}return end();
}iterator end()
{return iterator(nullptr, this);
}const_iterator begin() const
{for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]){return const_iterator(_tables[i], this);}}return end();
}const_iterator end() const
{return iterator(nullptr, this);
}

5.const迭代器权限放大的问题

接下来重载构造函数，使用const HashTable<K,T ,KeyOfT, Hash>*来接收参数。

此时，我们就可以不用提供非const版本的构造函数了。

6.解决值不能修改的问题

对于Set来说，key不可以修改，对于Map来说，pair<K,V>中的K不能修改，因此需要采取对应的措施。
对于Set来说：

普通迭代器与const迭代器都是const迭代器

对于Map来说：

Map成员中的pair修改为pair<const K,V>
迭代器正常走：

7.解决Insert返回值改为pair<iterator,bool>中存在的问题

接下来要做Insert返回值的修改，为重载operator[]做准备：
1、更改返回值。

2、find返回值也要对应修改

这里就Set代码存在问题，现在代码跑不过了。

对于Map来说：

对于Set来说：

因此我们需要提供const_iterator的构造函数，使用iterator构造const_iterator。

上图中涉及到函数返回值会创建临时对象的问题，具体可参考文章C++中产生临时对象的情况及其解决方案。

8.operator[]

对于Map，我们还需要重载operator[]，就像数组一样使用，可以插入数据，也可以查找、修改Value，这里我们要借助Insert来实现。

V& operator[](const K& key)
{pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));return ret.first->second;
}

9.HashTable的代码实现

#pragma once
#include<iostream>
#include<vector>
#include<string>
using namespace std;template<class T>
struct HashNode
{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data),_next(nullptr){}
};//前置声明
template<class K, class T, class KeyOfT, class Hash>
class HashTable;template<class K, class T, class Ref,class Ptr, class KeyOfT, class Hash>
struct __HashTableIterator
{KeyOfT keyoft;typedef __HashTableIterator<K, T,Ref, Ptr, KeyOfT, Hash> Self;typedef __HashTableIterator<K, T, T&, T*, KeyOfT, Hash> iterator;typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;Node* _node;const HT* _pHashTable;//指向哈希表的指针__HashTableIterator(Node* node, const HT* pHashTable):_node(node), _pHashTable(pHashTable){}__HashTableIterator(const iterator& it):_node(it._node), _pHashTable(it._pHashTable){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self operator++(){//当前桶还未遍历结束if (_node->_next){_node = _node->_next;}else{//此时，当前的桶已经遍历完了，需要对下一个桶进行遍历//1、计算当前桶的哈希值size_t hashi = _pHashTable->HashFunc(keyoft(_node->_data)) % _pHashTable->_tables.size();++hashi;//++i进入到下一个哈希桶for (; hashi < _pHashTable->_tables.size(); ++hashi){Node* cur = _pHashTable->_tables[hashi];if (cur){_node = cur;return *this;}}_node = nullptr;}return *this;}bool operator!=(const Self& s){return _node != s._node;}
};//如果K是一个整型，则直接返回该数据
template<class K>
struct _Hash
{const K& operator()(const K& key){return key;}
};//特化
template<>
struct _Hash<string>
{size_t operator()(const string& key){size_t hash = 0;for (size_t i = 0; i < key.size(); ++i){hash *= 131;hash += key[i];}return hash;}
};template<class K,class T ,class KeyOfT,class Hash>
class HashTable
{typedef HashNode<T> Node;template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc>friend struct __HashTableIterator;
public:typedef __HashTableIterator<K, T, T&, T*, KeyOfT, Hash> iterator;typedef __HashTableIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;iterator begin(){for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]){return iterator(_tables[i], this);}}return end();}iterator end(){return iterator(nullptr, this);}const_iterator begin() const{for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]){return const_iterator(_tables[i], this);}}return end();}const_iterator end() const{return const_iterator(nullptr, this);}//析构函数~HashTable(){Clear();}void Clear(){for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}size_t HashFunc(const K& key) const{Hash hash;return hash(key);}size_t GetNextPrime(size_t num){const int PRIMECOUNT = 28;static const size_t primeList[PRIMECOUNT] ={53ul, 97ul, 193ul, 389ul, 769ul,1543ul, 3079ul, 6151ul, 12289ul, 24593ul,49157ul, 98317ul, 196613ul, 393241ul, 786433ul,1572869ul, 3145739ul, 6291469ul, 12582917ul,25165843ul,50331653ul, 100663319ul, 201326611ul, 402653189ul,805306457ul,1610612741ul, 3221225473ul, 4294967291ul};for (size_t i = 0; i < PRIMECOUNT; ++i){if (primeList[i] > num){return primeList[i];}}return primeList[PRIMECOUNT - 1];}pair<iterator,bool> Insert(const T& data){KeyOfT keyoft;iterator it = Find(keyoft(data));if (it != end())return make_pair(it,false);if (_num == _tables.size()){//创建一个新表，并扩容vector<Node*> newtables;//size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;size_t newsize = GetNextPrime(_tables.size());newtables.resize(newsize);//将旧表中的数据拷贝到新表中for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){size_t index = HashFunc(keyoft(data)) % newtables.size();Node* next = cur->_next;cur->_next = newtables[index];newtables[index] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtables);}//正常先查看该数据在不在表中，如果在就返回false，代码前面已经查找过了，//这里就不再查询了。 //计算数据在表中映射的位置size_t index = HashFunc(keyoft(data)) % _tables.size();//将该数据头查到链表中Node* newnode = new Node(data);newnode->_next = _tables[index];_tables[index] = newnode;++_num;return make_pair(iterator(newnode, this), true);}iterator Find(const K& key){if (_tables.size() == 0)return iterator(nullptr,this);KeyOfT keyoft;size_t index = HashFunc(key) % _tables.size();Node* cur = _tables[index];while (cur){if (keyoft(cur->_data) == key){return iterator(cur,this);}else{cur = cur->_next;}}return iterator(nullptr, this);}bool Erase(const K& key){if (Find(key) == nullptr)return false;KeyOfT keyoft;size_t index = HashFunc(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[index];while (cur){if (keyoft(cur->_data) == key){if (prev == nullptr){//此时，说明要删除的节点就是链表的第一个节点_tables[index] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return nullptr;}private:vector<Node*> _tables;size_t _num;//记录哈希表中存储的数据的个数
};

10.unordered_map与unordered_set的实现

1、unordered_map：

#include"HashTable.h"template<class K, class V, class Hash=_Hash<K>>
class MyUnorderedMap
{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::const_iterator const_iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}const_iterator begin() const{return _ht.begin();}const_iterator end() const{return _ht.end();}pair<iterator,bool> Insert(const pair<K, V>& kv){return _ht.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));return ret.first->second;}private:HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};

2、unordered_set：

#include"HashTable.h"template<class K, class Hash = _Hash<K>>
class MyUnorderedSet
{struct MapKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename HashTable<K, K, MapKeyOfT, Hash>::const_iterator iterator;typedef typename HashTable<K, K, MapKeyOfT, Hash>::const_iterator const_iterator;iterator begin() {return _ht.begin();}iterator end() {return _ht.end();}const_iterator begin() const{return _ht.begin();}const_iterator end() const{return _ht.end();}pair<iterator,bool> Insert(const K& key){//写法1：//1、先用一个普通迭代器来接收/*pair<typename HashTable<K, K, MapKeyOfT, Hash>::iterator, bool>ret = _ht.Insert(key);//2、再用普通迭代器来构造const迭代器，前提是补充实现一个拷贝构造函数。return pair<iterator, bool>(ret.first, ret.second);*///写法2：该写法会将_ht.Insert(key)的返回值赋值给pair<iterator,bool>，该过程会自动调用拷贝构造函数return _ht.Insert(key);}private:HashTable<K, K, MapKeyOfT, Hash> _ht;
};

unordered_map的实现及测试代码可参考：unordered_map的实现。unordered_set的实现及测试代码可参考：unordered_set的实现。​​​​​​​