【高阶数据结构】封装unordered_map 和 unordered

这篇具有很好参考价值的文章主要介绍了【高阶数据结构】封装unordered_map 和 unordered_set。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🌈欢迎来到数据结构专栏~~封装unordered_map 和 unordered_set

(꒪ꇴ꒪(꒪ꇴ꒪ )🐣,我是Scort

目前状态：大三非科班啃C++中

🌍博客主页：张小姐的猫~江湖背景

快上车🚘，握好方向盘跟我有一起打天下嘞！

送给自己的一句鸡汤🤔：

🔥真正的大师永远怀着一颗学徒的心

作者水平很有限，如果发现错误，可在评论区指正，感谢🙏

🎉🎉欢迎持续关注！

包装unordered_map,数据结构—流浪计划,数据结构,算法,c++

看了上两篇的文章：用红黑树封装出map和set，那么本文思路其实是大差不差的，虽然哈希表的实现比红黑树要简单，但是unordered_map 和 unordered_set 的封装却要更加复杂一点，往下看吧，发车咯

一. 模板参数控制

老规矩unordered_set 是 K 模型的容器，而 unordered_map 是 KV 模型的容器，如果要实现封装，那么参数就必须控制

template<class K, class T>
class HashTable

T模板参数可能只是键值Key，也可能是由Key和Value共同构成的键值对。如果是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构成的键值对
};

这样一来就可以实现泛型了，当上层容器是unordered_set的时候，结点当中存储的是键值Key；当上层容器是unordered_map的时候，结点当中存储的就是<Key, Value>键值对

包装unordered_map,数据结构—流浪计划,数据结构,算法,c++

所以更改后的节点定义如下：

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

	//构造函数
	HashNode(const T& data)
		:_data(data)
		, _next(nullptr)
	{}
};

为了得到元素的键值，通过哈希计算出对应的哈希地址

我们插入的时候当然不能用data直接去比较

对于unordered_set而言是Key，可以比较
但是对于unordered_map是pair，那我们要取其中的first来比较，但是我们能取first吗？
这个地方的data有可能是unordered_map；也有可能是unordered_map

所以要实现一个仿函数，如果是unordered_map那就是用于获取T当中的键值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_set也必不可缺，直接返回key即可

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

所以在哈希表上也要加上这个仿函数

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

二. String类型无法取模问题

字符串无法取模，是哈希表中的老问题了吧

上文提到过了，我们都能想到的，写库的大佬还不能想到吗？早就预留了一个模板参数，此时无论上层容器是unordered_set还是unordered_map，我们都能够通过上层容器提供的仿函数获取到元素的键值

包装unordered_map,数据结构—流浪计划,数据结构,算法,c++

因为没有使得字符串与整型之间一一对应的方法，因为整型大小是有限的，最大的无符号整型是 4294967295，但是字符串的排列却是无穷的，因此我们提出了 BKDRHash算法

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

如果是在我们实现哈希表的时候，此仿函数就应该加在哈希表中，如今我们要把哈希封装起来，我们就根本不通过底层的哈希表来调用，而是上层的 unordered_map等，所以 仿函数加在上层！

	template<class K, class V, class Hash = Hashfunc<K>>
	class unordered_map

上层传入的数据：符合string类型的优先走string类型

template<class K>
struct Hashfunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

//特化版本
template<>
struct Hashfunc<string>
{
	//BKDR算法
	size_t operator()(const string& key)
	{
		size_t val = 0;
		for (auto ch : key)
		{
			val *= 131;
			val += ch;
		}
		return val;
	}
};

三. 默认成员函数实现

🌏构造函数

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

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

private:
	vector<Node*> _table;
	size_t _size = 0; //存储的有效数据个数

vector会自动去调用自己的构造，内置类型的size不处理，所以直接置0

这里默认构造已经完美完成了构造的任务，我们就不需要画蛇添足后期再去写一个构造函数，但是因为我们需要自己写拷贝构造函数，会使得初始化不使用默认构造，因此我们需要 default 关键字修饰来让他保持默认构造的属性

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

🌏析构函数

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

//析构 ： 内置类型不处理 但是桶要析构掉
~HashTable()
{
	for (size_t i = 0; i < _table.size(); ++i)
	{
		Node* cur = _table[i];
		while (cur)
		{
			Node* next = cur->_next;
			delete(cur);
			cur = next;
		}
		_table[i] = nullptr;
	}
}

四. 正向迭代器

哈希表的正向迭代器实际上就是对哈希结点指针进行了封装，实现++运算符重载，使他可以访问下一个非空的桶，所以每个正向迭代器里面存的都是哈希表地址。

template<class K, class T, class Hash, class KeyOfT>
struct HashTable;

template<class K, class T, class Hash, class KeyOfT>
struct __HashIterator
{
	typedef HashNode<T> Node;//节点类型
	typedef HashTable<K, T, Hash, KeyOfT> HT;//哈希表类型
	typedef __HashIterator<K, T, Hash, KeyOfT> Self;//迭代器类型

	Node* _node;
	HT* _pht;
}

所以在构造迭代器的时候就需要知道节点的指针，以及节点所在哈希表的地址：

	__HashIterator(Node* node, HT* pht)
		:_node(node)
		,_pht(pht)
	{}

++ 的实现逻辑也非常简单，只需要注意一下如果当前元素是该桶最后一个元素，那么 ++ 就是跳到下一个非空桶

包装unordered_map,数据结构—流浪计划,数据结构,算法,c++

T& operator*()
{
	return _node->_data;//返回节点数据的引用
}

T* operator->()
{
	return &_node->_data;//返回节点数据的地址
}

Self& operator++()
{
	if (_node->_next)//如果结点不是最后一个结点
	{
		//当前桶中迭代
		_node = _node->_next;
	}
	else
	{
		//找下一个桶 : 先算当前的哈希地址
		Hash hash;
		KeyOfT kot;
		size_t i = hash(kot(_node->_data)) % _pht->_table.size();//计算出哈希地址
		++i;//从下一个位置开始找
		for (; i < _pht->_table.size(); ++i)
		{
			if (_pht->_table[i])
			{
				_node = _pht->_table[i];//找到了node就跳转
				break;
			}
		}

		//说明后面没有 有数据的桶了
		if (i == _pht->_table.size())
		{
			_node = nullptr;
		}
	}
	return *this;
}

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

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

哈希表的迭代器类型是单向迭代器，没有反向迭代器，即没有实–运算符的重载，若是想让哈希表支持双向遍历，可以考虑将哈希桶中存储的单链表结构换为双链表结构

下面开始抠细节了：

由于 ++ 重载函数在寻找下一个结点时，会访问哈希表成员变量 _table，而 _table 是哈希表的私有成员，因此我们需要将正向迭代器类声明为哈希表类的友元
接下来就可以进行正向迭代器类型的 typedef，需要注意的是，为了让外部能够使用 typedef 后的正向迭代器类型 iterator，我们需要在 public 区域进行 typedef

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

	//模板的友元要带上声明
	template<class K, class T, class Hash, class KeyOfT>
	friend struct __HashIterator;
public: 

	typedef __HashIterator<K, T, Hash, KeyOfT> iterator;

	iterator begin()
	{
		for (int i = 0; i < _table.size(); ++i)
		{
			//遍历找到了，就返回 
			if (_table[i])
			{
				//this就是指向哈希表的指针
				return iterator(_table[i], this);
			}
		}
		return end();
	}

	iterator end()
	{
		return iterator(nullptr, this);
	}
private:
	vector<Node*> _table; //哈希表
	size_t _n = 0; //有效元素个数
}

[ ]的实现

首先把Insert的返回值改成pair<iterator, bool>，随后的返回值也要跟着改

如果表内有重复的元素就返回这个找到的ret的迭代器
没有重复的就返回newnode这个迭代器

iterator ret = Find(kot(data));
if (ret != end())
{
	return make_pair(ret, false);
}

//头插
Node* newnode = new Node(data);
newnode->_next = _table[hashi]; // _table[hashi]指向的就是第一个结点
_table[hashi] = newnode;

++_size;

return make_pair(iterator(newnode, this), true);

面试题

一个类型去做set和unordered_set的模板参数有什么要求？

set要求支持小于比较，或者显示提供比较的仿函数
unordered_set：
- K类型对象可以转换整形取模 or 提供转成整形的仿函数
- K类型对象可以支持等于比较 or 提供等于比较的仿函数

unordered_set的实现

#include"HashTable.h"

namespace ljj
{
	template<class K, class Hash = Hashfunc<K>>
	class unordered_set
	{
		//仿函数
		struct SetKeyOfT
		{
			const K& operator() (const K& key) //返回key
			{
				return key;
			}
		};

	public:
		//因为是调用的是内嵌类型，typename防止编译器认成静态变量， 是类型！！！
		typedef typename Bucket::HashTable<K, K, Hash, SetKeyOfT>::iterator iterator;

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

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

		pair<iterator, bool> Insert(const K& key)
		{
			return _ht.Insert(key);
		}

	private:
		Bucket::HashTable<K, K, Hash, SetKeyOfT> _ht;
	};
}

unordered_map的实现

#include"HashTable.h"

namespace ljj
{
	template<class K, class V, class Hash = Hashfunc<K>>
	class unordered_map
	{
		//仿函数
		struct MapKeyOfT
		{
			const K& operator() (const pair<K, V>& kv) //返回键值对当中的键值key
			{
				return kv.first;
			}
		};

	public:
		//因为是调用的是内嵌类型，typename防止编译器认成静态变量， 是类型！！！
		typedef typename Bucket::HashTable<K, pair<K, V>, Hash, MapKeyOfT>::iterator iterator;

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

		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 = _ht.Insert(make_pair(key, V()));
			return ret.first->second;
		}

	private:
		Bucket::HashTable<K, pair<K, V>, Hash, MapKeyOfT> _ht;
	};
}

哈希表代码

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

		//构造函数
		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};

	//前置声明
	template<class K, class T, class Hash, class KeyOfT>
	struct HashTable;

	template<class K, class T, class Hash, class KeyOfT>
	struct __HashIterator
	{
		typedef HashNode<T> Node;//节点类型
		typedef HashTable<K, T, Hash, KeyOfT> HT;//哈希表类型
		typedef __HashIterator<K, T, Hash, KeyOfT> Self;//迭代器类型

		Node* _node;
		HT* _pht;

		__HashIterator(Node* node, HT* pht)
			:_node(node)
			,_pht(pht)
		{}

		T& operator*()
		{
			return _node->_data;//返回节点数据的引用
		}

		T* operator->()
		{
			return &_node->_data;//返回节点数据的地址
		}

		Self& operator++()
		{
			if (_node->_next)//如果结点不是最后一个结点
			{
				//当前桶中迭代
				_node = _node->_next;
			}
			else
			{
				//找下一个桶 : 先算当前的哈希地址
				Hash hash;
				KeyOfT kot;
				size_t i = hash(kot(_node->_data)) % _pht->_table.size();//计算出哈希地址
				++i;//从下一个位置开始找
				for (; i < _pht->_table.size(); ++i)
				{
					if (_pht->_table[i])
					{
						_node = _pht->_table[i];//找到了node就跳转
						break;
					}
				}

				//说明后面没有 有数据的桶了
				if (i == _pht->_table.size())
				{
					_node = nullptr;
				}
			}
			return *this;
		}

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

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


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

		//模板的友元要带上声明
		template<class K, class T, class Hash, class KeyOfT>
		friend struct __HashIterator;
	public: 

		typedef __HashIterator<K, T, Hash, KeyOfT> iterator;

		iterator begin()
		{
			for (int i = 0; i < _table.size(); ++i)
			{
				//遍历找到了，就返回 
				if (_table[i])
				{
					//this就是指向哈希表的指针
					return iterator(_table[i], this);
				}
			}
			
			return end();
		}

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

		//析构 ： 内置类型不处理 但是桶要析构掉
		~HashTable()
		{
			for (size_t 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)
		{
			Hash hash;
			KeyOfT kot;

			//去重
			iterator ret = Find(kot(data));
			if (ret != end())
			{
				return make_pair(ret, false);
			}

			//负载因子到1就扩容
			if (_size == _table.size())
			{
				size_t newsize = _table.size() == 0 ? 10 : 2 * _table.size();
				vector<Node*> newTable;
				newTable.resize(newsize);

				//旧表节点移动映射到新表中
				for (size_t i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while (cur)
					{
						Node* next = cur->_next; //记录cur的下一个节点

						size_t hashi = hash(kot(cur->_data)) % newTable.size();//计算哈希地址
						//头插
						cur->_next = newTable[hashi];
						newTable[hashi] = cur;

						cur = next;
					}
					_table[i] = nullptr;//原桶取完后置空
				}
				//交换
				_table.swap(newTable);
			}

			size_t hashi = hash(kot(data)) % _table.size();
			//头插
			Node* newnode = new Node(data);
			newnode->_next = _table[hashi]; // _table[hashi]指向的就是第一个结点
			_table[hashi] = newnode;

			++_size;

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

		//查找
		iterator Find(const K& key)
		{
			if (_table.size() == 0)//哈希表为0，没得找
			{
				return end();
			}

			Hash hash;
			KeyOfT kot;

			size_t hashi = hash(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)
		{
			if (_table.size() == 0)
			{
				return nullptr;
			}

			//1、通过哈希函数计算出对应的哈希桶编号hashi
			Hash hash;
			KeyOfT kot;
			size_t hashi = hash(key) % _table.size();
			Node* prev = nullptr;
			Node* cur = _table[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					//头删
					if (prev == nullptr)
					{
						_table[hashi] = cur->_next;//将第一个结点从该哈希桶中移除
						delete cur;
					}
					else //中间删除
					{
						prev->_next = cur->_next;//将该结点从哈希桶中移除
						delete cur;
					}
					--_size;
					return true;
				}

				prev = cur;
				cur = cur->_next;
			}

			return false;
		}

	private:
		vector<Node*> _table;
		size_t _size = 0; //存储的有效数据个数
	};
}