6.C_数据结构_查询_哈希表

概述

哈希表的查询是通过计算的方式获取数据的地址,而不是依次比较。在哈希表中,有一个键值key,通过一些函数转换为哈希表的索引值。

其中:这个函数被称为哈希函数、散列函数、杂凑函数,记为:H(key)

哈希函数构造与冲突:

直接地址法、平方取中法、叠加法、保留余数法、随机函数法

  • 保留除数法(质数除余法):

设哈希表空间长度为m,则哈希函数为:H(key) = key%p     其中:p<=m 且 p为最大质数。

  • 冲突:

冲突是指表中某个地址已经存放了记录,但新的记录通过计算之后也要存放在这个地址。比如:p=3,key1=3,key2=6,key1、key2取余之后都是0,这就产生了冲突。

哈希函数一定会存在冲突,选择随机度好的哈希函数可以减少冲突但是不能消除冲突。

对于顺序存储哈希保留除数法的处理冲突的哈希函数:Hi = (H(key)+di)%m  即:加一个步长。

对于di,线性探查法di = 1,2,3....  二次探查法di = 1^2,-1^2,2^2,-2^2....

对于链式存储哈希保留除数法的处理冲突的方法:将冲突的位置连成一个链表。下一章详细分析。

  • 装填因子:

装填因子α = n/m ,代表总数据个数n,所占总哈希表空间m的值。一般α = 0.7~0.8这代表30%~20%的哈希表空间为空闲状态,用于存储冲突的数据。

  • 举例

例:有8个数据要存,装填因子α=0.8,这8个数据的键值为{0,1,2,3,4,5,6,7,8}。以线性探查法处理冲突设计一个哈希表。

解:哈希表的空间m = n/α = 10。那么哈希函数中的p的值就是不大于10的最大质数,就是7。

        对八个键值求H(key)=key%7得:{0,1,2,3,4,5,6,0,1},因此7,8冲突

        key=7  7%7=0,与0冲突,线性探查法依次为1,2,3,4,5,6,7,位置7不再冲突,因此存放在7处

        key=8  8%7=1,与1冲突,线性探查法依次为2,3,4,5,6,7,8,位置8不再冲突,因此存放在8处

        最终的哈希表数据分布如下:

链式哈希的实现

1、基本内容

链式哈希的构成是:将冲突结点构成一个链表,在哈希表中存放着这个冲突结点的冗余头结点。

具体的链式哈希结构如下:

哈希表及冲突数据结点结构体声明如下:

typedef int keyType;
typedef int data_t;
//数据冲突结点
typedef struct node{keyType key;	data_t data;struct node* pNext;
}listnode,*linklist;
//哈希表
typedef struct hash{listnode* pArr;  //存放链表结点指针,该指针为数组指针int len;         //哈希表的长度
}hash;

哈希表代码的文件构成:

  • hash.h:数据结构的定义、运算函数接口
  • hash.c:运算函数接口的实现
  • test.c:使用数据结构实现的应用功能代码

2、哈希表代码实现

2.1 哈希表创建

哈希表的创建就是开辟一个空间,初始化全部的元素,使得该冗余头的pNext = NULL

具体代码实现如下:

/** hash_create:创建哈希表* param len:哈希表的长度* @ret  NULL--err  other--哈希表的指针* */
hash* hash_create(int len){hash* pHash = NULL;//1.申请空间//1.1 申请哈希结构体空间pHash = (hash*)malloc(sizeof(hash));if(pHash == NULL){printf("hash malloc err\n");return NULL;}//1.2 申请存放链表结点指针的数组空间pHash->pArr = (linklist)malloc(sizeof(listnode)*len);if(pHash->pArr == NULL){printf("pArr malloc err\n");free(pHash);return NULL;}//2.初始化memset(pHash->pArr,0,sizeof(linklist)*len);pHash->len = len;return pHash;
}

2.2 冲突数据节点创建

这个创建与普通节点的创建完全一致

具体代码实现如下:

/** hashNode_create:创建哈希结点* param key:结点的键值* param data:结点的数据* @ret  NULL--err  other--结点地址* */
linklist hashNode_create(keyType key,data_t data){linklist pHashNode = NULL;//1.申请空间pHashNode = (linklist)malloc(sizeof(listnode));if(pHashNode == NULL){printf("malloc err\n");return NULL;}//2.初始化pHashNode->key = key;pHashNode->data = data;pHashNode->pNext = NULL;return pHashNode;
}

2.3 插入哈希表

将数据插入哈希表,先利用哈希函数算出在哈希表的哪个位置,之后以key递增的方式有序插入

具体代码实现如下:

/** hash_insert:在哈希表中插入数据* param pHash:哈希表的指针* param pHashNode:新数据的指针* @ret  -1--err  0--success* */
int hash_insert(hash* pHash,linklist pHashNode){int hash_i;//数据哈希表中的位置linklist pHead = NULL;//同一位置的链表头linklist pIn = NULL;//插入点linklist pAhead = NULL;//插入点前一个结点//1.判断参数有效性if(pHash == NULL || pHashNode == NULL){printf("param err\n");return -1;}//2.获取结点在哈希表中的位置hash_i = pHashNode->key % pHash->len;pHead = &(pHash->pArr[hash_i]);pIn = pHead->pNext;pAhead = pHead;//3.在指定哈希表位置处插入//3.1 指定位置出为空if(pHead->pNext == NULL){pHead->pNext = pHashNode;}//3.2 指定位置有数据,键值小的放前面else{//3.2.1 遍历插入while(pIn != NULL){if(pHashNode->key < pIn->key){//插入到当前结点前面pAhead->pNext = pHashNode;pHashNode->pNext = pIn;break;}pAhead = pIn;pIn = pIn->pNext;}//3.2.2 遍历之后依旧没插入,将结点尾插if(pIn == NULL){pAhead->pNext = pHashNode;}}return 0;
}

2.4 查询哈希表

查询哈希表,先利用哈希函数算出所在位置,之后遍历链表找到数据。

具体代码实现如下:

/** hash_search:根据键值查找元素* param pHash:哈希表的指针* param pHashNode:找到的数据存放的位置* param key:键值* @ret  -1--err  0--find it* */
int hash_search(hash* pHash,linklist* ppHashNode,keyType key){int hash_i;//数据哈希表中的位置linklist pHead = NULL;//同一位置的链表头linklist pTmp = NULL;//1.判断参数有效性if(pHash == NULL || ppHashNode == NULL){printf("param err\n");return -1;}//2.获取结点在哈希表中的位置hash_i = key % pHash->len;pHead = &(pHash->pArr[hash_i]);pTmp = pHead->pNext;//3.遍历查找while(pTmp != NULL){if(pTmp->key == key){*ppHashNode = pTmp;break;}pTmp = pTmp->pNext;}if(pTmp == NULL){//没找到printf("not find\n");return -1;}else{//找到了return 0;}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

使用 nvm 管理 node 版本:如何在 macOS 和 Windows 上安装使用nvm

&#x1f525; 个人主页&#xff1a;空白诗 文章目录 一、引言二、nvm的安装与基本使用2.1 macOS安装nvm2.1.1 使用 curl 安装2.1.2 使用 Homebrew 安装 2.2 Windows安装nvm2.2.1 下载 nvm-windows2.2.2 安装 nvm-windows 2.3 安装node2.4 切换node版本 三、常见问题及解决方案…

STM32读写内部flash

一.简介 在 STM32 芯片内部有一个 FLASH 存储器&#xff0c;它主要用于存储代码&#xff0c;我们在电脑上编写好应用程序后&#xff0c;使用下载器把编译后的代码文件烧录到该内部 FLASH 中&#xff0c;由于 FLASH 存储器的内容在掉电后不会丢失&#xff0c;芯片重新上电复位后…

【redis-01】redis基本数据类型和使用场景

redis系列整体栏目 内容链接地址【一】redis基本数据类型和使用场景https://zhenghuisheng.blog.csdn.net/article/details/142406325 redis基本数据类型和使用场景 一&#xff0c;redis基本数据类型和使用场景1&#xff0c;String数据类型2&#xff0c;Hash数据类型3&#xff…

Linux top命令详解与重点内容说明

文章目录 重点说明基本信息进程(任务)信息cpu占用信息%Cpu(s)内存信息交换内存信息每列含义说明交互命令多窗口模式颜色配置命令参数 重点说明 top命令非常强大&#xff0c;也非常复杂&#xff0c;很难面面俱到&#xff0c;也没有必要&#xff0c;这篇文章的目的是介绍重点&am…

2024华为杯研究生数学建模竞赛(研赛)选题建议+初步分析

提示&#xff1a;C君认为的难度&#xff1a;DE<C<F&#xff0c;开放度&#xff1a;CDE>F。 华为专项的题目&#xff08;A、B题&#xff09;暂不进行选题分析&#xff0c;不太建议大多数同学选择&#xff0c;对自己专业技能有很大自信的可以选择华为专项的题目。后续会…

英集芯IP5912:集成开关充电功能的低功耗8位POWER MCU芯片

英集芯IP5912是一款功能丰富的、集成了降压充电管理功能的8位MCU芯片&#xff0c;它内置了一个5V输入的同步降压充电DC-DC&#xff0c;功率管也是内置的&#xff0c;同时提供最大1.5A的充电电流。封装方式采用SOP16&#xff0c;方案应用时只需要很少的外围器件&#xff0c;就可…

【多线程】CAS的原理及应用,看这篇文章就够啦

&#x1f490;个人主页&#xff1a;初晴~ &#x1f4da;相关专栏&#xff1a;多线程 / javaEE初阶 一、CAS概述 CAS&#xff08;Compare and Swap&#xff09;&#xff0c;中文译为 “比较并交换” &#xff0c;是一种无锁算法中常用的原子操作。CAS通常用于实现线程之间的同…

linux之nacos安装

1:下载nacos安装包 方式一、进入官网下载压缩包 官网地址 找到nacos-server-2.0.1.tar.gz 点击进行下载&#xff0c;下载完成后上传到服务器中。 方式二、使用wget命令下载 也有两种方式&#xff1a;第一种下载速度较慢 wget https://github.com/alibaba/nacos/releases/downl…

Zookeeper学习

文章目录 学习第 1 章 Zookeeper 入门1.1 概述Zookeeper工作机制 1.2 特点1.3 数据结构1.4 应用场景统一命名服务统一配置管理统一集群管理服务器动态上下线软负载均衡 1.5 下载zookeeper 第 2 章 Zookeeper 本地安装2.1 本地模式安装安装前准备配置修改操作 Zookeeper本地安装…

【React】React18.2.0核心源码解读

前言 本文使用 React18.2.0 的源码&#xff0c;如果想回退到某一版本执行git checkout tags/v18.2.0即可。如果打开源码发现js文件报ts类型错误请看本人另一篇文章&#xff1a;VsCode查看React源码全是类型报错如何解决。 阅读源码的过程&#xff1a; 下载源码 观察 package…

uniapp使用uview2上传图片功能

官网地址Upload 上传 | uView 2.0 - 全面兼容 nvue 的 uni-app 生态框架 - uni-app UI 框架 前提&#xff0c;需要下载vuew2插件 <view class"upload"><view class"u-demo-block__content"><view class"u-page__upload-item"&…

Observability:构建下一代托管接入服务

作者&#xff1a;来自 Elastic Vishal Raj, Marc Lopez Rubio 随着无服务器&#xff08;serverless&#xff09;的引入&#xff0c;向 Elastic Cloud 发送可观察性数据变得越来越容易。你可以在 Elastic Cloud Serverless 中创建一个可观察性无服务器项目&#xff0c;并将可观察…

一文说清楚ETL与Kafka如何实现集成

ETL与Kafka为何需要集成? 随着企业对实时流数据的处理要求越来越高&#xff0c;很多企业都把实时流数(日志、实时CDC采集数据、设备数据…)先推入到kafka中&#xff0c;再通过ETL对kafka中的数据进行消费通过ETL强大的数据的转换、清洗功能来进行数据的集成与分发。 实时数据…

WebMagic:强大的Java网络爬虫框架

上班苦上班累&#xff0c;上班就想打瞌睡。 在当今信息爆炸的时代&#xff0c;数据的获取和处理变得越来越重要。网络爬虫作为获取网络数据的重要工具&#xff0c;已经成为许多开发者和数据科学家的必备技能。今天&#xff0c;我们将介绍一个广受欢迎的Java网络爬虫框架——We…

硬件工程师笔试面试——存储器件

目录 16、存储器件 16.1 基础 存储器件实物图 16.1.1 概念 16.1.2 常见的存储器件及其特点 16.2 相关问题 16.2.1 不同类型的存储器件在成本和性能上有哪些具体的差异 16.2.2 如何根据应用需求选择合适的存储器件? 16.2.3 存储器件的耐用性和可靠性是如何影响其在不同…

数据结构不再难懂:带你轻松搞定图

数据结构入门学习&#xff08;全是干货&#xff09;——图 1 图 1.1 什么是图 图是一种用于表示多对多关系的数学模型。它由一组顶点和一组边构成&#xff0c;用于描述事物之间的复杂关联。 顶点&#xff1a;通常用 V (Vertex) 表示&#xff0c;代表事物或对象。边&#xf…

uniapp+renderJS+google map开发安卓版APP非小程序

背景需求 需要在uniapp中接入google地图,研究了一番,都没有找到合适的,现在说一下教程。 效果图 前期工作 这两点缺一不可,否则你啥也看不到。 1、电脑安装L-O-U梯 用于访问G-OO-G-LE的API或者创建google map key。 2、手机安装L-O-U梯 用于显示google地图。我就是手…

Linux中的进程入门

冯诺依曼体系结构 操作系统(Operator System) 进程控制块&#xff08;PCB&#xff09; struct task_struct{//该进程的所有属性//该进程对应的代码和属性地址struct task_struct* next; }; struct task_struct 内核结构体——>创建内核结构体对象(task_struct&#xff09;…

LinuxC高级作业2

1.整理思维导图 2.做一套笔试题 一&#xff1a; 1.cd .. mkdir dir1 cd dir1 touch file1 2.cp ~/mnt/dir1/ -r * ~/home/dir2/ 3.pwd 4.ls -l 5.ifconfig 6.top 10.find /usr -type f -name "*name*" 11.:wq 13.df -h 14.tar -xzvf tmp.tar.gz 15.sudo c…

登录校验(令牌,过滤器,拦截器使用详解)

文章目录 前言一、会话技术1. Cookie2. Session3. 令牌 二、JWT令牌1. 简介 二、过滤器Filter1. 简介2. 快速入门3. 执行流程4. 使用示例5. 为什么自定义的Filter类不需要使用Component 四、拦截器Interceptor1. 介绍2. 入门程序3. Interceptor详解 前言 该篇详细对SpringBoot…