改造哈希表，封装unordered_map和unordered_set

正文开始前给大家推荐个网站，前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。

unordered_map是存的是pair是K，V型的，而unordered_set是K型的，里面只存一个值，那我们如何利用一个数据结构将他们都封装出来呢？

我们知道哈希表我们实现的是存pair的，我们可以使用最笨的方法直接复制一份，把存pair的改为存Key的，但是我们可以参考一下大佬的做法，大佬直接把存的东西弄成一个模版参数，这个东西具体存的啥由用户来决定，用户传什么就存什么，所以改造后的哈希表的第二个类型模版参数就是我们要存的类型！

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

	HashNode(const T& data)
		: _data(data)
		, _next(nullptr)
	{}
};
template <class K, class V,class KeyOfT, class Hash = HashFunc<K>>
class HashTable
{
	typedef HashNode<V> Node;
private:
	KeyOfT kt;
	vector<Node*> _tables;
	size_t _n = 0;
	Hash hs;
};

我们可以看到V是什么类型，那么这个哈希表中存的就是什么，但是会有下一个问题，我们在取余时，不管是unordered_map还是unordered_set都是对Key取余，但是这里我们不知道他是Key还是pair，那怎么办呢？

我们可以通过仿函数解决这个问题，我们每个需要用Key计算的地方都走一层仿函数，然后unordered_set的就直接返回key就行，unordered_map则需要返回pair的first。我们会看到上面的结果多了个KeyOfT的模版，这个就是返回Key的仿函数。

unordered_map

template<class K, class V>
class unordered_map
{
	struct MapKOfT
	{
		const K& operator()(const pair<const K, V>& kv)
		{
			return kv.first;
		}
	};
	private:
	hash_bucket::HashTable<K, pair<K,V>,MapKOfT> _ht;
};

unordered_set

template<class K>
class unordered_set
{
	struct SetKOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
		private:
	hash_bucket::HashTable<K, K,SetKOfT> _ht;
};

至此我们最简单的框架就搭建出来了。需要注意的是所有需要用Key的地方都要走一层仿函数。
插入删除什么的直接复用哈希表的就可以，就下来主要就是实现迭代器。

迭代器

迭代器的结构应该是什么样子的？
节点的指针肯定是必须的，但是如果我们当前的桶走完了，如何++到下一个桶呢？
所以我们需要这张哈希表，用来找当前桶走完以后的下一个桶。这里不传这张哈希表也是可以的，因为我们的目的是找下一个桶，所以把哈希表中的vector传过来也是可以的。

那么迭代器如何++呢？

如果他的下一个节点是空，那么就说明这个桶走完了，我们需要找下一个桶，所以我们需要当前的位置，所以我们可以直接把当前桶的位置传过来，也可以当场计算桶的位置，这两种方法都是可以的，但是如果这张表走完了还没找到下一个桶，那就说明这张表走完了，我们直接把节点的指针改为nullptr即可。
如果它的下一个节点不为空，那直接让它等于它的next即可。

const的迭代器我们可以和之前一样，直接用两个模版参数来决定它是普通迭代器还是const迭代器。

template <class K, class V,class Ref, class Ptr, class KeyOfT, class Hash = HashFunc<K>>
struct __HTIterator
{
	typedef HashNode<V> Node;
	typedef __HTIterator<K, V,Ref,Ptr, KeyOfT, Hash> Self;

	Node* _node;
	const HashTable<K, V, KeyOfT, Hash>* _pht;
	size_t hashi;
	__HTIterator(Node* node,const HashTable<K, V, KeyOfT, Hash>* pht,size_t i)
		: _node(node)
		, _pht(pht)
		, hashi(i)
	{}


	Self operator++()
	{
		if (_node->_next)
		{
			_node = _node->_next;
		}
		else
		{
			++hashi;
			while (hashi < _pht->_tables.size())
			{
				if (_pht->_tables[hashi])
				{
					_node = _pht->_tables[hashi];
					break;
				}
				++hashi;
			}
			if (hashi == _pht->_tables.size())
			{
				_node = nullptr;
			}
		}

		return *this;
	}

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

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

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

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

但是这里会有一个相互依赖的问题，就是哈希表需要用迭代器，迭代器需要用哈希表，如果哈希表在前面我们就需要前置声明一下迭代器，迭代器同理，我们需要在前面声明一个哈希表，但是解决完这个问题以后还存在一个问题，就是哈希表中的vector是私有成员，迭代器不能直接访问，所以我们需要把迭代器声明为哈希表的友元。

把迭代器实现好以后，接下来就是解决Key不能修改的问题。
unordeted_set和unordeted_map如何实现Key不能修改呢？
我们通过观察原码会发现unordeted_set迭代器和const迭代器都是const迭代器，它是通过这样的方式来实现的。unordeted_map是Key不能修改而Value是可以修改的，所以它的pair是pair<const K,V>它把Key设置为const，这样就能够保证Key不能修改，Value可以修改。

接下来需要实现的是unordered_map的[]重载，要实现这个重载我们就需要对哈希表的插入进行修改，它的返回值不能再是一个bool值，而是一个pair，这个pair的first是iterator迭代器，second是bool类型代表是否插入成功。改造完以后，就可以实现[]重载，但是对应容器的插入的返回值也需要变一下，[]重载主要就是存在就插入不存在就不插入，但是都会返回Val的是可以别被我们修改。

当改造完插入以后，我们会发现unordered_set的插入编译编不过，这是因为unordered_set的迭代器都是const迭代器，而哈希表的插入返回的是普通的迭代器，这里的iterator无法转化为const_iterator，所以编译错误，有两种方式可以解决，我们可以支持const迭代器转化为普通迭代器，我们也可以直接用const中的东西来构造新的普通迭代器。此时我们的封装差不多就完善了。

改造后的哈希表

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

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

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

	template <class K, class V,class Ref, class Ptr, class KeyOfT, class Hash = HashFunc<K>>
	struct __HTIterator
	{
		typedef HashNode<V> Node;
		typedef __HTIterator<K, V,Ref,Ptr, KeyOfT, Hash> Self;

		Node* _node;
		const HashTable<K, V, KeyOfT, Hash>* _pht;
		size_t hashi;
		__HTIterator(Node* node,const HashTable<K, V, KeyOfT, Hash>* pht,size_t i)
			: _node(node)
			, _pht(pht)
			, hashi(i)
		{}


		Self operator++()
		{
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				++hashi;
				while (hashi < _pht->_tables.size())
				{
					if (_pht->_tables[hashi])
					{
						_node = _pht->_tables[hashi];
						break;
					}
					++hashi;
				}
				if (hashi == _pht->_tables.size())
				{
					_node = nullptr;
				}
			}

			return *this;
		}

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

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

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

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

	template <class K, class V,class KeyOfT, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<V> Node;

		template <class K, class V,class Ref, class Ptr, class KeyOfT, class Hash>
		friend struct __HTIterator;

	public:
		typedef __HTIterator<K, V, V&, V*, KeyOfT, Hash> iterator;
		typedef __HTIterator<K, V, const V&,const V*,KeyOfT, Hash> const_iterator;

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

		iterator end()
		{
			return iterator(nullptr, this, -1);
		}

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

		const_iterator end() const
		{
			return const_iterator(nullptr, this, -1);
		}
		HashTable()
		{
			_tables.resize(10);
		}

		~HashTable()
		{
			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;
			}
		}
		pair<iterator,bool> Insert(const V& data)
		{
			iterator ret = Find(kt(data));
			if (ret!=end())
			{
				return make_pair(ret,false);
			}

			if (_n == _tables.size())
			{
				//需要扩容
				vector<Node*> newtables;
				newtables.resize(2 * _tables.size());

				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t hashi = hs(kt(cur->_data))% newtables.size();
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}

				_tables.swap(newtables);
			}

			size_t hashi = hs(kt(data)) % _tables.size();
			Node* cur = new Node(data);
			cur->_next = _tables[hashi];
			_tables[hashi] = cur;
			_n++;
			return make_pair(iterator(cur,this,hashi), true);
		}

		//__HTIterator<K, V, V&, V*, KeyOfT, Hash>
		// __HTIterator<K, V,Ref,Ptr, KeyOfT, Hash>
		iterator Find(const K& k)
		{
			size_t hashi = hs(k) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kt(cur->_data) == k)
				{
					return iterator(cur,this,hashi);
				}

				cur = cur->_next;
			}

			return end();
		}

		bool Erase(const K& k)
		{
			size_t hashi = hs(k) % _tables.size();

			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == k)
				{
					if (prev==nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					return true;
				}
				cur = cur->_next;
			}

			return false;
		}
	private:
		KeyOfT kt;
		vector<Node*> _tables;
		size_t _n = 0;
		Hash hs;
	};
}

封装的unordered_map

template<class K, class V>
	class unordered_map
	{
		struct MapKOfT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKOfT>::iterator iterator;
		typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKOfT>::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:
		hash_bucket::HashTable<K, pair<const K,V>,MapKOfT> _ht;
	};

封装的unordered_set

template<class K>
class unordered_set
{
	struct SetKOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
public:
	typedef typename hash_bucket::HashTable<K, K, SetKOfT>::const_iterator iterator;
	typedef typename hash_bucket::HashTable<K, K, SetKOfT>::const_iterator const_iterator;

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

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

	pair<iterator, bool> insert(const K& key)
	{
		auto ret = _ht.Insert(key);
		return make_pair(iterator(ret.first._node, ret.first._pht,ret.first.hashi), ret.second);
	}

private:
	hash_bucket::HashTable<K, K,SetKOfT> _ht;
};