哈希表封装实现 unordered_map 和 unordered_set——哈希表の华丽二重奏

77 阅读 0 评论 51 点赞

我是靠谱客的博主健壮雪碧，这篇文章主要介绍哈希表封装实现 unordered_map 和 unordered_set——哈希表の华丽二重奏，现在分享给大家，希望可以做个参考。

传统艺能????

小编是双非本科大一菜鸟不赘述，欢迎各位指点江山（期待~）（QQ：1319365055）
此前博客点我！点我！请搜索博主【知晓天空之蓝】

????????非科班转码社区诚邀您入驻????????
小伙伴们，打码路上一路向北，彼岸之前皆是疾苦
一个人的单打独斗不如一群人的砥砺前行
这是和梦想合伙人组建的社区，诚邀各位有志之士的加入！！
社区用户好文均加精（“标兵”文章字数2000+加精，“达人”文章字数1500+加精）
直达：社区链接点我

在这里插入图片描述
如果你看了上一篇用红黑树封装实现 map 和 set ，那么本文就比较熟悉了因为二者的思路是一样的，但是别看这里是哈希表，哈希表实现虽然没有红黑树麻烦，但是 unordered_map 和 unordered_set 的封装却要更加复杂一点。

和封装 map，set 一样，这里用一个 KV 模型来讲解，首先还是给出哈希表源码（有疑问的友友参见我上一篇文章）：

template<class K, class V>
struct HashNode
{
	pair<K, V> _kv;
	HashNode<K, V>* _next;

	//构造函数
	HashNode(const pair<K, V>& kv)
		:_kv(kv)
		, _next(nullptr)
	{}
};

//哈希表
template<class K, class V>
class HashTable
{
	typedef HashNode<K, V> Node; //哈希结点类型
public:
	//获取本次增容后哈希表的大小
	size_t GetNextPrime(size_t prime)
	{
		const int PRIMECOUNT = 28;
		//素数序列
		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
		};
		size_t i = 0;
		for (i = 0; i < PRIMECOUNT; i++)
		{
			if (primeList[i] > prime)
				return primeList[i];
		}
		return primeList[i];
	}
	//插入函数
	bool Insert(const pair<K, V>& kv)
	{
		//1、查看哈希表中是否存在该键值的键值对
		Node* ret = Find(kv.first);
		if (ret) //哈希表中已经存在该键值的键值对（不允许数据冗余）
		{
			return false; //插入失败
		}

		//2、判断是否需要调整哈希表的大小
		if (_n == _table.size()) //哈希表的大小为0，或负载因子超过1
		{
			//增容
			//a、创建一个新的哈希表，新哈希表的大小设置为原哈希表的2倍（若哈希表大小为0，则将哈希表的初始大小设置为10）
			vector<Node*> newtable;

			newtable.resize(GetNextPrime(_table.size()));
				
			//b、将原哈希表当中的结点插入到新哈希表
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i]) //桶不为空
				{
					Node* cur = _table[i];
					while (cur) //将该桶的结点取完为止
					{
						Node* next = cur->_next; //记录cur的下一个结点
						size_t index = cur->_kv.first%newtable.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
						//将该结点头插到新哈希表中编号为index的哈希桶中
						cur->_next = newtable[index];
						newtable[index] = cur;

						cur = next; //取原哈希表中该桶的下一个结点
					}
					_table[i] = nullptr; //该桶取完后将该桶置空
				}
			}
			//c、交换这两个哈希表
			_table.swap(newtable);
		}

		//3、将键值对插入哈希表
		size_t index = kv.first % _table.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
		Node* newnode = new Node(kv); //根据所给数据创建一个待插入结点
		//将该结点头插到新哈希表中编号为index的哈希桶中
		newnode->_next = _table[index];
		_table[index] = newnode;

		//4、哈希表中的有效元素个数加一
		_n++;
		return true;
	}
	//查找函数
	HashNode<K, V>* Find(const K& key)
	{
		if (_table.size() == 0) //哈希表大小为0，查找失败
		{
			return nullptr;
		}

		size_t index = key % _table.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
		//遍历编号为index的哈希桶
		HashNode<K, V>* cur = _table[index];
		while (cur) //直到将该桶遍历完为止
		{
			if (cur->_kv.first == key) //key值匹配，则查找成功
			{
				return cur;
			}
			cur = cur->_next;
		}
		return nullptr; //直到该桶全部遍历完毕还没有找到目标元素，查找失败
	}
	//删除函数
	bool Erase(const K& key)
	{
		//1、通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
		size_t index = key % _table.size();
		//2、在编号为index的哈希桶中寻找待删除结点
		Node* prev = nullptr;
		Node* cur = _table[index];
		while (cur) //直到将该桶遍历完为止
		{
			if (cur->_kv.first == key) //key值匹配，则查找成功
			{
				//找到了待删除结点，则删除该结点
				if (prev == nullptr) //待删除结点是哈希桶中的第一个结点
				{
					_table[index] = cur->_next; //将第一个结点从该哈希桶中移除
				}
				else //待删除结点不是哈希桶的第一个结点
				{
					prev->_next = cur->_next; //将该结点从哈希桶中移除
				}
				delete cur;
				//删除结点后，有效元素个数减一
				_n--;
				return true; //删除成功
			}
			prev = cur;
			cur = cur->_next;
		}
		//假删除可能会导致迭代器失效
			
		return false; //直到该桶全部遍历完毕还没有找到待删除元素，删除失败
	}
private:
	vector<Node*> _table;
	size_t _n = 0; //有效元素个数
};

模板参数????

老规矩，和 map，set 同理，unordered_set 是 K 模型的容器，而 unordered_map 是 KV 模型的容器，既然是实现同时封装，那么模板参数就必须进行控制，先给出哈希表的模板：

template<class K, class T>
class HashTable

针对上层容器是 unordered_set 的，我们传入 Key，Key；上层容器是 unordered_map 的我们传入 Key，Key 和 Value 的键值对：

template<class K>
class unordered_set
{
public:
	//...
private:
	HashTable<K, K> _ht; //传入K和K
};

template<class K, class V>
class unordered_map
{
public:
	//...
private:
	HashTable<K, pair<K, V>> _ht; //传入K以及K和V构成的键值对
};

也就是说，哈希表中的模板参数T的类型到底是什么，完全却决于上层所使用容器的种类。

在这里插入图片描述

哈希结点的模板参数也应该由原来的K、V变为T，上层容器是 unordered_set 时，传入的T是键值，哈希结点中存储的就是键值。上层容器是 unordered_map 时，传入的T是键值对，哈希结点中存储的就是键值对，更改后哈希结点的定义如下：

template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;

	//构造函数
	HashNode(const T& data)
		:_data(data)
		, _next(nullptr)
	{}
};

现在由于我们在哈希结点当中存储的数据类型是T，这个T可能就是一个键值，也可能是一个键值对，对于底层的哈希表来说，它并不知道哈希结点当中存储的数据究竟是什么类型，因此需要由上层容器提供一个仿函数，用于获取T类型数据当中的键值。

因此，unordered_map容器需要向底层哈希表提供一个仿函数，该仿函数返回键值对当中的键值。

template<class K, class V>
class unordered_map
{
	//仿函数
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv) //返回键值对当中的键值key
		{
			return kv.first;
		}
	};
public:
	//...
private:
	HashTable<K, pair<K, V>, MapKeyOfT> _ht;
};

同时 unordered_set 也需要一个仿函数进行键值返回，虽然他的参数只有 key 不用单独去去键值对的值，但是为了统一方法获取，都通过这个仿函数取值，我们也提供一个：

template<class K>
class unordered_set
{
	//仿函数
	struct SetKeyOfT
	{
		const K& operator()(const K& key) //返回键值key
		{
			return key;
		}
	};
public:
	//...
private:
	HashTable<K, K, SetKeyOfT> _ht;
};

因为有了取键值的仿函数，因此哈希表的模板参数也会多一个去接收上层：

template<class K, class T, class KeyOfT>
class HashTable

字符串取模????

字符串如何取模也是哈希表的常见经典问题，使用字符串作为 key 值，字符串并非整型这就意味着我们不能直接计算其哈希地址，所以应该先计算出哈希地址。

但是上帝没有眷顾字符串，没有使得字符串与整型之间一一对应的方法，因为整型大小是有限的，最大的无符号整型是 4294967295，但是字符串的排列却是无穷的，因此我们提出了 BKDRHash算法 。

经过前辈们实验后发现，BKDRHash算法无论是在实际效果还是编码实现中，效果都是最突出的。该算法由于在Brian Kernighan与Dennis Ritchie的《The C Programing Language》一书被展示而得名，是一种简单快捷的hash算法，也是Java目前采用的字符串的hash算法

因此，现在我们需要在哈希表的模板参数中再增加一个仿函数，用于将键值key转换成对应的整型

template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
class HashTable

该算法基本思想就是设置一个为 0 的初始值，每一位 string 对象都进行初始值乘以 131 再加上这个字符的 ASCII 码值，最后赋给初始值进行迭代：

template<class K>
struct Hash
{
	size_t operator()(const K& key) //返回键值key
	{
		return key;
	}
};
//string类型的特化
template<>
struct Hash<string>
{
	size_t operator()(const string& s) //BKDRHash算法
	{
		size_t value = 0;
		for (auto ch : s)
		{
			value = value * 131 + ch;
		}
		return value;
	}
};

默认成员函数????

构造函数????

哈希表中有两个成员变量，当我们实例化一个对象时：

_table会自动调用vector的默认构造函数进行初始化。
_n会根据我们所给的缺省值被设置为0。

vector<Node*> _table; //哈希表
size_t _n = 0; //有效元素个数

这里默认构造已经完美完成了构造的任务，我们就不需要画蛇添足后期再去写一个构造函数，但是因为我们需要自己写拷贝构造函数，会使得初始化不使用默认构造，因此我们需要 default 关键字修饰来让他保持默认构造的属性

HashTable() = default; //显示指定默认构造函数

拷贝构造函数????

因为哈希表的拷贝不是简单的拷贝，需要重新映射的话，我们需要自己实现一个深拷贝，逻辑上需要满足：

将哈希表的大小调整为ht._table的大小
将ht._table每个桶当中的结点一个个拷贝到自己的哈希表中
更改哈希表当中的有效数据个数

HashTable(const HashTable& ht)
{
	//大小调整为ht._table的大小
	_table.resize(ht._table.size());
	//将ht._table每个桶当中的结点拷贝过来
	for (size_t i = 0; i < ht._table.size(); i++)
	{
		if (ht._table[i]) //桶不为空
		{
			Node* cur = ht._table[i];
			while (cur) 
			{
				Node* copy = new Node(cur->_data); //创建拷贝结点
				//将结点头插到当前桶
				copy->_next = _table[i];
				_table[i] = copy;
				cur = cur->_next; 
			}
		}
	}
	//有效数据个数
	_n = ht._n;
}

赋值重载????

赋值运算符的重载可以通过拷贝构造实现，参数间接调用拷贝构造函数，之后将构造出来的哈希表和当前哈希表的成员变量进行交换即可。重载函数调用结束后，拷贝构造出来的哈希表会因为出了作用域而被自动析构，此时原哈希表之前的数据也就顺势被释放了

HashTable& operator=(HashTable ht)
{
	//交换哈希表中两个成员变量的数据
	_table.swap(ht._table);
	swap(_n, ht._n);

	return *this; //支持连续赋值
}

析构函数????

因为哈希表当中存储的结点都是new出来的，因此在哈希表被析构时必须进行结点的释放。在析构哈希表时我们只需要依次取出非空的哈希桶，遍历哈希桶当中的结点并进行释放即可

~HashTable()
{
	//将哈希表当中的结点一个个释放
	for (size_t i = 0; i < _table.size(); i++)
	{
		if (_table[i]) //桶不为空
		{
			Node* cur = _table[i];
			while (cur)
			{
				Node* next = cur->_next; //记录下一个结点
				delete cur;
				cur = next;
			}
			_table[i] = nullptr; //置空
		}
	}
}

正向迭代器????

哈希表的正向迭代器就是对哈希节点封装，实现了 ++ 运算符重载，使他可以访问下一个非空的桶，所以每个正向迭代器里面存的都是哈希表地址。

template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
struct __HTIterator
{
	typedef HashNode<T> Node; //结点类型
	typedef HashTable<K, T, KeyOfT, HashFunc> HT; //哈希表类型
	typedef __HTIterator<K, T, KeyOfT, HashFunc> Self; //正向迭代器类型

	Node* _node; //结点指针
	HT* _pht; //地址
};

所以在构造迭代器的时候就需要知道节点的指针，以及节点所在哈希表的地址：

__HTIterator(Node* node, HT* pht)
	:_node(node) //结点指针
	, _pht(pht) //哈希表地址
{}

++ 的实现逻辑也非常简单，只需要注意一下如果当前元素是该桶最后一个元素，那么 ++ 就是跳到下一个非空桶：

// 重载*

T& operator*()
{
	return _node->_data; //返回哈希结点中数据的引用
}
// 重载->

T* operator->()
{
	return &_node->_data; //返回哈希结点中数据的地址
}
//迭代器比较

bool operator!=(const Self& s) const
{
	return _node != s._node; //判断两个结点的地址是否不同
}

bool operator==(const Self& s) const
{
	return _node == s._node; //判断两个结点的地址是否相同
}
// ++ （前置）重载

Self& operator++()
{
	if (_node->_next) //结点不是最后一个结点
	{
		_node = _node->_next; //直接 ++
	}
	else //结点是最后一个结点
	{
		KeyOfT kot;
		HashFunc hf;
		size_t index = hf(kot(_node->_data)) % _pht->_table.size(); //哈希函数计算出桶编号index（除数不能是capacity）
		index++; //从下一个位置开始找非空哈希桶
		while (index < _pht->_table.size())
		{
			if (_pht->_table[index]) //当前哈希桶非空
			{
				_node = _pht->_table[index]; //直接 ++
				return *this;
			}
			index++; //当前哈希桶为空，找下一个哈希桶
		}
		_node = nullptr; //没有空桶 ++ 后变 nullptr
	}
	return *this;
}

哈希表的迭代器类型是单向迭代器，没有反向迭代器，即没有实现–运算符的重载，若是想让哈希表支持双向遍历，可以考虑将哈希桶中存储的单链表结构换为双链表结构。

敲黑板！

接下来就可以进行正向迭代器类型的 typedef，需要注意的是，为了让外部能够使用 typedef 后的正向迭代器类型 iterator，我们需要在 public 区域进行 typedef。
由于 ++ 重载函数在寻找下一个结点时，会访问哈希表成员变量 _table，而 _table 是哈希表的私有成员，因此我们需要将正向迭代器类声明为哈希表类的友元。
将哈希表中查找函数返回的结点指针，改为返回由结点指针和哈希表地址构成的正向迭代器。
将哈希表中插入函数的返回值类型，改为由正向迭代器类型和布尔类型所构成的键值对

template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
class HashTable
{
	//将正向迭代器类声明为哈希表类的友元
	template<class K, class T, class KeyOfT, class HashFunc>
	friend struct __HTIterator;

	typedef HashNode<T> Node; //哈希结点类型
public:
	typedef __HTIterator<K, T, KeyOfT, HashFunc> iterator; //正向迭代器类型

	iterator begin()
	{
		size_t i = 0;
		while (i < _table.size()) 
		{
			if (_table[i]) 
			{
				return iterator(_table[i], this); //返回第一个结点的正向迭代器
			}
			i++;
		}
		return end();
	}
	iterator end()
	{
		return iterator(nullptr, this); //返回nullptr的正向迭代器
	}
private:
	vector<Node*> _table; //哈希表
	size_t _n = 0; //有效元素个数
};

完整代码????

哈希表

template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;

	//构造函数
	HashNode(const T& data)
		:_data(data)
		, _next(nullptr)
	{}
};
template<class K>
struct Hash
{
	size_t operator()(const K& key) //返回键值key
	{
		return key;
	}
};
//string类型的特化
template<>
struct Hash<string>
{
	size_t operator()(const string& s) //BKDRHash算法
	{
		size_t value = 0;
		for (auto ch : s)
		{
			value = value * 131 + ch;
		}
		return value;
	}
};
//哈希表的实现
template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
class HashTable
{
	//将正向迭代器类声明为哈希表类的友元
	template<class K, class T, class KeyOfT, class HashFunc>
	friend struct __HTIterator;
	//friend struct __HTIterator<K, T,KeyOfT, HashFunc>;
	typedef HashNode<T> Node; //哈希结点类型
public:
	typedef __HTIterator<K, T, KeyOfT, HashFunc> iterator; //正向迭代器类型

	iterator begin()
	{
		size_t i = 0;
		while (i < _table.size()) //找到第一个非空哈希桶
		{
			if (_table[i]) //该哈希桶非空
			{
				return iterator(_table[i], this); //返回该哈希桶中的第一个结点的正向迭代器
			}
			i++;
		}
		return end(); //哈希桶中无数据，返回end()
	}
	iterator end()
	{
		return iterator(nullptr, this); //返回nullptr的正向迭代器
	}

	//构造函数
	HashTable() = default; //显示指定生成默认构造

	//拷贝构造函数
	HashTable(const HashTable& ht)
	{
		//将哈希表的大小调整为ht._table的大小
		_table.resize(ht._table.size());
		//将ht._table每个桶中的结点拷贝到自己的哈希表中（深拷贝）
		for (size_t i = 0; i < ht._table.size(); i++)
		{
			if (ht._table[i]) //桶不为空
			{
				Node* cur = ht._table[i];
				while (cur) 
				{
					Node* copy = new Node(cur->_data); //创建拷贝结点
					//将拷贝结点头插到当前桶
					copy->_next = _table[i];
					_table[i] = copy;
					cur = cur->_next; //取下一个待拷贝结点
				}
			}
		}
		//更改哈希表当中的有效数据个数
		_n = ht._n;
	}
	//赋值运算符重载函数
	HashTable& operator=(HashTable ht)
	{
		//交换哈希表中两个成员变量的数据
		_table.swap(ht._table);
		swap(_n, ht._n);

		return *this; //支持连续赋值
	}
	//析构函数
	~HashTable()
	{
		//将哈希表当中的结点释放
		for (size_t i = 0; i < _table.size(); i++)
		{
			if (_table[i]) //桶不为空
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next; //记录下一个结点
					delete cur; 
					cur = next;
				}
				_table[i] = nullptr; //将该哈希桶置空
			}
		}
	}
	//获取本次增容后哈希表的大小
	size_t GetNextPrime(size_t prime)
	{
		const int PRIMECOUNT = 28;
		//素数序列
		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
		};
		size_t i = 0;
		for (i = 0; i < PRIMECOUNT; i++)
		{
			if (primeList[i] > prime)
				return primeList[i];
		}
		return primeList[i];
	}
	//插入函数
	pair<iterator, bool> Insert(const T& data)
	{
		KeyOfT kot;
		//查看哈希表中是否存在该键值的键值对
		iterator ret = Find(kot(data));
		if (ret != end())
		{
			return make_pair(ret, false); //插入失败
		}

		if (_n == _table.size()) //哈希表的大小为0，或负载因子超过1
		{
			//创建一个新的哈希表，新哈希表的大小设置为原哈希表的2倍（若哈希表大小为0，则将哈希表的初始大小设置为10）
			HashFunc hf;
			vector<Node*> newtable;
			//size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
			//newtable.resize(newsize);

			newtable.resize(GetNextPrime(_table.size()));
				
			//将原哈希表当中的结点插入到新哈希表
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i]) //桶不为空
				{
					Node* cur = _table[i];
					while (cur)
					{
						Node* next = cur->_next; //记录cur的下一个结点
						size_t index = hf(kot(cur->_data))%newtable.size(); //哈希函数计算出哈希桶编号index（除数不能是capacity）
						//头插到编号为index的新哈希桶中
						cur->_next = newtable[index];
						newtable[index] = cur;

						cur = next; //取原哈希表中该桶的下一个结点
					}
					_table[i] = nullptr; //桶置空
				}
			}
			//交换两个哈希表
			_table.swap(newtable);
		}

		//3、将键值对插入哈希表
		HashFunc hf;
		size_t index = hf(kot(data)) % _table.size(); //哈希函数计算出哈希桶编号index（除数不能是capacity）
		Node* newnode = new Node(data); 
		//头插到编号为index的新哈希桶中
		newnode->_next = _table[index];
		_table[index] = newnode;

		//有效元素个数加一
		_n++;
		return make_pair(iterator(newnode, this), true);
	}
	//查找函数
	iterator Find(const K& key)
	{
		if (_table.size() == 0) //哈希表大小为0，查找失败
		{
			return end();
		}

		KeyOfT kot;
		HashFunc hf;
		size_t index = hf(key) % _table.size(); //哈希函数计算出哈希桶编号index（除数不能是capacity）
		//遍历编号为index的哈希桶
		HashNode<T>* cur = _table[index];
		while (cur) 
		{
			if (kot(cur->_data) == key) //key值匹配，则查找成功
			{
				return iterator(cur, this);
			}
			cur = cur->_next;
		}
		return end(); //查找失败
	}
	//删除函数
	bool Erase(const K& key)
	{
		KeyOfT kot;
		HashFunc hf;
		//哈希函数计算出哈希桶编号index（除数不能是capacity）
		size_t index = hf(key) % _table.size();
		//在编号为index的哈希桶中寻找待删除结点
		Node* prev = nullptr;
		Node* cur = _table[index];
		while (cur)
		{
			if (kot(cur->_data) == key) //key值匹配，则查找成功
			{
				
				if (prev == nullptr) //待删除结点是第一个结点
				{
					_table[index] = cur->_next; //从哈希桶移除
				}
				else //待删除结点不是第一个结点
				{
					prev->_next = cur->_next;
				}
				delete cur; //释放结点
				_n--;
				return true; //删除成功
			}
			prev = cur;
			cur = cur->_next;
		}
		//假删除可能会导致迭代器失效
			
		return false; //删除失败
	}
private:
	vector<Node*> _table; //哈希表
	size_t _n = 0; //有效元素个数
};

正向迭代器

template<class K, class T, class KeyOfT, class HashFunc>
class HashTable;

//正向迭代器
template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
struct __HTIterator
{
	typedef HashNode<T> Node; //哈希结点类型
	typedef HashTable<K, T, KeyOfT, HashFunc> HT; //哈希表类型
	typedef __HTIterator<K, T, KeyOfT, HashFunc> Self; //正向迭代器类型

	Node* _node; //结点指针
	HT* _pht; //哈希表的地址

	//构造函数
	__HTIterator(Node* node, HT* pht)
		:_node(node) //结点指针
		, _pht(pht) //哈希表地址
	{}

	T& operator*()
	{
		return _node->_data; //返回哈希结点中数据的引用
	}

	T* operator->()
	{
		return &_node->_data; //返回哈希结点中数据的地址
	}

	bool operator!=(const Self& s) const
	{
		return _node != s._node; 
	}

	bool operator==(const Self& s) const
	{
		return _node == s._node;
	}

	//前置++
	Self& operator++()
	{
		if (_node->_next) //该结点不是最后一个结点
		{
			_node = _node->_next; //++后变为当前哈希桶中的下一个结点
		}
		else //该结点是最后一个结点
		{
			KeyOfT kot;
			HashFunc hf;
			size_t index = hf(kot(_node->_data)) % _pht->_table.size(); //哈希函数计算出当前哈希桶编号index（除数不能是capacity）
			index++; //从下一个位置开始找
			while (index < _pht->_table.size()) 
			{
				if (_pht->_table[index]) //当前哈希桶非空
				{
					_node = _pht->_table[index]; //++后变为当前哈希桶中的第一个结点
					return *this;
				}
				index++; //当前哈希桶为空桶，找下一个哈希桶
			}
			_node = nullptr; //没有空桶了，++变为nullptr
		}
		return *this;
	}
};

unordered_set

namespace cl //防止命名冲突
{
	template<class K>
	class unordered_set
	{
		//仿函数
		struct SetKeyOfT
		{
			const K& operator()(const K& key) //返回键值key
			{
				return key;
			}
		};
	public:
		//现在没有实例化，没办法到HashTable里面找iterator，typename 告诉编译器这是一个类型，实例化以后再去取
		typedef typename HashTable<K, K, SetKeyOfT>::iterator iterator;

		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			return _ht.end();
		}
		//插入函数
		pair<iterator, bool> insert(const K& key)
		{
			return _ht.Insert(key);
		}
		//删除函数
		void erase(const K& key)
		{
			_ht.Erase(key);
		}
		//查找函数
		iterator find(const K& key)
		{
			return _ht.Find(key);
		}
	private:
		HashTable<K, K, SetKeyOfT> _ht;
	};
}

unordered_map

namespace cl //防止命名冲突
{
	template<class K, class V>
	class unordered_map
	{
		//仿函数
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv) //返回键值对当中的键值key
			{
				return kv.first;
			}
		};
	public:
		typedef typename HashTable<K, pair<K, V>, MapKeyOfT>::iterator iterator;

		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			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 = insert(make_pair(key, V()));
			iterator it = ret.first;
			return it->second;
		}
		//删除函数
		void erase(const K& key)
		{
			_ht.Erase(key);
		}
		//查找函数
		iterator find(const K& key)
		{
			return _ht.Find(key);
		}
	private:
		HashTable<K, pair<K, V>, MapKeyOfT> _ht;
	};
}