程序员经验分享-hwhale

用哈希简单封装unordered_map和unordered_set

2023-05-16

哈希表的改造

  • 哈希表的改造
  • unordered_map和unordered_set的基本结构
  • 哈希表改造
    • 节点结构体
    • 迭代器
    • 哈希表改造
  • unordered_map和unordered_set封装
    • unordered_map封装以及测试代码
    • unordered_set封装以及测试代码

哈希表的改造

在这里插入图片描述
在这里插入图片描述

unordered_map和unordered_set这两个stl容器，从上图可以看到，他们底层似乎都是使用哈希来实现的。那么在理解了哈希的基础上，不妨尝试一下自己模拟实现一下简单的unordered_map和unordered_set也给之前的哈希结构加上迭代器操作。

unordered_map和unordered_set的基本结构

从C++库中可以看出来，map和set一大区别就在于set只有一个关键字key，而map中存在key和T。因此他们的基本结构可以分别这样设计：其中在原来哈希的基础上又多了一个KeyOfT的仿函数，他的作用主要是确定需要进行比较的关键字，例如map中需要比较的是T中的first，而set就是key

	template<class K,class V,class HashFunc = Hash<K>>
	class Unordered_map
	{
			struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	private:
		LinkHash::HashTable<K, pair<K, V>, MapKeyOfT, hash> _ht;

	};


	template<class K, class HashFunc = Hash<K>>
	class unordered_map
	{
			struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	private:
		LinkHash::HashTable<K, K, SetKeyOfT, hash> _ht;

	};

哈希表改造

确定了基本结构之后就可以对原来的哈希表进行一系列的改造，例如：

节点结构体

为了方便使用同一个哈希表来实现unordered_map和unordered_set，这里是通过第二个参数将这两个进行区分，unordered_set传入的就是key，而unordered_map传入的则是一个pair，因此这里的哈希节点结构体可以进行如下改造

	//template<class K, class V>
	//struct HashNode
	//{
	//	pair<K,V> _data;
	//	HashNode<K, V>* _next;
	//	HashNode(const pair<K,V>& data)
	//		:_next(nullptr)
	//		,_data(data)
	//	{}
	//};
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next = nullptr;
		HashNode(const T& data)
			:_data(data)
			,_next(nullptr)
		{}
	};

迭代器

stl中的unordered_map和unordered_set内部实现了迭代器，可以使用迭代器访问其中的内容，这里我们也在哈希中实现一个迭代器操作，然后通过封装实现unordered_map和unordered_set的迭代器，实现代码如下，迭代器里面主要需要注意的是operator++操作。这个操作需要遍历哈希表以及每个点上所挂的链表。因此可以这样考虑：先判断当前链表是否走完，如果没走完就直接往下一个节点走，如果走完了就将index++，前往下一个哈希地址，然后开始遍历链表

	template<class K,class T,class Ref,class Ptr,class KeyOfT,class HashFunc>
	struct HTIterator//迭代器
	{
		typedef HashNode<T> Node;
		typedef HTIterator<K, T, Ref, Ptr, KeyOfT, HashFunc> Self;
		Node* _node;
		HashTable<K, T, KeyOfT, HashFunc>* _pht;
		HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht)
			:_node(node)
			,_pht(pht)
		{}

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


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

		Self& operator++()
		{
			if (_node->_next)//该链表还未走完
			{
				_node = _node->_next;
			}
			else
			{
				KeyOfT kt;
				HashFunc hf;
				size_t index = hf(kt(_node->_data)) % _pht->_tables.size();
				index++;//找下一个哈希地址
				while (index < _pht->_tables.size())
				{
					if (_pht->_tables[index])
					{
						break;
					}
					else
					{
						index++;
					}
				}
				if (index == _pht->_tables.size())//走完了
				{
					_node = nullptr;
				}
				else
				{
					_node = _pht->_tables[index];
				}
				
			}
			return *this;
		}

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

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

	};

哈希表改造

在完成迭代器之后，可以在原来的哈希表结构体中完善一下insert等参数的返回值，并加入新的begin，end接口函数，代码如下：

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

		template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc>
		friend struct HTIterator;//迭代器
	public:
		typedef HashTable<K, T, KeyOfT, HashFunc> Self;
		typedef HTIterator<K, T, T&, T*, KeyOfT, HashFunc> iterator;

		HashTable() = default;//默认构造函数

		HashTable(const Self& ht)//拷贝构造
		{
			_tables.resize(ht._tables.size());//开辟空间
			_n = ht._n;
			for (size_t i = 0; i < ht._tables.size(); i++)
			{

				Node* cur = ht._tables[i];
				while (cur)
				{
					Node* copy = new Node(cur->_data);
					copy->_next = _tables[i];
					_tables[i] = copy;
					cur = cur->_next;
				}

			}
		}


		Self& operator=(Self ht)
		{
			swap(_n, ht._n);
			_tables.swap(ht._tables);
			return *this;
		}


		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		iterator begin()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return iterator(_tables[i], this);
				}
			}
			return end();
		}

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

		bool Erase(const K& key)//删除
		{
			if (_tables.empty())//如果表是空的则不用删除
			{
				return false;
			}
			HashFunc hf;
			size_t index = hf(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[index];
			KeyOfT kt;
			while (cur)//寻找存放key值的节点
			{
				if (kt(cur->_data) == key)//找到了
				{
					//头删
					if (prev == nullptr)
					{
						_tables[index] = cur->_next;
					}
					else
					{
						//中间位置删除
						prev->_next = cur->_next;
					}
					--_n;
					delete cur;
					return true;
				}
				else//继续往下走
				{
					prev = cur;
					cur = cur->_next;		
				}

			}

		}


		iterator Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return end();
			}
			HashFunc hf;
			size_t index = hf(key) % _tables.size();
			Node* cur = _tables[index];
			KeyOfT kt;
			while (cur)
			{
				if (kt(cur->_data) == key)
				{
					return iterator(cur, this);
				}
				else
				{
					cur = cur->_next;
				}
			}
			return end();
		}



		pair<iterator,bool> Insert(const T& data)
		{
			KeyOfT kt;
			HashFunc hf;
			iterator ret = Find(kt(data));//判断是否已经存在重复值
			if (ret != end())
			{
				return make_pair(ret, false);
			}
			if (_tables.size() == _n)//载荷因子为1的时候需要进行扩容
			{
				size_t newCapacity = _tables.size() == 0 ? 10 : _tables.size() * 2;
				vector<Node*> newTables;
				newTables.resize(newCapacity);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						size_t index = hf(kt(cur->_data)) % newTables.size();
						Node* next = cur->_next;
						//头插
						cur->_next = newTables[index];
						newTables[index] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newTables);
			}
			size_t index = hf(kt(data)) % _tables.size();
			Node* newnode = new Node(data);
			newnode->_next = _tables[index];
			_tables[index] = newnode;
			_n++;
			return make_pair(iterator(newnode, this), true);
		}


	private:
		vector<Node*> _tables;//数组中存放的是节点的指针
		size_t _n = 0;
	};

完成了以上哈希表的改造之后就可以很简单的对哈希表进行封装来完成unordered_map和unordered_set的基本接口操作了。

unordered_map和unordered_set封装

unordered_map封装以及测试代码

	template<class K,class V,class HashFunc = Hash<K>>
	class Unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	private:
		LinkTable::HashTable<K, pair<K, V>, MapKeyOfT, HashFunc> _ht;
	public:
		typedef typename LinkTable::HashTable<K, pair<K,V>, MapKeyOfT, HashFunc>::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)
		{
			auto ret = _ht.Insert(make_pair(key, V()));
			return ret.first->second;
		}


	};

	void test_unordered_map()
	{
		Unordered_map<string, string> dict;
		dict.insert(make_pair("sort", "排序"));
		dict.insert(make_pair("string", "ַ字符串"));
		dict.insert(make_pair("map", "地图"));

		Unordered_map<string, string>::iterator it = dict.begin();
		while (it != dict.end())
		{
			cout << it->first << ":" << it->second << endl;
			++it;
		}
		cout << endl;
	}

运行结果如下：
在这里插入图片描述

unordered_set封装以及测试代码

	template<class K, class HashFunc = Hash<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	private:
		LinkTable::HashTable<K, K, SetKeyOfT, HashFunc> _ht;
	public:
		typedef typename LinkTable::HashTable<K, K, SetKeyOfT, HashFunc>::iterator iterator;
		iterator begin()
		{
			return _ht.begin();
		}

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

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

	};

	void test_unordered_set()
	{
		unordered_set<int> us;
		us.insert(4);
		us.insert(14);
		us.insert(34);
		us.insert(7);
		us.insert(24);
		us.insert(17);
		unordered_set<int>::iterator it = us.begin();
		while (it != us.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		unordered_set<string> uss;
		uss.insert("sort");
		uss.insert("hash");
	}

测试结果如下：
在这里插入图片描述

这样一来一个简单的unordered_map和unordered_set就用手写的哈希表来模拟实现完成了。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

用哈希简单封装unordered_map和unordered_set 的相关文章

随机推荐

  • linux驱动开发经验逐步积累2

    注 xff1a 笔记多少会有问题 xff0c 多多包涵 只是作为一个记录而已 1 cdev add的核心思想 cdev add允许添加一个字符设备到内核 xff0c 其核心是kobj map xff0c 也可以添加一个字符设备集合 xff0

  • 记录下在csdn那些年里所使用的博客座右铭

    xfeff xfeff 2016 xff0c 认认真真做事 xff0c 脚踏实地生活 路漫漫 xff0c 意不变 xff0c 求静 xff0c 求心 xff0c 求进 2017 xff0c 重新开始 xff0c 从心开始 xff0c 从家开

  • 多寄存器寻址指令ldmia/ldmib和ARM存储器访问指令——多寄存器存取

    多寄存器和堆栈寻址的用法 xff1a 多寄存器寻址 xff1a LDMIA xff0c LDMIB xff0c STMIA xff0c STMIB xff0c LDMDA xff0c LDMDB xff0c STMDA xff0c STMD

  • 使用CCS5.1导入的3.3工程编译错误lib/subdir_vars.mk:11: *** missing separator. Stop.

    D Program Files CCS5 1 ccsv5 utils bin gmake k all lib subdir vars mk 11 missing separator Stop TI方面说是CCS5 1的BUG xff0c 在

  • 写给我的2013

    前沿 xff1a 代码看的累了 xff0c 在新的一年终于可以找点时间来回忆我的2013 想着要写点什么 xff0c 可是又没有什么可以写 因为回忆无非就是夹杂着些许痛苦与欢乐 写给我的2013 家 生活 xff1a 2013年 xff0c

  • 写给我的2014——也写给我即将逝去的研究生生涯

    前言 xff1a 2014 1在写着代码的时写下了回忆 xff0c 2015 1在码着论文的时候开始写起消逝的2014 细细回忆 xff0c 真是又是那句老话 xff0c 时间过得真快 xff0c 1年过去了 xff1b 更快的是竟然都要毕

  • Oracle官网下载历史版本软件

    一 分享一个Oracle官网下载各种软件的网址 https edelivery oracle com osdc faces SoftwareDelivery 这个网址是Oracle官网专门下载软件的地址 xff0c 下载软件过程如下 xff

  • 技术盘点：消息中间件的过去、现在和未来

    作者介绍 xff1a 林清山 xff08 花名 xff1a 隆基 xff09 操作系统 数据库 中间件是基础软件的三驾马车 xff0c 而消息队列属于最经典的中间件之一 xff0c 已经有30多年的历史 其发展主要经历了以下几个阶段 xff

  • C语言小游戏——扫雷

    上次我们用C语言实现了一个三子棋的小游戏 xff0c 这次我们同样使用C语言来实现扫雷这个经典的小游戏 首先 xff0c 在开始编程之前还是先整理一下我们的编程思路 xff1a 一 菜单打印 xff1a 和上次实现三子棋的操作类型 xff0

  • 缺省参数讲解

    缺省参数 缺省参数定义缺省参数分类1 全缺省参数 xff1a 2 半缺省参数 xff1a 注意事项 缺省参数定义 缺省参数作为C 43 43 不同于C语言新增的一种语法功能 xff0c 他的作用是在声明或定义函数时为参数指定的一个默认值 x

  • Linux下的权限

    Linux下的权限 用户分类文件类型具体文件类型 基本权限root用户 xff1a 修改权限使用方法 xff1a 通过8进制数字更改权限 对于文件 xff0c 权限的意义读权限写权限运行权限 对于目录权限的意义 更改文件拥有者 所属组cho

  • 类和对象初识

    类和对象初识 类的由来类的定义类的特性封装访问限定符 类的定义方法声明和定义全部放在类体中声明放在 h文件中 xff0c 类的定义放在 cpp文件中类对象的大小 内存对齐规则 类的由来 在C语言中我们有自定义类型的struct xff0c

  • 类的默认成员函数——上

    类的默认成员函数 默认成员函数构造函数构造函数由来构造函数特征默认构造函数特征总结 xff1a 析构函数特征 拷贝构造默认拷贝构造总结 C 43 43 中如果一个类中什么成员都没有 xff0c 简称为为空类 空类中什么都没有吗 xff1f

  • 进程控制块

    进程控制模块 查看进程PCB内部构成标识符ppid 状态优先级查看优先级方式优先级确定原理调整优先级nice值范围 程序计数器内存指针上下文数据时间片上下文数据 I xff0f O状态信息记账信息 查看进程信息 进程 xff1a 加载到内存

  • 模拟实现stack/queue

    模拟实现stack queue stack大体框架接口函数实现 queue大体框架接口函数 stack 之前的博客中介绍了栈和队列的相关功能 xff0c 这里我们模拟实现一个栈和队列 大体框架 由于栈的特殊性 xff0c 栈不支持迭代器访问

  • 进程间通信——命名管道

    命名管道 命名管道定义命名管道创建命令行上创建程序内创建 命名管道间通信匿名管道和命名管道区别 命名管道定义 上一篇博客中介绍了匿名管道的用法以及他的特点 xff0c 但是它存在一定的限制 xff0c 例如他只能在两个具有公共祖先的进程间进

  • Altium Designer一些好用的系统设置

    AD软件系统设置 系统参数设置GeneralNavigationDesign InsightFile Types 原理图参数设置GeneralCross Overs位号自动增加设置原理图大小设置 Graphical Editing单一 39

  • 哈希——开散列

    哈希 开散列 开散列概念开散列的简单实现HashFunc开散列的构成插入去重扩容插入 测试 开散列概念 上一篇博客中介绍了解决哈希冲突的一种方法 xff1a 闭散列 但是闭散列中不管是线性探测还是二次探测 xff0c 解决哈希冲突问题都不够

  • 开发者七问七答：什么是产品化？

    简介 xff1a 之前参加了企业智能部门如何做产品化的讨论 xff0c 大家对产品化的定义和过程都有各自不同的见解 我觉得这个话题其实可以扩展下 xff0c 想站在一个开发人员的视角尝试探讨一下产品化 下面以自问自答的方式来展开 1 当我们

  • 用哈希简单封装unordered_map和unordered_set

    哈希表的改造 哈希表的改造unordered map和unordered set的基本结构哈希表改造节点结构体迭代器哈希表改造 unordered map和unordered set封装unordered map封装以及测试代码unorde

热门标签