哈希查找是通过计算数据元素的存储地址进行查找的一种方 法。

哈希查找的操作步骤：

⑴用给定的哈希函数构造哈希表；

⑵根据选择的冲突处理方法解决地址冲突；

⑶在哈希表的基础上执行哈希查找。

建立哈希表操作步骤：

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 1024

7:

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 ('\');

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;

}