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

server/2024/9/21 11:55:27/

概述

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

相关文章

【JVM】判断对象能否回收的两种方法:引用计数算法,可达性分析算法

1、引用计数算法&#xff1a; 给对象添加一个引用计数器&#xff0c;当该对象被其它对象引用时计数加一&#xff0c;引用失效时计数减一&#xff0c;计数为0时&#xff0c;可以回收。 特点&#xff1a;占用了一些额外的内存空间来进行计数&#xff0c;原理简单&#xff0c;判…

系统架构设计师 需求分析篇一

&#x1f4d8; 结构化分析SA 思想 自顶向下&#xff1a;像剥洋葱一样&#xff0c;层层深入&#xff0c;大问题拆成小问题&#xff0c;再拆成更小的问题。 核心模型 数据字典 &#x1f4d4;&#xff1a;记录数据元素的点点滴滴&#xff0c;从属性到使用方式&#xff0c;无所…

科研绘图系列:R语言散点图和小提琴图(scatter plot violin plot)

文章目录 介绍加载R包导入数据数据预处理函数画图系统信息介绍 提取模型的结果并对模型的结果进行可视化。 加载R包 library(ggplot2) library(ggridges) library(patchwork) library(party) library(caret) library(dplyr

SpringDataJpa自关联映射时出现StackOverflowError

使用Jpa自关联时&#xff0c;存在子数据的记录会报内存溢出问题StackOverflowError 原因&#xff1a; 使用了 lombok 插件中的Data注解来标注类&#xff0c;生成 gettet/setter 以及 toString lombok 在生成时会出现循环比较两类中的 hashcode&#xff0c;导致内存溢出。 解决…

一条sql是如何执行的详解

一条sql是如何执行的详解 1. SQL 解析&#xff08;Parsing&#xff09; 2. 查询重写&#xff08;Query Rewrite&#xff09; 3. 查询规划&#xff08;Query Planning&#xff09; 4. 查询执行&#xff08;Query Execution&#xff09; 5. 结果返回 示例&#xff1a;查询执…

vue2中使用vue-office库预览pdf /docx/excel文件

vue2中使用vue-office库预览pdf /docx/excel文件 - 简书 vue引用vue-office实现docx、excel、pdf等文件预览_vue-office-excel-CSDN博客

linux-软件包管理-软件源配置

Linux 软件包管理&#xff1a;软件源配置 1. 软件包管理概述 在 Linux 系统中&#xff0c;软件包管理器&#xff08;Package Manager&#xff09;是用户安装、更新、删除软件的重要工具。不同的 Linux 发行版通常使用不同的包管理系统&#xff0c;如 Debian 系列使用 dpkg 及…

【java】常见限流算法原理及应用

目录 前言 限流的作用 4种常见限流算法 固定窗口限流 基本原理 简单实现 优点和缺点 滑动窗口限流 基本原理 简单实现 优点和缺点 漏桶限流 基本原理 简单实现 优点和缺点 令牌桶限流 基本原理 简单实现 优点和缺点 算法比较与选择 前言 在现代分布式系统…