当前位置：首页 > news >正文

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

news 来源：原创 2024/9/21 7:53:03

概述

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