目录

unordered系列相关容器

unordered_map

unordered_map的文档介绍

unordered_set

底层结构

哈希概念

解决哈希冲突

闭散列：

代码实现

哈希基本结构

插入

查找find

删除

仿函数的应用

开散列

基本结构

插入的实现

查找

删除

Unordered_set/Unordered_set包装哈希

包装代码框架：

迭代器的哈希表

【operator*和operator->】

operator 前置

迭代结构

begin()和end()

operator!=

operator[]

复制结构、赋值重载和分析哈希表

拷贝构造

赋值重载

析构

unordered系列相关容器

在C 98中，STL它提供了一系列底部为红黑树结构的相关容器，在查询过程中可以达到效率 ，也就是说，在最差的情况下 红黑树的高度需要比较。当树上有很多节点时，查询效率并不理想。最好的查询是很少比较 数字可以找到元素，所以在C 11中，STL又提供了4个unordered与红黑相关的系列容器 树结构相关容器的使用方式基本相似，但其底层结构不同。本文仅适用于unordered_map和 unordered_set进行介绍，unordered_multimap和unordered_multiset用法可以类比multimap和multiset。

unordered_map

unordered_map的文档介绍

1. unordered_map是存储键值对的关联式容器，其允许通过keys快速索引与之对应 value。
2. 在unordered_map键值通常用于唯一的识别元素，而映射值是一个与此键相关的对象。 可能不同于映射值。
3. 在内部,unordered_map没有按照任何特定的顺序排序， 为了在常数范围内找到它key所 对应的value，unordered_map将相同哈希值的键放入相同的桶中。
4. unordered_map容器通过key比较访问单个元素map快，但在遍历元素子集的范围迭代中通常是有效的 较低。
5. unordered_maps实现了直接访问操作符(operator允许使用key直接访问参数value。
6. 它的迭代器至少是前向迭代器 （forward iterators）

unordered_set

在线文档说明

	//枚举数据状态
    enum status
	{
		EXIST,
		EMPTY,
		DILTE
	};

    //哈希每个数据状态
	template
	struct HashData
	{
		pair _kv;
		Status _status = EMPTY;
	};

    //哈希表结构
	template
	class HashTable
	{
	public:
	private:
		vector> _tables;
		size_t _n;//有效数据个数
	};

		bool Insert(const pair& kv)
		{
			size_t start = kv.first % _tables.size();
			size_t i = 0;
			size_t index = start;
			while (_tables[index]._status == EMPTY)//如果位置被占用
			{
				i++;
				//index = start + i;//线性探测
				index = start + i^i;//二次探测
				index %= _tables.size();//防止加之后的数大于表格长度，模一下，无论多大的值，都在这个表格内。
			}

			_tables[index]._kv = kv;
			_tables[index]._status = EXIST;
			++_n;
		}

		bool Insert(const pair& kv)
		{
			HashData* ret = Find(kv.first);
			if (ret)
			{
				return false;
			}

			if (_tables.size()==0 || _n * 10 / _tables.size() >= 7)
			{
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				HashTable newHT;
				newHT._tables.resize(newSize);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._status == EXIST)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
				_tables.swap(newHT._tables);
			}

			size_t start = kv.first % _tables.size();
			size_t i = 0;
			size_t index = start;
			while (_tables[index]._status != EMPTY)//如果位置被占用
			{
				i++;
				index = start + i;//线性探测
				//index = start + i^i;//二次探测
				index %= _tables.size();//防止加之后的数大于表格长度，模一下，无论多大的值，都在这个表格内。
			}

			_tables[index]._kv = kv;
			_tables[index]._status = EXIST;
			++_n;
			return true;
		}

		HashData* Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}

			size_t start = key%_tables.size();
			size_t i = 0;
			size_t index = start;
			while (_tables[index]._status != EMPTY)
			{
				if (_tables[index]._kv.first == key && _tables[index]._status==EXIST)
				{
					return &_tables[index];
				}

				++i;
				index = start + i;
				index %= _tables.size();
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			HashData* ret = Find(key);
			if (ret == nullptr)
			{
				return false;
			}
			else
			{
				ret->_status = DELETE;
                _n--;
				return true;
			}
		}

	struct HashStr
	{
		size_t operator()(const string& s)
		{
			size_t value = 0;
			for (auto& ch : s)
			{
				value += ch;
			}
			return value;
		}
	};

测试这个仿函数发现，可以得到字符串每个字符ascii每次相加对应的整数值，但是这样写还是有一点粗糙，就像上图，会出现不同的字符串，位置不一样，字符一样，相加是相同的值的请开给你。或者因为字符串是无限的，整数是有限的，在32位下，整数的大小一共是42亿byte，这样必然会造成整数值会重复，这种情况是无法避免的，所以为了解决这种情况，或者可以说将错误率减小，大佬们用了一个方法：字符串哈希算法

	template
	struct Hash
	{
		size_t operator()(const K& key)
		{
			return key;
		}
	};

void teset_unordered_set()
{
	unordered_set uss;
	uss.insert("srot");
}

	template
	struct Hash
	{
		size_t operator()(const K& key)
		{
			return key;
		}
	};

//上面的HashStr就不使用了。
//特化版本
	template<>
	struct Hash
	{
		size_t operator()(const string& s)
		{
			size_t value = 0;
			for (auto& ch : s)
			{
				value *= 31;
				value += ch;
			}
			return value;
		}
	};

所以对于这个仿函数，如果有一天，用一个自定义类型来做key，比如日期类Date,里面的成员函数由年月日，要对日期类进行除留余数法，那么它的仿函数就应该将年月日各个数字加起来，最后返回它的结果整数值。日期类必须配套一个对应的仿函数，具体怎么实现，要看自己，并不一定是我这种方法。

当key是一个自定义类型时，需要配置一个仿函数，将key转换成整型。

	struct Date
	{
        //...
		int _year;
		int _month;
		int _day;
	};

	struct HashDate
	{
		size_t operator()(const Date& d)
		{
			return d._day + d._month + d._year;
		}
	};
	void TestHashTable4()
	{
		HashTable htds;
	}

开散列

闭散列也叫开放定址法：不同位置冲突数据会相互影响，相邻位置的冲突会争抢位置，互相影响效率。

所以给出了一个优化思路：开散列，也叫做拉链发，或者叫做哈希桶。首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码 归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结 点存储在哈希表中。这样相邻位置冲突，不再争抢位置，不会互相影响。

当有10000个数据要存在哈希表中，哈希表长度只有100，平均一个桶要挂100个数据，这样造成了查找数据效率变低了，已经没有哈希的优势。所以我们通过控制负载因子，负载因子到了就扩容，这里我们让负载因子大小是1，也就是存储数据等于表长就扩容，这样最好的情况下，一个桶挂一个数据。如果几个数据的关键码都是一样的，也不至于一个桶挂很多数据，造成查找麻烦。还有一种，当一个桶的数据超过一定数后，在极端场景下，防止一个桶的位置冲突太多，链表太长，会将链表转成红黑树，这样的话，数据再多，查找效率也会从O(N)变成O(logN)(以2为底)。

在这里我们不用红黑树实现，因为是极端情况下，只需要知道就好。

基本结构

对于开散列的哈希表，它存放每个值都是通过链表所以我们给出节点的结构，成员变量包括每个节点的值，以及下一个节点的地址，也就是指针。

我们是用数组来存放写着哈希桶，那么哈希表HashLinkTable的成员变量中包括了一个vector数组和节点数据个数_n,这个数组的类型是指针类型，存放的都是每个桶链表最开始的地址。

我们主要实现的函数有插入，查找和删除，这样大框架就搭建好了。和闭散列类似。我将开散列和闭散列的函数都放到一个.h文件里，所以用namespace作用域的名称来区分这两种哈希表的实现。

namespace LinkHash
{
	template
	struct HashNode
	{
		HashNode* _next;
		pair _kv;

		HashNode(const pair& kv)
			:_next(nullptr)
			, _kv(kv)
		{}
	};

	template>
	class HashLinkTable
	{
		typedef LinkNode Node;
	public:
		bool Insert(const pair& kv)
		{}

		Node* Find(const K& key)
		{}

		bool Erase(const K& key)
		{}


	private:
		vector _tables;
		size_t _n=0;//记录表里面有多少有效数据
	};
}

插入的实现

插入的方法：让插入的键值对的first和哈希表大小进行取模，因为哈希桶要用链表链接，所以数组每个值放入的是链表头的地址。所以将新开辟好的，放入值的节点的地址放入到vector数组中。当遇到哈希冲突的值，新开辟节点后，我们使用头插，如果是尾插，还要找链表尾，很麻烦，因为哈希不需要注重顺序，所以直接在桶中头插就好。

头插就是先让新节点链接_tables[start]指向的旧桶的头节点地址，然后_tables[start]存放新插入节点的地址。

此时扩容的实现不能用闭散列的方法，扩容之后，写一个类的对象，复用Insert，这样代码虽然减少，但是每次插入都要开辟新的节点，这样很麻烦。我们开辟一个新数组，直接将链表节点的地址重新链接到新的数组中。

开散列需要注意的是，它的扩容条件也是通过负载因子（现有数据个数/哈希表大小），开散列的负载因子比为1，我们上面也提到过，是为了最好情况数组每个位置都存一个桶。所以当哈希表的大小是0，或者有效数据个数等于哈希表的大小的时候，我们就扩容。扩容的大小和闭散列的一样。如果表的大小是0，就开10个指针的空间，如果不是0，就开到原vector大小的2倍。（其实这里_tables.size()==0条件可以不写，因为_talbes.size()的大小是0的时候，有效数据_n也是0，二者相等）开好空间之后，我们让新定义的vector直接扩容到新空间大小。然后将原哈希表节点一个一个拷贝到新表中。

我们用cur来记录一个桶的位置，并用循环来遍历拷贝这个桶，因为会将cur地址直接拷贝到新表newTable中，形成新的链接关系，这样会找不到旧表_table中cur对应的下一个节点的地址。所以先用一个next变量来保存下一个地址，然后再对cur的地址进行新表链接。

最后遍历完一个桶，将一个桶的地址置空。遍历完所有的旧桶之后，将新的哈希表和旧的哈希表交换，这样出了作用域，会直接将旧哈希表地址释放。

这里还要注意，不可以插入重复的值，所以要用Find查找函数来遍历一下，当前插入的值是否已经存在，如果存在了，那么Find函数返回的是存在的值的地址，这样地址不为空，判断条件如果不为空，那么insert函数直接返回false，插入失败。如果Find找不到这个要插入的数据，说明表中还没有这个数，那么Find返回nullptr，进入不了if判断语句，直接执行下面的函数。

		bool Insert(const pair& kv)
		{
			Node* ret = Find(kv.first);
			if(ret)//存在返回false
				return false;

			HashFunc hf;
			//负载因子为1的时候扩容，最好的情况是数组每个值都能挂一个桶
			if (_tables.size() == 0 || _n == _tables.size())
			{
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				vector newTable;
				newTable.resize(newSize);
				HashFunc hf;
				for (size_t i = 0; i < _tables.size(); ++i)
				{
					Node* cur = _tables[i];//用一个cur来遍历桶
					while (cur)
					{
						Node* next = cur->_next;//保存cur的下一个节点，不然cur连接到新表找不到下一个值了

						size_t index = hf(cur->_kv.first) % newTable.size();
						cur->_next = newTable[index];
						newTable[index] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newTable);
			}

			size_t start = hf(kv.first) % _tables.size();
			Node* newnode = new Node(kv);
			//头插
			newnode->_next = _tables[start];
			_tables[start] = newnode;
			++_n;
			return true;
		}

查找

因为要对查找的数据，先进行取模找到对应的关键码位置，因为不知道查找数据类型，所以还是用仿函数封装一下，开散列的仿函数和闭散列的一样，这里就不再展示，直接将闭散列的仿函数拷贝到开散列作用域LinkHash当中。

因为要模哈希表大小，因为插入函数最开始表大小为0的时候，要先走Find函数，所以表的大小不能为0，不然程序会崩溃。用if条件句判断一下，如果是空，那么直接返回nullptr。

当拿到要查找数字的关键码，那么这个数一定在对应关键码的单链表中。所以还是使用一个cur指针变量来遍历这个桶，如果找到了，就返回找到节点的地址。如果没有找到继续向下遍历_next，cur走到空都没有找到的话，那么返回nullptr。

		Node* Find(const K& key)
		{
			if (_tables.empty())
				return nullptr;

			HashFunc hf;
			size_t index = hf(key) % _tables.size();
			Node* cur = _tables[index];
			while(cur)
			{
				if (cur->_kv.first == key)
					return cur;
				else
					cur = cur->_next;
			}
			return nullptr;
		}

删除

思路：找到要删除数据key的关键码，用一个cur指针变量来遍历当前关键码对应的桶，如果找到了，那么就删除数据，删除数据要将前一个位置和后一个位置链接，再释放删除的数据节点，所以要用一个变量prev来保存前一个位置。这里删除数据分两种情况：a.如果删除的是链表头的数据，说明它没有前一个位置，前一个位置是空，那么直接将数据放入删除数据的下一个数据，再释放节点，b.如果删除的是链表中间，直接让prev和next链接。然后删除节点。

删除节点之后，有效数据的个数也要减少。

		bool Erase(const K& key)
		{
			HashFunc hf;
			size_t index = hf(key) % _tables.size();
			Node* cur = _tables[index];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					//如果找到的要删除的数据是链表的头，说明它没有prev前一个节点，直接将vector的位置给上删除节点的下一个节点的地址
					if (prev == nullptr)//头删
					{
						_tables[index] = cur->_next;
					}
					//删除的数据不是链表的头，有prev前一个节点
					else//中间删除
					{
						prev->_next = cur->_next;
					}
					delete cur;
					--_n;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}

【面试题】：map/set的key和unordered_map/unordered_set的key有什么要求个区别？

map/set的key只需要比较大小，所以它们的仿函数模板参数有一个Compare用来比较对象数据的大小的。那么为什么必须有这个比较仿函数呢？最经典的距离，如果我们写自定义类型的时候，用日期类来做比较，如果传的是一个对象，里面比较的内容无法实现，需要用一个仿函数来实现，或者是日期类的指针Date*,此时比较的是地址的大小，并不是我们想要比较的内容，我们想要比较的是指针指向对象内容的大小，所以对于这种，比较完不是自己想要的，也需要写一个仿函数。

所以什么情况需要写仿函数？1.不支持比较的，需要自己写一个仿函数。2.支持比较的，但是比较的不是我们想要的，需要写一个仿函数。

那么unordered_map/unordered_set对key的要求：

1. 能支持取模或者支持转换成取模的无符号整数，比如string转size_t 和负数转无符号整数
2. 支持比较key大小的仿函数，因为哈希只需要比较相等还是不相等，所以只需要一个equal_to比较相等的仿函数即可，用来比较一些无法进行比较的类型，比如Date这种自定义类型。

Unordered_set/Unordered_set对哈希的封装

对于unordered_set和unordered_map封装HashLinkTable,我们需要改一下对应模板参数，来适用于map或key，这个和红黑树封装成map/set类似。因为在stl源码中unordered_map/unordered_set共用的是一套哈希底层源码，也就是说无论要插入的值是key还是pair，它们用的都是上面写的pair的类型。pair类型变成key类型，就要用到仿函数，也就是说HashLinkTable套了两层仿函数。

那么我们将上面的class V模板参数，变成class T，这样可以变换参数模板的类型为key或pair，用来适应map、set。那么class K还是要保留的，K是真正要求关键码的值，因为比如在查找函数的传参，需要查找的是key或pair的first，必须要传模板K的参数，这样才能查找。（STL源码也是这样用的）。

因为不知道是map还是set,节点存放数据的类型不再是pair，而是K类型的data。

封装代码框架：

set和map的成员函数是一个哈希表类型的，因为要对节点中数据进行取值，map中data类型是pair，要取pair的first；set的data类型是K，直接取到K类型就可以。所以写一个仿函数，在各自的封装.h文件中，获取各自的仿函数。set取K类型的数据，就是SetKeyOfT,map取pair的first，用到的是MapKeyOfT。

因为这个仿函数模板参数没有缺省值，而Hash模板参数有缺省值，缺省值是从右向左给的，所以对于KeyOfT这个模板参数，得放到Hash的左边。

可以看到，将HashLinkTable的模板参数类型由V改成T，set对T模板的应用是K类型，而map对T模板的应用是pair类型。

我们将HashLinkTable中Hash仿函数的缺省值给map/set中，因为在文档中也是这样体现的。但是Hash仿函数的位置不用改变，还是在HashTable.h这个底层文件的。如果map/set实例化想要使用这个仿函数，遇到string直接找到string的特化版本仿函数，遇到int这种内置类型直接找正常的class K版本即可。如果是一个自定义类型，那么不能使用缺省值的仿函数，必须自己实现一个。

//HashTable.h
namespace LinkHash
{
	template
	struct HashNode
	{
		HashNode* _next;
		T _data;

		HashNode(const T& data)
			:_data(data)
			,_next(nullptr)
		{}
	};

    template
	class HashLinkTable
	{
		typedef HashNode Node;
	};

//UnorderedSet.h
#pragma once
#include "HashTable.h"

namespace wjy
{
	template>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	private:
		LinkHash::HashLinkTable _ht;
	};
}

//UnorderedMap.h
#pragma once
#include "HashTable.h"

namespace wjy
{
	template>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair& kv)
			{
				return kv.first;
			}
		};
	private:
		LinkHash::HashLinkTable,MapKeyOfT，hash> _ht;
	};
}

所以HashLinkTable对应实现的一些成员函数也要改变。

因为map/set中的仿函数，取到的key值是用来比较大小的，所以如果用key取模，是不用添加KeyOfValue这个仿函数的。

Insert:

哈希表的迭代器

 我们平时使用迭代器像下面这样,我们需要实现begin().end()迭代器，++函数，!=函数等等。

auto it=ht.begin();
while(it!=ht.end())
{
    ++it;
}

那么迭代器struct类中迭代器里面的数据是什么？首先需要给一个节点的指针，通过指针遍历一个桶，当++的时候，cur=cur->_next，遍历到下一个节点。当一个桶走完，我们要走下一个桶，第一种方法是在迭代器结构体中，存一个当前桶对应的vector所对应的地址（不是桶的第一个节点地址，而是vector这个空间的地址），这样遍历下一个桶，让这个指针++即可，但是哈希表的底层是用vector封装的，里面的begin,end,endofstorage是私有的，我们拿不到。如果是自己写的vector还可以。第二种方式

 首先我们来实现解引用和箭头

【operator*和operator->】

解引用operator*,是将一个指针指向的内容取出来，它返回的是哈希节点的数据。operator->是将指针指向的地址取出来，也就是节点指向数据的地址。

因为对于这两个函数，有const和普通版本，如果单独写，需要写两个一摸一样的版本，所以为了减少代码冗余，我们使用模板。如果是当是指针类型，那么可以对这个指针类型传T*，const版本传cosnt T*。

	template
	struct __HTIterator
	{
		Ref operator*()
		{
			return _node->_data;
		}

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

	};

operator++前置++

如果这个桶没有走完，那么直接遍历当前迭代器指向节点的下一个节点。如果这个桶走完了，要遍历下一个位置，需要知道当前桶的关键码，并一直遍历这个数组vector，直到找到下一个不为空的数组。想要得到关键码，我们已经直到当前迭代器指向的数据，只要拿到该数组的大小即可，所以我们在迭代器类中增加一个HashLinkTable表的指针成员变量，有了HashLinkTable的指针，我们能够访问里面的_table数组，因为这个数组是私有的成员变量，所以将迭代器类变成HashLinkTable类的友元函数，这样就能直接访问。

因为要用当前节点的数据，不知道它是map还是pair，string还是int，所以定义一个KeyOfT和Hash。算出当前还没有++的节点的关键码之后，寻找下一个不为空的vector，在_tables.size()范围内，找到了这个不为空的vector，直接跳出循环，如果没有找到继续++。跳出循环有两种可能，第一：遍历完整个数组都没有找到不为空的vector，这样的话直接返回end迭代器，end迭代器就是一个空的迭代器。第二：上面的循环break出来的说明找到了不为空的位置，那么++之后指针变成找到位置index的内容，里面存放的是链表头的地址。最后返回*this，也就是_node指针。

因为end我们要在HashLinkTable中实现，我们还没有实现，所以将_node赋给一个空指针。

还要注意的一点，在迭代器__HTIterator我们引用了HashLinkTable，HashLinkTable也同样要使用__HTIterator迭代器类来构造begin和end，二者互相引用，所以造成在__HTIterator中找不到HashLinkTable（因为HashLinkTable写在__HTIterator下面）,所以我们将HashLinkTable放在__HTIterator上面声明一下。

//声明HashLinkTable
	template
	class HashLinkTable;

	template
	struct __HTIterator
	{
		typedef HashNode Node;
		typedef __HTIterator Self;//因为返回的迭代器类型名字太长，将它重定义名字。

		Node* _node;
		HashLinkTable* _pht;

		//构造迭代器--需要节点的指针 + 哈希表对象指针
		__HTIterator(Node* node, HashLinkTable* pht)
			:_node(node)
			, _pht(pht)
		{}

        Self& operator++()
		{
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else//这个桶没走完
			{
				KeyOfT kot;
				HashFunc hf;
				size_t index = hf(kot(_node->_data)) % _pht->_tables.size();//_next是空，但自己不为空
				//找下一个不为空的桶
				++index;
				while (index < _pht->_tables.size())
				{
					if (_pht->_tables[index])//当小于表的大小，不等于空就跳出循环，找到了
					{
						break;
					}
					else
						++index;
				}
				//如果表走完了，都没有找到下一个桶，直接返回end--空的迭代器
				if (index == _pht->_tables.size())
				{
					_node = nullptr;
				}
				else//找到了下一个节点，是上面循环break出来的
				{
					_node = _pht->_tables[index];
				}
			}
			return *this;
		}
	};

 迭代器的构造

这里迭代器的构造不仅要构造节点指针，还要构造哈希表对象的指针。

begin()和end()

begin就是找到_tables表的第一个不为空的桶的头节点，如果找到了，返回第一个位置的迭代器，因为迭代器的构造需要节点指针和哈希表的指针，那么哈希表的指针是什么呢？哈希表的指针就是this，this代表了整个哈希表的指针。将this指针传给迭代器的构造，那么我们就能取到_table。

如果表走完了全部是空的，没有数据存在，那么就返回end，空迭代器。

	template
	class HashLinkTable
	{
		typedef HashNode Node;
		template
		friend struct __HTIterator;
	public:
		typedef __HTIterator 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);
		}
    };

对于unordered_set对哈希表的封装，先封装我们已经写好的begin和end。因为要用到SetKeyOfT这个模板参数，所以将迭代器重定义名字写在struct SetKeyOfT下面。

因为unordered_set引用了还没有初始化的HashLinkTable中的iterator,iterator也是使用的位置的模板参数，所以为了在链接时候，为了防止找不到实体类，而引发的编译错误，我们在typedef成iterator中加一个typename，告诉这个语句，先保存对他的编译，等到实例化之后再进行编译。

unordered_map同理。

UnorderedSet.h:

namespace wjy
{
	template>
	class unordered_set
	{
	public:
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};

		typedef typename LinkHash::HashLinkTable::iterator iterator;

		iterator begin()
		{
			return _ht.begin();
		}

		iterator end()
		{
			return _ht.end();
		}
		bool insert(const K& key)
		{
			return _ht.Insert(key);
		}
	private:
		LinkHash::HashLinkTable _ht;
	};
}

UnorderedMap.h

namespace wjy
{
	template>
	class unordered_map
	{
	public:
		struct MapKeyOfT
		{
			const K& operator()(const pair& kv)
			{
				return kv.first;
			}
		};

		typedef typename LinkHash::HashLinkTable, MapKeyOfT, hash>::iterator iterator;

		iterator begin()
		{
			return _ht.begin();
		}

		iterator end()
		{
			return _ht.end();
		}

		bool insert(const pair& kv)
		{
			return _ht.Insert(kv);
		}
	private:
		LinkHash::HashLinkTable,MapKeyOfT,hash> _ht;
	};
}

operator!=

用一个对象的引用来比较

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

到现在写的这些内容，我们来测试一下：结果正确

 再来测试一下map:

operator[]

operator[]只有map中有，因为operator[]可以对插入的值进行增加，查找，修改，unordered_map和map是一样的。如果该值第一次出现，那么operator[]充当的是插入，下图可以看到当插入值时候，如果第一次出现，给到的是second值的缺省值,并且insert返回的pair，first返回的是插入的该值的迭代器指针，insert的返回值的second是一个bool类型，如果插入的pair值的first第一次插入，返回true。如果插入的键值对pair的first出现过了，那么insert返回的second是false。这时候就会直接对插入的键值对的second进行修改，因为要对插入值的second进行修改，所以会在同一个栈帧中，返回值要使用引用。

我们来看一下具体实现，因为返回值是pair键值对pair，所以HashLinkTable中的insert函数要改一下返回值。最开始Find检查是否已经插入该值，如果哈希表中存在该值，返回的该值的迭代器，和flase。所以Find函数的返回值也要改变一下，返回值类型是一个迭代器。

insert如果插入成功，返回插入值的迭代器和true，插入失败，返回存在的值的迭代器和false。

所以map和set中的insert返回值需要改成pair。

//HashLinkTable
        pair Insert(const T& data)
		{
			KeyOfT kot;
			iterator ret = Find(kot(data));
			if(ret!=end())//不等于end表示找到了
				return make_pair(ret,false);//返回迭代器和false的键值对，ret本身就是一个迭代器

			HashFunc hf;
			if (_tables.size() == 0 || _n == _tables.size())
			{
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				vector newTable;
				newTable.resize(newSize);
				HashFunc hf;
				for (size_t i = 0; i < _tables.size(); ++i)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;

						size_t index = hf(kot(cur->_data)) % newTable.size();
						cur->_next = newTable[index];
						newTable[index] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newTable);
			}

			size_t start = hf(kot(data)) % _tables.size();
			Node* newnode = new Node(data);
			//头插
			newnode->_next = _tables[start];
			_tables[start] = newnode;
			++_n;
			return make_pair(iterator(newnode,this),true);
		}

		iterator Find(const K& key)
		{
			if (_tables.empty())
				return end();//查找失败，返回nullptr迭代器，直接返回end()迭代器。

			HashFunc hf;
			KeyOfT kot;
			size_t index = hf(key) % _tables.size();
			Node* cur = _tables[index];
			while(cur)
			{
				if (kot(cur->_data) == key)
					return iterator(cur,this);
				else
					cur = cur->_next;
			}
			return end();
		}
//UnorderedMap
		pair insert(const pair& kv)
		{
			return _ht.Insert(kv);
		}

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

//UnorderedSet
		pair insert(const K& key)
		{
			return _ht.Insert(key);
		}

哈希表的拷贝构造和赋值重载和析构

拷贝构造

就是新开辟一块数组空间，将原数据一个一个拷贝到新数组中。但是这样导致每个桶中数据顺序改变，但是这样并不影响，顺序对哈希表来说，不重要。遍历旧数组，用一个节点指针cur来记录一个桶，用cur来遍历一个桶中每个数据，当遍历到一个节点，在新表中新建节点，将cur指向的旧数据构造出来。并进行头插链接。

写好拷贝构造之后，又有一个新问题，这样的话没有合适的默认构造函数。拷贝构造也是一种特殊的构造函数，有了自己写的拷贝构造，默认构造函数就会被覆盖，所以我们直接写一个不带参数的构造函数即可，内容不必我们实现，因为我们在成员函数中增加了_n的缺省值，如果没写这个缺省值，那么就需要我们显示写无参构造。

有的时候我们会遇到default这种写法的，也是生成一个默认构造函数。

		HashLinkTable()
		{}

		HashLinkTable(const HashLinkTable& ht)//拷贝构造给一个哈希表的对象
		{
			_tables.resize(ht._tables.size());
			for (size_t i = 0; i < ht._tables.size(); i++)
			{
				Node* cur = ht._tables[i];
				while (cur)
				{
					Node* copy = new Node(cur->_data);//用cur的数据构造新节点
					copy->_next = _tables[i];
					_tables[i] = copy;

                    cur=cur->_next;
				}
			}
			_n = ht._n;
		}

因为HashLinkTable这个类的参数太长了，我们将它typedef重命名一下。

拷贝构造是对没有存在的对象进行拷贝，赋值重载是对已经存在的对象进行拷贝。

赋值重载

，需要将原数据拷贝到新的栈帧中，最后返回这个新的栈帧的内容，这样的话需要先释放旧空间，开辟空间，然后一点一点拷贝，有点麻烦。我们还有一种方法，就是用一个中间栈帧tmp来拷贝构造旧数据，直接让存在的对象和tmp进行交换，最后释放tmp这个空间。这样节省了重新写一份拷贝的代码，并且tmp在出了operator=这个函数的作用域之后，自动释放，不用我们手动释放。

还有一个更简便的写法，因为需要中间值，比如t1=t2,t2需要传给形参，形参会建立栈帧，这样就不用写一个中间值，直接让this和形参进行交换，出了作用域会直接释放形参。

		typedef HashLinkTable Self;

		Self& operator=(Self copy)
		{
			swap(_n, copy._n);
			swap(_table, copy._table);
			return *this;
		}

析构

析构函数需要一个一个将节点释放，还是用一个节点指针找到不为空的vector对应桶的位置，释放节点之前记录当前节点的下一个节点，以免释放之后找不到。

		~HashLinkTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)//当遇到不是空的vector，遇到桶了，开始释放
				{
					Node* next = cur->_next;//记录下一个位置，以免释放找不到下一个了
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;//最后将vector也释放，因为还存着链表头节点地址。
			}
			_n = 0;
		}

我们在HashLinkTable中写了构造、拷贝构造，析构这些函数，在map/set中就不必实现，因为map/set中的成员变量是一个自定义类型，会去调自定义类型的构造、拷贝构造，析构。