【 C++ 】用一个哈希表封装unordered_map和unordered_set

目录

1、哈希表源代码

2、哈希函数模板参数的控制

3、对上层容器构建仿函数便于后续映射

4、部分类型无法取模问题

5、哈希表底层迭代器的实现

        框架

        ++运算符重载

        != 和 == 运算符重载

        * 和 -> 运算符重载

6、哈希表的迭代器相关函数（begin和end）

7、哈希表的优化（素数表）

8、unordered_map的插入和[ ]运算符重载

9、封装后源代码

        哈希表源代码链接

        unordered_set的模拟实现源代码

        unordered_map的模拟实现源代码

---

1、哈希表源代码

根据先前对unordered_map和unordered_set的学习，我们得知其底层是借助哈希表来实现的，下面，我将用上篇博文实现的开散列哈希表来模拟实现unordered_map和unordered_set，哈希表源代码链接如下：

简化版哈希表

下面我将对哈希表进行改造，使其能够很好的封装unordered_map与unordered_set。

---

2、哈希函数模板参数的控制

我们都清楚unorderded_map是KV模型，而unordered_set是K模型，而先前实现的哈希表是写死的pair键值对的KV模型，很显然不适用_set模型，因此要实现一个泛型，这就需要我们对哈希表的模板参数进行控制。

更改哈希节点的模板参数：

• 这里我们把参数设为T，如果后续传入节点的类型为K模型，则T为K模型，若为pair键值对KV模型，则为KV模型，代码如下：

template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;
	//构造函数
	HashNode(const T& data)
		:_data(data)
		, _next(nullptr)
	{}
};

更改哈希表的模板参数：

• 这里我们把第二个模板参数设为T，便于识别后续传入的数据类型

//unordered_map -> HashTable<K, pair<K, V>> _ht;
//unordered_set -> HashTable<K, K> _ht;
template<class K, class T, class HashFunc = DefaultHash<K>>
class HashTable

unordered_set的参数控制：

• 如果上层使用的是unordered_set容器，那么哈希表的参数对应的就是K，K类型。

template<class K>
class unordered_set
{
private:
	Bucket::HashTable<K, K> _ht;
};

unordered_map的参数控制：

• 如果上层使用的是unordered_map容器，那么哈希表的参数对应的就是K，pair<K, V>类型。

template<class K, class V>
class unordered_map
{
private:
	Bucket::HashTable<K, pair<K, V>> _ht;
};

---

3、对上层容器构建仿函数便于后续映射

在哈希映射的过程中，我们需要获得元素的键值，然后通过对应的哈希函数计算获得映射的地址，上一步为了适配_set和_map，我们对模板参数进行了整改，现在哈希节点存储的数据类型是T，T可能是一个键值，也可能是一个键值对，底层的哈希并不知道传入的数据是啥类型，因此我们需要对上层容器套一层仿函数来告诉底层哈希。

unordered_set的仿函数：

• 针对于unordered_set这种K类型的容器，我们直接返回key即可。

template<class K>
class unordered_set
{
	//仿函数
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
private:
	Bucket::HashTable<K, K, SetKeyOfT> _ht;
};

unordered_map的仿函数：

• _map的数据类型是pair键值对，我们只需要取出其first第一个数据key然后返回即可。

template<class K, class V>
class unordered_map
{
	//仿函数
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv)
		{
			return kv.first;
		}
	};
private:
	Bucket::HashTable<K, pair<K, V>, MapKeyOfT> _ht;
};

更改底层哈希的模板参数：

• 上层容器的仿函数已经套好，下面需要整改下底层哈希的模板参数来接收上层容器的数据类型。

//unordered_map -> HashTable<K, pair<K, V>, MapKeyOfT> _ht;
//unordered_set -> HashTable<K, K, SetKeyOfT> _ht;
template<class K, class T, class KeyOfT, class HashFunc = DefaultHash<K>>
class HashTable

---

4、部分类型无法取模问题

现在，我们已经通过构建仿函数成功获得无论unordered_map还是unordered_set的key数据，但是这又存在一个问题，那就是建立映射关系时存在无法取模的问题，就比如说我现在有一个自定义类型的日期类，那么我传入的模板参数就是Date日期类：

struct Date
{
	Date(int year = 1, int month = 1, int day = 1)
		:_year(year)
		, _month(month)
		, _day(day)
	{}
	bool operator==(const Date& d) const
	{
		return _year == d._year
			&& _month == d._month
			&& _day == d._day;
	}
	int _year;
	int _month;
	int _day;
};
cpp::unordered_set<Date> sd;
sd.insert(Date(2022, 3, 4));

• 这里的key是自定义类型日期类Date，不能直接转化为整型，我们可以像之前那样整个特化，但是日期类不是常用的类，而且这也相当于是改库了，比较好的解决办法是显示的传一个仿函数，来帮助我们解决取模问题。但是就要把放到哈希表这一层的仿函数挪到上层容器的模板参数那，整改后上层容器的模板参数如下：

unordered_set的模板参数：

template<class K, class HashFunc = DefaultHash<K>>
class unordered_set
{
	//仿函数
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
public:
	//插入
	bool insert(const K& key)
	{
		return _ht.Insert(key);
	}
private:
	Bucket::HashTable<K, K, SetKeyOfT, HashFunc> _ht;
};

unordered_map的模板参数：

template<class K, class V, class HashFunc = DefaultHash<K>>
class unordered_map
{
	//仿函数
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv)
		{
			return kv.first;
		}
	};
public:
	//插入
	bool insert(const pair<K, V>& kv)
	{
		return _ht.Insert(kv);
	}
private:
	Bucket::HashTable<K, pair<K, V>, MapKeyOfT, HashFunc> _ht;
};

哈希表底层的模板参数：

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

更改了仿函数的设定方式后，我们就可以针对上述日期类单独写个仿函数并采用BKDRhash算法来帮助我们获取对应的整型，以此完成日期类的映射关系：

struct DateHash
{
	size_t operator()(const Date& d)
	{
		size_t hash = 0;
		hash += d._year;
		hash *= 131;
		hash += d._month;
		hash *= 1313;
		hash += d._day;
		return hash;
	}
};
cpp::unordered_set<Date, DateHash> sd;
sd.insert(Date(2022, 3, 4));
sd.insert(Date(2022, 4, 3));

建立映射关系后，调试窗口如下：

---

5、哈希表底层迭代器的实现

框架

这里的框架遵循两个关键点：

1. 哈希表的正向迭代器实际上就是对哈希结点指针进行了封装，但是由于在实现++运算符重载时，需要在哈希表中去寻找下一个非空哈希桶，因此每一个正向迭代器中除了存放节点指针外，还都应该存储一个哈希表的地址。最后写个构造函数，初始化_node和_pht。
2. 这里我们的迭代器的位置放在了哈希表（HashTable）的上面，而我迭代器内部又使用了HashTable，因为编译器是向上寻找，按照此位置摆放，迭代器的类里是找不到HashTable的，所以我们需要把HashTable的类在迭代器前面进行声明。

//哈希表的声明
template<class K, class T, class KeyOfT, class HashFunc>
class HashTable;
//正向迭代器
template<class K, class T, class KeyOfT, class HashFunc>
class __HTIterator
{
	typedef HashNode<T> Node; //哈希节点的类型
	typedef __HTIterator<K, T, KeyOfT, HashFunc> Self; //正向迭代器的类型
public:
	//构造函数
	__HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht)
		:_node(node)
		, _pht(pht)
	{}
	//……
	Node* _node;//节点指针
	HashTable<K, T, KeyOfT, HashFunc>* _pht;//哈希表的地址
};

---

++运算符重载

假设此时的哈希表结构如图所示：

注意这里是一个哈希桶结构，每一个桶都是一串单链表，在单个桶中，我们拿到头节点指针，可以挨个遍历++it走完全程，但是这是多串单链表，我们需要保证在一个桶走完后要到下一个桶去，因此在++运算符重载的设定上要按照如下规则：

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

//++运算符重载
Self& operator++()
{
	if (_node->_next)
	{
		_node = _node->_next;
	}
	else//当前桶已经走完，需要到下一个不为空的桶
	{
		KeyOfT kot;//取出key数据
		HashFunc hf;//转换成整型
		size_t hashi = hf(kot(_node->_data));
		for (; hashi < _pht->_tables.size(); ++hashi)
		{
			if (_pht->_tables[hashi])//更新节点指针到非空的桶
			{
				_node = _pht->_tables[hashi];
				break;
			}
		}
		//没有找到不为空的桶，用nullptr去做end标识
		if (hashi == _pht->_tables.size())
		{
			_node = nullptr;
		}
	}
	return *this;
}

由于正向迭代器中++运算符重载函数在寻找下一个结点时，会访问哈希表中的成员变量_table，而_table成员变量是哈希表的私有成员，因此我们需要将正向迭代器类声明为哈希表类的友元。

template<class K, class T, class KeyOfT, class HashFunc>
class HashTable
{
	//把迭代器设为HashTable的友元
	template<class K, class T, class KeyOfT, class HashFunc>
	friend class __HTIterator;
 
	typedef HashNode<T> Node;//哈希结点类型
public:
	//……
}

---

!= 和 == 运算符重载

比较两迭代器是否相等，只需要判断两迭代器所封装的节点是否是同一个即可。

//!=运算符重载
bool operator!=(const Self& s) const
{
	return _node != s._node;
}
//==运算符重载
bool operator==(const Self& s) const
{
	return _node == s._node;
}

---

* 和 -> 运算符重载

• *运算符返回的是哈希节点数据的引用
• ->运算符返回的是哈希节点数据的地址

//*运算符重载
T& operator*()
{
	return _node->_data;//返回哈希节点中数据的引用
}
//->运算符重载
T* operator->()
{
	return &(_node->_data);//返回哈希节点中数据的地址
}

---

6、哈希表的迭代器相关函数（begin和end）

这里我们需要进行正向迭代器类型的typedef，需要注意的是，为了让外部能够使用typedef后的正向迭代器类型iterator，我们需要在public区域进行typedef。

template<class K, class T, class KeyOfT, class HashFunc>
class HashTable
{
    //把迭代器设为HashTable的友元
	template<class K, class T, class KeyOfT, class HashFunc>
	friend class __HTIterator;
 
	typedef HashNode<T> Node;//哈希结点类型
public:
	typedef __HTIterator<K, T, KeyOfT, HashFunc> iterator;//正向迭代器的类型
}

• typedef之后，就可以实现begin()和end()的函数了。

begin()：

1. 遍历哈希表，返回第一个不为空的桶的第一个节点的迭代器位置，借助正向迭代器的构造函数完成，还得传this指针（哈希表的指针）
2. 若遍历结束没找到，说明哈希表里没有一个是空，直接返回end()尾部的迭代器位置。

//begin
iterator begin()
{
	for (size_t i = 0; i < _tables.size(); i++)
	{
		Node* cur = _tables[i];
		//找到第一个不为空的桶的节点位置
		if (cur)
		{
			return iterator(cur, this);
		}
	}
	return end();
}

end()：

• 哈希表的end()直接返回迭代器的构造函数（节点指针为空，哈希表指针为this）即可。

//end()
iterator end()
{
	return iterator(nullptr, this);
}

---

7、哈希表的优化（素数表）

在除留余数法时，最好模一个素数，这样模完后不会那么容易出现哈希冲突的问题，因此我们可以专门写一个素数表来解决。

//素数表
size_t GetNextPrime(size_t prime)
{
	const int PRIMECOUNT = 28;
	static const size_t primeList[PRIMECOUNT] =
	{
		53ul, 97ul, 193ul, 389ul, 769ul,
		1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
		49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
		1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
		50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
		1610612741ul, 3221225473ul, 4294967291ul
	};
 
	// 获取比prime大那一个素数
	size_t i = 0;
	for (; i < PRIMECOUNT; ++i)
	{
		if (primeList[i] > prime)
			return primeList[i];
	}
 
	return primeList[i];
}

---

8、unordered_map的插入和[ ]运算符重载

insert插入：

• unordered_map的数据类型是KV模型，其插入的是一个pair键值对，这里要区别于unordered_set，实现方式也有所区别。

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

[ ]运算符重载：

1. 首先调用insert函数插入键值对返回迭代器ret
2. 通过返回的迭代器ret调用元素值value

//[]运算符重载
V& operator[](const K& key)
{
	pair<iterator, bool> ret = insert(make_pair(key, V()));
	return ret.first->second;
}

---

9、封装后源代码

哈希表源代码链接

调整后的哈希表源代码链接：哈希表封装的unordered_map与unordered_set源代码

---

unordered_set的模拟实现源代码

封装好了底层哈希表，剩下的就是相当于是在套模板了，具体实现的功能有插入、删除、查找、迭代器……功能。

#include"HashTable.h"
namespace cpp
{
	template<class K, class HashFunc = DefaultHash<K>>
	class unordered_set
	{
		//仿函数
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		//现在没有实例化，没办法到HashTable里面找iterator，所以typename就是告诉编译器这里是一个类型，实例化以后再去取
		typedef typename Bucket::HashTable<K, K, SetKeyOfT, HashFunc>::iterator iterator;
		//begin()
		iterator begin()
		{
			return _ht.begin();
		}
		//end()
		iterator end()
		{
			return _ht.end();
		}
		//insert插入
		pair<iterator, bool> insert(const K& key)
		{
			return _ht.Insert(key);
		}
		//find查找
		iterator find(const K& key)
		{
			return _ht.Find(key);
		}
		//erase删除
		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}
	private:
		Bucket::HashTable<K, K, SetKeyOfT, HashFunc> _ht;
	};
}

---

unordered_map的模拟实现源代码

实现unordered_map的各个接口时，也是调用底层哈希表对应的接口就行了，此外还需要实现[]运算符的重载。

#include"HashTable.h"
namespace cpp
{
	template<class K, class V, class HashFunc = DefaultHash<K>>
	class unordered_map
	{
		//仿函数
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		//现在没有实例化，没办法到HashTable里面找iterator，所以typename就是告诉编译器这里是一个类型，实例化以后再去取
		typedef typename Bucket::HashTable<K, pair<K, V>, MapKeyOfT, HashFunc>::iterator iterator;
		//begin()
		iterator begin()
		{
			return _ht.begin();
		}
		//end()
		iterator end()
		{
			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 = insert(make_pair(key, V()));
			return ret.first->second;
		}
		//find查找
		iterator find(const K& key)
		{
			return _ht.Find(key);
		}
		//erase删除
		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}
	private:
		Bucket::HashTable<K, pair<K, V>, MapKeyOfT, HashFunc> _ht;
	};
}