用一个哈希表同时封装出unordered_map和unordered_set

我们这边介绍了如何重哈希表只能存pair<K,V>开始到能存Key类型和pair<Key,Value>。以及介绍了string类型无法取模的问题，并且我们添加了哈希表中默认的成员函数，已经对哈希表添加了插入，查找，删除的功能。我们后续又重点介绍了迭代器如果使用，这里的迭代器即使重点也是难点，大家一定要认真看。最后如果是小比特的同学，这里我建议先跟着杭哥把代码打一遍，因为这里其实的难度其实就是参数列

无名领头羊

1122人浏览 · 2025-03-31 18:06:22

无名领头羊 · 2025-03-31 18:06:22 发布

7. unordered_set的模拟实现

8. unordered_map的模拟实现

1. 哈希表源代码

下面我们将对一个KV模型的哈希表进行封装，源代码如下：

而我们要模拟实现出C++STL库当中的unordered_map和unordered_set，就需要在源代码的基础上进行修改添加操作

#include <iostream>
using namespace std;
template <class K>
struct HashFunc
{
	size_t operator() (const K& key)
	{
		return (size_t)key;
	}
};
 
//特化
template <>
struct HashFunc <string>
{
	size_t operator() (const string& key)
	{
		size_t hash = 0;
		for (const auto& e : key)
		{
			//字符串有很多排列组合，abc和bca
			//如果不乘31，那这两个字符串就会有冲突
			hash *= 31;
			hash += e;
		}
		return hash;
	}
};
 
namespace open_address
{
	//节点中元素的状态
	enum State
	{
		//存在
		EXIST,
		//空的
		EMPTY,
		//删除
		DELETE
	};
 
	//哈希表中要存储的数据
	template <class K, class V>
	struct HashDate
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};
 
	//哈希表（开放定址法）
	template <class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			//开10个空间，这边默认初始化都是0
			_tables.resize(10);
		}
 
		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			if (_n * 10 / _tables.size() >= 7)
			{
				//创建哈希对象
				HashTable<K, V> newTables;
				//扩容
				newTables._tables.resize(2 * _tables.size());
				for (int i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._state == EXIST)
					{
						//把旧数据插入到newTables中
						//此时复用Insert插入函数，this是newTables
						newTables.Insert(_tables[i]._kv);
					}
				}
				//让旧的哈希表与newTables中的哈希表进行交换
				_tables.swap(newTables._tables);
			}
			Hash hs;
			size_t hashi = hs(kv.first) % _tables.size();
			while (_tables[hashi]._state == EXIST)
			{
				hashi++;
				hashi %= _tables.size();
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			_n++;
			return true;
		}
 
		//查找
		HashDate<K, V>* Find(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			//节点状态不等于空进来
			while (_tables[hashi]._state != EMPTY)
			{
				//节点状态不等于删除并且找到元素才返回
				if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
					return &_tables[hashi];
				hashi++;
				hashi %= _tables.size();
			}
			return nullptr;
		}
 
		//删除
		bool Erase(const K& key)
		{
			HashDate<K, V>* ret = Find(key);
			if (ret == nullptr)
				return false;
			ret->_state = DELETE;
			_n--;
			return true;
		}
 
	private:
		vector<HashDate<K, V>> _tables;
		size_t _n = 0;//表中存储有效元素的个数（判断负载因子的关键）
	};

2. 哈希表模板参数的控制

首先需要明确的是，unordered_set是K模型的容器，而unordered_map是KV模型的容器。

要想只用一份哈希表代码同时封装出K模型和KV模型的容器，我们必定要对哈希表的模板参数进行控制。

为了与原哈希表的模板参数进行区分，这里将哈希表的第二个模板参数的名字改为T。

template<class K, class T>
class HashTable

如果上层使用的是unordered_set容器，那么传入哈希表的模板参数就是key和key。

template<class K>
class unordered_set
{
public:
	//...
private:
	HashTable<K, K> _ht; //传入底层哈希表的是K和K
};

但如果上层使用的是unordered_map容器，那么传入哈希表的模板参数就是key以及key和value构成的键值对。

template<class K, class V>
class unordered_map
{
public:
	//...
private:
	HashTable<K, pair<K, V>> _ht; //传入底层哈希表的是K以及K和V构成的键值对
};

也就是说，哈希表中的模板参数T的类型到底是什么，完全却决于上层所使用容器的种类。

而哈希结点的模板参数也应该由原来的K、V变为T：

上层容器是unordered_set时，传入的T是键值，哈希结点中存储的就是键值。
上层容器是unordered_map时，传入的T是键值对，哈希结点中存储的就是键值对。

更改模板参数后，哈希结点的定义如下：

//节点存放的元素
template<class T>
struct HashNode
{
	T _date;
	HashNode* _next;

	HashNode(const T& date)
		:_date(date)
		, _next(nullptr)
	{}
};

在哈希映射过程中，我们需要获得元素的键值，然后通过哈希函数计算出对应的哈希地址进行映射。

现在由于我们在哈希结点当中存储的数据类型是T，这个T可能就是一个键值，也可能是一个键值对，对于底层的哈希表来说，它并不知道哈希结点当中存储的数据究竟是什么类型，因此需要由上层容器提供一个仿函数，用于获取T类型数据当中的键值。

因此，unordered_map容器需要向底层哈希表提供一个仿函数，该仿函数返回键值对当中的键值。（我们用一颗红黑树实现map和set的时候用的就是这种）

template<class K, class V>
class unordered_map
{
	//仿函数
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv) //返回键值对当中的键值key
		{
			return kv.first;
		}
	};
public:
	//...
private:
	HashTable<K, pair<K, V>, MapKeyOfT> _ht;
};

而虽然unordered_set容器传入哈希表的T就是键值，但是底层哈希表并不知道上层容器的种类，底层哈希表在获取键值时会统一通过传入的仿函数进行获取，因此unordered_set容器也需要向底层哈希表提供一个仿函数。

template<class K>
class unordered_set
{
	//仿函数
	struct SetKeyOfT
	{
		const K& operator()(const K& key) //返回键值key
		{
			return key;
		}
	};
public:
	//...
private:
	HashTable<K, K, SetKeyOfT> _ht;
};

因此，底层哈希表的模板参数现在需要增加一个，用于接收上层容器提供的仿函数。

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

3. string类型无法取模问题

字符串无法取模，是哈希问题中最常见的问题。

经过上面的分析后，我们让哈希表增加了一个模板参数，此时无论上层容器是unordered_set还是unordered_map，我们都能够通过上层容器提供的仿函数获取到元素的键值。

但是在我们日常编写的代码中，用字符串去做键值key是非常常见的事，比如我们用unordered_map容器统计水果出现的次数时，就需要用各个水果的名字作为键值。

而字符串并不是整型，也就意味着字符串不能直接用于计算哈希地址，我们需要通过某种方法将字符串转换成整型后，才能代入哈希函数计算哈希地址。

但遗憾的是，我们无法找到一种能实现字符串和整型之间一对一转换的方法，因为在计算机中，整型的大小是有限的，比如用无符号整型能存储的最大数字是4294967295，而众多字符能构成的字符串的种类却是无限的。

鉴于此，无论我们用什么方法将字符串转换成整型，都会存在哈希冲突，只是产生冲突的概率不同而已。

经过前辈们实验后发现，BKDRHash算法无论是在实际效果还是编码实现中，效果都是最突出的。该算法由于在Brian Kernighan与Dennis Ritchie的《The C Programing Language》一书被展示而得名，是一种简单快捷的hash算法，也是Java目前采用的字符串的hash算法

因此，现在我们需要在哈希表的模板参数中再增加一个仿函数，用于将键值key转换成对应的整型。

template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
class HashTable

若是上层没有传入该仿函数，我们则使用默认的仿函数，该默认仿函数直接返回键值key即可，但是用字符串作为键值key是比较常见的，因此我们可以针对string类型写一个类模板的特化，此时当键值key为string类型时，该仿函数就会根据BKDRHash算法返回一个对应的整型。

template<class K>
struct Hash
{
	size_t operator()(const K& key) //返回键值key
	{
		return key;
	}
};
//string类型的特化
template<>
struct Hash<string>
{
	size_t operator()(const string& s) //BKDRHash算法
	{
		size_t value = 0;
		for (auto ch : s)
		{
			value = value * 131 + ch;
		}
		return value;
	}
};

或者是和之前一样让每个字符的ASCII码 × 31也可以，我自己使用的时候就×31

4. 哈希表默认成员函数实现

一、构造函数
哈希表中有两个成员变量，当我们实例化一个对象时：

_table会自动调用vector的默认构造函数进行初始化。
_n会根据我们所给的缺省值被设置为0。

vector<Node*> _table; //哈希表
size_t _n = 0; //哈希表中的有效元素个数

因此我们不需要编写构造函数，使用默认生成的构造函数就足够了，但是由于我们后面需要编写拷贝构造函数，编写了拷贝构造函数后，默认的构造函数就不会生成了，此时我们需要使用default关键字显示指定生成默认构造函数。

//构造函数
HashTable() = default; //显示指定生成默认构造函数

显示写了拷贝构造，默认的构造才不会生成。显示写了构造（不是默认的构造），那拷贝构造还是会生成

二、拷贝构造函数
哈希表在拷贝时需要进行深拷贝，否则拷贝出来的哈希表和原哈希表中存储的都是同一批结点。

哈希表的拷贝构造函数实现逻辑如下：

将哈希表的大小调整为ht._table的大小。
将ht._table每个桶当中的结点一个个拷贝到自己的哈希表中。
更改哈希表当中的有效数据个数。

//拷贝构造函数
HashTable(const HashTable& ht)
{
	//1、将哈希表的大小调整为ht._table的大小
	_table.resize(ht._table.size());
	//2、将ht._table每个桶当中的结点一个个拷贝到自己的哈希表中（深拷贝）
	for (size_t i = 0; i < ht._table.size(); i++)
	{
		if (ht._table[i]) //桶不为空
		{
			Node* cur = ht._table[i];
			while (cur) //将该桶的结点取完为止
			{
				Node* copy = new Node(cur->_data); //创建拷贝结点
				//将拷贝结点头插到当前桶
				copy->_next = _table[i];
				_table[i] = copy;
				cur = cur->_next; //取下一个待拷贝结点
			}
		}
	}
	//3、更改哈希表当中的有效数据个数
	_n = ht._n;
}

三、赋值运算符重载函数
实现赋值运算符重载函数时，可以通过参数间接调用拷贝构造函数，之后将拷贝构造出来的哈希表和当前哈希表的两个成员变量分别进行交换即可，当赋值运算符重载函数调用结束后，拷贝构造出来的哈希表会因为出了作用域而被自动析构，此时原哈希表之前的数据也就顺势被释放了。

//赋值运算符重载函数
HashTable& operator=(HashTable ht)
{
	//交换哈希表中两个成员变量的数据
	_table.swap(ht._table);
	swap(_n, ht._n);

	return *this; //支持连续赋值
}

四、析构函数
因为哈希表当中存储的结点都是new出来的，因此在哈希表被析构时必须进行结点的释放。在析构哈希表时我们只需要依次取出非空的哈希桶，遍历哈希桶当中的结点并进行释放即可。

//析构
~HashTable()
{
	for (int i = 0; i < _tables.size(); i++)
	{
		//cur是当前桶的地址
		Node* cur = _tables[i];
		Node* prev = nullptr;
		//桶不为空
		while (cur)
		{
			prev = cur;
			cur = cur->_next;
			delete prev;
		}
		//将哈希桶置空
		_tables[i] = nullptr;
	}
}

5. 哈希表正向迭代器的实现

哈希表的正向迭代器实际上就是对哈希结点指针进行了封装，但是由于在实现++运算符重载时，可能需要在哈希表中去寻找下一个非空哈希桶，因此每一个正向迭代器中都应该存储哈希表对象的地址。

我这边先把总代码展示出来，方便大家理解

//对迭代器中的哈希表进行前置声明
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable;

//这些模板参数 Ptr,Ref给的是迭代器的，其他的都是给哈希表的
template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
class HTIterator
{
	typedef HashNode<T> Node;
	typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;
	//编译器只会向上找，迭代器内要用哈希表，向上找找不到哈希表 
public:
	//这里对HashTable<K, T, KeyOfT, Hash>* pht加const的原因是
	//如果是const_iterator，那传入过来的this是有被const修饰的
	//因此如果我们这边不用const修饰接收过来的哈希对象，那可能会引起权限的放大（类型不匹配）
	HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht)
		:_node(node)
		, _pht(pht)
	{
	}

	Ptr operator*()
	{
		return _node->_date;
	}

	Ref operator->()
	{
		return &(_node->_date);
	}

	Self& operator++()
	{
		Node* cur = _node;
		if (cur != nullptr && cur->_next != nullptr)
		{
			//当前桶还有节点
			_node = cur->_next;
		}
		else
		{
			//当前桶走完了，找下一个不为空的桶
			KeyOfT kot;
			Hash hs;
			//迭代器中去访问迭代器中私有的成员变量
			size_t hashi = hs(kot(cur->_date)) % _pht->_tables.size();
			++hashi;
			while (hashi < _pht->_tables.size())
			{
				if (_pht->_tables[hashi])
				{
					break;
				}
				++hashi;
			}
			//如果hashi走到了pht->_tables.size()那就说明都是_node后面的桶都是空桶
			if (hashi < _pht->_tables.size())
				_node = _pht->_tables[hashi];
			else
				_node = nullptr;
		}
		return *this;
	}

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

private:
	Node* _node;
	//这里加const就是防止迭代器修改哈希对象
	const HashTable<K, T, KeyOfT, Hash>* _pht;
};

迭代器内之所以需要哈希表对象的地址是因为：当我们把当前桶遍历完后，我们需要继续向后找不为空的桶，如果我们单纯只有节点的指针是完不成这事的

而我们迭代器是写在实现哈希表的上面，因为编译器是向上寻找，我们在迭代器内部就用了哈希表来定义变量（const HashTable<K, T, KeyOfT, Hash>* _pht），所以如果我们不进行前置声明，那编译器找不到就会报错

因此在构造正向迭代器时，我们不仅需要对应哈希结点的指针，还需要该哈希结点所在哈希表的地址。

//这里对HashTable<K, T, KeyOfT, Hash>* pht加const的原因是
//如果是const_iterator，那传入过来的this是有被const修饰的
//因此如果我们这边不用const修饰接收过来的哈希对象，那可能会引起权限的放大（类型不匹配）
HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht)
	:_node(node)
	, _pht(pht)
{
}

当对正向迭代器进行解引用操作时，我们直接返回对应结点数据的引用即可。

//Ptr是元素类型的引用
Ptr operator*()
{
	return _node->_date;
}

当对正向迭代器进行->操作时，我们直接返回对应结点数据的地址即可。

//Ref是节点类型的指针
Ref operator->()
{
	return &(_node->_date);
}

当我们需要比较两个迭代器是否相等时，只需要判断这两个迭代器所封装的结点是否是同一个即可。

bool operator!=(const Self& s) const
{
	return _node != s._node; //判断两个结点的地址是否不同
}

bool operator==(const Self& s) const
{
	return _node == s._node; //判断两个结点的地址是否相同
}

++运算符重载函数的实现逻辑并不是很难，我们只需要知道如何找到当前结点的下一个结点即可。

若当前结点不是当前哈希桶中的最后一个结点，则++后走到当前哈希桶的下一个结点。
若当前结点是当前哈希桶的最后一个结点，则++后走到下一个非空哈希桶的第一个结点。

Self& operator++()
{
	Node* cur = _node;
	if (cur != nullptr && cur->_next != nullptr)
	{
		//当前桶还有节点
		_node = cur->_next;
	}
	else
	{
		//当前桶走完了，找下一个不为空的桶
		KeyOfT kot;
		Hash hs;
		//迭代器中去访问迭代器中私有的成员变量
		size_t hashi = hs(kot(cur->_date)) % _pht->_tables.size();
		++hashi;
		while (hashi < _pht->_tables.size())
		{
			if (_pht->_tables[hashi])
			{
				break;
			}
			++hashi;
		}
		//如果hashi走到了pht->_tables.size()那就说明都是_node后面的桶都是空桶
		if (hashi < _pht->_tables.size())
			_node = _pht->_tables[hashi];
		else
			_node = nullptr;
	}
	return *this;
}

但这里我们需要而外注意的点是：

我们在迭代器中使用了哈希表中的私有成员变量_tables，因为实现哈希表和实现迭代器是在不同的类中，因此我们迭代器内要使用哈希表中的成员变量，那我们声明迭代器是哈希表的友元即可解决私有问题

正向迭代器实现后，我们需要在哈希表的实现当中进行如下操作：

进行正向迭代器类型的typedef，需要注意的是，为了让外部能够使用typedef后的正向迭代器类型Iterator和Const_Iterator，我们需要在public区域进行typedef。
由于正向迭代器中++运算符重载函数在寻找下一个结点时，会访问哈希表中的成员变量_table，而_table成员变量是哈希表的私有成员，因此我们需要将正向迭代器类声明为哈希表类的友元。
将哈希表中查找函数返回的结点指针，改为返回由结点指针和哈希表地址构成的正向迭代器。
将哈希表中插入函数的返回值类型，改为由正向迭代器类型和布尔类型所构成的键值对。

然后我们就可以在哈希表中实现迭代器相关的成员函数了：

begin函数： 返回哈希表中第一个非空哈希桶中的第一个结点的正向迭代器。
end函数： 返回空指针的正向迭代器。

//Hash主要是让节点中的值能转换为整形  你不传递 一直用的是缺省值  
template<class K, class T, class KeyOfT, class Hash> //声明和定义放一个缺省参数就行
class HashTable
{
	//迭代器中想用哈希中私有变量（因此我们这边要声明成有元）
	template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
	friend  class HTIterator;

	typedef HashNode<T> Node;
	//通过HashTable的模板参数传给Iterator
	//Iterator里面包含的节点的指针还有哈希对象

public:
	typedef HTIterator<K, T, T&, T*, KeyOfT, Hash > Iterator;
	typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash > ConstIterator;


	Iterator Begin()
	{
		for (int i = 0; i < _tables.size(); i++)
		{
			if (_tables[i])
				return Iterator(_tables[i], this);
		}
		return Iterator(nullptr, this);
	}

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

	ConstIterator Begin()const
	{
		for (int i = 0; i < _tables.size(); i++)
		{
			if (_tables[i])
				return ConstIterator(_tables[i], this);
		}
		return ConstIterator(nullptr, this);
	}

	ConstIterator End()const
	{
		//这里this被const修饰，所以构造的时候由于HashTable<K, T, KeyOfT, Hash>* pht
		//没有被const修饰，因此传过去是一种权限的放大
		return ConstIterator(nullptr, this);
	}
private:
	vector<Node*> _tables;  // 指针数组
	size_t _n = 0;			// 表中存储数据个数
};