哈希表-数据结构
一、哈希表基本概念
哈希表(也称为散列表)是根据键而直接访问在内存存储位置的数据结构,也就是说实际上是经过哈希函数进行映射,映射道表中一个位置来访问记录,这个存放记录的数组称为散列表。
哈希函数:就是将要存储的数据经过运算,映射到我们要存储的位置
二、哈希的本质
本质是一给数组,将通过哈希函数映射,将一定的数据放在指定的位置,再通过映射能够很快找到数据。
三、哈希冲突(哈希矛盾)

就是经过运算,不同的数据,但是,对应相同的位置,而前面这个地方已经将数据存储,要尽可能避免冲突
四、解决哈希冲突的办法
4.1、开放寻址法
简单点来说,对于冲突元素,找到空位置,放进去即可
开放寻址法(Open Addressing)是一种解决哈希冲突的方法,它在哈希表中直接解决冲突,即当两个或多个键的哈希值相同时,它们会尝试在哈希表中找到下一个空闲位置来存储数据。开放寻址法的主要思想是所有的元素都存储在哈希表中,而不是像链地址法那样在表外链接。
4.2、链地址法
链地址法(Separate Chaining)是另一种解决哈希冲突的方法。在这种方法中,哈希表的每个槽(slot)或桶(bucket)都关联一个链表,我们把具有相同属性的元素进行连接,最后只需要我们进行查找的时候只需要进行哈希映射,找到数组的地址之后,去遍历里面的链表,找到对应的元素。用于存储具有相同哈希值的所有元素。
工作原理
1. **哈希函数**:首先,使用哈希函数将键映射到哈希表的一个位置。
2. **冲突处理**:如果两个键映射到同一个位置(即发生冲突),它们会被存储在同一个链表中。
3. **插入操作**:插入新元素时,首先计算其哈希值,然后在对应的链表中添加新元素。
4. **查找操作**:查找元素时,首先计算其哈希值,然后在对应的链表中遍历查找。
5. **删除操作**:删除元素时,首先找到对应的链表,然后在链表中找到并删除元素。
### 优点
- **简单易实现**:链地址法的实现相对简单,容易理解。
- **动态扩容**:可以通过调整链表的大小来动态地处理负载因子的变化,从而保持操作的效率。
### 缺点
- **额外空间**:每个槽需要额外的空间来存储链表的指针,这可能会增加内存的使用。
- **性能依赖于负载因子**:当哈希表的负载因子(即表中元素数量与槽数量的比率)较高时,链表可能会变得较长,导致查找效率下降。
### 性能优化
- **动态扩容**:随着元素的增加,可以动态地增加哈希表的大小,以保持负载因子在一个合理的范围内。
- **负载因子控制**:通过控制负载因子,可以平衡内存使用和查找效率。
链地址法是哈希表中常用的冲突解决策略之一,适用于键值对的存储和快速查找。
五、哈希操作
1、哈希表的创建
int hash_function(char key)
{if (key >= 'a' && key <= 'z'){return key-'a';}else if (key >= 'A' && key <= 'Z'){return key-'A';}else{return HASH_SIZE-1;}
}
2、哈希表的插入
int insert_hashtable(HSDataTYpe data)
{int addr = hash_function(data.name[0]);HSNode_t *pnode = malloc(sizeof(HSNode_t));if(NULL == pnode){perror("fail malloc");return -1;}pnode->data = data;pnode->pnext = NULL;pnode->pnext = hashtable[addr];hashtable[addr] = pnode;return 0;
}vv
3、哈希表的遍历
void each_for_hsnode()
{for(int i = 0;i < HASH_SIZE;++i){HSNode_t *pnode = hashtable[i];while(pnode != NULL){printf("name = %s\n",pnode->data.name);printf("telephone = %s\n",pnode->data.tel);pnode = pnode->pnext;}}printf("\n");
}
4、哈希表的查找
void find_hsnode(HSDataTYpe data)
{int addr = hash_function(data.name[0]);HSNode_t *pnode = hashtable[addr];while(pnode != NULL){if(strcmp(pnode->data.name,data.name) == 0){printf("name = %s\n",pnode->data.name);printf("telephone = %s\n",pnode->data.tel);break;}pnode = pnode->pnext;}printf("\n");
}
5、哈希表的销毁
void destory_hsnode()
{for(int i = 0;i < HASH_SIZE;++i){HSNode_t *p = NULL;while(hashtable[i]!= NULL){p = hashtable[i];hashtable[i] = p->pnext;free(p);}}
}
相关文章:
哈希表-数据结构
一、哈希表基本概念 哈希表(也称为散列表)是根据键而直接访问在内存存储位置的数据结构,也就是说实际上是经过哈希函数进行映射,映射道表中一个位置来访问记录,这个存放记录的数组称为散列表。 哈希函数:就…...
指针之旅(4)—— 指针与函数:函数指针、转移表、回调函数
目录 1. 函数名的理解 1.1 “函数名”和“&函数名”的含义 1.2 函数(名)的数据类型 2. 函数指针(变量) 2.1 函数指针(变量)的创建格式 2.2 函数指针(变量)的使用格式 2.3 例子 判别 3. typedef 关键字 3.1 typedef的作用 3.2 typedef的运作逻辑 和 函数指针类型…...
打造线上+线下相结合的O2O平台预约上门服务小程序源码系统 带完整的安装代码包以及搭建部署教程
系统概述 本系统采用前后端分离的设计架构,前端以微信小程序为载体,提供直观、易用的用户界面;后端则采用稳定的服务器架构,确保数据处理的高效与安全。系统主要包括用户端、商户端和管理员端三大模块,通过API接口实现…...
python sys模块
在Python中,sys模块提供了访问和使用解释器的许多功能的方法,包括命令行参数、环境变量、路径管理、标准输入输出流等。sys模块是Python的标准库的一部分,不需要额外安装即可使用。 常用的sys模块功能 1. sys.argv sys.argv是一个包含命令…...
【Linux 报错】SSH服务器拒绝了密码。请再试一次。(xshell)
出现该错误 可能的原因: 你写入的登录密码错误了,错误原因有: 1、本来输入就错误了 2、创建用户时,只创建了用户名,但密码没有重新设置 3、多人使用同一台服务器时,该服务器管理员(本体&#x…...
云计算实训43——部署k8s基础环境、配置内核模块、基本组件安装
一、前期系统环境准备 1、关闭防火墙与selinux [rootk8s-master ~]# systemctl stop firewalld[rootk8s-master ~]# systemctl disable firewalldRemoved symlink /etc/systemd/system/multi-user.target.wants/firewalld.service. Removed symlink /etc/systemd/system/dbus…...
TAbleau 可视化 干货分享 | 简单三步助你打造完美仪表板
只需单击几下,你将能轻松创建美观、信息丰富的可视化效果、节省时间并推动业务向前发展! 借助精心设计的仪表板,分析师可以更好地理解复杂数据背后的信息,更有效地向他人分享你的见解,从而做出更明智的决策。 值得思考…...
JVM性能调优之5种垃圾收集器
JDK垃圾收集器 一、Serial GC垃圾收集器Serial GC的工作原理Serial GC的特点Serial GC的配置参数Serial GC的适用场景Serial GC的优缺点优点:缺点: Serial GC的总结 二、Parallel GC垃圾收集器Parallel GC的工作原理Parallel GC的特点Parallel GC的配置参…...
基于单片机的仔猪喂饲系统设计
文章目录 前言资料获取设计介绍功能介绍设计清单具体实现截图参考文献设计获取 前言 💗博主介绍:✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师,一名热衷于单片机技术探索与分享的博主、专注于 精通51/STM32/MSP430/AVR等单片机设…...
Helm Deploy Online Rancher v2.9.1
文章目录 准备安装查看下载 准备 $ kubectl get node NAME STATUS ROLES AGE VERSION kube-master01 Ready control-plane 19d v1.29.5 kube-node01 Ready <none> 19d v1.29.5 kube-node02 Ready <none&…...
【办公效率】Axure会议室预订小程序原型图,含PRD需求文档和竞品分析
作品说明 作品页数:共50页 兼容版本:Axure RP 8/9/10 应用领域:中小型企业的会议室在线预订 作品申明:页面内容仅用于功能演示,无实际功能 作品特色 本作品为会议室预订小程序原型图,定位于拥有中大型…...
论文解析一: SuperPoint 一种自监督网络框架,能够同时提取特征点的位置以及描述子
目录 SuperPoint:一种自监督网络框架,能够同时提取特征点的位置以及描述子1.特征点预训练2.自监督标签3.整体网络结构3.1 先对图像进行卷积3.2 特征点提取部分(Interest Point Decoder)3.3 特征描述子提取部分(Descrip…...
【评估指标】Fβ-score
1. Fβ-score 概述 Fβ-score 是一种综合考量精确率(precision)和召回率(recall)的分类评估指标。其公式为: 1.1 Precision(精确率):预测为正类的样本中,实际为正类的比…...
1963Springboot个性化音乐推荐管理系统idea开发mysql数据库web结构java编程计算机网页源码maven项目
博主介绍:专注于Java .net php phython 小程序 等诸多技术领域和毕业项目实战、企业信息化系统建设,从业十五余年开发设计教学工作 ☆☆☆ 精彩专栏推荐订阅☆☆☆☆☆不然下次找不到哟 我的博客空间发布了1000毕设题目 方便大家学习使用 感兴趣的可以…...
solidity从入门到精通(持续更新)
我一度觉得自己不知何时变成了一个浮躁的人,一度不想受外界干扰的我被干扰了,再无法平静的去看一本书,但我仍旧希望我能够克服这些,压抑着自己直到所有的冲动和奇怪的思想都无法再左右我行动。 自律会让你更加自律,放纵…...
UEFI入门(二):edk2项目编译流程
UEFI入门(二):edk2项目编译流程 一、编译构建流程:1. 安装依赖工具2. 初始化构建环境3. 配置工具链和目标4. 定义平台配置5. 构建并编译 二、uefi-tools编译edk2实践:1. 克隆EDK2 项目2. 构建并编译 参考文章ÿ…...
局域网一套键鼠控制两台电脑(台式机和笔记本)
服务端(有键盘和鼠标的电脑作为服务端) 下载软件 分享文件:BarrierSetup-2.3.3.exe 链接:https://pan.xunlei.com/s/VO66rAZkzxTxVm-0QRCJ33mMA1?pwd4jde# 配置服务端 一, 二, 客户端屏幕名称一定要和…...
最新Nessus2024.9.8版本主机漏洞扫描/探测工具下载Windows版
Nessus号称是世界上最流行的漏洞扫描程序,全世界有超过75000个组织在使用它。该工具提供完整的电脑漏洞扫描服务,并随时更新其漏洞数据库。Nessus不同于传统的漏洞扫描软件,Nessus可同时在本机或远端上遥控,进行系统的漏洞分析扫描…...
关于使用 @iconify/vue2图标库组件的离线使用
Iconify 是最通用的图标框架,将各种图标库的图标集中在这里的一个组件库,例如ant-design,element-ui等 网站地址如下 https://iconify.design/getting-started/ 1.安装依赖 这两个包提供了图标组件和离线图标数据的支持。 npm install iconify/vue2 i…...
pdfmake生成pdf的使用
实际项目中有时会有根据填写的表单数据或者其他格式的数据,将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdf…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
