哈希查找 _生活百科

哈希查找【哈希查找】哈希查找是通过计算数据元素的存储地址进行查找的一种方法。
基本介绍中文名：哈希查找
解释：计算数据元素的存储地址进行查找
操作步骤个数：3步
解决冲突方法：开放地址法、链地址法
定义哈希查找的操作步骤：⑴用给定的哈希函式构造哈希表；⑵根据选择的冲突处理方法解决地址冲突；⑶在哈希表的基础上执行哈希查找。操作步骤step1 取数据元素的关键字key，计算其哈希函式值。若该地址对应的存储空间还没有被占用，则将该元素存入；否则执行step2解决冲突。step2 根据选择的冲突处理方法，计算关键字key的下一个存储地址。若下一个存储地址仍被占用，则继续执行step2，直到找到能用的存储地址为止。哈希查找步骤为：设哈希表为HST[0~M-1]，哈希函式取H（key），解决冲突的方法为R（x）；Step1 对给定k值，计算哈希地址 Di=H（k）；若HST为空，则查找失败；若HST=k，则查找成功；否则，执行step2（处理冲突）。Step2 重複计算处理冲突的下一个存储地址 Dk=R（Dk-1），直到HST[Dk]为空，或HST[Dk]=k为止。若HST[Dk]=K，则查找成功，否则查找失败。哈希查找的本质是先将数据映射成它的哈希值。哈希查找的核心是构造一个哈希函式，它将原来直观、整洁的数据映射为看上去似乎是随机的一些整数。哈希查找的产生有这样一种背景——有些数据本身是无法排序的(如图像)，有些数据是很难比较的(如图像) 。如果数据本身是无法排序的，就不能对它们进行比较查找。如果数据是很难比较的，即使採用折半查找，要比较的次数也是非常多的。因此，哈希查找并不查找数据本身，而是先将数据映射为一个整数(它的哈希值)，并将哈希值相同的数据存放在同一个位置一即以哈希值为索引构造一个数组。在哈希查找的过程中，只需先将要查找的数据映射为它的哈希值，然后查找具有这个哈希值的数据，这就大大减少了查找次数。如果构造哈希函式的参数经过精心设计，记忆体空间也足以存放哈希表，查找一个数据元素所需的比较次数基本上就接近于一次。解决冲突影响哈希查找效率的一个重要因素是哈希函式本身。当两个不同的数据元素的哈希值相同时，就会发生冲突。为减少发生冲突的可能性，哈希函式应该将数据儘可能分散地映射到哈希表的每一个表项中。解决冲突的方法有以下两种：(1) 开放地址法如果两个数据元素的哈希值相同，则在哈希表中为后插入的数据元素另外选择一个表项。当程式查找哈希表时，如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素，程式就会继续往后查找，直到找到一个符合查找要求的数据元素，或者遇到一个空的表项。(2) 链地址法将哈希值相同的数据元素存放在一个鍊表中，在查找哈希表的过程中，当查找到这个鍊表时，必须採用线性查找方法。例3. 6是一个简单的哈希查找算法程式，你可以将它和本章结尾的有关代码一起编译连线成一个可执行程式。例3．6一个简单的哈希查找算法程式1: #include<stdlib.h>2: #include<string.h>3: #include "list.h"4: #include "hash.h"5:6: #define HASH_SIZE 10247:8: static listnode_t *hashTable[HASH_SIZE];9:10: void insert(const char * s)11: {12: listnode_t *ele = newNode((void * ) s)13: unsigned int h = hash(s) % HASH_SIZE;14:15: ele->next = hashTable[h]16: hashTable[h] = ele;17: }18:19: void print (void)20: {21: int h;22:23: for (h = 0; h < HASH_SIZE; h++)24: {25: listnode_t * lp = hashTalbe[h];26:27: if(lp == NULL)28:continue;29: printf("[%d]" , h);30: while (lp)31: {32:printf("\t'%s'" , lp->u.str)33:lp = ip->next;34: }35: putchar ('\n');36: }37: }38:39: const char *search(const char *s)40: {39: unsigned int h = hash(s) % HASH_SIZE;42: listnode_t * lp = hashTable[h];43:44: while (lp)45: {46: if (! strcmp (s, lp->u.str))47:return lp->u.str;48: lp = lp->next; 49: }50: return NULL;51: }请参见：3. 4 哪一种查找方法最方便?3．5 哪一种查找方法最快?3．8 怎样查找鍊表中的数据?_____________________________________________以下是一个简单示例：#include<iostream>#include<string>using namespace std;#define m 5 //人数#define n 10 //哈希表长度#define q 7 //随机数struct name{char *py;int k;};name namelist[n];struct hash{char *py;int k;int s;};hash hashlist[n];void listname(){char *f;int s0,r,i;namelist[0].py="as";namelist[1].py="sa";namelist[2].py="d";namelist[3].py="f";namelist[4].py="g";for(i=0;i<m;i++){s0=0;f=namelist[i].py;for(r=0;*(f+r)!='\0';r++)s0+=*(f+r);namelist[i].k=s0;}}void creathash(){int i;for(i=0;i<n;i++){hashlist[i].py="";hashlist[i].k=0;hashlist[i].s=0;}for(i=0;i<m;i++){int sum=0;int adr=(namelist[i].k)%q;int d=adr;if(hashlist[adr].s==0){hashlist[adr].py=namelist[i].py; hashlist[adr].k=namelist[i].k;hashlist[adr].s=1;}else{while(hashlist[d].k!=0){d=(d+namelist[i].k%5+1)%q;sum+=1;}hashlist[d].py=namelist[i].py;hashlist[d].k=namelist[i].k;hashlist[d].s=sum+1;}}}void find(){string nam;int s0=0,r,sum=1,adr,d;cout<<"请输入姓名的拼音："<<endl;cin>>nam;;for(r=0;r<20;r++)s0+=nam[r];adr=s0%q;d=adr;if(hashlist[adr].k==s0)cout<<"姓名:"<<hashlist[d].py<<" "<<"关键字:"<<s0<<" "<<"查找长度为: 1"<<endl;else if(hashlist[adr].k==0)cout<<"无此记录！"<<endl;else{int g=0;while(g==0){d=(d+s0%5+1)%q;sum+=1;if(hashlist[d].k==0){cout<<"无此记录！"<<endl;g=1;}if(hashlist[d].k==s0){cout<<"姓名:"<<hashlist[d].py<<" "<<"关键字:"<<s0<<" "<<"查找长度为: 1"<<endl; g=1;}}}}void display(){int i;float av=0;for(i=0;i<n;i++){cout<<"姓名:"<<hashlist[i].py<<" "<<"关键字:"<<hashlist[i].k<<"搜寻长度："<<hashlist[i].s<<endl;}for(i=0;i<7;i++){av+=hashlist[i].s;}av/=m;cout<<"平均查找长度：="<<av<<endl;}int main(){char x;listname();creathash();cout<<"d. 显示哈希表 f. 查找任意键退出请选择："<<endl;while(cin>>x){if(x=='d'){display(); cout<<endl;}else if(x=='f'){find();cout<<endl;}else break;}return 0;}