【C++篇】STL的关联容器：unordered_map和unordered_set（下篇）：用一个哈希表同时封装unordered_map和unordered_set

我想吃余

发布于 2025-08-21 08:45:21

2160

文章被收录于专栏：C语言学习C语言学习

前言

在不久前我们实现了：用一颗红黑树同时封装map和set。【C++篇】STL的关联容器：map和set（下篇）：用一颗红黑树同时封装出map和set 本文与其知识点大致相同，建议先学习上述文章，然后用本文强化练习和查漏补缺。

一、哈希表源码

本文被用于封装的哈希表：

template<class K, class V>
struct HashData
{
	pair<K, V> _kv;
	HashData<K, V>* _next;

	HashData(const pair<K, V>& kv)
		:_kv(kv)
		,_next(nullptr)
	{ }
};

template<class K, class V, class Hashfunc = DefaultHashfunc<K>>
class HashTable
{
	typedef HashData<K, V> Node;
public:
	//构造
	HashTable()
	{
		_table.resize(10, nullptr);
	}

	//拷贝构造
	HashTable(const HashTable<K, V, Hashfunc>& ht)
		: _table(ht._table.size(), nullptr)
		, _n(ht._n)
	{
		for (size_t i = 0; i < ht._table.size(); ++i)
		{
			Node* cur = ht._table[i];
			Node* tail = nullptr;
			while (cur)
			{
				Node* newNode = new Node(cur->_data);
				if (!_table[i])
				{
					_table[i] = newNode;
				}
				else
				{
					tail->_next = newNode;
				}
				tail = newNode;
				cur = cur->_next;
			}
		}
	}

	//赋值重载
	HashTable<K, V, Hashfunc>& operator=(const HashTable<K, V, Hashfunc>& ht)
	{
		_table = ht._table;
		_n = ht._n;
		return *this;
	}

	//析构
	~HashTable()
	{
		for (int i = 0; i < _table.size(); ++i)
		{
			Node* cur = _table[i];
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}

			_table[i] = nullptr;
		}
	}

	bool insert(const pair<K, V>& kv)
	{
		if (find(kv.first))
			return false;

		Hashfunc hf;
		//当负载因子对于1时，扩容
		if (_n / _table.size() == 1)
		{
			size_t NewSize = _table.size() * 2;
			HashTable<K, V> NewTable;
			NewTable._table.resize(NewSize, nullptr);

			//遍历旧表，将旧表上的节点迁到新表上（避免节点创建释放操作）
			for (int i = 0; i < _table.size(); ++i)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;
					int hashi = hf(cur->_kv.first) % NewTable._table.size();
					cur->_next = NewTable._table[hashi];
					NewTable._table[hashi] = cur;

					cur = next;
				}
			}
			_table.swap(NewTable._table);
		}
		
		Node* NewData = new Node(kv);
		int hashi = hf(kv.first) % _table.size();
		NewData->_next = _table[hashi];
		_table[hashi] = NewData;
		++_n;

		return true;
	}

	Node* find(const K& key)
	{
		Hashfunc hf;
		int hashi = hf(key) % _table.size();
		Node* cur = _table[hashi];
		while (cur)
		{
			if (cur->_kv.first == key)
				return cur;
			cur = cur->_next;
		}

		return nullptr;
	}

	bool erase(const K& key)
	{
		Hashfunc hf;
		int hashi = hf(key) % _table.size();
		Node* dele = _table[hashi];
		Node* prev = nullptr;
		while (dele)
		{
			if (dele->_kv.first == key)
			{
				if (prev)
					prev->_next = dele->_next;
				else
					_table[hashi] = dele->_next;

				delete dele;
				return true;
			}
			prev = dele;
			dele = dele->_next;
		}
		
		return false;
	}
private:
	vector<Node*> _table;
	size_t _n = 0;
};

二、控制哈希表的模板参数

如何使得一颗KV模型的哈希表可以同时适配K和KV模型呢？

我们控制unordered_map和unordered_set传入底层哈希表的模板参数，为了与原哈希表的模板参数进行区分，我们将哈希表第二个模板参数的名字改为T，意为通用参数。

template<class K, class T, class Hashfunc>
class HashTable

对于unordered_set：

template<class K>
class unordered_set
{
public:
	//...
private:
	BRTree<K, K> _t;
};

对于unordered_map：

template<class K, class V>
class unordered_map
{
public:
	//...
private:
	BRTree<K, pair<K, V>> _t;
};

哈希表节点类也需要更改：对于模板参数，我们只需T即可，并没有任何用到K的地方。成员我们依次更改一下类型即可：

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

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

三、提取Key，仿函数的添加

在哈希表的find、insert等的接口中，需要对T类型的数据进行比较操作。对于set来说，没啥问题；但对于map，其类型为pair<K, V>，pair的比较运算符的重载并不符合我们的要求，需要利用仿函数来手动解决。

目标仿函数功能：提取出pair<Key，Val>中的Key 设置哈希表仿函数模板参数为KeyOfT：

template<class K, class T, class KeyOfT, class Hashfunc>
class HashTable

在unordered_map中：

template<class K, class V>
class unordered_map
{
	//作为内部类
	//提取key
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv)
		{
			return kv.first;
		}
	};
public:
	//...
private:
	BRTree<K, pair<K, V>, MapKeyOfT> _t;

虽然对于·unordered_set·无需这般操作，但红黑树必须添加这个模板参数，·unordered_set·也只能无奈“陪跑”了

template<class K>
	//仿函数提取key
	struct SetKeyOfT
	{
		const K& operator()(const K& Key)
		{
			return Key;
		}
	};
class unordered_set
{
public:
	//...
private:
	BRTree<K, K, SetKeyOfT> _t;
};

四、普通迭代器的实现

在哈希表中，迭代器必然封装的是桶的节点指针，因此节点指针就是我们迭代器的成员。

在operator++时，在桶内部访问下一个节点容易，直接next即可；但这个桶走完了，需要访问下一个桶的头结点时，该如何访问呢？

因此，operator++()需要用到哈希表来查找非空桶。我们不妨再添加其对应的哈希表指针作为迭代器成员，方便operator++()使用。

template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hashfunc>
struct HashIterator
{
	typedef HashNode<T> Node;
	typedef HashIterator<K, T, Ptr, Ref, KeyOfT, Hashfunc> Self;

	Node* _node;//桶的节点指针
	HashTable<K, T, KeyOfT, Hashfunc>* _pht;//其对应的哈希表指针
};

operator++实现

具体逻辑：

如果下一个节点不为空，访问_node->next
如果下一个节点为空，从后一个桶开始，寻找不为空的桶

Self& operator++()
{
	Hashfunc hf;
	KeyOfT kot;
	//若下一个节点不为空，访问next
	if (_node->_next)
	{
		_node = _node->_next;
	}
	else//下一个节点为空，从后一个桶开始，寻找不为空的桶
	{
		size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
		++hashi;
		while (hashi < _pht->_table.size())
		{
			if (_pht->_table[hashi])
			{
				_node = _pht->_table[hashi];
				return *this;
			}
			else
			{
				++hashi;
			}
		}

		_node = nullptr;
	}
	return *this;
}

其余接口比较简单，详见后文源码。

依赖类问题

因为HashIterator需要使用到HashTable类，但编译器编译HashIterator时，尚未编译到HashTable，会导致报错。 HashIterator和HashTable互相利用，互为依赖类

解决方案： 前置声明

//前置声明：因为HashIterator需要使用HashTable类，但编译器尚未编译到HashTable，会报错，因此需要声明。
//HashIterator和HashTable互相利用，互为依赖类
template<class K, class T, class KeyOfT, class Hashfunc>
class HashTable;

template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hashfunc>
struct HashIterator
{
	//…………
};

添加友元

HashIterator在operator++()接口中需要访问HashTable的private成员，因此需要让HashIterator成为HashTable的友元。

注意：声明模板友元，需加上template

template<class K, class T, class KeyOfT, class Hashfunc = DefaultHashfunc<K>>
class HashTable
{
	typedef HashNode<T> Node;

	//友元声明：HashIterator需要访问HashTable的private成员
	//声明模板友元，需加上template
	template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hashfunc>
	friend struct HashIterator;

	//…………
};

最后在哈希表、unordered_map、unordered_set中实现iterator的begin（）、end（）接口

五、const迭代器实现

将哈希表传入迭代器的T*、T&参数用const修饰

typedef HashIterator<K, T, const T*, const T&, KeyOfT, Hashfunc> const_iterator;

然后最后在哈希表、unordered_map、unordered_set中实现const_iterator的begin（）、end（）接口

六、设置Key值不可修改

我们知道，unordered_map和unordered_set中的Key是不可修改的，如何做到呢？

对于unordered_set，我们使用“障眼法”（记住这个障眼法，后文要考）：

typedef typename HashTable<K, K, SetKeyOfT>::const_Iterator iterator;
typedef typename HashTable<K, K, SetKeyOfT>::const_Iterator const_iterator;

对于unordered_map，我们巧妙地将传入底层红黑树的pair<K, V>改为pair<const K, V>，方可实现Key值无法修改。

七、修改insert的返回值、operator[]的实现

我们知道，operator[]的本质是插入，它是调用insert的接口实现的，且insert的返回值被设置为pair<iterator, bool>。

修改insert返回值非常简单，我们将原本的返回值和当前插入节点的迭代器make_pair即可。

然后我们修改unordered_map和unordered_set的insert接口：对于unordered_map，直接修改insert返回值即可

pair<iterator, bool> insert(const pair<K, V>& kv)
{
	return _t._Insert(kv);
}

然而对于unordered_set，如果和unordered_map一样处理的话，是会报错的，为什么呢？

//错误写法
pair<iterator, bool> insert(const K& key)
{
	return _t._Insert(key);
}

还记得我们之前使用的妙计“障眼法”吗？没错，我们现在要来付出代价了🤣 在unordered_set中，iterator是“假“”的，它本质上是const_iterator，而我们insert返回值中的iterator是“货真价实”的iterator。

错误点：用pair<const_iterator, bool>类型作为返回值类型去返回pair<iterator, bool>类型的值。

别看它们长得像，它们可是两个不同的类型！

【解决方案】用一个pair<iterator, bool>类型的变量ret去接收insert的返回值，然后再用iterator去构造成const_iterator，再返回。

pair<iterator, bool> insert(const K& key)
{
	pair<typename HashTable<K, K, KeyOfSet>::iterator, bool> ret = _ht.Insert(key);
	return pair<iterator, bool>(ret.first, ret.second);
}

还没完，我们的迭代器还不支持用普通迭代器去构造const迭代器，我们需要去写一个构造函数：

HashIterator(const Iterator& it)
	:_node(it._node)
	,_pht(it._pht)
{ }

别看这个函数普普通通，其实别有洞天：

当这个迭代器类被实例化为const迭代器，这个函数的作用是一个构造函数。可以用普通迭代器去构造一个const迭代器。
当这个迭代器类被实例化为普通迭代器，这个函数就是一个拷贝构造函数。

最后我们来实现unordered_map的operator[]（）：直接返回insert返回的迭代器的value即可

V& operator[](const K& key)
{
	pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
	return ret.first->second;
}

八、封装后的源码

虽然封装过程已经阐述完毕了，但在代码更改过程中还是有许多细节的，下面给出完整封装后的代码。

哈希表

template<class K, class T, class KeyOfT, class Hashfunc = DefaultHashfunc<K>>
class HashTable
{
	typedef HashNode<T> Node;

	//友元声明：HashIterator需要访问HashTable的private成员
	//声明模板友元，需加上template
	template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hashfunc>
	friend struct HashIterator;
public:
	typedef HashIterator<K, T, T*, T&, KeyOfT, Hashfunc> iterator;
	typedef HashIterator<K, T, const T*, const T&, KeyOfT, Hashfunc> const_iterator;

	iterator Begin()
	{
		//找第一个非空桶
		size_t hashi = 0;
		while (hashi < _table.size())
		{
			if (_table[hashi])
			{
				return iterator(_table[hashi], this);
			}
			++hashi;
		}

		return iterator(nullptr, this);
	}

	iterator End()
	{
		return iterator(nullptr, this);
	}

	const_iterator Begin() const
	{
		//找第一个非空桶
		size_t hashi = 0;
		while (hashi < _table.size())
		{
			if (_table[hashi])
			{
				return const_iterator(_table[hashi], this);
			}
			++hashi;
		}

		return const_iterator(nullptr, this);
	}

	const_iterator End() const
	{
		return const_iterator(nullptr, this);
	}

	//构造
	HashTable()
	{
		_table.resize(10, nullptr);
	}

	//拷贝构造
	HashTable(const HashTable<K, T, KeyOfT, Hashfunc>& ht)
		: _table(ht._table.size(), nullptr)
		, _n(ht._n)
	{
		for (size_t i = 0; i < ht._table.size(); ++i)
		{
			Node* cur = ht._table[i];
			Node* tail = nullptr;
			while (cur)
			{
				Node* newNode = new Node(cur->_data);
				if (!_table[i])
				{
					_table[i] = newNode;
				}
				else
				{
					tail->_next = newNode;
				}
				tail = newNode;
				cur = cur->_next;
			}
		}
	}

	//赋值重载
	HashTable<K, T, KeyOfT, Hashfunc>& operator=(const HashTable<K, T, KeyOfT, Hashfunc>& ht)
	{
		_table = ht._table;
		_n = ht._n;
		return *this;
	}

	//析构
	~HashTable()
	{
		for (int i = 0; i < _table.size(); ++i)
		{
			Node* cur = _table[i];
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}

			_table[i] = nullptr;
		}
	}

	pair<iterator, bool> Insert(const T& data)
	{
		Hashfunc hf;
		KeyOfT kot;
		iterator it = Find(kot(data));
		if(it != End())
			return make_pair(it, false);

		//当负载因子对于1时，扩容
		if (_n == _table.size())
		{
			size_t NewSize = _table.size() * 2;
			vector<Node*> NewTable;
			NewTable.resize(NewSize, nullptr);

			//遍历旧表，将旧表上的节点迁到新表上（避免节点创建释放操作）
			for (int i = 0; i < _table.size(); ++i)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;
					int hashi = hf(kot(cur->_data)) % NewTable.size();
					cur->_next = NewTable[hashi];
					NewTable[hashi] = cur;

					cur = next;
				}
			}
			_table.swap(NewTable);
		}
			
		Node* NewData = new Node(data);
		int hashi = hf(kot(data)) % _table.size();
		NewData->_next = _table[hashi];
		_table[hashi] = NewData;
		++_n;

		return make_pair(iterator(NewData, this), true);
	}

	iterator Find(const K& key)
	{
		Hashfunc hf;
		KeyOfT kot;
		int hashi = hf(key) % _table.size();
		Node* cur = _table[hashi];
		while (cur)
		{
			if (kot(cur->_data) == key)
				return iterator(cur, this);
			cur = cur->_next;
		}

		return End();
	}

	bool Erase(const K& key)
	{
		Hashfunc hf;
		KeyOfT kot;
		int hashi = hf(key) % _table.size();
		Node* dele = _table[hashi];
		Node* prev = nullptr;
		while (dele)
		{
			if (kot(dele->_data) == key)
			{
				if (prev)
					prev->_next = dele->_next;
				else
					_table[hashi] = dele->_next;

				delete dele;
				return true;
			}
			prev = dele;
			dele = dele->_next;
		}
			
		return false;
	}

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

迭代器

//前置声明：因为HashIterator需要使用HashTable类，但编译器尚未编译到HashTable，会报错，因此需要声明。
//HashIterator和HashTable互相利用，互为依赖类
template<class K, class T, class KeyOfT, class Hashfunc>
class HashTable;

template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hashfunc>
struct HashIterator
{
	typedef HashNode<T> Node;
	typedef HashIterator<K, T, Ptr, Ref, KeyOfT, Hashfunc> Self;
	typedef HashIterator<K, T, T*, T&, KeyOfT, Hashfunc> Iterator;

	Node* _node;

	//HashTable<K, T, KeyOfT, Hashfunc>*前加const避免传const指针参数导致权限放大
	const HashTable<K, T, KeyOfT, Hashfunc>* _pht;

	HashIterator(Node* node, const HashTable<K, T, KeyOfT, Hashfunc>* pht)
		:_node(node)
		,_pht(pht)
	{ }

	//当实例化为普通迭代器时，该函数为构造函数，可以构造出const迭代器
	//当实例化为const迭代器时，该函数为拷贝构造函数
	HashIterator(const Iterator& it)
		:_node(it._node)
		,_pht(it._pht)
	{ }

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

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

	Self& operator++()
	{
		Hashfunc hf;
		KeyOfT kot;
		//若下一个节点不为空，访问next
		if (_node->_next)
		{
			_node = _node->_next;
		}
		else//下一个节点为空，从后一个桶开始，寻找不为空的桶
		{
			size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
			++hashi;
			while (hashi < _pht->_table.size())
			{
				if (_pht->_table[hashi])
				{
					_node = _pht->_table[hashi];
					return *this;
				}
				else
				{
					++hashi;
				}
			}

			_node = nullptr;
		}
		return *this;
	}

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

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

};

unordered_set

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

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

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

	pair<iterator, bool> insert(const K& key)
	{
		pair<typename HashTable<K, K, KeyOfSet>::iterator, bool> ret = _ht.Insert(key);
		return pair<iterator, bool>(ret.first, ret.second);
	}

	
private:
	HashTable<K, K, KeyOfSet> _ht;
};

unordered_map

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-07-28，如有侵权请联系 cloudcommunity@tencent.com 删除

set

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度