【C++练级之路】【Lv.18】哈希表(哈希映射,光速查找的魔法)



快乐的流畅:个人主页


个人专栏:《算法神殿》《数据结构世界》《进击的C++》

远方有一堆篝火,在为久候之人燃烧!

文章目录

  • 引言
  • 一、哈希
    • 1.1 哈希概念
    • 1.2 哈希函数
    • 1.3 哈希冲突
  • 二、闭散列
    • 2.1 数据类型
    • 2.2 成员变量
    • 2.3 默认成员函数
      • 2.3.1 constructor
    • 2.4 查找
    • 2.5 插入
    • 2.6 删除
  • 三、开散列
    • 3.1 结点
    • 3.2 成员变量
    • 3.3 默认成员函数
      • 3.3.1 constructor
      • 3.3.2 destructor
    • 3.4 查找
    • 3.5 插入
    • 3.6 删除
    • 3.7 哈希化
  • 总结

引言

之前学习的红黑树,增删查改都为O(logN),但是今天学习的哈希表,理论上可以达到增删查改都为O(1),让我们来看看是什么结构这么神奇吧~

一、哈希

1.1 哈希概念

在线性结构和树形结构中,元素键值key与其存储位置之间没有对应关系,因此在查找指定元素时,要经过key的多次对比

时间复杂度:顺序查找为O(N),二叉搜索平衡树查找为O(logN)。


理想的查找方式:不经过任何比较,直接通过key获取其存储位置

这就是哈希的本质,通过某种函数(称之为哈希函数)构建key与其存储位置的一一映射关系,从而达到查找为O(1)。而这种结构也称为哈希表(Hash Table),又称散列表。

1.2 哈希函数

哈希函数设计原则:

  • 哈希函数的定义域必须包括需要存储的全部key,而如果散列表允许有m个地址时,其值域必须在0到m-1之间
  • 哈希函数计算出来的地址能均匀分布在整个空间中
  • 哈希函数应该比较简单

那么,下面介绍两种常见的哈希函数:

  1. 直接定址法
    • Hash(key) = A*key + B

优点:简单、均匀
缺点:需要事先知道key的分布情况

  1. 除留余数法
    • Hash(key) = key % p (p<=m)
    • 其中m为地址数,p为最接近m的素数

优点:不需要事先知道key的分布情况
缺点:会产生哈希冲突

选择除数为素数的原因:减少哈希冲突
如果选择的除数包含多个正因数,那么哈希地址可能会集中在某些特定的值上,从而导致冲突概率增加。

1.3 哈希冲突

哈希冲突,又称哈希碰撞,即为不同key通过相同哈希函数计算出相同的哈希地址

数学表达:对于两个数据元素的关键字 k i k_i ki k j k_j kj(i != j),有 k i k_i ki != k j k_j kj,有:Hash( k i k_i ki) == Hash( k j k_j kj)


面对陌生数据,我们一般比较常用的除留余数法会产生哈希冲突,而哈希冲突则是影响哈希表效率的关键因素。

那么,如何解决哈希冲突呢?这里有两种方法:闭散列和开散列

二、闭散列

闭散列,又称开放定址法

当哈希冲突发生时,开放定址法尝试在哈希表内部找到一个空闲的单元来存放冲突的元素。这个空闲的单元被称为开放单元或空白单元。

2.1 数据类型

enum State
{
	EMPTY,
	EXIST,
	DELETE
};

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

细节:

  1. 每个哈希数据,都要设置状态变量,以便区分
  2. 状态分为空,存在和删除,数据状态初始化为空

2.2 成员变量

template<class K, class V>
class HashTable
{
public:
protected:
	vector<HashData<K, V>> _tables;
	size_t _n = 0;//有效数据个数
};

细节:

  1. 哈希表底层一般使用数组(vector)
  2. 哈希表的有效数据个数_n与vector的size不同

2.3 默认成员函数

2.3.1 constructor

HashTable()
{
	_tables.resize(10);
}

细节:这里vector提前开空间,可以避免后续为空的讨论

2.4 查找

HashData<K, V>* Find(const K& key)
{
	size_t hashi = key % _tables.size();
	size_t pos = hashi;
	size_t i = 1;
	while (_tables[pos]._state != EMPTY)
	{
		if (_tables[pos]._state == EXIST && _tables[pos]._kv.first == key)
		{
			return &_tables[pos];
		}

		pos = hashi + i;
		if (pos >= _tables.size())
		{
			return nullptr;
		}
		++i;
	}
	return nullptr;
}

细节:

  1. 先用key取模数组size,得到哈希地址hashi
  2. 然后沿当前位置向后找,直到该位置状态为空超出数组边界,才算找不到
  3. 如果该位置状态为存在且key相等,则找到了

2.5 插入

bool Insert(const pair<K, V>& kv)
{
	if (Find(kv.first))//保持key唯一
	{
		return false;
	}
	//...
	size_t hashi = kv.first % _tables.size();
	size_t pos = hashi;
	size_t i = 1;
	while (_tables[pos]._state == EXIST)
	{
		pos = hashi + i;//线性探测
		if (pos >= _tables.size())
		{
			return false;
		}
		++i;
	}
	_tables[pos]._kv = kv;
	_tables[pos]._state = EXIST;
	++_n;
	return true;
}

细节:

  1. 先查找当前是否存在该值,如果存在,则不插入
  2. 用key取模数组size,得到哈希地址hashi
  3. 然后沿当前位置向后找,直到状态为空或删除,才插入

但是,上述情况是哈希表未满时,如果满了如何扩容?还有,一定要满了才扩容吗?

这里,我们引入负载因子的概念:α = 有效数据个数 / 哈希表长度

当负载因子越大,哈希冲突的概率就越大,同时发生哈希踩踏的概率也越大,对于开放定址法,应该控制负载因子小于0.7,超过将扩容。

if (_n * 10 / _tables.size() >= 7)//负载因子大于等于0.7, 扩容
{
	size_t newsize = _tables.size() * 2;
	vector<HashData<K, V>> newtables(newsize);
	for (auto& cur : _tables)
	{
		size_t hashi = cur._kv.first % newsize;
		size_t pos = hashi;
		size_t i = 1;
		while (newtables[pos]._state == EXIST)
		{
			pos = hashi + i;//线性探测
			++i;
		}
		newtables[pos]._kv = kv;
	 _tables[pos]._state = EXIST;
	}
	_tables.swap(newtables);
}

细节:

  1. 判断时左右同乘以10,避免比较浮点数而带来误差
  2. newsize为原本的2倍(本来应该是接近2倍的素数,这里简单起见没实现)
  3. 将原哈希表中的元素一一映射到新表中
  4. 最后交换旧表和新表(类似于拷贝构造的现代写法)

2.6 删除

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

细节:

  1. 先查找当前是否存在该值,如果存在,则删除
  2. 这里的删除,只用将状态变量改为删除即可

以上讲解的查找和插入,它们所用的探测方法是线性探测(一个一个往后找),这种探测方法可能会造成大量的哈希冲突。

那么,有没有什么探测方法能缓解哈希冲突呢?有,那就是二次探测!

改法也很简单,以一小段代码举例:

while (newtables[pos]._state == EXIST)
{
	pos = hashi + i*i;//二次探测
	++i;
}

这样就是每次跨越 i 的二次方向后探测,中间间隔大,哈希冲突就可以得到缓解。

三、开散列

但是,闭散列(开放定址法)有一个致命的缺陷,那就是空间利用率低!它必须保留相当一部分的开放空间,才能不断插入。

所以,实际上,我们更常用另一种方式来实现哈希表——闭散列,又称为开链法

在开链法中,哈希表的每个槽位(bucket),又称为哈希桶通过一个单链表来存储所有散列到该槽位的元素。这意味着即使不同的key经过哈希函数映射到同一个槽位,它们也可以被存储在同一个单链表上,从而避免了冲突。

3.1 结点

template<class K, class V>
struct HashNode
{
	HashNode<K, V>* _next;
	pair<K, V> _kv;

	HashNode(const pair<K, V>& kv)
		: _next(nullptr)
		, _kv(kv)
	{}
};

细节:

  • 这里没有使用STL的list或者forward_list,而是自己设计结点,为了更方便操纵内部细节

3.2 成员变量

template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
protected:
	typedef HashNode<K, V> Node;
public:
protected:
	vector<Node*> _tables;
	size_t _n = 0;//有效数据个数
};

细节:

  1. 数组(vector)中存储单链表的头结点指针
  2. 模板参数的Hash,是为了任意类型都能转换为整型来取模

3.3 默认成员函数

3.3.1 constructor

HashTable()
{
	_tables.resize(10);
}

细节:这里vector提前开空间,可以避免后续为空的讨论

3.3.2 destructor

~HashTable()
{
	for (auto& cur : _tables)
	{
		while (cur)
		{
			Node* del = cur;
			cur = cur->_next;
			delete del;
		}
	}
}

细节:因为涉及链表结点空间的动态开辟,所以要手动释放

3.4 查找

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

细节:

  1. 先取模计算出哈希地址
  2. 再沿当前单链表向下查找

3.5 插入

bool Insert(const pair<K, V>& kv)
{
	if (Find(kv.first))//保持key唯一
	{
		return false;
	}

	Hash hash;
	//...
	size_t hashi = hash(kv.first) % _tables.size();
	Node* newnode = new Node(kv);
	//头插
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;
	return true;
}

细节:

  1. 先查找当前是否存在该值,如果存在,则不插入
  2. 取模计算出哈希地址,再头插新节点

运用开链法后,虽然没有哈希冲突了,但是链表长度过长也会影响效率。所以,哈希表也需要通过扩容来使链表长度变短,理想的状态是负载因子为1时扩容。

悄悄说一句:链表过长,还有另一种解决方法,那就是在该哈希桶下改挂一棵红黑树~

if (_n == _tables.size())//负载因子为1时,扩容
	{
		size_t newsize = _tables.size() * 2;
		vector<Node*> newtables(newsize);
		for (auto& cur : _tables)
		{
			while (cur)
			{
				Node* next = cur->_next;
				//将旧表结点重新映射到新表上
				size_t hashi = hash(cur->_kv.first) % newsize;
				cur->_next = newtables[hashi];
				newtables[hashi] = cur;
				//跳回旧表的下一结点
				cur = next;
			}
		}
		_tables.swap(newtables);
	}

细节:

  1. 二倍扩容(本来应该是接近2倍的素数,这里简单起见没实现)
  2. 遍历旧表,将旧表结点重新映射到新表上(这里直接链接,而不是创建新节点)
  3. 最后交换旧表和新表

3.6 删除

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

细节:

  1. 单链表删除,设置prev前置指针
  2. 注意头删的情况,分类处理

3.7 哈希化

由于除留余数法涉及到取模运算,而只有整型才能取模。所以针对非整型的数据,需要将其转化为整型,这一过程称为哈希化

template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return key;
	}
};

template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto& ch : s)
		{
			hash = hash * 31 + ch;
		}
		return hash;
	}
};

细节:

  1. 第一个哈希化函数,针对的是内置类型(整型或浮点型等),返回值设置为size_t,相近类型会进行隐式类型转换
  2. 第二个哈希化函数,针对的是字符串,运用了模板的特化。同时,为了防止字符串的异位串(对应字符数相同,而位置不同),并不是直接相加,而是每次相加后乘以31,保证肯定不重复。
  3. 同时,如果针对特殊的类,用户可以手写一个特定的哈希化函数进行模板传参

总结

相比闭散列,开散列看似增加了存储指针的空间开销,实际上闭散列要保证大量的空闲单元以降低哈希冲突,所以开散列反而更加节省空间,其空间利用率更高


哈希表与红黑树的对比:

  • 哈希表平均查找可达O(1),但最坏降到O(N)(哈希冲突)
  • 红黑树最坏查找也可保持O(logN),比较稳定

数据有序性:哈希表无序,而红黑树有序

适用场景:哈希表适合单点查找,红黑树适合范围查找


真诚点赞,手有余香

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

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

相关文章

保研线性代数复习3

一.基底&#xff08;Basis&#xff09; 1.什么是生成集&#xff08;Generating Set&#xff09;&#xff1f;什么是张成空间&#xff08;Span&#xff09;&#xff1f; 存在向量空间V(V&#xff0c;&#xff0c;*)&#xff0c;和向量集&#xff08;xi是所说的列向量&#xff…

【软件工程】概要设计

1. 导言 1.1 目的 该文档的目的是描述学生成绩管理系统的概要设计&#xff0c;其主要内容包括&#xff1a; 系统功能简介 系统结构简介 系统接口设计 数据设计 模块设计 界面设计 本文的预期读者是&#xff1a; 项目开发人员 项目管理人员 项目评测人员&#xff08;…

算法设计与分析实验报告python实现(串匹配问题、采用分治法求解最大连续子序列和问题、用分治策略求众数问题、最近点对问题)

一、 实验目的 1&#xff0e;加深学生对算法设计方法的基本思想、基本步骤、基本方法的理解与掌握&#xff1b; 2&#xff0e;提高学生利用课堂所学知识解决实际问题的能力&#xff1b; 3&#xff0e;提高学生综合应用所学知识解决实际问题的能力。 二、实验任务 1、串匹配问…

Docker安装mysql并且设置主从

Docker安装部署mysql 下载镜像 docker pull mysql:5.7.35查看镜像 docker images启动 直接启动不挂载文件 docker run -p 3306:3306 --name mysql -e MYSQL_ROOT_PASSWORD123456 -d mysql:5.7.35挂载文件 docker run -p 3306:3306 --name mysql \ -v /usr/local/docker/m…

正则表达式与JSON序列化:去除JavaScript对象中的下划线键名

&#x1f31f; 前言 欢迎来到我的技术小宇宙&#xff01;&#x1f30c; 这里不仅是我记录技术点滴的后花园&#xff0c;也是我分享学习心得和项目经验的乐园。&#x1f4da; 无论你是技术小白还是资深大牛&#xff0c;这里总有一些内容能触动你的好奇心。&#x1f50d; &#x…

【Java EE】关于Maven

文章目录 &#x1f38d;什么是Maven&#x1f334;为什么要学Maven&#x1f332;创建⼀个Maven项目&#x1f333;Maven核心功能&#x1f338;项目构建&#x1f338;依赖管理 &#x1f340;Maven Help插件&#x1f384;Maven 仓库&#x1f338;本地仓库&#x1f338;私服 ⭕总结 …

STM32G系 编程连接不上目标板,也有可能是软件不兼容。

由于一直用的老版本STM32 ST-LINK Utility 4.20 &#xff0c;找遍了所有问题&#xff0c;SWD就是连不上目标板。 电源脚 VDDA 地线&#xff0c;SWD的四条线&#xff0c;还是不行&#xff0c;浪费了一天&#xff0c;第二天才想起&#xff0c;是不是G系升级了 SWD协议。结果下载…

从汇编看函数调用

文章目录 函数调用流程栈相关寄存器及的作用简介寄存器功能指令功能 栈函数的括号{}正括号反括号 参数传递传值&#xff0c;变量不可改传指针&#xff0c;变量可改C 传引用 函数调用实例 函数调用流程 目标&#xff1a;函数调用前后栈保持不变 保存main函数的寄存器上下文移…

【HTML】简单制作一个3D动画效果重叠圆环

目录 前言 开始 HTML部分 CSS部分 效果图 总结 前言 无需多言&#xff0c;本文将详细介绍一段代码&#xff0c;具体内容如下&#xff1a; 开始 首先新建文件夹&#xff0c;创建两个文本文档&#xff0c;其中HTML的文件名改为[index.html]&#xff0c;CSS的…

Tensorflow2.0笔记 - 自定义Layer和Model实现CIFAR10数据集的训练

本笔记记录使用自定义Layer和Model来做CIFAR10数据集的训练。 CIFAR10数据集下载&#xff1a; https://www.cs.toronto.edu/~kriz/cifar-10-python.tar.gz 自定义的Layer和Model实现较为简单&#xff0c;参数量较少&#xff0c;并且没有卷积层和dropout等&#xff0c;最终准确率…

Java—抽象方法与接口

声明&#xff1a;以下内容是根据B站黑马程序员的Java课程&#xff0b;博主自己的理解整理而成&#xff0c;课程很好&#xff0c;适合初学者学习。 关于此类题目&#xff0c;重要的是识别出用什么来实现&#xff0c;到底是接口还是抽象方法&#xff0c;还是共有的属性等等&…

医用三维影像PACS系统源码 一套成熟的PACS系统应具备哪些核心要素?

医用三维影像PACS系统源码 一套成熟的PACS系统应具备哪些核心要素&#xff1f; PACS及影像存取与传输系统”( Picture Archiving and Communication System)&#xff0c;为以实现医学影像数字化存储、诊断为核心任务&#xff0c;从医学影像设备&#xff08;如CT、CR、DR、MR、…

ZZS-7/1G212分合闸电源综合控制装置 220VAC 板前接线 JOSEF约瑟

系列型号&#xff1a; ZZS-7G/1分闸、合闸、电源监视综合控制装置&#xff1b; ZZS-7G/11分闸、合闸、电源监视综合控制装置&#xff1b; ZZS-7G/23分闸、合闸、电源监视综合控制装置&#xff1b; ZZS-7G/24分闸、合闸、电源监视综合控制装置&#xff1b; ZZS-7/1G11分闸、合闸…

21.兼容性测试

考试频率低&#xff1b; 一般考兼容性测试会结合web测试&#xff1b;&#xff08;兼容性矩阵&#xff09; 主要议题&#xff1a; 1.兼容性测试概述 2.硬件兼容性测试 最低配置不讲究工作负载&#xff0c;意思是软件能够运行的最低要求环境&#xff1b; 推荐配置&#xff0c…

修复503 Service Unavailable Error问题

近期我们网网站经常出现503 Service Unavailable Error&#xff0c;在此之前我们的网站从未出现过这种问题&#xff0c;我们向虚拟主机提供商Hostease咨询后&#xff0c;了解到503 Service Unavailable错误是指服务器暂时无法处理请求&#xff0c;通常是由于服务器过载、维护、…

Python数据结构与算法——数据结构(链表、哈希表、树)

目录 链表 链表介绍 创建和遍历链表 链表节点插入和删除 双链表 链表总结——复杂度分析 哈希表(散列表) 哈希表介绍 哈希冲突 哈希表实现 哈希表应用 树 树 树的示例——模拟文件系统 二叉树 二叉树的链式存储 二叉树的遍历 二叉搜索树 插入 查询 删除 AVL树 …

路由Vue-Router使用

Vue Router 是 Vue.js 的官方路由。它与 Vue.js 核心深度集成&#xff0c;让用 Vue.js 构建单页应用变得轻而易举。 介绍 | Vue Router (vuejs.org) 1. 安装 npm install vue-router4 查看安装好的vue-router 2. 添加路由 新建views文件夹用来存放所有的页面&#xff0c;在…

初入职,如何用好 git 快速上手项目开发

前言 介绍在工作中使用 git 工具 文章目录 前言一、git 简介1、是什么作用操作3、用途 二、基本概念1、工作区2、暂存区3、版本库4、操作过程 三、基本命令操作 一、git 简介 1、是什么 git 是一个方便管理代码版本的工具&#xff0c;用一个树结构来维护和管理所有的历史版本…

数据结构记录

之前记录的数据结构笔记&#xff0c;不过图片显示不了了 数据结构与算法(C版) 1、绪论 1.1、数据结构的研究内容 一般应用步骤&#xff1a;分析问题&#xff0c;提取操作对象&#xff0c;分析操作对象之间的关系&#xff0c;建立数学模型。 1.2、基本概念和术语 数据&…

Finite Element Procedures K.J.Bathe 【教材pdf+部分源码】|有限元经典教材 | 有限元编程

专栏导读 作者简介&#xff1a;工学博士&#xff0c;高级工程师&#xff0c;专注于工业软件算法研究本文已收录于专栏&#xff1a;《有限元编程从入门到精通》本专栏旨在提供 1.以案例的形式讲解各类有限元问题的程序实现&#xff0c;并提供所有案例完整源码&#xff1b;2.单元…