【C++】哈希冲突的解决办法:闭散列 与 开散列
哈希冲突解决
上一篇博客提到了,哈希函数的优化可以减小哈希冲突发生的可能性,但无法完全避免。本文就来探讨一下解决哈希冲突的两种常见方法:闭散列和开散列
1.闭散列
闭散列也叫开放定址法,发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还存在空位置,那么就可以把key存放到冲突位置的"下一个"空位置中去。那如何寻找下一个空位置呢?
1.1线性探测
插入的情况
还是上述这种情况,当我想插入元素13时,通过哈希函数计算出哈希地址为3,但此时该位置已经存放了元素3,发生了哈希冲突。
进行线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置。
由于下标4、5都有元素存放,此时找到的空位置下标为6,于是在下标6处存放元素13。
但是哈希表中的空间终究是有限的,空间不够时我们需要进行扩容。但如果等到表被填满再进行扩容的话,这样一来搜索的时间复杂度更趋向于O(N)了,因为表中数据存放越满,理论哈希地址与实际哈希地址相隔越远,最坏情况就近乎O(N)。所以我们需要更早地进行扩容。我们规定在什么情况下进行扩容呢?这里要引入一个载荷因子的概念。
散列表的载荷因子: α = 表中的元素个数 / 散列表的长度
载荷因子标记了需要进行扩容的情况。我们可以得知,载荷因子α越大,散列表越满,而散列表越满,产生冲突的可能性越大;反之α越小,产生冲突的可能性越小。但是不是载荷因子越小越好呢,并不是,载荷因子太小,会造成空间的极大浪费,因此对于开放定址法,载荷因子应限制在0.7-0.8 之间。也就是散列表的空间被利用了70%-80%时,就可以进行扩容了。
扩容之后,由于地址数增加了,关键码通过哈希函数求得的哈希地址也随之改变了,所以需要改变映射关系,改变映射关系之后,原先冲突的元素可能就不再冲突了:
原先元素13,元素17分别和元素3,元素7发生冲突,但是扩容之后,映射关系重新调整,它们就不再冲突了,这就是为什么即使哈希结构不能完全保证搜索的时间复杂度为O(1),但也可以近似于O(1)。
搜索的情况
搜索元素时,同样将关键码通过哈希函数计算出理论上的哈希地址,但是该地址处可能发生哈希冲突,若发生哈希冲突,则需要继续向后探测,当我们遇到空时,探测结束,说明搜索失败。
但是碰到下面这种情况呢:
我们搜索的目标元素是:13,由于13前一个位置的元素25被删除,该位置为空,所以会导致探测失败,但实际上13是存在的。所以我们在采用闭散列处理哈希冲突时,不能随意对已有元素进行物理删除,若直接删除,会影响其他元素的搜索。因此线性探测采用标记的的伪删除法来删除元素。
对哈希表每个空间给个标记:
EMPTY(此位置空), EXIST(此位置已经有元素), DELETE(元素已经删除)
enum State{EMPTY, EXIST, DELETE};
在删除元素时,只需要把该哈希位置的标记从 EXIST 改成 DELETE 即可;
在搜索元素时,探测到标记为 EMPTY 位置时停止,表示探测失败。
这样一来就完美解决了上述问题。
线性探测的代码实现:
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 hash = 0;for (auto e : key){hash *= 31;hash += e;}return hash;}
};// 以下采用开放定址法,即线性探测解决冲突
namespace open_address
{enum State{EXIST,EMPTY,DELETE};template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY;};template<class K, class V, class HashFunc = HashFunc<K>>class HashTable{public:HashTable(){_table.resize(10);}bool Insert(const pair<K, V>& kv){// 根据装载因子决定是否扩容if (_n * 10 / _table.size() >= 7){// 平衡因子>=0.7,需要扩容,扩容后需要重新插入size_t newSz = _table.size() * 2;HashTable<K, V, HashFunc> newHT;newHT._table.resize(newSz);for (size_t i = 0; i < _table.size(); i++){if (_table[i]._state == EXIST)newHT.Insert(_table[i]._kv);}_table.swap(newHT._table);}// 插入过程HashFunc hf;size_t hashi = hf(kv.first) % _table.size();while (EXIST == _table[hashi]._state){++hashi;hashi %= _table.size();}_table[hashi]._kv = kv;_table[hashi]._state = EXIST;++_n;return true;}HashData<K, V>* Find(const K& key){HashFunc hf;size_t hashi = hf(key) % _table.size();while (_table[hashi]._state != EMPTY){if (_table[hashi]._kv.first == key)return &_table[hashi];}return nullptr;}bool Erase(const K& key){if (Find(key)){Find(key)->_state = DELETE;return true;}return false;}void Print(){for (size_t i = 0; i < _table.size(); i++){if (_table[i]._state == EXIST)cout << i << " -> " << _table[i]._kv.first << "," << _table[i]._kv.second << endl;elsecout << i << " -> NULL" << endl;}}private:vector<HashData<K, V>> _table;size_t _n = 0; // 表中存储数据个数};
}
1.2二次探测
线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式是挨个往后去找。二次探测就避免了这个问题,在二次探测中,若初始哈希位置 Hash(Key) = h
已被占用,则探测下一个位置的公式为:h(i) = (h + i^2) % m(其中i = 1,2,3,...)。
插入元素13时,与元素3产生冲突,通过二次探测,找到新的哈希位置7进行插入。
2. 开散列
概念
开散列法又叫链地址法(开链法),它解决哈希冲突的办法是:将具有相同哈希地址的元素通过单链表链接,而哈希表中存放的是各链表的头节点。
插入的情况:
初始哈希表中存放都是空指针。需要进行元素插入时,首先根据哈希函数计算出对应的哈希地址,然后为该元素开辟一块地址空间(存放元素数据_data 以及_next指针用于链接冲突的元素)
如果该哈希地址为空,则存放元素节点指针:
如果当前地址发生哈希冲突,则使用头插的方法,即新节点的_next指针指向旧节点,哈希表中更新头结点指针:
与开散列不同的是,由于插入的元素通过单链表的方式进行链接,哈希表中只需要存放各链表头结点指针,所以哈希表不需要扩容就可以实现任意元素的插入。但是不要忘记我们的初衷,哈希表是为了提高数据的搜索效率的,因此我们需要控制链表的长度(链表越长,搜索效率越低下),原理和闭散列一样,也是通过对哈希表扩容,实现元素的分散存储。
在开散列中,我们通常将载荷因子定为1 ,即表中元素个数等于散列表长度时,进行扩容。扩容之后需要更新哈希地址,重新进行存储。
下面是扩容后的情况(仅演示地址更新情况,其实该散列还不需要扩容):
删除的情况:
删除指定元素时,我们需要对该元素存放节点进行空间释放,释放后要注意更新链表的链接情况
代码实现
#pragma once
#include<iostream>
using namespace std;
#include<string>
#include<vector>// 哈希函数采用除留余数法
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 hash = 0;for (auto e : key){hash *= 31;hash += e;}return hash;}
};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 = HashFunc<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;}_n = 0;}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;HashFunc hf;// 根据装载因子决定是否扩容if (_n == _table.size()){size_t newSz = _table.size() * 2;vector<Node*> newTB ;newTB.resize(newSz, nullptr);for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){Node* next = cur->_next;// 头插到新表size_t newi = hf(cur->_kv.first) % newSz;cur->_next = newTB[newi];newTB[newi] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newTB);}// 插入操作size_t hashi = hf(kv.first) % _table.size();Node* newNd = new Node(kv);newNd->_next = _table[hashi];_table[hashi] = newNd;++_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* cur = _table[hashi];if (!cur)return false;if ( cur->_kv.first == key){_table[hashi] = cur->_next;return true;}Node* prev = _table[hashi];cur = cur->_next;while (cur){if (cur->_kv.first == key){prev->_next = cur->_next;delete cur;cur = nullptr;return true;}cur = cur->_next;prev = prev->_next;}return false;}void Print(){for (size_t i = 0; i < _table.size(); i++){if (_table[i]){cout << i << ":";Node* cur = _table[i];while (cur){cout << "-->(" << cur->_kv.first << "," << cur->_kv.second << ")";cur = cur->_next;}}elsecout << i << ":-->NULL";cout << endl;}}private:vector<Node*> _table; // 指针数组size_t _n = 0; // 存储了多少个有效数据};
}
以上就是对哈希冲突的两种常见解决办法的介绍,欢迎在评论区留言,码文不易,觉得这篇博客对你有帮助的,可以点赞收藏关注支持一波~😉
相关文章:

【C++】哈希冲突的解决办法:闭散列 与 开散列
哈希冲突解决 上一篇博客提到了,哈希函数的优化可以减小哈希冲突发生的可能性,但无法完全避免。本文就来探讨一下解决哈希冲突的两种常见方法:闭散列和开散列 1.闭散列 闭散列也叫开放定址法,发生哈希冲突时,如果哈…...

复刻系列-原神 5.1 版本先行展示页
复刻原神 5.1 版本先行展示页 0. 视频 BilBil站视频演示 复刻-原神5.1版本先行展示页 1. 基本信息 作者: 啊是特嗷桃系列: 复刻系列官方的网站: 《原神》官方网站-全新5.1版本「命定将焚的虹光」上线!复刻的网站: 《原神》复刻网站-全新5.1版本「命定将焚的虹光」…...

STM32 第3章 如何用串口下载程序
时间:2024.10.28 一、学习内容 1、安装USB转串口驱动 1.1串口下载连接示意图 1、USB转串口模块在开发板上是一个独立的模块,可通过调帽与其他串口连接,USART1/2/3/4/5 2、只有USART1才具有串口下载的功能。 3、CH340是电平转换芯片,将电脑端输出的USB电平和单片机输…...

HT71782 20V,15A全集成同步升压转换器
1、特征 输入电压范围VN:2.7V-20V 输出电压范围VouT:4.5V-20V 可编程峰值电流:15A 高转换效率: 93%(VIN7.4V,VoUT15.5V,IouT 1.5A) 轻载条件下两种调制方式:脉频调制(PFM)和 强制脉宽调试(FPWM) 支持两种tr/t模式,应对EMI挑战 低关断功耗,关断电流1uA 可…...

[含文档+PPT+源码等]精品基于PHP实现的培训机构信息管理系统的设计与实现
基于PHP实现的培训机构信息管理系统的设计与实现背景,可以从以下几个方面进行阐述: 一、社会发展与教育需求 随着经济的不断发展和人口数量的增加,教育培训行业迎来了前所未有的发展机遇。家长对子女教育的重视程度日益提高,课外…...

亚信安全DeepSecurity中标知名寿险机构云主机安全项目
近日,亚信安全DeepSecurity成功中标国内知名寿险机构的云主机安全项目。亚信安全凭借在云主机安全防护领域的突出技术优势,结合安全运营的能力,以“实战化”为指导,为用户提供无惧威胁攻击、无忧安全运营的一站式云安全体系&#…...

论文解析八: GAN:Generative Adversarial Nets(生成对抗网络)
目录 1.GAN:Generative Adversarial Nets(生成对抗网络)1、标题 作者2、摘要 Abstract3、导言 IntroductionGAN的介绍 4、相关工作 Related work5、模型 Adversarial nets总结 6.理论计算 Theoretical Results具体算法公式全局优化 Global O…...
【ARM】ARM架构参考手册_Part B 内存和系统架构(2)
目录 2.1 关于系统控制协处理器 2.2 寄存器 2.1 关于系统控制协处理器 所有标准内存和系统设施都由协处理器15(CP15)控制,因此它被称为系统控制协处理器。有些设施也使用其他控制方法,这些方法在描述这些设施的章节中有描述。例…...
HttpServer模块 --- 封装TcpServer支持Http协议
目录 模块设计思想 模块代码实现 模块设计思想 本模块就是设计一个HttpServer模块,提供便携的搭建http协议的服务器的方法。 那么这个模块需要如何设计呢? 这还需要从Http请求说起。 首先http请求是分为静态资源请求和功能性请求的。 静态资源请求…...

蓝牙资讯|iOS 18.1 正式版下周推送,AirPods Pro 2耳机将带来助听器功能
苹果公司宣布将在下周发布 iOS 18.1 正式版,同时确认该更新将为 AirPods Pro 2 耳机带来新增“临床级”助听器功能。在启用功能后,用户首先需要使用 AirPods 和 iPhone 进行简短的听力测试,如果检测到听力损失,系统将创建一项“个…...
C语言之环形缓冲区概述及实现
在C语言中存在一种高效的数据结构,叫做环形缓存区,其被广泛用于处理数据流与缓存区的管理。如:数据的收发、程序层级之间的数据交换、硬件接收大量数据的场景,同时也可配合DMA实现通信协议收发数据,已确保流量控制、数…...
C++Socket通讯样例(服务端)
1. 创建Socket实例并开启。 private int OpenTcp(int port, string ip "") {//1. 开启服务端try{_tcpServer new Socket(AddressFamily.InterNetwork, SocketType.Stream, ProtocolType.Tcp);IPAddress ipAddr IPAddress.Any;if (ip ! "" && i…...

【学术会议论文投稿】大数据治理:解锁数据价值,引领未来创新
第六届国际科技创新学术交流大会(IAECST 2024)_艾思科蓝_学术一站式服务平台 更多学术会议请看:https://ais.cn/u/nuyAF3 目录 引言 一、大数据治理的定义 二、大数据治理的重要性 三、大数据治理的核心组件 四、大数据治理的实践案例…...
location中href和replace的区别
1.有两种方式: a、使用 location.href:window.location.href“success.html”; b、使用location.replace:window.location.replace(“new_file.html”); 2.区别是什么? 结果:href相当于打开一个新页面,…...

基于Spring Boot的在线摄影工作室开发指南
1系统概述 1.1 研究背景 随着计算机技术的发展以及计算机网络的逐渐普及,互联网成为人们查找信息的重要场所,二十一世纪是信息的时代,所以信息的管理显得特别重要。因此,使用计算机来管理网上摄影工作室的相关信息成为必然。开发合…...

JDK源码系列(五)—— ConcurrentHashMap + CAS 原理解析
更好的阅读体验 \huge{\color{red}{更好的阅读体验}} 更好的阅读体验 ConcurrentHashMap 类 ConcurrentHashMap 1.7 在JDK1.7中ConcurrentHashMap采用了数组分段锁的方式实现。 Segment(分段锁)-减少锁的粒度 ConcurrentHashMap中的分段锁称为Segment,它即类似于…...
技术成神之路:二十三种设计模式(导航页)
设计原则/模式链接面向对象的六大设计原则技术成神之路:面向对象的六大设计原则创建型模式单例模式建造者模式原型模式工厂方法模式抽象工厂模式行为型模式策略模式状态模式责任链模式观察者模式备忘录模式迭代器模式模板方法模式访问者模式中介者模式命令模式解释器…...

Rust编程与项目实战-元组
【图书介绍】《Rust编程与项目实战》-CSDN博客 《Rust编程与项目实战》(朱文伟,李建英)【摘要 书评 试读】- 京东图书 (jd.com) Rust编程与项目实战_夏天又到了的博客-CSDN博客 8.2.1 元组的定义 元组是Rust的内置复合数据类型。Rust支持元组,而且元…...

容性串扰和感性串扰
串扰根源在于耦合,电场耦合产生容性耦合电流,磁场耦合产生感性耦合电流 关于容性后向串扰电压与后向串扰系数推导...

windows Terminal 闪退 -- 捣蛋砖家
最近点击Windows 终端总是闪退。 日志提示: 错误应用程序名称: WindowsTerminal.exe,版本: 1.21.2410.17001,时间戳: 0x67118f02 错误模块名称: ucrtbase.dll,版本: 10.0.22621.3593,时间戳: 0x10c46e71 异常代码: 0xc0000409 错…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...

微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...

练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...

全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...

MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...