【C++进阶】用哈希实现unordered_set和unordered_map的模拟

🪐🪐🪐欢迎来到程序员餐厅💫💫💫

          主厨：邪王真眼

主厨的主页：Chef‘s blog  

所属专栏：c++大冒险
 

总有光环在陨落，总有新星在闪烁

前言：

        之前我们学完红黑树后对他进行了改造，使之成为map和set的底层容器，今天我们则要把哈希表进行修改并以此为基础实现unordered_set和unordered_map

一.哈希桶（修改版）

1.1.节点

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

注意事项：

  • 数据类型是T，因为要同时适用unordered_set（存储键值）和unordered_map（存储键值对）

类比咱们用红黑树写map和set时的做法。

1.2.迭代器

哈希表的迭代器类型是单向迭代器，没有反向迭代器

1.2.1成员变量

template<class K, class T, class KeyOfT, class HF>
class HashTable;
template<class K,class T, class Ref,class Ptr,class KeyOfT, class HF>
struct HashIterator
{
	typedef HashNode<T> Node;
	typedef HashIterator<K, T, Ref, Ptr, KeyOfT, HF> self;
	typedef HashIterator<K, T, T&, T*, KeyOfT, HF> iterator;
	typedef HashTable<K, T, KeyOfT, HF> HT;
	Node* _node;
	HT* _ht;
};

注意事项：

  •  增加了_ht成员变量，因为在重载++时，当一条单链表走到空，则需要走到下一个哈希桶的位置，需要通过哈希表的vector成员找下一个位置 
  • 因为HashTable是在后面实现的，所以我们要先写一个声明

1.2.2简单函数实现

HashIterator(Node*&node=nullptr,Node*&ht=nullptr)
	:_node(node)
	,_ht(ht)
{}
HashIterator(const iterator&it)
	:_node(it._node)
	, _ht(it._ht)
{}
Ref& operator*()const
{
	return _node->_data;
}
Ptr& operator->()const
{
	return &(_node->_data);
}
bool operator==(const self&se)
{
	return _node == se._node;
}
bool operator!=(const self& se)
{
	return _node != se._node;
}

注意事项：

  • 拷贝构造函数可以以普通迭代器拷贝出普通迭代器（普通迭代器调用时）以及const迭代器（const迭代器调用时）

1.2.3operator++

self& operator++()
{
	Node* node = _node;
	if (node->_next)
	{
		_node = node->_next;
		return *this;
	}
	else
	{
		KeyOfT kot;
		size_t hash = HF(kot(_node->_data)) % _ht->_tables.size()+1;
		for (hash; hash < _ht->_tables.size(); hash++)
		{
			if (_ht->tables[hash])
			{
				_node = _ht->tables[hash];
				return *this;
			}

		}
		_node = nullptr;
		return *this;
	}
}
self operator++(int)
{
	self new_self=*this;
	(*this)++;
	return new_self;
}

思路：

  1. 前置++的思路： 
    1. 下一个结点不为空，则跳到下一位
    2. 下一个结点为空，则先取模算出哈希地址，再往后探测不为空的哈希桶 
  2. 后置++：复用前置++，返回临时对象

1.3哈希桶本身

1.3.1成员变量

template<class K, class T, class KeyOfT, class HF>
class HashTable
{
	template<class K, class T, class Ref, class Ptr, class KeyOfT, class HF>
	friend struct HashIterator;
	typedef HashNode<T> Node;
public:
protected:
	vector<Node*> _tables;
	size_t _size = 0;//有效数据个数
};

注意事项：

  1. 迭代器要访问哈希桶的私有成员，所以要声明友元
  2. 模板参数KeyOfT是为了从类型T中取出键值
  3. 模板参数HF即是HashFunc，哈希函数，用于辅助键值转化为整型进行取模操作

1.3.2构造函数和析构函数

HashTable(size_t size = 10)
{
	_tables.resize(size);
}
~HashTable()
{
	for (auto hash_node : _tables)
	{
		while (hash_node)
		{
			Node* new_node = hash_node->_next;
			delete hash_node;
			hash_node = new_node;
		}
	}
}

1.3.3 begin和end 

typedef HashIterator< K,T, T&, T*,  KeyOfT,  HF> iterator;
typedef HashIterator< K, T, const T&, const T*,  KeyOfT,  HF> const_iterator;
iterator begin()
{
	for (size_t i = 0; i < _tables.size(); i++)
		if (_tables[i])
			return iterator(_tables[i], this);
	return iterator(nullptr, this);
}
const_iterator begin()const
{
	for (size_t i = 0; i < _tables.size(); i++)
		if (_tables[i])
			return const_iterator(_tables[i], this);
	return const_iterator(nullptr, this);
}
iterator end()
{
	return iterator(nullptr, this);
}
const_iterator end()
{
	return const_iterator(nullptr, this);
}

注意事项：

  1. begin返回最开始不为空的哈希桶的迭代器，而不是最开始的哈希桶的迭代器
  2. end返回空迭代器
  3. 构造迭代器需要传入哈希表本身的地址，这里直接传this指针即可

1.3.4Find函数 

iterator Find(const K&key)
{
	HF hf;
	KeyOfT kot;
	size_t hash = hf(key) % _tables.size();
	Node* cur = _tables[hash];
	while (cur)
	{
		if (kot(cur->_data) == key)
			return iterator(cur,_tables);
		cur = cur->_next;
	}
	return iterator(nullptr,_tables);
}

注意事项：

  1. 返回值类型是迭代器
  2. 运用两个仿函数，，kot负责获取存储的键值，hf作为哈希函数把键值key转整型

1.3.5   Insert函数 

	pair<iterator,bool> Insert(T& data)
{
	KeyOfT kot;
	HF hf;
	iterator it = Find(kot(data));
	if (it._node)
	{
		return make_pair(it, false);
	}
	if (_size == _tables.size())
	{
		vector<Node*> new_tables(_size * 2);
		for (auto node : _tables)
		{
			while (node)
			{
				Node* next = node->_next;
				size_t hash = hf(kot(node->_data)) % new_tables.size();
				node->_next = new_tables[hash];
				new_tables[hash] = node;
				node = next;
			}
		}
		_tables.swap(new_tables);
	}
	
	size_t hash = hf(kot(data)) % _tables.size();
	Node* cur = _tables[hash];
	Node* p(data);
	p->_next = cur;
	_tables[hash] = p;
	_size++;
	return make_pair(iterator(p,this),true);
}

注意事项：

  1. 返回值类型是pair，第一个参数为迭代器，第二个参数为布尔值（记录是否插入成功）
  2. 运用两个仿函数，，kot负责获取存储的键值，hf作为哈希函数把键值key转整型

1.3.6Erase函数 

	bool Erase(const K& key)
{
	HF hf;
	KeyOfT kot;
	size_t hash = hf(key) % _tables.size();
	Node* cur = _tables[hash];
	Node* pre = nullptr;
	while (cur)
	{
		if (kot(cur->data) == key)
			break;
		pre = cur;
		cur = cur->_next;
	}
	if (cur == nullptr)
		return false;
	_size--;
	if (pre == nullptr)
		_tables[hash] = cur->_next;
	else
		pre->_next = cur->_next;
	delete cur;
	return true;
}

二、unordered_set

2.1成员变量及仿函数 

template<class K,class HF=HashFunc<K>>
class unordered_set
{
public:
	struct SetKeyOfT
	{
		K& operator()(const K& key)
		{
			return key;
		}
	};
protected:
	HashTable<K, K, SetKeyOfT, HF> _hf;
};

注意事项：

  •  1.这里的数据存储类型就是键值Key本身，所以SetKeyOfT直接返回key就行
  • 2.哈希函数不是固定的，可以根据需求自己进行实现并传到给定模板参数中

2.2 begin和end 

typedef typename HashTable<K, K, SetKeyOfT, HF>::iterator iterator;
typedef typename HashTable<K, K, SetKeyOfT, HF>::const_iterator const_iterator;
iterator begin()
{
	return _ht.begin();
}
const_iterator begin()const
{
	return _ht.begin();
}
iterator end()
{
	return _ht.end();
}
const_iterator end()const
{
	return _ht.end();
}

注意事项：

  • 在C++中，编译器默认iterator为变量名，如果作为类型名，需要在前面加上typename加上typename关键字。
  • unordered_set中存储的键值key不允许修改，所以其普通迭代器和const迭代器均为哈希表的const迭代器
  • 我们称set的begin为A，哈希的begin为B，A的实现是对B的调用，在A的参数是普通迭代器时，B也是普通迭代器，B的返回值也是普通迭代器，但A的返回值是const迭代器，所以这里需要用普通迭代器创建一个const迭代器的临时变量，这就用到之前写的拷贝构造函数了。

2.3Find 

wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw== 
iterator Find(const K&key)
{
	return _ht.Find(key);
}

注意事项： 

  •  此时也有从普通迭代器到const迭代器的转换 

2.4Insert

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

注意事项： 

  1. 函数形参类型是K
  2. 此时也有从普通迭代器到const迭代器的转换

 2.5Erase

bool Erase(const K& key)
{
	return _ht.Erase(key);
}

三、unordered_map

unordered_map和unordered_set的实现有众多相似之处，

3.1 成员变量与仿函数

template<class K,class V,class HF=HashFunc<K>>
class unordered_map
{
	struct MapKeyOfT
{
	const K& operator()(const pair<K, V>&kv)
	{
		return kv.first;
	}
	};
protected:
	HashTable<K, pair<const K, V>, MapKeyOfT, HF> _ht;
};

注意事项：

  • 1.这里节点存的数据类型是pair<K,V>,我们的MapKeyOfT作用是返回其中的键值key 
  • 2.哈希函数不是固定的，可以根据需求自己进行实现并传到给定模板参数中

3.2 begin和end

typedef typename HashTable<K, pair<K,V>, MapKeyOfT, HF>::iterator iterator;
typedef typename HashTable<K, pair<K,V>, MapKeyOfT, HF>::const_iterator const_iterator;
iterator begin()
{
	return _ht.begin();
}
const_iterator begin()const
{
	return _ht.begin();
}
iterator end()
{
	return _ht.end();
}
const_iterator end()const
{
	return _ht.end();
}

注意事项：

  1. 加上typename关键字，编译器才能识别类型
  2. unordered_map不允许修改key，故普通迭代器和const的pair中的K都要加上const修饰，但是允许修改存储的data，所以普通和const迭代器一一对应(好好想想这点map和set的处理差异)

3.3 find

iterator Find(const K& key)
{
	return _ht.Find(key);
}

3.4Insert

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

注意事项：

  • 形参类型是键值对而不是键值

3.5 operator[ ]

V& operator[](const& K key)
{
	return (*(_ht.Insert(make_pair(key, V()))).first).second;
}
//或者你也可以这么写
V& operator[](const K& key)
{
	pair<iterator, bool> cur = insert(make_pair(key, V()));
	return cur.first->second;
}

注意事项：

  1.  利用operator[]进行插入和修改操作是很方便的，所以要学会灵活运用哦 
  2. 返回值是value的引用，我们可以直接进行修改 

3.6 Erase 

bool Erase(const K& key)
{
	return _ht.Erase(key);
}

 

 如果你对该系列文章有兴趣的话不妨点个关注哦，我会持续更新相关博客的

🥰创作不易，你的支持对我最大的鼓励🥰

🪐~ 点赞收藏＋关注 ~🪐

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/527142.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

网络安全 | 什么是区块链？

网络安全 | 什么是区块链？

关注WX&#xff1a;CodingTechWork 概述 定义 区块链是一个共享的、不可篡改的账本&#xff0c;旨在促进业务网络中的交易记录和资产跟踪流程。资产可以是有形的&#xff08;如房屋、汽车、现金、土地&#xff09;&#xff0c;也可以是无形的&#xff08;如知识产权、专利、…
阅读更多...
leetcode代码记录（最长连续递增序列

leetcode代码记录（最长连续递增序列

目录 1. 题目&#xff1a;2. 我的代码&#xff1a;小结&#xff1a; 1. 题目&#xff1a; 给定一个未经排序的整数数组&#xff0c;找到最长且 连续递增的子序列&#xff0c;并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r&#xff08;l < r&#xff09;确定…
阅读更多...
极市平台 | 综述：一文详解50多种多模态图像融合方法

极市平台 | 综述：一文详解50多种多模态图像融合方法

本文来源公众号“极市平台”&#xff0c;仅用于学术分享&#xff0c;侵权删&#xff0c;干货满满。 原文链接&#xff1a;综述&#xff1a;一文详解50多种多模态图像融合方法 0 极市导读 本工作总结了50篇论文中Lidar和camera的多模态融合的一些概念方法。笔者结合原文以及自…
阅读更多...
变电站设计综合应用软件-光纤回路设计解决方案

变电站设计综合应用软件-光纤回路设计解决方案

产品概述 智能变电站光纤回路设计软件——让您的光纤设计之旅变得轻松而高效！ 光纤回路设计作为智能变电站的关键环节，对电网的稳定运行起着至关重要的作用。为了让您的光纤设计之路更加顺畅，我们隆重推出了这款智能变电站光纤回路设计软件。这款软件以其简单易用的…
阅读更多...
SpringBoot学习笔记-S2

SpringBoot学习笔记-S2

1. SpringBoot中的常见注解 RequestBody&#xff1a;使SpringMVC框架可自动读取请求体里面的JSON格式的数据&#xff0c;转换成map类型的集合对象RestController&#xff1a;开发RESTful API 时使用&#xff0c;等价于ResponseBody Controller。RestController和Controller的…
阅读更多...
10分钟上手：MySQL8的Json格式字段使用总结干货

10分钟上手：MySQL8的Json格式字段使用总结干货

一、关于效率和适用范围 尽管官方承诺Json格式字段采用了空间换时间的策略&#xff0c;比Text类型来存储Json有大幅度的效率提升。但是Json格式的处理过程仍然效率不及传统关系表&#xff0c;所以什么时候用Json格式字段尤为重要。 只有我们确定系统已经能精确定位到某一行&am…
阅读更多...
红外疼痛医学分会成立大会暨首届学术交流会即将盛大开幕

红外疼痛医学分会成立大会暨首届学术交流会即将盛大开幕

2024年4月7日&#xff0c;中国中医药研究促进会官网发布“关于召开红外疼痛医学分会成立大会暨首届学术交流会的第三轮通知”通知&#xff0c;大会开幕在即&#xff0c;这充分显示了官方对此次活动的高度重视。 本次大会将于 2024年4月19日至21日在重庆海兰云天海琴酒店隆重举行…
阅读更多...
memcached集群

memcached集群

一、介绍 memcache本身没有像redis所具备的数据持久化功能&#xff0c;但是可以通过做集群同步的方式&#xff0c;让各memcache服务器的数据进行同步&#xff0c;从而实现数据的一致性&#xff0c;即保证各memcache的数据是一样的&#xff0c;即使有任何一台memcache发生故障&…
阅读更多...
Linux addr2line介绍

Linux addr2line介绍

打开linux调试选项 嵌入式 linux 经常要编译 linux 内核&#xff0c;默认情况下编译出的内核镜像是不带调试信息的&#xff0c;这样&#xff0c;当内核 crash 打印 PC 指针和堆栈信息时&#xff0c;我们需要反汇编来确认出错位置&#xff0c;不直观。 如果内核开启了调试选项&…
阅读更多...
K8s学习十（高级调度）

K8s学习十（高级调度）

高级调度 CronJob计划任务 在 k8s 中周期性运行计划任务&#xff0c;与 linux 中的 crontab 相同注意点&#xff1a;CronJob 执行的时间是 controller-manager 的时间&#xff0c;所以一定要确保 controller-manager 时间是准确的cron表达式如下&#xff1a; 配置如下&#x…
阅读更多...
7.1.4 Selenium 爬取京东商品信息实战

7.1.4 Selenium 爬取京东商品信息实战

目录 1、实战内容 2、思路 3、分析 url 4、开始操作 1、得到 Cookies 2、访问页面&#xff0c;得到 response 3、解析页面 4、存入 MySQL 5、1-3步总代码 1、实战内容 爬取京东笔记本电脑商品的信息(如&#xff1a;价格、商品名、评论数量)&#xff0c;存入 MySQL 中…
阅读更多...
字符串匹配算法之BF与KMP算法

字符串匹配算法之BF与KMP算法

目录 BF算法(暴力匹配算法) KMP算法 核心思想&#xff1a; next数组 next数组的优化 BF算法(暴力匹配算法) #include <assert.h> int BF(const char* str, const char* sub) {assert(str ! NULL && sub ! NULL);if (str NULL || sub NULL){return -1;}int…
阅读更多...
962: 括号匹配问题

962: 括号匹配问题

【学习版】 【C语言】 【C】 #include<iostream>class MyStack { public:struct Node {char val;Node* prev;Node* next;Node(char x) :val(x), prev(NULL),next(NULL) {};};MyStack() {base new Node(0);top base;}bool empty() {return top base;}void push(int …
阅读更多...
C++类与对象下（个人笔记）

C++类与对象下（个人笔记）

类与对象下 1.构造函数补充1.1构造函数体赋值1.2初始化列表1.3explicit关键字 2.static成员2.1特性 3.友元3.1友元函数3.2友元类 4.内部类5.匿名对象6.拷贝对象的一些优化7.笔试题 1.构造函数补充 1.1构造函数体赋值 在创建对象时&#xff0c;编译器通过调用构造函数&#xf…
阅读更多...
在数字化转型的背景下，如何构建高效的数据资产管理体系？

在数字化转型的背景下，如何构建高效的数据资产管理体系？

在数字化转型的大潮中&#xff0c;数据已成为企业创新发展的重要驱动力。如何高效地管理这些数据资产&#xff0c;不仅关系到企业的日常运营&#xff0c;更直接决定了企业能否在激烈的市场竞争中脱颖而出。对于企业管理者或首席信息官&#xff08;CIO&#xff09;而言&#xff…
阅读更多...
大学英语ab级题搜题软件？分享7个支持答案和解析的工具 #笔记#其他

大学英语ab级题搜题软件？分享7个支持答案和解析的工具 #笔记#其他

合理利用学习辅助工具和资料&#xff0c;可以帮助大学生更好地组织学习内容、掌握知识点和提升学术水平。 1.智能翻译官 这是一款多语言在线翻译神器&#xff0c;除了最基础的英语以外&#xff0c;还支持日语、德语、俄语、法语等几十种语言文本翻译和拍照翻译&#xff0c;并…
阅读更多...
一文搞懂从爬楼梯到最小花费（力扣70,746）

一文搞懂从爬楼梯到最小花费（力扣70,746）

文章目录 题目前知动态规划简介动态规划模版 爬楼梯一、思路二、解题方法三、Code 使用最小花费爬楼梯一、思路二、解题方法三、Code 总结 在计算机科学中&#xff0c;动态规划是一种强大的算法范例&#xff0c;用于解决多种优化问题。本文将介绍动态规划的核心思想&#xff0c…
阅读更多...
积木-蓝桥每日真题

积木-蓝桥每日真题

0积木 - 蓝桥云课 (lanqiao.cn) 题目描述 小明用积木搭了一个城堡。 为了方便&#xff0c;小明在搭的时候用的是一样大小的正方体积木&#xff0c;搭在了一个n行m列的方格图上&#xff0c;每个积木正好占据方格图的一个小方格。 当然&#xff0c;小明的城堡并不是平面的&#x…
阅读更多...
2014最新AI智能系统ChatGPT网站源码+Midjourney绘画网站源码+搭建部署教程文档

2014最新AI智能系统ChatGPT网站源码+Midjourney绘画网站源码+搭建部署教程文档

一、文章前言 SparkAi创作系统是基于ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统&#xff0c;支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美&#xff0c;那么如何搭建部署AI创作ChatGPT&#xff1f;小编这里写一个详细图文教程吧。已支持…
阅读更多...
2.SpringBoot利用Thymeleaf实现页面的展示

2.SpringBoot利用Thymeleaf实现页面的展示

什么是Thymeleaf&#xff1f; Thymeleaf是一个现代服务器端Java模板引擎&#xff0c;适用于Web和独立环境&#xff0c;能够处理HTML&#xff0c;XML&#xff0c;JavaScript&#xff0c;CSS甚至纯文本。 Thymeleaf的主要目标是提供一种优雅且高度可维护的模板创建方式。为实现这…
阅读更多...
最新文章

Copyright @ 2022~2023