冰冰学习笔记：哈希表与无序容器

欢迎各位大佬光临本文章！！！

还请各位大佬提出宝贵的意见，如发现文章错误请联系冰冰，冰冰一定会虚心接受，及时改正。

本系列文章为冰冰学习编程的学习笔记，如果对您也有帮助，还请各位大佬、帅哥、美女点点支持，您的每一分关心都是我坚持的动力。

我的博客地址：bingbing~bang的博客_CSDN博客https://blog.csdn.net/bingbing_bang?type=blog

我的gitee：冰冰棒 (bingbingsupercool) - Gitee.comhttps://gitee.com/bingbingsurercool

---

系列文章推荐

冰冰学习笔记：《平衡二叉搜索树》

冰冰学习笔记：《Linux的文件系统》

---

目录

系列文章推荐

前言

1.无序容器与有序容器的效率对比

2.无序容器的底层结构

2.1哈希冲突

2.2哈希函数

2.3哈希闭散列的实现

2.3.1线性探测

2.3.2二次探测

2.3.3闭散列的数据存储结构 

2.3.4闭散列的数据查找

2.3.5闭散列的数据插入 

2.3.6闭散列的数据删除 

2.4哈希开散列的实现

2.4.1开散列的数据存储形式

2.4.2开散列的查找

2.4.3开散列的插入

2.4.4开散列的删除

2.4.5开散列的性能分析

3.unordered_map和unordered_set的封装

3.1开散列哈希表的改造

3.2unordered_map和unordered_set的封装代码

总结

---

前言

        在C++11之前，基于哈希表实现的map和set并没有加入库中，库中只有使用红黑树实现的map和set。红黑树实现的容器查询效率可以达到log(N)，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个 unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，这四个底层实现的结构采用了哈希表，其查找效率平均上可以做到O(1)。

1.无序容器与有序容器的效率对比

        unordered_map和unordered_set都是采用哈希表实现的容器，其内部的函数与map和set一样。unordered系列容器也实现了迭代器，但是容器内部的数据如果采用迭代器遍历将不再是有序的。unordered系列容器的迭代器时单向迭代器，而map和set的迭代器是双向的。

        无序容器在插入大量数据时扩容的消耗比较大，map和set将占优势。但是在数据查找时，无序容器基本上能维持O(1)的效率，性能远远优于map和set。

unordered_set的无序性：

        下图为set和unordered_set两个容器在分别插入10000，100000，1000000，10000000无序数据和有序时进行的插入，查找，删除的性能测试，使用编译器为VS2019，均为32位，release版本。

        我们发现在无序数据的插入中，二者相差不大，删除中无序容器更胜一筹，查找相对稳定，都在常量级。 

        在大量有序数据的插入下，无序容器的效率开始降低，删除数据也不及有序容器。查找在测试结果来看基本上都在常数级，并没有太大的区别，那为什么会说无序的查找效率占优势呢？这就需要我们对哈希表的构造具备基本的了解。

2.无序容器的底层结构

        我们前面一直在说unordered_map等无序容器采用了哈希表结构，那什么是哈希表结构呢？在顺序结构和平衡树中，关键码和存储位置并没有对应的关系，因此在查找一个元素时，必须经过关键码的多次比对，像vector这种顺序容器，我们查找一个数据的时间复杂度需要O(N)，在平衡树中也需要log(N)的时间复杂度。

        如果我们能够构建一种关键码和存储位置一一对应的存储结构，那么在查找的时候就不需要比较，一次就能通过关键码找到对应的数据位置。基于这种思想，哈希表应运而生，在哈希表中，每个存储位置和关键码都由哈希函数一一映射。

        当我们插入数据时，会通过数据的关键码经过特定的转化函数的运算得到一一对应的数值，该数值就是哈希表中存储数据的位置，让后将数据放入哈希表中。

        当查找数据时，我们通过数据的关键码，经过特定的转化函数得到对应数据的存储位置，然后直接访问该数据的存储位置即可。

        这就是哈希散列的方法，此方法中使用的转化函数称为哈希散列函数，构造出来的结果称为哈希表（Hash Table）或者散列表。

2.1哈希冲突

        但是此种方式并非万全之策，我们理想状态下是一个关键码对应一个存储位置，但是有些数据的关键码有可能在经过哈希函数的转换后出现相同的情况，此时一个存储位置就会对应两个关键码，从而变成一对多的映射关系。

        我们将不同关键字通过相同哈希函数计算出相同的哈希地址的现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

        因此要想实现合理的哈希表，就必然需要合适的处理哈希冲突。

2.2哈希函数

        哈希函数的设计是否合理通常是引起哈希冲突的原因之一。因此哈希函数的设计具备下列规则：

（1）哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值 域必须在0到m-1之间

（2）哈希函数计算出来的地址能均匀分布在整个空间中

（3）哈希函数应该比较简单

通常情况下，我们使用下面的几种哈希函数：

（1）直接定址法

        取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

        优点：简单、均匀

        缺点：需要事先知道关键字的分布情况

        使用场景：适合查找比较小且连续的情况

（2）除留余数法

        设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除

        数， 按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

（3）平方取中法

        假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；

        再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地

        址。平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

（4）折叠法

        折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后

        将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。

（5）随机数法

        选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),

        其中 random为随机数函数。 通常应用于关键字长度不等时采用此法。

        哈希函数设计的越精妙，产生哈希冲突的可能性越小，但是哈希冲突是无法避免的。 

        通常情况下我们采用两种方式来解决哈希冲突，分别是闭散列和开散列。

2.3哈希闭散列的实现

        闭散列也叫开放定址法，当我们存储数据发生哈希冲突的时候，如果哈希表中没有满，我们就可以将key存储到冲突位置的"下一个"空位置。

        对于哈希表中"下一个"空位置的寻找需要有不同的探测方式，通常情况下我们采用线性探测或者二次探测。

2.3.1线性探测

        线性探测就是从冲突发生的位置一个接一个的向后进行查找，直到找到没有存储数据的空位置，然后将冲突的数据放入此位置。例如在下面的表中，我们存储44时，按照除留余数法计算的存储位置位4，但是该位置已经存储了数据4，就需要一直向后探测，直到找到下标8指向的空位置，然后将数据存储下来。当我们查找数据时，会先通过哈希函数计算得到下标4的位置，然后进行比对，如果是查找的数据就返回，不是就继续向后探测，直到找到数据为止。

        在进行数据删除时，我们不能直接将表中的数据进行删除，如果直接删除元素，有可能影响到其他元素的查找，例如在上表中，我们将4删除，此时下标为4的存储位置就为空，当我们查找44元素的时候，根据关键码的计算会直接找到下标为4的位置，此时发现位置为空，会直接返回数据不存在，但实际上44存在表中，只是为了解决冲突被我们放到关键码的后面的位置。因此我们采用标记位进行伪删除的方式进行删除。

2.3.2二次探测

        二次探测也是一种闭散列处理冲突的方式，与线性探测类似，二次探测也是在哈希表中寻找未存储的数据位置，然后将数据进行插入，只是寻找的方式不再是逐次查找。线性探测的缺点是如果在存储数据的冲突过多时，会将大量的数据堆叠在一起，将一些元素的存储位置相互占用，这就使得查找插入的效率越来越低，原本并不冲突的数据由于上一次插入的数据发生冲突占用了此数据的位置，将导致该数据发生冲突，只能去占用其他数据的位置。

        二次探测虽然也是占用别人的位置，但是并不是紧接着占用，而是利用平方计算的方式，找到距离关键码很远的位置进行存放。当第一次进来插入数据时，如果原有位置被占用，将去探测关键码位置后面的第 i^2 个位置（i初始为0，每次循环后加1），当发现还是有数据存在时，将继续进行循环，探测的位置将指数级向后增加。

        使用二次探测存储数据时将避免大量的数据集中分布，就会间接避免连续冲突的可能。

2.3.3闭散列的数据存储结构 

        为了实现伪删除状态，我们在进行了枚举状态值，并且在每个哈希表的数据存储区域引用状态信息。哈希表的底层采用线性表vector进行实现，并记录存储数据的个数_n。哈希表含有三个模板参数，分别是关键字K，存储数据类型V，以及将关键字转换成无符号整形的仿函数。由于存储数据的关键字可以为任意类型，当数据类型为string或者字符类型时将不能直接进行取模运算，这就需要我们自己进行仿函数的传递。

	enum State
	{
		EMPTY,
		EXIST,
		DELETE
	};
    //数据节点
	template<class K, class V>
	struct HashNode
	{
		State _st = EMPTY;//状态值
		pair _data;//存储的键值对
	};
	template<class K,class V ,class Hash = HashFunc>
    class HashTable//哈希表结构
	{
		typedef HashNode Node;
    public :
        //.....功能函数
	private:
		vector _tables;
		size_t _n = 0;//存储数据个数
	};

        实际运用中，string类型会经常作为关键字类型进行插入，因此我们就直接使用模板的特化进行了实现， 这里转换为无符号整型并没有直接使用ASCII值进行累加，而是采用了大佬的写法。

        一些大佬为了研究将字符串转为整形值的最优方案，提出了很多方式，最著名的就是BKD算法，此算法将最大限度的减少不同关键字转化为整型的相同概率。

    template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
	template<>
	struct HashFunc
	{
		size_t operator()(const string& key)
		{
			int val = 0;
			for (auto e:key)
			{
				val *= 131;//BKDR
				val += e;
			}
			return val;
		}
	};

        当然还有其他大佬提出的算法，这里不在一一赘述，可前往此网页进行阅读： 各种字符串Hash函数 - clq - 博客园 (cnblogs.com)

2.3.4闭散列的数据查找

        在使用线性探测或者二次探测对数据进行存储前，通常需要使用Find函数来进行查找，如果数据存在就不需要插入，不存在再进行插入操作。

        查找算法比较简单，我们使用仿函数获取关键字的无符号整型值，然后通过哈希函数（这里为取模操作，对整个哈希表的size进行取模）获得对应的存储位置，然后进行对比，如果状态为EMPTY，则直接返回nullptr，如果存储位置的元素的关键字与查找的关键字相同，那就找到直接返回该存储位置的指针，如果没找到那我们就需要探测是否是因为出现冲突而放在了其他位置。

        如果采用线性探测，则直接逐步向后查找，当遇到查找元素时则返回节点指针，当遇到节点状态为EMPTY，或者查找一圈返回开始查找的位置时则查找结束，返回nullptr。

        如果是二次探测方式进行的存储，我们则需要计算每次存储的位置进行查找，而不能单纯的使用单步查找方式，因为有可能先遇到状态为EMPTY的节点而终止查找，返回错误信息。

        当状态为EMPTY时才会停止查找，状态为EXIST的DELETE都需要继续查找比对关键字。 

        Node* Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}
			Hash comp;
			size_t hashi = comp(key) % _tables.size();
			size_t start = hashi;
			
			//二次探测查找方式
			//int i = 1;
			//while (_tables[hashi]._st != EMPTY)
			//{
			//	if (_tables[hashi]._st != DELETE
			//		&& _tables[hashi]._data.first == key)
			//	{
			//		return &_tables[hashi];
			//	}
			//	hashi=start+i*i;
            //  i++;
			//	hashi %= _tables.size();
			//	if (hashi == start)//回到起点，说明找了一圈
			//		break;
			//}
			//线性探测方式查找
			while (_tables[hashi]._st != EMPTY)
			{
				if (_tables[hashi]._st != DELETE
					&& _tables[hashi]._data.first == key)
				{
					return &_tables[hashi];
				}
				hashi++;
				hashi %= _tables.size();
				if (hashi == start)//回到起点，说明找了一圈
					break;
			}
			return nullptr;
		}

2.3.5闭散列的数据插入 

        哈希表中也不能存储多余的值，哈希表中已有的值是不能继续插入的。哈希表的插入与查找类似，我们需要先计算出关键字对应的哈希表中的下标，然后判断该位置是否已有元素，如果元素存在则采用线性探测或者二次探测得出表中新位置进行数据插入，当位置状态为DELETE和EMPTY时，表明数据可以插入，然后将插入节点的状态改为EXIST，数据个数_n++。

        数据的插入必然会考虑到扩容，那么什么时机进行扩容将影响哈希表的效率。因此在哈希表的实现时，我们通常会设定一个载荷因子：α=填入表的数据个数 / 散列表的长度。 

        闭散列的哈希表不能在表满的时候才进行扩容，通常情况下当负载因子到达0.7左右时，哈希表就需要扩容，当负载因子过大时，查找效率将会降低。

        扩容的实际操作比较简单，无非是将底层结构的vector进行扩容，将其扩大到新的容量，然后将旧表中的数据拷贝到新表中。但是我们要切记，旧表中的数据不能单纯的直接拷贝到新表中，我们需要按照哈希表插入的方式将数据插入的新表中。因为原本在旧表中冲突的数据在新表扩容后就可能不冲突了！所以我们不用单独的扩大vector，而是直接创建一个新的哈希表，并直接复用哈希表的插入操作将数据进行插入，然后交换新表和旧表。

 实现代码：

		bool Insert(const pair& kv)
		{
			if (Find(kv.first))
				return false;
			if (_tables.size() == 0 || 10 * _n / _tables.size() >= 7)
				//首次进来和超过平衡因子需要扩容
			{
				size_t NewSize = _tables.size() == 0 ? 10 : 2 * _tables.size();
				HashTable NewHT;
				NewHT._tables.resize(NewSize);
				for (auto& e : _tables)
				{
					if (e._st == EXIST)
						NewHT.Insert(e._data);
				}
				_tables.swap(NewHT._tables);
			}
			Hash comp;//取出K进行取模
			//线性探测
			size_t hashi = comp(kv.first) % _tables.size();
			while (_tables[hashi]._st == EXIST)
			{
				hashi++;
				hashi %= _tables.size();
			}
			//二次探测
			/*size_t start = comp(kv.first) % _tables.size();
			size_t hashi = start;
			size_t i=1;
			while (_tables[hashi]._st == EXIST)
			{
				i++;
				hashi = start + i*i;
				hashi %= _tables.size();
			}*/
			_tables[hashi]._data = kv;
			_tables[hashi]._st = EXIST;
			_n++;
            return true;
		}

2.3.6闭散列的数据删除 

        由于是闭散列，删除操作不需要将数据删除，只需要修改数据状态即可，先使用查找找到对应数据的位置，然后更改状态。

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

2.4哈希开散列的实现

        闭散列无论怎么实现，当发生冲突时，终归是在一个容器中相互占用元素位置，因此哈希表基本实现都是采用开散列的方式。

        开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地 址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

        也就是说，开散列解决哈希冲突不在采用相互占用的方式，而是将每个元素都变成一个节点，表中存储节点的地址，当发生冲突的时候，将节点挂在冲突位置的下面。

2.4.1开散列的数据存储形式

        由于开散列中数据不在相互占用，因此我们不用在进行数据状态的标注，当元素插入时需要将节点指针放入哈希表中，发生冲突的节点链接在节点后面，相当于单链表的头插，删除节点只需要进行单链表的删除操作即可。

        因此，哈希表中存储的是每个数据的节点指针，节点中则为具体的数据类型，和指向下一个节点的指针。

namespace open_hash//开散列
{
	template<class K, class V>
	struct HashNode
	{
		pair _data;
		HashNode* _next;
		HashNode(const pair& data)
			:_data(data)
			, _next(nullptr)
		{}
 
	};
    template<class K, class V, class Hash = HashFunc>
	class HashTable
	{
		typedef HashNode Node;
	public:
          //数据操作
	private:
		vector _tables;
		size_t _n = 0;
    }
 
}

2.4.2开散列的查找

        由于开散列中存储的是数据的节点，每个节点都是开辟出来的，因此拷贝构造，析构等函数需要自己将节点释放，这里不在赘述，可参考链表的析构和拷贝。

        开散列的查找依旧需要计算哈希值，将计算出来的哈希值映射的哈希表的位置找到，此时我们找到的并不是一个元素，而是有可能存储多个元素的链表的头节点的指针，如果当前位置为空指针，则说明表中并没有此元素，直接返回false即可。

        当节点指针不为空的时候，我们就需要遍历这个单链表，此时就变成了单链表的查找方式。

Node* Find(const K& key)
{
	if (_tables.size() == 0)
		return nullptr;
	Hash comp;
	size_t hashi = comp(key) % _tables.size();
	Node* cur = _tables[hashi];
	while (cur)
	{
		if (cur->_data.first == key)
		{
			return cur;
		}
		cur = cur->_next;
	}
	return nullptr;
}

2.4.3开散列的插入

        开散列插入数据之前要先确保数据不存在，因此我们需要先调用查找函数，当没有找到该数据的时候在进行插入。

        插入操作需要先计算哈希值，然后通过哈希值找到位置，最后使用单链表头插的形式将节点插入到表中。

        当数据到达一定范围的时候我们就需要扩容，可是什么时候进行扩容呢？如果扩容不及时，那么表中的单链表的节点就会变得很长，甚至查找元素时退化成一个单链表的结构，变为O(N)的时间复杂度。如果频繁扩容将会带来大量的消耗，原因在于此时的扩容不能单纯的扩大存储节点指针的vector的容量，我们还需要将旧表中的原节点链接到新的表中。

        通常扩容的条件是当插入数据个数与哈希表的大小相同时进行扩容操作（此时哈希表不一定是满的）。扩容的大小变为原表的二倍是可以的，但是最优的情况是变为一个素数，库中就引用的素数表进行扩容的容量，这样就会每次计算哈希值的时候取的是一个素数，会减少冲突的数量。

        将旧表中的节点重新连入的时候也需要计算哈希值，新表扩容后，旧表中每个单链表的长度都有可能减少。

//素数表
inline size_t __stl_next_prime(size_t n)
{
	static const size_t __stl_num_primes = 28;
	static const size_t __stl_prime_list[__stl_num_primes] =
	{
		53, 97, 193, 389, 769,
		1543, 3079, 6151, 12289, 24593,
		49157, 98317, 196613, 393241, 786433,
		1572869, 3145739, 6291469, 12582917, 25165843,
		50331653, 100663319, 201326611, 402653189, 805306457,
		1610612741, 3221225473, 4294967291
	};
 
	for (size_t i = 0; i < __stl_num_primes; ++i)
	{
		if (__stl_prime_list[i] > n)
		{
			return __stl_prime_list[i];
		}
	}
 
	return -1;
}
bool Insert(const pair& data)
{
	//去重
	if (Find(data.first))
	{
		return false;
	}
	Hash comp;
	//扩容
	//if (_tables.size() == 0 || _n == _tables.size())
	if (_n == _tables.size())
	{
		//size_t NewSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
		vector NewTables;
		size_t NewSize = __stl_next_prime(_tables.size());
		NewTables.resize(NewSize, nullptr);
		for (size_t i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;
				size_t hashi = comp(cur->_data.first) % NewSize;
				cur->_next = NewTables[hashi];
				NewTables[hashi] = cur;
				cur = next;
			}
			_tables[i] = nullptr;
		}
		_tables.swap(NewTables);
	}
	size_t hashi = comp(data.first) % _tables.size();
	//头插节点
	Node* NewNode = new Node(data);
	NewNode->_next = _tables[hashi];
	_tables[hashi] = NewNode;
	_n++;
	return true;
}

2.4.4开散列的删除

        开散列的删除函数就是单链表的删除函数的变形，在删除之前，我们先计算哈希值找到需要删除的节点处于的单链表的位置，然后判断删除节点是否为链表头节点，如果是，则将头节点的next变为哈希表中的值，如果不是头节点，则进行链表的删除操作。

bool Erase(const K& key)
{
	if (_tables.size() == 0)
		return false;
	Hash comp;
	size_t hashi = comp(key) % _tables.size();
	Node* cur = _tables[hashi];
	Node* pre = nullptr;
	while (cur)
	{
		if (cur->_data.first == key)
		{
			if (pre == nullptr)
			{
				//头删
				_tables[hashi] = cur->_next;
			}
			else
			{
				//非头删
				pre->_next = cur->_next;
			}
			delete cur;
			--_n;
			return true;
		}
		pre = cur;
		cur = cur->_next;
	}
	return false;
}

2.4.5开散列的性能分析

        开散列性能究竟好不好呢？有些人会有很多疑问，说开散列存储的是一个一个的节点指针，溢出是需要进行链表的头插操作，开销会不会增大呢？如果插入元素一直发生冲突会不会出现退化成单链表的情况呢？

        实际上开散列并没有占用太大的空间，只要我们的扩容实际控制的好，单链表不会过长，更何况单链表可以挂在表中，难道树结构不能挂吗？我们可以进行验证：

        我们插入10000000，19000000，25000000个数据，然后看表中每个桶的大小，桶的个数以及最长桶的长度，并且计算出平均每个桶的长度，并算出负载因子（数据个数/桶的个数）

        再插入大量数据后我们发现，当表中数据与表的长度接近相同时桶的最大长度才为2，平常情况下都是为长度为1的桶 。因此哈希表的查找效率接近O(1)。哈希桶在插入大量数据的时候会引发扩容，扩容的操作会降低效率，我们可以在插入数据之前进行主动扩容，降低扩容的消耗。

开散列的实现代码：哈希表，闭散列，开散列的实现 · 366ec3c · 冰冰棒/C++ - Gitee.com

3.unordered_map和unordered_set的封装

3.1开散列哈希表的改造

        与树结构的map和set一样，在封装之前需要对我们的哈希表进行改造，改造内容一样，就是让我们的哈希表中的节点的数据类型不再是pair类型，而是泛型，让上层提供存储类型。并且上层的map和set需要显示提供获得key的仿函数，哈希表进行存储时的key均由仿函数从数据类型得到。插入函数需要返回由迭代器和布尔类型组成的键值对，查找函数返回迭代器。

        哈希表需要提供迭代器来让上层进行封装，哈希表中的迭代器由节点指针和哈希表本身构成，迭代器只提供了单向的递增操作。迭代器的递增是先走当前所在的桶，当桶中元素走完后，访问后面最近的有元素的桶。

        因此迭代器的构造就需要两个指针，一个是当前节点的指针，用来访问当前桶的内容，当桶中还有元素，即节点指针的next存在时，直接返回当前节点的next。当指针不存在，我们就需要重新计算当前节点数据所在哈希表的位置，然后向后遍历寻找第一个有数据的桶，并返回节点指针。

    struct __HashIterator
	{
		using Node = HashNode;
		using  HT = HashTable;
		using Self = __HashIterator;
 
		Node* _node;
		HT* _hash;
 
		__HashIterator(Node* node, HT* hash)
			:_node(node)
			, _hash(hash)
		{}
 
		Ref operator* ()
		{
			return _node->_data;
		}
		Ptr operator->()
		{
			return &_node->_data;
		}
		Self& operator++()
		{
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				Hash comp;
				KeyOfT koft;
				size_t hashi = comp(koft(_node->_data)) % _hash->_tables.size();
				hashi++;//向后先移动
				while (hashi < _hash->_tables.size() && _hash->_tables[hashi] == nullptr)
				{
					hashi++;
				}
				if (hashi == _hash->_tables.size())//走到结尾，说明没有含有数据的桶
					_node = nullptr;
				else
					_node = _hash->_tables[hashi];
			}
			return *this;
		}
		Self operator++(int)
		{
			Self tmp=*this;
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				Hash comp;
				KeyOfT koft;
				size_t hashi = comp(koft(_node->_data)) % _hash->_tables.size();
				hashi++;//向后先移动
				while (hashi < _hash->_tables.size() && _hash->_tables[hashi] == nullptr)
				{
					hashi++;
				}
				if (hashi == _hash->_tables.size())//走到结尾，说明没有含有数据的桶
					_node = nullptr;
				else
					_node = _hash->_tables[hashi];
			}
			return tmp;
		}
		bool operator == (const Self& s)const
		{
			return _node == s._node;
		}
		bool operator != (const Self& s)const
		{
			return _node != s._node;
		}
	};

3.2unordered_map和unordered_set的封装代码

        map和set的封装就是对哈希表中的函数进行调用，显示传递给适合map或者set的模板参数。具体代码如下：unordered_map,unorder_set的封装 · 1dca16c · 冰冰棒/C++ - Gitee.com

总结

        红黑树和哈希表实现的map和set的使用方式基本相同，无序容器的迭代器遍历没有顺序，红黑树实现的是按照升序遍历的。无序容器的查找效率接近O(1)，但是频繁扩容会影响效率。无序容器的迭代器是单向的，只支持自增操作。

        这里要注意，哈希实现的set或者map与红黑树实现的set或者map的模板类型K具备不同的要求，红黑树实现的容器需要支持小于比较，或者显示提供比较的仿函数，而对于哈希实现的容器则需要K类型对象可以转换整形比较，或者提供整形比较的仿函数，还需要K类型对象支持等于比较或者提供等于比较的仿函数。