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

news/2024/9/29 1:26:29/

概述

哈希表的查询是通过计算的方式获取数据的地址,而不是依次比较。在哈希表中,有一个键值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.ppmy.cn/news/1531241.html

相关文章

重建大师区块划分的原则是什么?

根据计算机内存来进行划分&#xff0c;一般预估内存不超过计算机内存的2/3。 重建大师&#xff0c;这是一款专为超大规模实景三维数据生产设计的集群并行处理软件&#xff0c;支持卫星影像、航空影像、倾斜影像和激光点云多源数据输入建模&#xff0c;可完成超大规模数据的空三…

Ubuntu 安装配置nginx

参考文章&#xff1a; Ubuntu20.04安装配置Nginx_ubuntu20.04安装nginx-CSDN博客

【操作系统强化】王道强化一轮笔记

第一章 计算机系统概述 考点1 操作系统的概念、特征和功能 1. 2. 考点2 内核态与用户态 1. 2.用户态和内核态之间的切换本质上就是应用程序和操作系统对CPU控制器的切换 考点3 中断和异常 1. 2. 考点4 系统调用 1. 2. 3.C 考点5 操作系统引导 1. 2. ①磁盘的物理格式化&…

小说阅读器小程序+ssm论文源码调试讲解

2 系统开发环境 为了能够使本系统较好、较为完善的被设计实现出来&#xff0c;在功能上&#xff0c;我对新系统进行了细致的分析。通过详细的分析&#xff0c;我选择了SSM框架来进行开发设计&#xff0c;在数据存储上&#xff0c;采用 Mysql数据库来进行设计。本系统选择的开发…

OpenCV视频I/O(5)视频采集类VideoCapture之从视频流中获取下一帧的函数grab()的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 从视频文件或捕获设备中抓取下一帧。 grab() 函数是 OpenCV 中 VideoCapture 类的一个成员函数&#xff0c;用于从视频流中获取下一帧而不立即检…

DoppelGanger++:面向数据库重放的快速依赖关系图生成

doi&#xff1a;DoppelGanger: Towards Fast Dependency Graph Generation for Database Replay&#xff0c;点击前往 文章目录 1 简介2 架构概述3 依赖关系图3.1 符号和问题定义3.2 无 IT(k) 图3.3 无 OT 图表3.4 无 OTIT 图表3.5 无 IT[OT] 图表3.6 输出确定性保证 4 重复向后…

深度学习500问——Chapter15:异构计算,GPU和框架选型(1)

文章目录 异构计算&#xff0c;GPU和框架选型指南 15.1 什么是异构计算 15.2 什么是GPU 15.3 GPU架构简介 15.3.1 如何通俗理解GPU的架构 15.3.2 CUDA的核心是什么 15.3.3 为什么要使用GPU 异构计算&#xff0c;GPU和框架选型指南 深度学习训练和推理的过程中&#xff0c;会涉…

使用Python实现图形学光照和着色的光线追踪算法

目录 使用Python实现图形学光照和着色的光线追踪算法引言1. 光线追踪算法概述2. Python实现光线追踪算法2.1 向量类2.2 光源类2.3 材质类2.4 物体类2.5 光线追踪器类2.6 使用示例 3. 实例分析4. 光线追踪算法的优缺点4.1 优点4.2 缺点 5. 改进方向6. 应用场景结论 使用Python实…