[数据结构] 哈希结构的哈希冲突解决哈希冲突
标题:[C++] 哈希结构的哈希冲突 && 解决哈希冲突
@水墨不写bug

目录
一、引言
1.哈希
2.哈希冲突
3.哈希函数
二、解决哈希冲突
1.闭散列
I,线性探测
II,二次探测
2.开散列
正文开始:
一、引言
哈希表是一种非常实用而且好用的关联式容器,如果你刷过不少题,一定会惊叹哈希竟然能解决如此多的实际问题。
但是哈希表令人头疼的问题是哈希冲突的问题。在具体讲解之前,我们先铺垫引入几个概念:哈希,哈希函数,哈希冲突。
1.哈希
哈希结构最明显的特点是高效。在以往的顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O(log2 N),搜索的效率取决于搜索过程中元素的比较次数。
最优的搜索方法:不经过任何比较,一次直接从表中得到要搜索的元素。
如果存在一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码(key)之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素。
当我们向该结构中:
插入元素的时候:根据插入元素的关键码,根据这个关键码来通过某种映射关系来得到哈希表中对应的存储位置,然后将这个元素存入哈希表的对应位置。
搜索元素的时候:对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在哈希表中按照此位置进行查找,若关键码相等,则搜索成功。
这种存储结构和方法统称为哈希。
哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(Hash Table)(或者称散列表).
2.哈希冲突
我们可以设计一个简单的哈希表:10个位置,哈希函数也是非常简单的除留取余(插入元素除以表的大小,就通过哈希函数得到了这个值应该在表中存储的位置):
用该方法进行搜索可以一次找到存储对应值的位置,因此搜索的速度比较快。
但是,如果向上面这样的哈希表中插入14呢?
我们发现14的位置被4占据了,这就是哈希冲突。
即:不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”.
3.哈希函数
引起哈希冲突的一个原因可能是:哈希函数设计不够合理。
哈希函数设计原则:
1.哈希函数的定义域必须包括需要存储的全部关键码,同时如果散列表允许有m个地址时,其值域必须在0到m-1之间。
2.哈希函数计算出来的地址能尽可能的均匀分布在整个空间中。
3.哈希函数应该比较简单。
我们需要了解一下常见的哈希函数的设计方法:
1. 直接定址法
取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B
优点:简单、均匀、一般不会出现哈希冲突
缺点:需要事先知道关键字的分布情况
使用场景:适合查找比较小且连续的情况
2. 除留余数法.
设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:Hash(key) = key% p(p<=m),将关键码转换成哈希地址.
优点:适用情况广泛
缺点:会出现哈希冲突,需要解决哈希冲突的问题
二、解决哈希冲突
哈希冲突的解决方法常用的有两种:闭散列与开散列。
1.闭散列
闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。
寻找下一个“空位置”也有多种方法,这里介绍常见的两种:线性探测,二次探测。
I,线性探测
在上面的例子中,我们想要插入14,本来14经过哈希函数计算得到的位置是4,但是4这个位置已经被占据了。
线性探测就是:从发生冲突的位置开始,一个一个向后探测,直到寻找到下一个空位置为止。
a.插入
首先通过哈希函数获取待插入元素在哈希表中的位置。 如果该位置中没有元素则直接插入新元素;如果该位置中有元素发生哈希冲突,使用线性探测找到下一个空位置,插入新元素:b.删除
采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。
比如:删除元素4,如果直接删除掉,14查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
我们可以通过一个标记状态的变量来表示哈希表内的数据的状态:存在,删除,空(EXIST,DELETE,EMPTY):
enum STATE {EXIST,DELETE,EMPTY }在封装哈希表中每一个数据的类型时,在每个数据结构体内加入一个表示状态的变量即可。对于一个哈希表的位置,如果没有元素插入过,状态为EMPTY;
如果存在元素,状态为EXIST;
如果原来存在元素,但是之后删除了,状态为DELETE;
不同的状态对于将来查找(find)的处理会有影响。
II,二次探测
通过了解上面的线性探测,你自然也会发现线性探测的困难:
产生冲突的数据堆积在一块,这与其一个一个向下找空位置有关系,找空位置的方式就是挨着往后逐个去找.
二次探测的找下一个空位置的方法就大不相同了:二次探测向下找的方式是依次加上位置差的平方:
H_i = (H_0 + i^2 )% m 或者H_i = (H_0 - i^2 )% m
其中:i = 1,2,3…, H_0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置,m是表的大小。
对于上面的例子,如果使用二次探测,插入的过程:
插入 44 的过程:
1.44 的初始哈希值是 14 % 10 = 4 ,但是位置 4 已经被占用了。
2.触发二次探测,从 i = 1 开始。对于 i = 1 ,探测位置是:(4 + 1^2) % 10 = 5 但位置 5 也被占用了。
3.继续探测, i = 2 时,探测位置是:(4 + 2^2) % 10 = 8位置 8 是空的,所以 14 被插入到位置 8。

对于闭散列而言,哈希表是需要扩容的,因为我们每次插入的时候都需要保证哈希表有空余的位置,所以我们需要一个判断哈希表内数据 装满程度的标志因子:载荷因子
载荷因子记为a,a越大,表明填入表中的数据越多,产生哈希冲突的可能就越大。反之则相反。
对于开放定址法,载荷因子需要严格控制在0.7-0.8以下。当载荷因子接近这个值时,就需要扩容。
2.开散列
开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中:

当插入14时,对4这个位置的链表头插即可:

以上是哈希结构解决哈希冲突的方法。
完~
未经作者同意禁止转载
相关文章:
[数据结构] 哈希结构的哈希冲突解决哈希冲突
标题:[C] 哈希结构的哈希冲突 && 解决哈希冲突 水墨不写bug 目录 一、引言 1.哈希 2.哈希冲突 3.哈希函数 二、解决哈希冲突 1.闭散列 I,线性探测 II,二次探测 2.开散列 正文开始: 一、引言 哈希表是一种非常实用而…...
Wimdows使用Appium IOS自动化
启动appium服务器: appium -a 127.0.0.1 -p 4724 配置 { "platformName": "iOS", "appium:platformVersion": "16.5.1", "appium:deviceName": "(★StatTrak™) |午夜黑(崭新出厂&#…...
C语言深度剖析--不定期更新的第四弹
哈哈哈哈哈哈,今天一天两更! void关键字 void关键字不能用来定义变量,原因是void本身就被编译器解释为空类型,编译器强制地不允许定义变量 定义变量的本质是:开辟空间 而void 作为空类型,理论上不应该开…...
【手撕数据结构】八大排序神功(上)
目录 冒泡排序【有点拉胯】动图演示:思路解析单趟算法图解代码详解性能优化复杂度分析 直接插入排序【还阔以】动图演示思路解析代码分析与讲解复杂度分析 希尔排序【有点强】动图演示思路讲解排序过程总览代码分析讲解复杂度分析 堆排序【太有石粒啦】动图演示堆的概念与结构向…...
【2024高教社杯全国大学生数学建模竞赛】B题模型建立求解
目录 1问题重述1.1问题背景1.2研究意义1.3具体问题 2总体分析3模型假设4符号说明(等四问全部更新完再写)5模型的建立与求解5.1问题一模型的建立与求解5.1.1问题的具体分析5.1.2模型的准备 目前B题第一问的详细求解过程以及对应论文部分已经完成ÿ…...
OpenHarmony鸿蒙开发( Beta5.0)智能手表应用开发实践
样例简介 本项目是基于BearPi套件开发的智能儿童手表系统,该系统通过与GSM模块(型号:SIM808)的通信来实现通话和定位功能。 智能儿童手表系统可以通过云和手机建立连接,同步时间和获取天气信息,通过手机下…...
共享单车轨迹数据分析:以厦门市共享单车数据为例(一)
共享单车数据作为交通大数据的一个重要组成部分,在现代城市交通管理和规划中发挥着越来越重要的作用。通过对共享单车的数据进行深入分析,城市管理者和规划者能够获得大量有价值的洞察,这些洞察不仅有助于了解城市居民的日常出行模式…...
SprinBoot+Vue在线商城微信小程序的设计与实现
目录 1 项目介绍2 项目截图3 核心代码3.1 Controller3.2 Service3.3 Dao3.4 application.yml3.5 SpringbootApplication3.5 Vue3.6 uniapp代码 4 数据库表设计5 文档参考6 计算机毕设选题推荐7 源码获取 1 项目介绍 博主个人介绍:CSDN认证博客专家,CSDN平…...
4--SpringBootWeb-请求响应
目录 postman 1.简单参数 请求参数名与形参变量名一致时 请求参数名与形参变量名不一致时 2.实体参数 简单实体对象 复杂实体对象 3.数组集合参数 数组 集合 4.日期参数 5.JSON参数 6.路径参数 1 2 postman Postman值一款功能强大的网页调试与发送网页HTTP请求的…...
电脑点击关机之后,又自动重启开机了。根本就关不了?
前言 有个小姐姐说,她家的电脑好生奇怪:点击【关机】按钮之后,电脑提示【正在关机】,过了几秒,电脑又自动开机了…… 好家伙!也就是说关机和重启根本就没区别,电脑完全无法断电。 最后忍无可…...
强化网络安全:通过802.1X协议保障远程接入设备安全认证
随着远程办公和移动设备的普及,企业网络面临着前所未有的安全挑战。为了确保网络的安全性,同时提供无缝的用户体验,我们的 ASP 身份认证平台引入了先进的 802.1X 认证协议,确保只有经过认证的设备才能接入您的网络。本文档将详细介…...
链动2+1模式AI智能名片S2B2C商城小程序源码在社群商业价值构建中的应用探索
摘要:在数字经济浪潮的推动下,社群作为商业生态的核心组成部分,其商业价值正以前所未有的速度增长。本文深入探讨了如何通过“链动21模式AI智能名片S2B2C商城小程序源码”这一前沿技术工具,深度挖掘并优化社群的商业价值。通过详细…...
基于SpringBoot+Vue+MySQL的校园周边美食探索及分享平台
系统背景 在当今数字化时代,校园生活正日益融入信息技术的浪潮之中,学生们对于便捷、高效且富有趣味性的生活方式有着越来越高的追求。特别是在饮食文化方面,随着校园周边餐饮业态的日益丰富,学生们渴望一个能够集美食探索、分享与…...
“设计模式双剑合璧:工厂模式与策略模式在支付系统中的完美结合”
工厂模式(Factory Pattern)和策略模式(Strategy Pattern)都是常见的设计模式,但它们解决的问题和应用场景不同。下面是它们的区别: 1. 目的不同: 工厂模式(Factory Pattern…...
第二百一十九节 JPA 教程 - JPA 字段映射示例
JPA 教程 - JPA 字段映射示例 当将 Java bean 字段映射到数据库列时,我们可以选择标记字段,标记 getter 方法并标记两者。 标记字段 以下代码来自 Professor.java。 它显示如何将主键列标记为 Java bean 字段标识。 package cn.w3cschool.common; im…...
目标检测-YOLOv6
YOLOv6 YOLOv6 是 YOLO 系列的一个新版本,相比 YOLOv5 进行了大量的优化与改进。YOLOv6 的设计目标是在提高模型检测精度的同时,进一步优化速度和效率,特别是在推理速度和部署便捷性方面。它采用了更先进的网络架构和优化技巧,在…...
Java面向对象与多态
目录 Java面向对象与多态 多态介绍 形成多态的前提 多态下成员访问的特点 成员变量 成员方法 访问特点总结 多态对比普通继承 普通继承优点与缺点 多态优点与缺点 向上转型与向下转型 向下转型存在的问题 多态接口练习 Java面向对象与多态 多态介绍 在前面学习到…...
redis分布式锁和lua脚本
业务场景:多个线程对共同资源的访问:库存超卖/用户重复下单的原因 解决方法一:利用jvm内置锁,将非原子性操作变成原子性操作 Synchronized锁的是对象,对象必须是单例的。锁的是this,代表当前所在的类,这个…...
项目实战 ---- 商用落地视频搜索系统(5)---service层核心
目录 背景 向下service 层 描述 功能 代码实现 核心阐述 向上service层 描述 功能 代码实现 核心阐述 背景 之前的 1-4 重点在介绍系统的实现架构,录入数据的组织形式,存储模式,search 方式,以及后期算法等。重点都是聚焦在后端。现在来看,基本的后端实现我们…...
Win32远线程注入
远线程注入 远线程(RemoteThread)注入是指一个进程在另一个进程中创建线程的技术,这是一种很经典的DLL注入技术。 虽然比较古老,但是很实用。通过远线程注入,再配合api函数的hook技术,可以实现很多有意思的功能。 实现远线程注入…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...


b.删除