哈希(hash)——【C++实现】

2023-09-19 11:09:11

在这里插入图片描述

本章gitee代码仓库：Hash

文章目录

💐1. 哈希概念

我们对元素进行搜索有几种方式：

  1. 暴力查找，直接遍历元素，时间复杂度为O(N)

    image-20230917101056152

  2. 二分查找，时间复杂度为O(logN)

    但二分查找有2个弊端：

    • 必须为有序
    • 增删查改不方便

    这两个弊端导致二分查找只是一个理想的查找方式，并不是很现实

    image-20230917101700713

  3. 平衡搜索树，增删查改的时间复杂度都是O(logN)，总体性能都很不错

    image-20230917101710006

这些结构中的元素关键码和存储位置都没有对应的关系，而有一种方法名为哈希（也叫散列），它提供了一种与这些完全不同的存储和查找方式，即将存储的值和存储的位置建立出一个对应的函数关系。

有一种排序名为计数排序，将不同的值映射到对应的位置，这本质上就是哈希

不了解的可以看下这篇文章——非比较排序——计数排序

我们的通讯录，按照名字的首字母进行分类，本质也是哈希

image-20230917103230972

以数组{1,8,6,3}为例，假设hashi = key % 6 ，那则有如下对应关系

image-20230917104706750

这样就能通过取模直接定位到该元素的位置

但是如果进行插入元素，例如插入2，2%6=2，这就会导致和8的位置一样

🌻2. 哈希冲突

不同的关键字通过哈希函数计算出了相同的地址，值和位置出现了多对一的关系，这种线性称之为哈希冲突（哈希碰撞）。

解决方案：

  1. 选择合理的哈希函数
  2. 拟定冲突方案

🌼3. 哈希函数

出现哈希碰撞的原因之一可能就是哈希函数设计的不合理

🌸3.1 哈希函数设计原则

  • 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须是[0,m-1]之间
  • 哈希函数计算出来的地址能均匀分布在整个空间中
  • 哈希函数较为简单，能在较短时间内计算出结构

🌸3.2 常见哈希函数

  1. 直接定址法（值的范围集中）

    取某个线性函数作为散列的地址：Hash(key) = A*key + B

  2. 除留余数法（值的范围分散）

    设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，

    按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

🪴4. 哈希冲突解决方案

🌱4.1 闭散列——开放定址法

如果当前位置被占用，按照规则找到下一个位置（占用其他元素的位置）

image-20230917112017514

我们删除元素通常都不是直接删除，而采用覆盖的方式，而这里无法很好的覆盖

例如我们删除元素1，如果挪动后面的数据，这就导致映射关系全部乱了，如果不直接覆盖，那么之后又元素插入进来的时候，1这个位置还是有元素的，无法插入

所有这里采用状态的方式进行标记：

  • 存在——EXIST
  • 空——EMPTY
  • 删除——DELETE

🌿4.11 负载因子

哈希表定义了一个载荷因子：α = 填入表中元素个数 / 哈希表的长度，这个是表示哈希表装满长度的标志因子

如果负载因子设计的大，那么哈希冲突的概率就越大（空间利用率高）

如果负载因子设计的小，那么哈希冲突的概率就越小（空间利用率低）

对于开放定址法，经过测算，负载因子应该控制在0.7 ~ 0.8，下面代码实现采用0.7

🌿4.12 字符串哈希算法

面对字符串的哈希函数，我们采用BKDRHash函数

有兴趣可查看此篇文章——各种字符串Hash函数

🌿4.13 代码实现

template<class K>
struct DefaultHashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
//模板特化
template<>
struct DefaultHashFunc<string>
{
	size_t operator()(const string& str)
	{
		//BKDR hash
		size_t hash = 0;
		for (auto ch : str)
		{
			hash *= 131;
			hash += ch;
		}
		return (size_t)str[0];
	}
};


//开放定址法
namespace open_address
{
	enum STATE
	{
		EXIST,
		EMPTY,
		DELETE
	};

	template<class K, class V>
	struct HashDate
	{
		pair<K, V> _kv;
		STATE _state = EMPTY;
	};

	template<class K, class V, class HashFunc = DefaultHashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_table.resize(10);	//预先开好10个空间
		}

		bool Insert(const pair<K, V>& kv)
		{

			if (Find(kv.first))
				return false;

			//扩容
			if (_n * 10 / _table.size() >= 7)	//设负载因子为0.7
			{
				size_t newSize = _table.size() * 2;
				//扩容之后关系改变，需要重新映射
				HashTable<K, V> newHT;
				newHT._table.resize(newSize);

				//旧表数据插入到新标
				for (size_t i = 0; i < _table.size(); i++)
				{
					if (_table[i]._state == EXIST)
					{
						newHT.Insert(_table[i]._kv);
					}
				}
				//新标和旧表交换
				_table.swap(newHT._table);
			}

			//不能取模capacity，虽然空间有，但访问还是要看size的大小，不然会发生越界
			HashFunc hf;
			size_t hashi = hf(kv.first) % _table.size();
			while (_table[hashi]._state == EXIST)
			{
				//线性探测
				hashi++;
				hashi %= _table.size();
			}
			_table[hashi]._kv = kv;
			_table[hashi]._state = EXIST;
			++_n;
			return true;
		}

		HashDate<const K, V>* Find(const K& key)
		{
			HashFunc hf;
			size_t hashi = hf(key) % _table.size();
			while (_table[hashi]._state != EMPTY)
			{
				if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key)
				{
					return (HashDate<const K, V>*) & _table[hashi];
				}
				++hashi;
				hashi %= _table.size();
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			HashDate<const K, V>* ret = Find(key);
			if (ret)
			{
				ret->_state = DELETE;
				--_n;
				return true;
			}
			return false;
		}

	private:
		vector<HashDate<K, V>> _table;	//哈希表
		size_t _n = 0;	//有效元素个数
	};
}

线性探测会导致一片拥堵，为此还有一种方法为二次探测

例如线性探测是：

hashi = key % n;
//如果有值了 i>=0
hashi+=i;

而二次探测则是：

hashi = key % n;
//如果有值 i>=0
hashi + i^2;

这样就能在一定程度上减少拥堵

🌱4.2 开散列——哈希桶

开放定址法的缺陷就是冲突会相互影响。而哈希桶的做法是，设置一个指针数组，如果发现冲突，则内部消化

image-20230917141822713

这里桶的结构其实就是链式结构，对每个桶的管理就相当于对于链表的管理，下面的代码采用的是单链表

这里也是需要进行扩容，如果不扩容，就会导致在某种情况下，桶越来越长，这样查找数据就变成了对链表数据的查找，时间复杂度为O(N)，所以还是需要进行扩容。

这里的负载因子可以适当放大一点，一般负载因子控制在1，平均下来每个桶都有数据

🌿4.21 代码实现

这里的桶因为是自定义的链式结构，所以需要我们自己写拷贝构造和析构函数

//哈希桶
namespace hash_bucket
{
	template<class K, class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode<K,V>* _next;

		HashNode(const pair<K, V>& kv)
			:_kv(kv)
			,_next(nullptr)
		{}
	};
	
	template<class K,class V,class HashFunc = DefaultHashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;

	public:
		HashTable()
		{
			_table.resize(10, nullptr);
		}

		~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;
			}
		}
		//拷贝构造
		HashTable(const HashTable& ht)
		{
			_table.resize(ht._table.size(), nullptr);
			HashFunc hf;
			for (size_t i = 0; i < ht._table.size(); i++)
			{
				Node* cur = ht._table[i];
				while (cur)
				{
					Node* newNode = new Node(cur->_kv);
					size_t hashi = hf(cur->_kv.first) % ht._table.size();

					//头插
					newNode->_next = _table[hashi];
					_table[hashi] = newNode;

					cur = cur->_next;
				}
			}
			_n = ht._n;
		}

		void Print()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				printf("[%d]->", (int)i);
				Node* cur = _table[i];
				while (cur)
				{
					cout << cur->_kv.first << "->";
					cur = cur->_next;
				}
				cout << "NULL" << endl;
			}
			cout << endl;
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;

			HashFunc hf;
			//扩容 -- 扩容的时候会稍微慢一点 ---^(扩容)-----^(扩容)----------^(扩容)-----.....
			//这里的扩容不能和开放定址法一样采用将旧表元素重新插入新表
			//因为这里涉及到开节点，新表开新节点，旧表释放旧节点，浪费
			if (_n == _table.size())
			{
				size_t newSize = _table.size() * 2;
				vector<Node*> newTable;
				newTable.resize(newSize,nullptr);

				//遍历旧表，将节点牵过来
				for (size_t i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while (cur)
					{
						Node* next = cur->_next;
						//头插到新表
						size_t newHashi = hf(cur->_kv.first) % newSize;
						cur->_next = newTable[newHashi];
						newTable[newHashi] = cur;

						cur = next;
					}
					_table[i] = nullptr;
				}
				_table.swap(newTable);
			}

			size_t hashi = hf(kv.first) % _table.size();
			//头插
			Node* newNode = new Node(kv);
			newNode->_next = _table[hashi];
			_table[hashi] = newNode;

			++_n;
			return true;
		}

		Node* Find(const K& key)
		{
			HashFunc hf;
			size_t hashi = hf(key) % _table.size();
			Node* cur = _table[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			HashFunc hf;
			size_t hashi = hf(key) % _table.size();
			Node* prev = nullptr;
			Node* cur = _table[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					//头删
					if (prev == nullptr)
					{
						_table[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					--_n;
					delete cur;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}


	private:
		vector<Node*> _table;	//指针数组
		size_t _n = 0;	//有效元素
	};
}

本次参考了《数据结构（用面向对象方法与C++语言描述）》，详细的内容可以参考此书

那么本期的分享就到这里咯，我们下期再见，如果还有下期的话。

更多推荐

国产化系统中遇到的视频花屏、卡顿以及延迟问题的记录与总结

目录1、国产化系统概述1.1、国产化操作系统与国产化CPU1.2、国产化服务器操作系统1.3、当前国产化系统的主流配置2、视频解码花屏与卡顿问题2.1、视频解码花屏2.2、视频解码卡顿2.3、关于I帧和P帧的说明3、国产显卡处理速度慢导致图像卡顿问题3.1、视频延时和卡顿原因分析3.2、SDL2库跑在景嘉微国产显卡上效

亚马逊、敦煌网、国际站自养号测评需要哪些资源与技术门槛？

测评服务商说的天花乱坠，实际真假难辨，FB等社交软件自找测评犹如大海捞针。产品都要上架了，靠谱的测评服务还是没找到，亚马逊测评求人不如求己，今天来教你怎么养一批安全、可控的买家号。亚马逊等跨境平台测评自养号需要用到哪些资源呢？1、养号系统及软件2、代理IP资源3、收货地址及注册资料4、外币信用卡及礼品卡5、邮箱及手机号

当量因子法、InVEST、SolVES模型等多技术融合在生态系统服务功能社会价值评估中的应用及论文写作、拓展分析

生态系统服务是人类从自然界中获得的直接或间接惠益，可分为供给服务、文化服务、调节服务和支持服务4类，对提升人类福祉具有重大意义，且被视为连接社会与生态系统的桥梁。自从启动千年生态系统评估项目（MillenniumEcosystemAssessment，MA）以来，生态系统服务成为学术界的研究热点，其中在生态系统服务功能

学习笔记|模数转换器|ADC原理|STC32G单片机视频开发教程（冲哥）|第十七集：ADC采集

文章目录1.模数转换器（ADC）是什么？手册说明：2.STC32G单片机ADC使用原理19.1.1ADC控制寄存器（ADC_CONTR)19.1.2ADC配置寄存器（ADCCFG)19.1.4ADC时序控制寄存器（ADCTIM）19.3ADC相关计算公式3.编写最简单的ADC采集代码（查询&中断）P10的引脚去获取一个

4、ARM异常处理

一、异常处理1、异常概念处理器在正常执行程序的过程中可能会遇到一些不正常的的事件发生，这时处理器就要将当前的程序暂停下来转去处理这个异常的事件，异常事件完成后再返回到之前被异常打断的点继续执行2、异常处理机制不同的处理器对异常的处理流程大体相同，但是不同的处理器在具体实现的机制上有所不同。比如处理器遇到哪些事件认为是异

【Flink实战】玩转Flink里面核心的Source Operator实战

🚀作者：“大数据小禅”🚀文章简介：【Flink实战】玩转Flink里面核心的SourceOperator实战🚀欢迎小伙伴们点赞👍、收藏⭐、留言💬目录导航Flink的API层级介绍SourceOperator速览Flink预定义的Source数据源案例实战Flink自定义的Source数据源案例-订单来源实战F

Android UT开发简介

一、概述AndroidUT（UnitTesting）开发是指在Android应用程序中进行单元测试的开发过程。单元测试是一种软件测试方法，用于测试应用程序中的最小可测试单元（通常是函数或方法）的正确性。AndroidUT开发的主要目标是确保应用程序的各个单元在不同情况下能够按照预期正确运行。通过编写、运行和维护单元测试

免费、安全、可靠！一站式构建平台 ABS 介绍及实例演示 | 龙蜥技术

编者按：操作系统是一个大的软件集合，成百上千个软件之间有相互调用、相互依赖等各种复杂的关联关系，所以统一的软件包格式，能够更友好地管理、定义这些复杂关系。今天，龙蜥社区基础设施Contributor单凯伦带大家了解龙蜥社区官方构建平台ABS，熟悉AnolisOS软件包、镜像构建流程以及ABS未来规划等。本文整理自龙蜥大

【Windows 11】安装 Android子系统 和 Linux子系统

本文使用电脑系统：文章目录一、安卓子系统1.1安装WSA1.2使用二、Linux子系统2.1安装WSL以及WSL相关概念2.2安装一个Linux发行版2.21从MicrosoftStore安装2.22用命令安装2.23拓展三、拓展3.1存储位置3.2虚拟化技术3.3Windows虚拟内存3.3wsl帮助文件一、安卓子系

MySQL 锁机制

1.锁是什么？是为了保证数据并发访问时的一致性和有效性，数据库提供的一种机制。锁机制的优劣直接影响到数据库的并发处理能力和系统性能，所以锁机制也就成为了各种数据库的核心技术之一。同时，锁机制也为实现MySQL事务的各个隔离级别提供了保证。2.锁的缺点锁是一种消耗资源的机制，想要实现锁的各种操作，包括获得锁、检测锁是否已

2023数学建模国赛游记

第一参加数学建模国赛，大概也是最后一次参加了，记录一下这几天的历程吧。我们队的情况是计算机+电气+数统，计算机负责编程，电气学院的负责论文部分，数统的同学负责建模，数据处理部分我们是共同承担。第一天下午6点发题，5点学校的所有队伍基本都到管理学院的机房在等着发题，5点多题发了，我们开始看题，几个人扫了一下C题觉得可以做

热文推荐
  1. 系统集成|第九章(笔记)

    目录第九章成本管理9.1成本管理概念及相关术语9.2主要过程9.2.1制订成本管理计划9.2.2成本估算9.2.3成本预算9.2.4成本控制上篇：第八章、进度管理第九章成本管理9.1成本管理概念及相关术语概述：项目成本管理就是要确保在批准的预算内完成项目项目成本失控的原因：①对项目认识不足②组织制度不健全③方法问题④技

  2. LuatOS-SOC接口文档(air780E)--audio - 多媒体音频

    常量常量类型解释audio.PCMnumberPCM格式，即原始ADC数据audio.MORE_DATAnumberaudio.on回调函数传入参数的值，表示底层播放完一段数据，可以传入更多数据audio.DONEnumberaudio.on回调函数传入参数的值，表示底层播放完全部数据了audio.BUS_DACnum

  3. ES6的代理模式 | Proxy

    🎬岸边的风：个人主页🔥个人专栏:《VUE》《javaScript》⛺️生活的理想，就是为了理想的生活!目录正文语法Handler对象常用的方法handler.get可撤消的ProxyProxy的应用场景校验器私有属性为什么要用Proxy重构Vue中的defineProperty对象新增属性为什么不更新数组变异对比p

  4. 开发项目的前后端分离，学习Vue的生命周期

    目录一、概述(1)介绍1-1背景1-2是什么(2)库和框架的区别(3)MVVM与Vue3.1MVVM介绍3.2MVVM与Vue二、Vue入门三、生命周期3-1讲述3-2演示带给我们的收获一、概述(1)介绍1-1背景Vue的背景可以追溯到2013年，当时尤雨溪（EvanYou）是Google的工程师，负责开发Angula

  5. Ubuntu修改静态IP、网关和DNS的方法总结

    Ubuntu修改静态IP、网关和DNS的方法总结ubuntu系统（其他debian的衍生版本好像也可以）修改静态IP有以下几种方法。（搜索总结，可能也不太对）/etc/netplan(use)Ubuntu18.04开始可以使用netplan配置网络，其也是默认安装的。配置文件位于/etc/netplan/xxx.yam

  6. 深入实现 MyBatis 底层机制的实现任务阶段 7- 实现动态代理 Mapper 的方法

    😀前言在Java世界里，MyBatis是一个优秀的持久层框架，它支持自定义SQL、存储过程以及高级映射。MyBatis消除了几乎所有的JDBC代码和参数的手动设置以及结果集的检索。MyBatis可以使用简单的XML或注解进行配置，并且能映射基本类型、Map接口及任何JavaPOJO(PlainOldJavaObjec

  7. 应用案例 | 使用dataFEED OPC Suite将汽车零部件工厂数据集成到SAP Business Suite

    一背景某知名空气过滤和热管理组件供应商是一家专业的汽车零部件制造集团——专注于液体和空气过滤系统、进气系统以及热管理组件的生产与销售。该集团在全球范围内拥有24个生产工厂，并在运营中广泛采用了SAPBusinessSuite作为其企业资源规划（ERP）和制造执行系统（MES）。该集团的主要业务需求是将来自车间设备的生产

  8. SpringSecurity 权限管理的实现

    文章目录前言权限管理的实现权限校验的原理FilterSecurityInterceptorAccessDescisionManagerAffirmativeBasedConsensusBasedUnanimousBasedAccessDecisionVoterWebExpressionVoterAuthenticate

  9. 响应式网页设计（Responsive Web Design）的核心原理

    聚沙成塔·每天进步一点点⭐专栏简介⭐响应式网页设计的核心原理⭐优点和缺点优点缺点⭐写在最后⭐专栏简介前端入门之旅：探索Web开发的奇妙世界欢迎来到前端入门之旅！感兴趣的可以订阅本专栏哦！这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域的朋友们量身打造的。无论你是完全的新手还是有一些基础的开发者，这里都将为你提供一个