哈希封装unordered_map和unordered_set的模拟实现

（一）认识unordered_map和unordered_set

unordered_map和unordered_set这两个容器是C++11之后才更新的。unordered_map的底层复用了哈希表来实现key/value的结构，而unordered_set的底层也是复用了哈希表，但实现的是key的结构。这两个容器的使用其实跟map和set的使用是一致的，只是map和set的底层复用的是红黑树，unordered_set和unordered_map这两个容器的使用如下代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

int main()
{
	//unordered_map
	unordered_map<int, int> myunmap = { {4,4},{2,2},{8,8},{11,11},{2,2} };
	for (auto& e : myunmap)
	{
		cout << e.first  << ":" << e.second << endl;
	}
	//unordered_set
	unordered_set<int> myunset = { 3,4,2,1,7,0,5,6,9,8,3,3 };
	for (auto& e : myunset)
	{
		cout << e << " ";
	}
	cout << endl << endl;

	//map
	map<int, int> mymap = { {4,4},{2,2},{8,8},{11,11},{2,2} };
	for (auto& e : mymap)
	{
		cout << e.first << ":" << e.second << endl;
	}
	//set
	set<int> myset = { 3,4,2,1,7,0,5,6,9,8,3,3 };
	for (auto& e : myset)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

打印结果：

从代码和打印结果来看，unordered_map和unordered_set这两个容器跟map、set一样都支持initializer_list初始化，但是从打印结果来看，unordered_map和unordered_set支持去重+不排序，而map和set支持去重+排序，这就是它们底层复用的封装不同所导致的，map和set的底层是红黑树，迭代器在遍历时走中序遍历，所以打印出来的数据是有序的，而unordered_map和unordered_set底层是哈希表，哈希表是通过哈希桶来将值一个个存储进去的，迭代器遍历时是遍历一个个哈希桶，所以底层复用的不同，实现出来的效果也略有不同，但是这几个容器的使用方式完全是类似的。

（二）模拟实现unordered_map和unordered_set

2.1 实现出复用哈希表的框架

• 首先我们得知道，哈希表既能被unordered_map复用又能被unordered_set复用，而unordered_map的数据结构是pair<key,value>，而unordered_set的数据结构就是一个key，由于这两个容器的存储的数据结构不同，所以哈希表在实现时应该使用泛型参数T来接收unordered_map和unordered_set传过来的数据结构的类型，才能实例化出不同的哈希表，提供给这两个容器使用
• 哈希表在实现时还需要使用一个K参数来接收unordered_map和unordered_set的关键字，因为这两个容器的find/erase等一些接口都是通过关键字来实现的。unordered_set传给泛型T的就是关键字，但还是需要再传一遍，就是为了要与unordered_map保持兼容，unordered_map传给泛型T的是一堆pair值，实现find/erase等接口时就不方便，所以为了保持兼容，哈希表在实现时还需要使用一个K参数来接收unordered_map和unordered_set的关键字
• 因为哈希表实现了泛型T，不知道传过来的数据是k，还是pair<k,v>，那么insert内部进行插入时要用k对象转换成整型取模和比较相等，因为pair的value不参与计算取模，且默认支持的是key和value一起比较相等，所以在任何时候只需要比较k对象，那么我们就需要在unordered_map和unordered_set层分别实现一个MapOfKey和SetOfKey的仿函数来传给哈希表中的KeyOfT，然后在哈希表中通过KeyOfT仿函数取出T类型对象中的k对象，再转换成整型取模和k比较相等

代码实现如下：
步骤1：实现哈希表

#pragma once
#include <iostream>
#include <vector>
using namespace std;

//将关键字转成可以取模，如string本身取不了模，利用ASCII码值即可，用仿函数实现
template<class K>
class HashFunc
{
public:
	//全部转成无符号的整型，这样才能取模
	const size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
//使用库里面的unordered_map和unordered_set时，我们不用给string的取模进行仿函数的实现，因为库里面为string的仿函数进行了特化
template<>
class HashFunc<string>
{
public:

	size_t operator()(const string& str)
	{
		size_t ret = 0;
		for (auto& s : str)
		{
			ret += s;
			ret *= 131;
		}
		return ret;
	}
};

namespace li //模拟实现时防止与库里面的冲突，用了命名空间
{
	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
	{
		typedef HashNode<T> Node;
	public:
		inline unsigned long _stl_next_prime(unsigned long n)
		{
			static const int _stl_num_primes = 28;
			static const unsigned long _stl_primes_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
			};
			const unsigned long* first = _stl_primes_list;
			const unsigned long* last = _stl_primes_list + _stl_num_primes;
			const unsigned long* pos = lower_bound(first, last, n);
			//lower_bound()在迭代器的范围内取>=n的最小值
			return pos == last ? *(pos - 1) : *(pos);
		}
		HashTable()
		{
			//提前开好第一个质数大小的空间
			_tables.resize(_stl_next_prime(1),nullptr);
		}
		~HashTable()
		{
			for (int i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
			_tables[i] = nullptr;
			}
		}
		bool insert(const T& data)
		{
			Hash hs;
			KeyOfT kot;
			if(find(kot(data)))
				return false;
			//负载因子为1就扩容
			if (_n == _tables.size())
			{
				unsigned long newsize = _stl_next_prime(_tables.size() + 1);

				vector<Node*> newtables(newsize, nullptr);
				for (int i = 0; i < _tables.size(); i++)
				{
					//遍历旧表，将数据挪到新表
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t hashi = hs(kot(cur->_data)) % newtables.size();
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newtables);
			}

			//算出key在哈希表中映射的存储空间
			size_t hashi = hs(kot(data)) % _tables.size();
			//头插
			Node* cur = new Node(data);
			cur->_next = _tables[hashi];
			_tables[hashi] = cur;
			++_n;
			return true;
		}

		bool find(const K& key)
		{
			Hash hs;
			KeyOfT kot;
			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (hs(kot(cur->_data)) == hs(key))
				{
					return true;
				}
				cur = cur->_next;
			}
			return false;
		}

		bool erase(const K& key)
		{
			Hash hs;
			KeyOfT kot;
			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (hs(kot(cur->_data)) == hs(key))
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					--_n;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}

	private:
		vector<Node*> _tables;
		size_t _n = 0;
	};
}

步骤2：封装unordered_map和unordered_set的框架，解决获取关键字(KeyOfT)的问题

//unordered_map.h
#pragma once
#include "HashTable.h"
namespace Unordered_map
{
	template<class K, class V,class Hash = HashFunc<K>>
	class unordered_map
	{
		struct MapOfKey
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		bool insert(const pair<K, V>& kv)
		{
			return _hash.insert(kv);
		}
		bool find(const K& key)
		{
			return _hash.find(key);
		}
		bool erase(const K& key)
		{
			return _hash.erase(key);
		}
	private:
		li::HashTable<K, pair<const K, V>,MapOfKey,Hash> _hash;
	};
}

//unordered_set.h
#pragma once
#include "HashTable.h"
namespace Unordered_set
{
	template<class K,class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetOfKey
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		bool insert(const K& key)
		{
			return _hash.insert(key);
		}
		bool find(const K& key)
		{
			return _hash.find(key);
		}
		bool erase(const K& key)
		{
			return _hash.erase(key);
		}
	private:
		li::HashTable<K,const K,SetOfKey,Hash> _hash;
	};
}

2.2 迭代器iterator的实现思路分析

• iterator的实现就是用一个类型去封装结点的哈希结点的指针，再通过重载运算符实现迭代器像指针一样访问的行为，这里哈希表的迭代器是一个单项迭代器
• 重载运算符中，operator++如何实现呢，iterator中有一个结点的指针，该指针指向哈希桶里的一个结点，若桶下面还有结点，则将迭代器指向下一个结点即可。若桶的下面没有结点，则需要找到哈希桶，为了能找到下一个桶，我们需要在迭代器中增加一个哈希表指针，让该指针指向哈希表，这样的话若当前桶走完了，要找到下一个桶就方便了，直接用key值计算出当前桶的位置，依次往后找不为空的桶即可，若往后找到的桶都为空，遍历到哈希尾，就可返回一个nullptr

代码如下：
步骤1：实现哈希表的迭代器，重载运算符

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

template<class K, class T, class KeyOfT, class Hash>
struct HashTableIterator
{
	typedef HashNode<T> Node;
	typedef HashTable<K, T, KeyOfT, Hash> ht;
	typedef HashTableIterator<K, T, KeyOfT, Hash> Self;

	Node* _node; //结点的指针
	const ht* _ht; //哈希表指针

	HashTableIterator(Node* node,const ht* ht)
		:_node(node)
		,_ht(ht)
	{ }

	T& operator*()
	{
		return _node->_data;
	}
	T* operator->()
	{
		return &_node->_data;
	}
	Self operator++()
	{
		if (_node->_next)
		{
			//说明桶的下面还有结点
			_node = _node->_next;
		}
		else
		{
			KeyOfT kot;
			Hash hs;
			size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();
			hashi++;
			//找下一个不为空的桶
			while (hashi < _ht->_tables.size())
			{
				if (_ht->_tables[hashi])
				{
					_node = _ht->_tables[hashi];
					break;
				}
				else
				{
					hashi++;
				}
			}
			if (hashi == _ht->_tables.size())
			{
				//没有不为空的桶
				_node = nullptr;
			}
		}
		return *this;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
	bool operator==(const Self& s)
	{
		return _node == s._node;
	}
};

步骤2：begin()返回第一个桶中第一个结点指针构造的迭代器，end()返回的迭代器可以用空来表示

template<class K,class T,class KeyOfT,class Hash>
class HashTable
{
	typedef HashNode<T> Node;

	template<class K, class T, class KeyOfT, class Hash>
	friend struct HashTableIterator; //友元声明，方便迭代器访问哈希表中的私有成员

public:
	typedef HashTableIterator<K, T, KeyOfT, Hash> Iterator;
	Iterator Begin()
	{
		for (int i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			if (cur)
			{
				return Iterator(cur, this);
			}
		}
		return End();
	}
	Iterator End()
	{
		return Iterator(nullptr, this);
	}
};

上面两个步骤实现的迭代器是可以修改的，我们知道unordered_map和unordered_set的关键字是不可以被修改的，所以我们需要把unordered_set的第二个模板参数改成const K，unordered_map的第二个模板参数改成pair<const K,V>，代码如下：

步骤3：封装哈希迭代器实现unordered_map和unordered_set的迭代器

//unordered_map.h
template<class K, class V,class Hash = HashFunc<K>>
class unordered_map
{
public:
	typedef typename li::HashTable<K, pair<const K, V>, MapOfKey, Hash>::Iterator iterator;
	iterator begin()
	{
		return _hash.Begin();
	}
	iterator end()
	{
		return _hash.End();
	}
private:
	li::HashTable<K, pair<const K, V>,MapOfKey,Hash> _hash;
};

//unordered_set.h
template<class K,class Hash = HashFunc<K>>
class unordered_set
{
public:
	typedef typename li::HashTable<K,const K, SetOfKey, Hash>::Iterator iterator;
	iterator begin()
	{
		return _hash.Begin();
	}
	iterator end()
	{
		return _hash.End();
	}
private:
	li::HashTable<K,const K,SetOfKey,Hash> _hash;
};

li::HashTable<K, pair<const K, V>,MapOfKey,Hash> _hash; //unordered_map
li::HashTable<K,const K,SetOfKey,Hash> _hash; // unordered_set

步骤4：实现const迭代器
增加迭代器的模板参数

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
{
	typedef HashNode<T> Node;
	typedef HashTable<K, T, KeyOfT, Hash> ht;
	typedef HashTableIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;

	Node* _node; //结点的指针
	const ht* _ht; //哈希表指针

	HashTableIterator(Node* node,const ht* ht)
		:_node(node)
		,_ht(ht)
	{ }

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

步骤5：实现const Begin()和const End()

template<class K,class T,class KeyOfT,class Hash>
class HashTable
{
	typedef HashNode<T> Node;

	template<class K, class T, class KeyOfT, class Hash>
	friend struct HashTableIterator; //友元声明，方便迭代器访问哈希表中的私有成员

public:
	typedef HashTableIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
	typedef HashTableIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;
	ConstIterator Begin() const
	{
		for (int i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			if (cur)
			{
				return ConstIterator(cur, this);
			}
		}
		return End();
	}
	ConstIterator End() const
	{
		return ConstIterator(nullptr, this);
	}
};

步骤6：封装哈希const_iterator实现unordered_map和unordered_set的const_iterator

//unordered_map.h
template<class K, class V,class Hash = HashFunc<K>>
class unordered_map
{
public:
	typedef typename li::HashTable<K, pair<const K, V>, MapOfKey, Hash>::ConstIterator const_iterator;
	const_iterator begin() const
	{
		return _hash.Begin();
	}
	const_iterator end() const
	{
		return _hash.End();
	}
private:
	li::HashTable<K, pair<const K, V>,MapOfKey,Hash> _hash;
};

//unordered_set.h
template<class K,class Hash = HashFunc<K>>
class unordered_set
{
public:
	typedef typename li::HashTable<K,const K, SetOfKey, Hash>::ConstIterator const_iterator;
	const_iterator begin() const
	{
		return _hash.Begin();
	}
	const_iterator end() const
	{
		return _hash.End();
	}
private:
	li::HashTable<K,const K,SetOfKey,Hash> _hash;
};

2.3 unordered_map支持[]

unordered_map要支持[]主要需要修改insert返回值支持，修改HashTable中insert的返回值为pair<Iterator,bool> insert(const T& data)，有了insert支持unordered_map的[]就很好实现了

代码如下：

pair<Iterator,bool> insert(const T& data)
{
	Hash hs;
	KeyOfT kot;
	Iterator it = find(kot(data)); //find函数的返回值也要进行修改，修改成Iterator
	if (it != End())
		return { it,false };

	//负载因子为1就扩容
	if (_n == _tables.size())
	{
		unsigned long newsize = _stl_next_prime(_tables.size() + 1);

		vector<Node*> newtables(newsize, nullptr);
		for (int i = 0; i < _tables.size(); i++)
		{
			//遍历旧表，将数据挪到新表
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;
				size_t hashi = hs(kot(cur->_data)) % newtables.size();
				cur->_next = newtables[hashi];
				newtables[hashi] = cur;
				cur = next;
			}
			_tables[i] = nullptr;
		}
		_tables.swap(newtables);
	}

//unordered_map.h
V& operator[](const K& key)
{
	pair<iterator, bool> ret = _hash.insert(make_pair(key, V()));
	return ret.first->second;
}

既然哈希表中的inser的返回值修改了，那么对应的unordered_map和unordered_set的insert函数的返回值也要进行修改

（三）结束语

用哈希表来模拟实现这两个容器，就得先学习底层的哈希表，不了解哈希表的友友可以看我的上一篇文章https://blog.csdn.net/muzi_liii/article/details/147519118?spm=1001.2014.3001.5501。该模拟实现简易的unordered_map和unordered_set就完成了。一起学习吧！