【高阶数据结构】封装unordered

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

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

  • (꒪ꇴ꒪(꒪ꇴ꒪ )🐣,我是Scort
  • 目前状态大三非科班啃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>键值对

在这里插入图片描述

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

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我们都能够通过上层容器提供的仿函数获取到元素的键值

在这里插入图片描述

因为没有使得字符串与整型之间一一对应的方法因为整型大小是有限的最大的无符号整型是 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)
	{}

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

在这里插入图片描述

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;
}
};

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

下面开始抠细节了

  1. 由于 ++ 重载函数在寻找下一个结点时会访问哈希表成员变量 _table而 _table 是哈希表的私有成员因此我们需要将正向迭代器类声明为哈希表类的友元
  2. 接下来就可以进行正向迭代器类型的 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; //存储的有效数据个数
	};
}

📢写在最后

鹅鹅鹅

在这里插入图片描述

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
返回列表

上一篇：【每日一道智力题】之猴子搬香蕉

下一篇：【230125-1】已知：x平方+y平方+xy-3y+3=0 求：x,y?

“【高阶数据结构】封装unordered” 的相关文章

Python数据可视化 | Python实现Matplotlib系列colorbar的设置1年前 (2023-02-02)
C++ move()函数及priority_queue队列使用记录1年前 (2023-02-02)
cookie、session,、token，还在傻傻分不清？1年前 (2023-02-02)
day02-Promise1年前 (2023-02-02)
【Azure Developer】在Github Action中使用Azure/functions-container-action@v1配置Function App并成功部署Function Image1年前 (2023-02-02)
设计模式之模板方法模式和策略模式1年前 (2023-02-02)
FalseSharing-伪共享1年前 (2023-02-02)
目标文件1年前 (2023-02-02)
【Redis技术专区】「优化案例」谈谈使用Redis慢查询日志以及Redis慢查询分析指南1年前 (2023-02-02)
阿里云Docker仓库操作1年前 (2023-02-02)

阿里云国际版