unordered_map和unordered_set实现(底层封装哈希表)

个人主页：Lei宝啊 

愿所有美好如期而遇

前言

在看这篇文章前，建议先了解哈希表的实现：哈希表模拟实现

如果说你对哈希表的实现很清楚，那么可以直接往下看，但是本篇文章对unordered_map和unordered_set的封装使用的哈希表是哈希表模拟实现的一种更改。

我们会指出哪里做了更改以及为什么做更改，但是上篇文章提起过的这里不会再提及。

这里贴出哈希表代码：

//开散列哈希表
namespace Open
{
 
	template<class K, class V>
	struct HashNode
	{
		HashNode<K, V>* next;
		pair<K, V> _kv;
 
		HashNode(const pair<K, V>& kv)
			:next(nullptr)
			,_kv(kv)
		{}
	};
 
	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable;
 
	template<class K, class V, class Hash = HashFunc<K>>
	class HashIterator
	{
		typedef HashNode<K, V> Node;
		typedef HashTable<K, V, Hash> hstable;
		typedef HashIterator<K, V, Hash> iterator;
 
	public:
 
		HashIterator(Node* n, hstable* h)
			:node(n)
			,hst(h)
		{}
 
		iterator& operator++()
		{
			if (node->next)
			{
				node = node->next;
				
			}
			else
			{
				Hash hs;
				int pos = hs(node->_kv.first) % hst->_table.size();
 
				pos++;
 
				while (pos < hst->_table.size())
				{
					if (hst->_table[pos])
					{
						node = hst->_table[pos];
						break;
					}
 
					pos++;
				}
 
				if (pos == hst->_table.size())
					node = nullptr;
			}	
 
			return *this;
		}
 
		pair<K, V>& operator*()
		{
			return node->_kv;
		}	
 
		bool operator!=(const iterator& s)
		{
			return node != s.node;
		}
 
	private:
		Node* node;
		hstable* hst;
	};
 
	template<class K, class V, class Hash>
	class HashTable
	{
 
		template<class K, class V, class Hash>
		friend class HashIterator;
 
	public:
		typedef HashIterator<K, V, Hash> iterator;
		typedef HashNode<K, V> Node;
		
		iterator begin()
		{
			for (auto& e : _table)
			{
				if (e)
				{
					return iterator(e, this);
				}
			}
 
			return end();
		}
 
		iterator end()
		{
			return iterator(nullptr, this);
		}
 
		HashTable()
		{
			_table.resize(10);
		}
 
		Node* Find(const K& key)
		{
			Hash hs;
			int pos = hs(key) % _table.size();
 
			Node* cur = _table[pos];
			while (cur)
			{
				if (cur->_kv.first == key)
					return cur;
 
				cur = cur->next;
			}
 
			return nullptr;
		}
 
		~HashTable()
		{
			for (auto& e : _table)
			{
				Node* cur = e;
				while (cur)
				{
					Node* next = cur->next;
					delete cur;
 
					cur = next;
				}
 
				e = nullptr;
			}
		}
 
		bool insert(const pair<K, V>& kv)
		{
			
			if (Find(kv.first))
				return false;
 
			Hash hs;
 
			if (_table.size() == _size)
			{
				vector<Node*> newtable;
				newtable.resize(_table.size() * 2);
 
				for (auto e : _table)
				{
					Node* cur = e;
					Node* next;
 
					while (cur)
					{
						int pos = hs(cur->_kv.first) % newtable.size();
						next = cur->next;
 
						cur->next = newtable[pos];
						newtable[pos] = cur;
 
						cur = next;
					}				
				}
 
				_table.swap(newtable);
			}
		
			int pos = hs(kv.first) % _table.size();
 
			Node* cur = _table[pos];
			Node* newnode = new Node(kv);
 
			newnode->next = _table[pos];
			_table[pos] = newnode;
 
			_size++;
			return true;
		}
 
		bool Erase(const K& key)
		{		
			Hash hs;
			int pos = hs(key) % _table.size();
 
			Node* prev = nullptr;
			Node* cur = _table[pos];
 
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev)
					{
						prev->next = cur->next;
					}
					else
					{
						_table[pos] = nullptr;
					}
 
					delete cur;
					--_size;
 
					return true;
				}
 
				prev = cur;
				cur = cur->next;
			}	
 
			return false;
		}
 
	private:
		vector<Node*> _table;
		size_t _size = 0;
	};
}

为封装而基于哈希表做的更改

首先是模板参数，我们改为T，因为将来这个哈希表我们不仅仅unordered_map要封装，unordered_set也要使用，所以T可以是key，也可以是pair<K,V>

	template<class T>
	struct HashNode
	{
		HashNode<T>* next;
		T _data;
 
		HashNode(const T& data)
			:next(nullptr)
			,_data(data)
		{}
	};

再一个就是HashTable和HashIterator模板参数的更改，多出了KeyOfT这个仿函数，这个是为了提取节点的key值，因为我们不知道节点是pair还是key，所以需要这样一个仿函数。

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

再一个修改就是Find和insert的返回值，我们改为了pair<iterator,bool>

iterator Find(const K& key)

pair<iterator,bool> insert(const T& data)

 其他没有什么大的修改，都是基于上面修改连锁带来的修改，我们下面贴出修改后的代码。

//开散列哈希表
namespace Open
{
 
	template<class T>
	struct HashNode
	{
		HashNode<T>* next;
		T _data;
 
		HashNode(const T& data)
			:next(nullptr)
			,_data(data)
		{}
	};
 
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable;
 
	template<class K, class T, class KeyOfT, class Hash>
	class HashIterator
	{
		typedef HashNode<T> Node;
		typedef HashTable<K, T, KeyOfT, Hash> hstable;
		typedef HashIterator<K, T, KeyOfT, Hash> iterator;
 
	public:
 
		HashIterator(Node* n, hstable* h)
			:node(n)
			, hst(h)
		{}
 
		iterator& operator++()
		{
			if (node->next)
			{
				node = node->next;
			}
			else
			{
				KeyOfT kot;
				Hash hs;
				int pos = hs(kot(node->_data)) % hst->_table.size();
 
				pos++;
 
				while (pos < hst->_table.size())
				{
					if (hst->_table[pos])
					{
						node = hst->_table[pos];
						break;
					}
 
					pos++;
				}
 
				if (pos == hst->_table.size())
					node = nullptr;
			}
 
			return *this;
		}
 
		T& operator*()
		{
			return node->_data;
		}
 
		bool operator!=(const iterator& s)
		{
			return node != s.node;
		}
 
	private:
		Node* node;
		hstable* hst;
	};
 
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable
	{
 
		template<class K, class T, class KeyOfT, class Hash>
		friend class HashIterator;
 
	public:
		typedef HashIterator<K, T, KeyOfT, Hash> iterator;
		typedef HashNode<T> Node;
 
		iterator begin()
		{
			for (auto& e : _table)
			{
				if (e)
				{
					return iterator(e, this);
				}
			}
 
			return end();
		}
 
		iterator end()
		{
			return iterator(nullptr, this);
		}
 
		HashTable()
		{
			_table.resize(10);
		}
 
		iterator Find(const K& key)
		{
			KeyOfT kot;
			Hash hs;
			int pos = hs(key) % _table.size();
 
			Node* cur = _table[pos];
			while (cur)
			{
				if (kot(cur->_data) == key)
					return iterator(cur, this);
 
				cur = cur->next;
			}
 
			return iterator(nullptr, this);
		}
 
		~HashTable()
		{
			for (auto& e : _table)
			{
				Node* cur = e;
				while (cur)
				{
					Node* next = cur->next;
					delete cur;
 
					cur = next;
				}
 
				e = nullptr;
			}
		}
 
		pair<iterator,bool> insert(const T& data)
		{
			KeyOfT kot;
 
			iterator it = Find(kot(data));
			if (it != end())
				return make_pair(it, false);
 
			Hash hs;
 
			if (_table.size() == _size)
			{
				vector<Node*> newtable;
				newtable.resize(_table.size() * 2);
 
				for (auto e : _table)
				{
					Node* cur = e;
					Node* next;
 
					while (cur)
					{
						int pos = hs(kot(cur->_data)) % newtable.size();
						next = cur->next;
 
						cur->next = newtable[pos];
						newtable[pos] = cur;
 
						cur = next;
					}
				}
 
				_table.swap(newtable);
			}
 
			int pos = hs(kot(data)) % _table.size();
 
			Node* cur = _table[pos];
			Node* newnode = new Node(data);
 
			newnode->next = _table[pos];
			_table[pos] = newnode;
 
			_size++;
			return  make_pair(iterator(newnode, this), true);
		}
 
		bool Erase(const K& key)
		{
			KeyOfT kot;
			Hash hs;
			int pos = hs(kot(key)) % _table.size();
 
			Node* prev = nullptr;
			Node* cur = _table[pos];
 
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev)
					{
						prev->next = cur->next;
					}
					else
					{
						_table[pos] = nullptr;
					}
 
					delete cur;
					--_size;
 
					return true;
				}
 
				prev = cur;
				cur = cur->next;
			}
 
			return false;
		}
 
	private:
		vector<Node*> _table;
		size_t _size = 0;
	};
}