【C++】unordered_map，unordered_set模拟实现

喜欢的点赞，收藏，关注一下把！

上一篇文章我们把unordered_map和unordered_set底层哈希桶的知识也都说清楚了，今天就根据哈希桶模拟实现出unordered_map和unordered_set。

这里如果看过以前文章【C++】map和set的模拟实现，应该会觉得简单。

因为unordered_map和unordered_set底层都是哈希桶，因此我们只需要一个哈希桶就好了。所以哈希桶的代码我们做一下修改，让它能够同时满足unordered_map和unordered_set的需求。

unordered_map是KV模型，unordered_set是K模型，因此先把链表节点改一下，传个T，这个T既可以是KV，也可以是K。

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

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

插入这里也要改一下，因为find我们只要key，但是unordered_map是pair，我们要把key取出来，因此HashTable需要增加一个模板参数，这个模板参数分别由unordered_set、unordered_map传过来一个仿函数。作用是把key取出来

bool Insert(const T& data)
{
   
	KeyOfT kot;//不知道T是key还是pair
	if (Find(kot(data))//仿函数把key取出来
		return false;

	//负载因子控制在1,超过就扩容
	if (_n == _tables.size())
	{
   

		vector<Node*> newtable;
		//newtable.resize(_tables.size() * 2);
		newtable.resize(__stl_next_prime(_tables.size()));
		for (size_t i = 0; i < _tables.size(); ++i)
		{
   
			Node* cur = _tables[i];
			//头插到新表
			while (cur)
			{
   
				Node* next = cur->_next;
				size_t hashi = Hash()(kot(data)) % newtable.size();
				cur->_next = newtable[hashi];
				newtable[hashi] = cur;
				cur = next;
			}
			_tables[i] = nullptr;
		}
		_tables.swap(newtable);//旧表和新表交换一下
	}

	//匿名对象去调用仿函数,算在第几个桶里面
	int hashi = Hash()(kot(data)) % _tables.size();
	//头插
	Node* newnode = new Node(data);//调用Node的构造,因此Node写个构造
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;
	return true;
}

然后再说这个模板参数Hash的问题

可以看见keyOfT写在Hash后面，Hash报错了，因为它有缺省值keyOfT没有。当然你也可以把Hash放在keyOfT后面，但是这里的问题不是这个。因为Hash在HashTable不应该有缺省值，应该是由它的上层unordered_map和unordered_set传过去。为什么？

因为不见得你以后写一个vector< string >这样类似的自定义类型底层可以把它转成整数，还是要由调用的unordered_map和unordered_set人传一个能把这样类型转成整数的仿函数。所以把Hash的缺省值放在unordered_map和unordered_set的模板参数中。

下面我们把unordered_map和unordered_set模拟实现大框架搭建出来

//UnorderedMap.h
namespace wdl
{
   
	template<class K,class V,class Hash=HashFunc<K>>
	class unordered_map
	{
   
		struct MapKeyOfT
		{
   
			const K& operator()(const pair<const K, V>& kv)
			{
   
				return kv.first;
			}
		};
	public:

	private:
		//第二个参数决定是KV模型
		HashTable<K, pair<const K, V>, Hash, MapKeyOfT> _ht;
	};
}

//UnorderedSet.h
namespace wdl
{
   
	template<class K,class Hash = HashFunc<K>>
	class unordered_set
	{
   
		struct SetKeyOfT
		{
   
			const K& operator()(const K& key)
			{
   
				return key;
			}
		};
	public:

	private:
		//第二个参数决定是K模型
		HashTable<K, K, Hash, SetKeyOfT> _ht;
	};
}

插入

复用哈希桶的插入

//UnorderedMap.h
bool insert(const pair<K, V>& kv)
{
   
	return _ht.Insert(kv);
}

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

插入很简单，但注意到库里的插入返回的是pair，插入成功是返回指向这个节点的指针和true，插入失败也就是插入的是相同的值返回指向这个相同节点的指针和false

所以下面我们先实现迭代器在把插入完善

普通迭代器

思考这样一个问题，++怎么走，如何做到把一个桶走完了找到下一个桶？

可不可以把这些桶都链接起来？

这样遍历起来就方便了，找到第一个桶的第一个位置然后next往下走就像单链表一样遍历就走完了。如果查找的话给每个桶最后一个节点标记位这样也可以解决找别的桶去了的问题。
但是真正麻烦的是插入怎么办？

插入13，要找到上一个桶的最后一个节点连接起来，再找到下一个桶的第一个节点连接起来。

删除怎么办？

删除13，不还是要找到上一个桶最后一个节点和下一个桶第一个节点然后连接起来吗。

其实哈希桶的遍历也很简单，无非就是当前桶走完了找下一个桶，如果我们有这个表的话，当前桶走完遍历一下找到下一个桶不就好了吗。因此我们不仅要有这个节点的指针，还要有这个表。库里就是这样的实现方式。

通过哈希表的指针找到这张表。

template<class K, class T, class Hash, class KeyOfT>
class __HTIterator
{
   
	typedef HashNode<T> Node;
	typedef __HTIterator<K, T, Hash, KeyOfT> Self;
	Node* _node;//节点的指针

	Self& operator++()
	{
   
		if (_node->_next)
		{
   
			_node = _node->_next;//遍历当前桶的所有节点
		}
		else
		{
   
			//当前桶走完,要找下一个桶的第一个节点
			Hash hf;
			KeyOfT kot;
			size_t hashi = hf(kot(_node->_data)) % ;//计算当前在那个桶
		}
	}
};

要模表长，因此把表的指针传过去，当然也可以只把vector传过去。

template<class K, class T, class Hash, class KeyOfT>
class __HTIterator
{
   
	typedef HashNode<T> Node;
	typedef __HTIterator<K, T, Hash, KeyOfT> Self;
	typedef HashTable<K, T, Hash, KeyOfT> HT;
	Node* _node;//节点的指针
	HT* _ht;//哈希表的指针


	Self& operator++()
	{
   
		if (_node->_next)
		{
   
			_node = _node->_next;//遍历当前桶的所有节点
		}
		else
		{
   
			//当前桶走完,要找下一个桶的第一个节点
			Hash hf;
			KeyOfT kot;
			size_t hashi = hf(kot(_node->_data)) % _ht->_tables.size();//计算当前在那个桶
		}
	}
};

但是vector在HashTable可是私有成员。这里不能直接用。

因此在HashTable声明一下__HTIterator是HashTable的友元类就可以用HashTable私有成员

Self& operator++()
{
   
	//_node最开始指向第一个存数据桶的第一个节点
	if (_node->_next)
	{
   
		_node = _node->_next;//遍历当前桶的所有节点
	}
	else
	{
   
		//当前桶走完,要找下一个存数据桶的第一个节点
		Hash hf;
		KeyOfT kot;
		size_t hashi = hf(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;
}

接下来我们把剩下的都补充一下，

template<class K, class T, class Hash, class KeyOfT>
class __HTIterator
{
   
	typedef HashNode<T> Node;
	typedef __HTIterator<K, T, Hash, KeyOfT> Self;
	typedef HashTable<K, T, Hash, KeyOfT> HT;
	Node* _node;//节点的指针
	HT* _ht;//哈希表的指针
	
public:
	__HTIterator(Node* node,HT* ht)
		:_node(node)
		,_ht(ht)
	{
   }

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

	T* operator->()
	{
   
		return &_node->_data;
	}
	
	bool operator!=(const Self& s)
	{
   
		return _node != s._node;
	}

	Self& operator++()
	{
   
		//_node最开始指向第一个存数据桶的第一个节点
		if (_node->_next)
		{
   
			_node = _node->_next;//遍历当前桶的所有节点
		}
		else
		{
   
			//当前桶走完,要找下一个存数据桶的第一个节点
			Hash hf;
			KeyOfT kot;
			size_t hashi = hf(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;
	}
};

在把哈希桶的begin和end写一下。

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

	//友元类
	template<class K, class T, class Hash, class KeyOfT>
	friend class __HTIterator;
public:
	typedef __HTIterator<K, T, Hash, KeyOfT> iterator;
	
public:
	iterator begin()
	{
   
		//找第一个桶
		for (size_t i = 0; i < _tables.size(); ++i)
		{