数据结构与算法——第9章-查找表-哈希查找算法(9.13)

发表于 2023-05-28 分类于开发， N-数据与算法，数据结构与算法阅读时长 ≈ 2 分钟

一概述

1 2	1.实现思路分析 2.示例代码

二实现思路分析

上一节介绍了有关哈希表及其构造过程的相关知识，本节将介绍如何利用哈希表实现查找操作。

在哈希表中进行查找的操作同哈希表的构建过程类似，其具体实现思路为：
对于给定的关键字 K，将其带入哈希函数中，求得与该关键字对应的数据的哈希地址，
如果该地址中没有数据，则证明该查找表中没有存储该数据，查找失败：
如果哈希地址中有数据，就需要做进一步的证明（排除冲突的影响），找到该数据对应的关键字同 K 进行比对，
如果相等，则查找成功；反之，如果不相等，说明在构造哈希表时发生了冲突，
需要根据构造表时设定的处理冲突的方法找到下一个地址，同地址中的数据进行比对，
直至遇到地址中数据为 NULL（说明查找失败），或者比对成功。

回顾：哈希表在构造过程中，处理冲突的方法有：开放定址法、再哈希法、链地址法、建立公共溢出区法。

三示例代码

假设哈希表在构造过程采用的开放定址法处理的冲突，则哈希表的查找过程用代码实现为

#include "stdio.h"
#include "stdlib.h"
#define HASHSIZE 7 //定义散列表长为数组的长度
#define NULLKEY -1
typedef struct{
    int *elem;//数据元素存储地址，动态分配数组
    int count; //当前数据元素个数
}HashTable;
//对哈希表进行初始化
void Init(HashTable *hashTable){
    int i;
    hashTable->elem= (int *)malloc(HASHSIZE*sizeof(int));
    hashTable->count=HASHSIZE;
    for (i=0;i<HASHSIZE;i++){
        hashTable->elem[i]=NULLKEY;
    }
}
//哈希函数(除留余数法)
int Hash(int data){
    return data%HASHSIZE;
}
//哈希表的插入函数，可用于构造哈希表
void Insert(HashTable *hashTable,int data){
    int hashAddress=Hash(data); //求哈希地址
    //发生冲突
    while(hashTable->elem[hashAddress]!=NULLKEY){
        //利用开放定址法解决冲突
        hashAddress=(++hashAddress)%HASHSIZE;
    }
    hashTable->elem[hashAddress]=data;
}

//哈希表的查找算法
int Search(HashTable *hashTable,int data){
    int hashAddress=Hash(data); //求哈希地址
    while(hashTable->elem[hashAddress]!=data){//发生冲突
        //利用开放定址法解决冲突
        hashAddress=(++hashAddress)%HASHSIZE;
        //如果查找到的地址中数据为NULL，或者经过一圈的遍历回到原位置，则查找失败
        if (hashTable->elem[hashAddress]==NULLKEY||hashAddress==Hash(data)){
            return -1;
        }
    }
    return hashAddress;
}
int main(){
    int i,result;
    HashTable hashTable;
    int arr[HASHSIZE]={13,29,27,28,26,30,38};
    //初始化哈希表
    Init(&hashTable);
    //利用插入函数构造哈希表
    for (i=0;i<HASHSIZE;i++){
        Insert(&hashTable,arr[i]);
    }
    //调用查找算法
    result= Search(&hashTable,29);
    if (result==-1) printf("查找失败");
    else printf("29在哈希表中的位置是:%d",result+1);
    return  0;
}

运行结果为：

1	29 在哈希表中的位置是:2

四参考

C语言中文网—哈希查找算法

0%