Hash表的查找-C语言

文章目录

• • • 一、基本概念
    • • • 1.基本术语
    • 二、代码示例
    • 三、散列函数构造方法
    • • • 1.考虑因素
        • 2.两条原则
        • 3.构造方法
    • 四、处理冲突的方法
    • • • 1.开放地址法
        • 2.链地址法
    • 五、平均查找长度
    • • • 1.平均查找长度取决于：
        • 2.等概率下的平均查找长度

一、基本概念

基于线性表、树表结构的查找方法，都是以关键字的比较为基础的在查找过程中，只考虑各元素关键字之间的相对大小，记录在存储结构中的位置和其关键字无直接关系，其查找时间与表长度有关，特别是当结点个数很多时，查找需要大量与无关结点的关键字进行比较，导致查找速度很慢。

如果在存储位置与其关键字之间建立某种直接关系，则在进行查找时，就无需作比较或比较很少次，按照这种关系直接由关键字找到相应位置的记录。这就是Hash Search,即哈希查找，又称散列查找（杂凑法）。

1.基本术语

1. 散列函数和散列地址

p = H(key)
称对应关系 H为散列函数，p为散列地址

2. 散列表

通常指一个连续的地址空间，作一维数组，散列地址即数组下标。

3. 冲突和同义词

具有相同函数值的关键字对该散列函数称作同义词，出现同义词的现象称为冲突。

二、代码示例

//Authors:xioabei#include
#include#define m 5
#define NULLKEY 0//Hash表的定义
typedef int KeyType;
typedef char InfoType;
typedef struct Hash{KeyType key;InfoType otherinfo;
}HashTable[m];
//创建哈希表
int CreateHT(HashTable &HT){int i;for(i=0;i<m;i++){printf("\n请依次输入节点关键字项:\n>>>");scanf("%d",&HT[i].key);HT[i].otherinfo = NULL;}return 1;
}
//Hash函数(除留余数法)
int Hash(KeyType key){int p = m-2;return key%p;
}
//Hash表查找函数
int SearchHash(HashTable HT,KeyType key){
//在Hash表HT中查找关键字为key的元素，查找成功。返回Hash表的单元标号，否则返回-1int H0,Hi,i;H0 = Hash(key);if(HT[H0].key==NULLKEY)return -1;else if(HT[H0].key==key)return H0;else{for(i=1;i<m;++i){Hi = (H0+i)%m;if(HT[Hi].key==NULLKEY)return -1;else if(HT[Hi].key==key)return Hi;}return -1;}
}
//主函数
int main(){int key , loc;HashTable HT={NULL};if(CreateHT(HT))printf("\nHash表创建成功!\n………………\n");printf("\n请输入待查找关键字:\n>>>");scanf("%d",&key);loc = SearchHash(HT,key);if(loc==0 || loc!=-1)printf("\n查找成功!位置为%d\n",loc);elseprintf("\n查找失败!\n");getchar();scanf("%d",&key);return 0;
}

三、散列函数构造方法

1.考虑因素

1. 散列表长度
2. 关键字长度
3. 关键字分布情况
4. 计算散列函数所需时间
5. 记录的查找频率

2.两条原则

1. 函数计算要简单，每个关键字只能有一个散列地址与之对应。
2. 函数值域要在表长范围内，计算出散列地址的分布应该要均匀，尽可能减少冲突。

3.构造方法

构造方法有：数字分析法、直接定址法、平方取中法、折叠法、除留余数法。其中最常用的是除留余数法。

除留余数法：
设表长为m，选择不大于m的数p:H(key) = key%p

四、处理冲突的方法

1.开放地址法

1. 线性探测法
2. 二次探测法
3. 伪随机探测法

Hi=(H(key) + di) % m,i=1,2,…，k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法：
1)． di=1,2,3,…，m-1，称线性探测，会出现二次聚集现象
2)． di=1^2,-12,2^2,-22,3^2,…，±k2,(k<=m/2)称二次探测
3)． di=伪随机数序列，称伪随机探测

2.链地址法

链地址法又称拉链法。具体如下图，采用链式结构，建立一个公共溢出区。

五、平均查找长度

1.平均查找长度取决于：

1. 哈希函数
2. 处理冲突的方法
3. 哈希表的装填因子

装填因子r：
r = 表中填入的记录数/散列表长度；
r代表散列表的装满程度，r越小，发生冲突可能性越小；反之，r越大，再次填入数据时，发生冲突的可能性就越大。

2.等概率下的平均查找长度

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！