c++哈希表(原理、实现、开放寻址法)适合新手

c++系列哈希的原理及实现(上)

文章目录

  • c++系列哈希的原理及实现(上)
  • 前言
  • 一、哈希的概念
  • 二、哈希冲突
  • 三、哈希冲突解决
    • 3.1、开放寻址法
    • 3.2、删除操作
    • 3.3、负载因子
    • 四、代码实现
  • 总结


前言

红黑树平衡树和哈希有不同的用途。

红黑树、平衡树这类数据结构是有序的数据结构,它们可以高效地进行范围查询,比如查找一个区间内的值。在需要保持数据有序存储,并且频繁进行插入、删除和查找操作的场景下很有用,像数据库索引的实现就可能会用到。

而哈希主要用于快速的数据查找。它通过一个哈希函数把数据映射到一个特定的位置,理想情况下,查找操作可以在常数时间复杂度内完成,也就是时间复杂度为O(1)。在只需要快速判断某个元素是否存在的场景下,哈希就非常合适。所以学了红黑树等平衡树之后还需要学哈希,是因为它们解决的是不同类型的问题。


一、哈希的概念

首先我们要知道顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。
而我们想要的是可以不经过任何比较,一次直接从表中得到要搜索的元素。
下面我们看一个小问题:

有这样一个由小写字母组成的字符串“abcdef”我们需要查找某一个字符是否存在,这时我们就可以将他映射到一个数组中,要查找字符是否存在,我们只需要利用这给映射方法,判断它对应数组中的值是否为1即可。

string s = "abcdef";
int arr[26] = {0};//开辟空间初始化为0
for (auto ch : s)
{
    arr[ch - 'a'] = 1;
}

这就是利用哈希思想,哈希就是一种特殊的存储结构,通过特定的函数(方法),使得数据的存储位置与它的关键码之间建立一种一一映射的关系,这样在查找数据时就可以直接通过关键值来快速查找,这个函数也称为映射函数。
再来看一个例子:
对于这样一组数据{1,2,4,5,7,6},我们要将他映射到一个数组中就可以使用直接映射,即:
在这里插入图片描述
而如果数据的范围较大如:{1,2,3,4,7,6,9999999},这样一组数据,如果使用直接映射,就要开辟足够大的空间,这样开空间浪费的有点离谱了,这时我们就需要给它提供一个方法,将数据控制在一定的范围,所以就有了,除留余数法。我们将这个方法封装为一个函数,这个函数就称为映射函数
除留余数法:
我们将待存入数,对开辟空间大小,进行取余,得到的余数,作为下标,利用下标将带存入数存入到空间中。(待存入数据,我们称为关键字,余数我们称为,存储位置)

size_t hashFunc(size_t key)
{
    size_t i=key%capacity;
    return i;
}

在这里插入图片描述
下面我们再思考一个问题:
如果我们想再存储一个3,通过3进行哈希映射发现,家被偷了,该怎么办呢?
我们需要的位置已经存在值,这种问题称为,哈希冲突。我们先来对上面进行一下总结再来解决这个问题。

总结:

映射关系
1、直接定址法(直接映射):适合数据范围小,数据量小,没有重复值的数据。不存在哈希冲突。
2、除留余数法:适合数据范围大,数据量可以大。存在哈希冲突。

二、哈希冲突

哈希冲突指的是在使用哈希表进行数据存储和查找时,不同的关键字通过哈希函数计算得到了相同的哈希值(存储位置)。
哈希函数是将关键字映射到哈希表中的某个位置的函数。由于哈希表的存储空间是有限的,而可能的关键字数量是无限的,所以不同的关键字有可能被映射到相同的位置,这就产生了哈希冲突。
哈希冲突会影响哈希表的性能,比如增加查找、插入等操作的时间复杂度。

解决哈希冲突有两种常见的方法:

  • 闭散列:也叫开放寻址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。
  • 开散列:也叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。

这次我们先介绍闭散列法

三、哈希冲突解决

3.1、开放寻址法

开放定址法是解决哈希冲突的一种方法,其基本思想是当发生冲突时,通过某种系统的方法在哈希表中寻找下一个空槽位,并将冲突的关键码存储在这个槽位中。常用的方法有两种:

1、线性探测:当发生哈希冲突时,从映射位置开始,向后按顺序查找,直到找到下一个空位。
2、二次探测:从映射位置开始,依次增加1、4、9…,探测距离是i^2的倍数,i为从零开始自增的整数。

线性探测例子:
如果我们想将11插入哈希表中,通过哈希函数得到的存储位置已经被占用,我们就从当前位置开始,依次向后查找空位置。
在这里插入图片描述
这种解决哈希冲突的方式,又给我们带来了一个麻烦。
大家思考一下,当我们要查找1这个元素是否存在哈希表中,我们该如何来查找呢?解铃还须系铃人,肯定第一时间就想到利用哈希映射,找到这个值的存储位置,然后比较哈希表中的值,是否等于要查找的值。这个问题是很简单的,那么我们又该如何查找11呢?显然简单的使用哈希函数映射得到到值是无法找到的,这时我们就需要判断它后面是否还有值,如果有,我们就将他与后面存储值继续比较,直到找到,或者遇到值为空的位置。

3.2、删除操作

接着上面的来讲,如果我们要将2删除,是否可以直接将它所在位置,制为空。如果我们这样做了那么上面查找11的操作,该怎么来完成呢?这时我们就需要一个方式将存储位置的状态进行标记,我们将删除位置标记为删除、已有数据位置,标记为存在,未存储数据位置设置为空。这样我们在查找元素时,跳过删除位置,直至空或找到终止程序。

3.3、负载因子

在我们向哈希表中不断映射数据时,发生哈希冲突的概率会随数据量的增大而提高,这会导致我们插入、查找效率大幅度下降,这时我们就需要对哈希表进行扩容操作。那么什么时候扩容呢,总不能等到哈希表存满,哈希冲突最多的时候再进行扩容吧!!!!这时就有了负载因子,来作为我们判断是否扩容的阈值,这个负载因子是使用已插入元素除以哈希表大小。那么当这个负载因子多大时我们对哈希表进行扩容操作呢?这个没有具体要求,但是我们要知道,如果设置太小,会产生空间浪费,设置太大就会发生较多的哈希冲突,所以我们也不能设置的太离谱,在接下来的代码实现中,我将他设置为0.7。

四、代码实现

具体操作及原理,上面已经讲解过了,由于这个结构实现起来还是很简单的,大家在看代码时结合注释及上文。

//使用枚举标识哈希表状态
enum status {
	EMPTY,
	EXIST,
	DELETE
};
template<class k, class v>
struct hashdate {
	pair<k, v>_kv;
	status _s;
};
//使用模板
template<class k>//仿函数将待存入数据统一处理为无符号整型
struct HashFunc {
	size_t operator ()(const k& key)
	{
		return (size_t)key;
	}
};
template<>//模板特化,应字符串存储问题
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t cout = 0;
		for (int i = 0; i < key.size(); i++)
		{
			cout += key[i];
		}
		return cout;
	}
};
//缺省值为哈希函数(仿函数),可跟据需要自己提供
template<class k, class v,class Hash=HashFunc<k>>
class hashTable {
	Hash hash;
public:
	hashTable()
	{
		_table.resize(10);
	}
	bool Insert(const pair<k, v>& kv)
	{
		if (Find(kv))
		{
			return false;
		}
		//负载因子设置为0.1因为隐式这里因为会发生隐式类型转换,特殊处理一下
		if (_n * 10 / _table.size() == 7)
		{
			size_t newsize = _table.size() * 2;
			hashTable<k, v> Newhs;
			Newhs._table.resize(newsize);
			for (int i = 0; i < _table.size(); i++)
			{
				if (_table[i]._s == EXIST)
				{
					Newhs.Insert(_table[i]._kv);
				}
			}
			_table.swap(Newhs._table);
		}
		size_t hashi = hash(kv.first) % _table.size();
		while (_table[hashi]._s == EXIST)
		{
			hashi++;
			hashi %= _table.size();
		}
		_table[hashi]._kv = kv;
		_table[hashi]._s = EXIST;
		_n++;
		return true;
	}
	//查找函数
	hashdate<k,v>* Find(const pair<k, v>& kv) {
		size_t hsi = hash(kv.first) % _table.size();
		while (_table[hsi]._s != EMPTY)
		{
			if (_table[hsi]._s == EXIST && _table[hsi]._kv.first == kv.first)
			{
				return &_table[hsi];
			}
			hsi++;
		}
		return NULL;
	}
	bool earse(const k& key)
	{
		size_t hasi = key % _table.size();
		while (_table[hasi]._s != EMPTY)
		{
			if (_table[hasi]._s == EXIST && _table[hasi]._kv.first == key)
			{
				_table[hasi]._s = DELETE;
				return true;
			}
			hasi++;
		}
		return false;
	}
	void print()
	{
		for (int i = 0; i < _table.size(); i++)
		{
			if (_table[i]._s == EXIST)
			{
				cout << _table[i]._kv.first << ' ';
			}
		}
	}
private:
	size_t _n = 0;
	vector<hashdate<k, v>> _table;//使用vector充当哈希表
};

总结

线性探测优点:实现非常简单
线性探测缺点:一旦发生哈希冲突,所有的冲突连在一起,容易产生数据“堆积”,即:不同关键码占据了可利用的空位置,使得寻找某关键码的位置需要许多次比较,导致搜索效率降低。如何缓解呢?这就需要用到开放定址法了

下篇也完成了,链接放下面了

c++哈希开散列讲解

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

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

相关文章

用MATLAB符号工具建立机器人的动力学模型

目录 介绍代码功能演示拉格朗日方法回顾求解符号表达式数值求解 介绍 开发机器人过程中经常需要用牛顿-拉格朗日法建立机器人的动力学模型&#xff0c;表示为二阶微分方程组。本文以一个二杆系统为例&#xff0c;介绍如何用MATLAB符号工具得到微分方程表达式&#xff0c;只需要…

MongoDB集群分片安装部署手册

文章目录 一、集群规划1.1 集群安装规划1.2 端口规划1.3 目录创建 二、mongodb安装&#xff08;三台均需要操作&#xff09;2.1 下载、解压2.2 配置环境变量 三、mongodb组件配置3.1 配置config server的副本集3.1.1 config配置文件3.1.2 config server启动3.1.3 初始化config …

java 调用 k8s crd 生成 crd model

k8s官方提供了自动生成Java模型代码的工具&#xff0c;使用指南&#xff1a; https://github.com/kubernetes-client/java提供有两种方法&#xff1a; github action远程生成本地docker镜像生成 本地docker镜像生成很简单&#xff0c;跟着官方指南下载镜像执行命令即可&…

36 基于单片机的电磁炉系统设计

目录 一、主要功能 二、硬件资源 三、程序编程 四、实现现象 一、主要功能 基于51单片机&#xff0c;通过DS18B20温度传感器检测温度&#xff0c;通过八位数码管显示&#xff0c; 如果温度超过阈值&#xff0c;则蜂鸣器报警&#xff0c;红灯亮起&#xff1b;若不超过阈值&…

IoTDB 常见问题 QA 第一期

开始&#xff01;关于 IoTDB 的 Q&A 我们将定期汇总社区讨论频繁的问题&#xff0c;并展开进行详细回答&#xff0c;通过积累常见问题“小百科”&#xff0c;方便大家使用 IoTDB。 Q1&#xff1a;WAL 堆积导致写入失败 问题及现象 集群报错&#xff1a; The write is rejec…

buildroot 制作Linux嵌入式文件系统,并添加telnet 以及ssh

在开始配置前&#xff0c;我们需要了解SSH和Telnet的基本概念。SSH&#xff08;Secure Shell&#xff09;为加密的网络协议&#xff0c;用于在不安全的网络中执行命令并管理网络服务。相对于SSH&#xff0c;Telnet是一个老旧且非加密的协议&#xff0c;用于进行远程登录 sshd 服…

Simulink的SIL软件在环测试

以基于模型的设计&#xff08;MBD&#xff09;的软件开发时&#xff0c;需要进行SIL&#xff08;软件在环测试&#xff09;。SIL测试就是在PC上验证模型是否与代码功能一致。在项目开展中&#xff0c;用在需要将控制器生成移植到硬件前&#xff0c;把控制器的模块生成代码&…

【赵渝强老师】PostgreSQL中的模式

在PostgreSQL中&#xff0c;所有的数据库对象都是属于模式中的对象。这里的数据库对象包括&#xff1a;表、索引、视图、存储过程、触发器等等。所有数据库对象都有各自的对象标识符oid&#xff08;object identifiers&#xff09;,它是一个无符号的四字节整数&#xff0c;相关…

【分页查询】.NET开源 ORM 框架 SqlSugar 系列

.NET开源 ORM 框架 SqlSugar 系列 【开篇】.NET开源 ORM 框架 SqlSugar 系列【入门必看】.NET开源 ORM 框架 SqlSugar 系列【实体配置】.NET开源 ORM 框架 SqlSugar 系列【Db First】.NET开源 ORM 框架 SqlSugar 系列【Code First】.NET开源 ORM 框架 SqlSugar 系列【数据事务…

Android 图形系统之四:Choreographer

Choreographer 是 Android 系统中负责帧同步的核心组件&#xff0c;它协调输入事件、动画和绘制任务&#xff0c;以确保界面以固定频率&#xff08;通常是每 16ms&#xff0c;一帧&#xff09;流畅渲染。通过管理 VSYNC 信号和调度任务&#xff0c;Choreographer 是实现流畅 UI…

计算机毕业设计Python异常流量检测 流量分类 流量分析 网络流量分析与可视化系统 网络安全 信息安全 机器学习 深度学习

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…

关于扩散方程的解

1-D 扩散方程的形式 Cauchy齐次方程 这个解无积分无级数&#xff0c;很简单的形式 美其名曰&#xff1a;基本解。 把基本解和初值做卷积&#xff0c;就得到cauchy方程的解。

零基础学安全--Burp Suite(4)proxy模块以及漏洞测试理论

目录 学习连接 一些思路 proxy模块 所在位置 功能简介 使用例子 抓包有一个很重要的点&#xff0c;就是我们可以看到一些在浏览器中看不到的传参点&#xff0c;传参点越多就意味着攻击面越广 学习连接 声明&#xff01; 学习视频来自B站up主 **泷羽sec** 有兴趣的师傅可…

python打包深度学习虚拟环境

今天师兄让我把环境打包发给他&#xff0c;我才知道可以直接打包深度学习虚拟环境&#xff0c;这样另一个人就不用辛辛苦苦的去装环境了&#xff0c;我们都知道有些论文他需要的环境很难装上。比如装Apex&#xff0c;装 DCN&#xff0c;mmcv-full 我现在把3090机子上的ppft虚拟…

M4V 视频是一种什么格式?如何把 M4V 转为 MP4 格式?

M4V 是一种视频文件格式&#xff0c;主要由苹果公司用于其产品和服务中&#xff0c;如 iTunes Store 上的电影和电视节目。这种格式可以包含受版权保护的内容&#xff0c;并且通常与苹果的 DRM&#xff08;数字版权管理&#xff09;技术结合使用&#xff0c;以限制内容的复制和…

【C++】从零到一掌握红黑树:数据结构中的平衡之道

个人主页: 起名字真南的CSDN博客 个人专栏: 【数据结构初阶】 &#x1f4d8; 基础数据结构【C语言】 &#x1f4bb; C语言编程技巧【C】 &#x1f680; 进阶C【OJ题解】 &#x1f4dd; 题解精讲 目录 前言1 红黑树的概念**红黑树的五大性质** 2 红黑树的实现2.1 红黑树的结构…

webpack(react)基本构建

文章目录 概要整体架构流程技术名词解释技术细节小结 概要 Webpack 是一个现代 JavaScript 应用程序的静态模块打包工具。它的主要功能是将各种资源&#xff08;如 JavaScript、CSS、图片等&#xff09;视为模块&#xff0c;并将它们打包成一个或多个输出文件&#xff0c;以便…

C++STL(四)-->vector 的模拟实现

1.vector的各函数接口&#xff1a; namespace cl {//模拟实现vectortemplate<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//默认成员函数vector(); //构造函数vector(size_t n, cons…

机器学习实战:泰坦尼克号乘客生存率预测(数据处理+特征工程+建模预测)

项目描述 任务&#xff1a;根据训练集数据中的数据预测泰坦尼克号上哪些乘客能生存下来 数据源&#xff1a;csv文件&#xff08;train.csv&#xff09; 目标变量&#xff1a;Survived&#xff08;0-1变量&#xff09; 数据集预览&#xff1a; 1、英文描述&#xff1a; 2、…

MATLAB不动点迭代法求单变量非线性方程的根程序加实例

不动点迭代法用于单变量线性方程近似根&#xff0c;首先确定一个方程根附近的近似初始值&#xff0c;采用逐次逼近的方法&#xff0c;使用迭代公式不断地更新这个初始值&#xff0c;使这个初始值不断趋近于准确值。 1.不动点迭代法自定义函数 fixed_point.m是一个MATLAB函数&a…