哈希表技术.docx
《哈希表技术.docx》由会员分享，可在线阅读，更多相关《哈希表技术.docx（12页珍藏版）》请在冰点文库上搜索。
哈希表技术
实验报告
课程名称计算机软件基础
实验项目哈希表技术
实验仪器VS2005
系别光电信息与通信工程
专业电子信息工程
班级/学号
学生姓名____________
实验日期__2011-4-24________
成绩_______________________
指导教师_______________________
1、实验目的：
掌握HASH表的建立和查表技术。
2、实验内容：
1）编写函数实现线性探查HASH表的插入和查找算法；
2）编写主函数完成以下功能：
▪定义一个长度为128的HASH表；
▪随机产生120个0~255之间的不重复的伪随机整数，依次插入到HASH表中；HASH函数为H（k）=k*0.618mod127；
▪查找存在的和不存在的关键字；
选做内容：
选择实现以下功能：
3）编写函数，统计该HASH表的平均查找长度；
4）变换关键字个数，观察平均查找长度的变化；
5）变换HASH函数，观察平均查找长度的变化；
6）编写函数实现HASH表的删除算法。
3、实验步骤
（1）HASH表的插入和查找算法源代码已经给出；
（2）主函数功能源代码也已实现；
（3）HASH表的平均查找长度跟查找函数类似，其代码如下：
intasl（intkeys[],intn）
{
//计算平均查找长度ASL并返回结果。
参照find函数。
inti,h,ASL=0;
for（i=0;i{
n=1;
h=hash（keys[i]）;
while（（HashTable[h].key!
=-1）&&（HashTable[h].key!
=keys[i]））
{n++;h=（h+1）%M;}
ASL=ASL+n;
}
ASL=ASL/KeyNum;
returnASL;
}
运行结果如下：
（4）变换关键字个数后（HASH函数不变），运行结果如下:
Keynum=100
Keynum=80
Keynum=60
Keynum=40
通过比较可以发现，随着关键字个数keynum减小，平均查找长度ASL也越来越小，最小为1；
（5）变换HASH函数（关键字个数不变）后，运行结果如下：
HASH函数为（int）（k*0.618）%100
HASH函数为（int）（k*0.618）%50
HASH函数为（int）（k*0.618）%10
通过上面的运行结果可以发现，HASH函数值越大，得到的平均查找长度ASL越大；
（6）HASH表的删除
代码如下：
voiddel（intk）//HASH表的删除
{
inth;
h=hash（k）;
while（（HashTable[h].key!
=-1）&&（HashTable[h].key!
=k））h=（h+1）%M;
if（HashTable[h].key==-1）;
elseHashTable[h].key=999;
}
被删除的关键字用999来标记，最后运行结果如下图所示：
4、程序清单：
#include
#include
#include
#defineM128//Hash表长度
#defineKeyNum120//关键字个数
structelement{
intkey;
intotherterm;
};
typedefstructelementDATATYPE;
DATATYPEHashTable[M];
inthash（intk）//哈希函数，返回关键字的存储地址
{
return（（int）（k*0.618）%127）;
}
voidinsert（intk）//插入哈希关键字
{
inth;
h=hash（k）;
while（HashTable[h].key!
=-1）h=（h+1）%M;
HashTable[h].key=k;
}
intfind（intk）//查找哈希关键字
{
inth;
h=hash（k）;
while（（HashTable[h].key!
=-1）&&（HashTable[h].key!
=k））h=（h+1）%M;//进行查找
if（HashTable[h].key==-1）return-1;//没有找到
elsereturnh;//找到后返回存储地址
}
voidcreate_random（intran[],intN,intn）
{
//产生n个0~R-1范围的不重复随机整数，存入ran数组中
inti,j,r;
int*sz;
//初始化随机数种子
srand（（unsigned）time（NULL））;
//产生0~R-1范围的n个数，存入数组sz中
sz=（int*）malloc（N*sizeof（int））;
for（i=0;i//产生n个随机数
for（i=0;ir=rand（）%（N-i）;
ran[i]=sz[r];
for（j=r;j}
free（sz）;
}
voiddel（intk）//HASH表的删除
{
inth;
h=hash（k）;
while（（HashTable[h].key!
=-1）&&（HashTable[h].key!
=k））h=（h+1）%M;//查找关键字k
if（HashTable[h].key==-1）;//没有发现k，不进行操作
elseHashTable[h].key=999;//找到k后，用999标记
}
intasl（intkeys[],intn）
{
//计算平均查找长度ASL并返回结果。
参照find函数。
inti,h,ASL=0;
for（i=0;i{
n=1;//n用来记录查找长度
h=hash（keys[i]）;
while（（HashTable[h].key!
=-1）&&（HashTable[h].key!
=keys[i]））{n++;h=（h+1）%M;}
ASL=ASL+n;//把查找长度累加起来
}
ASL=ASL/KeyNum;//计算平均查找长度
returnASL;
}
voidmain（）
{
inti,h,key;
charch='y',ch_='y';//ch用来判断是否继续查找，ch_用来判断是否继续删除
intkeys[KeyNum];
for（i=0;iHashTable[i].key=-1;//初始化哈希表
create_random（keys,256,KeyNum）;//创建一组随机数
printf（"Keys:
\n"）;
for（i=0;iprintf（"%d",keys[i]）;//输出随机数
printf（"\nHashTable:
\n"）;
for（i=0;iinsert（keys[i]）;//插入哈希关键字
for（i=0;iprintf（"%d",HashTable[i]）;//输出哈希表
printf（"\n"）;
printf（"ASL=%d\n",asl（keys,KeyNum））;//输出平均查找长度
while（ch=='y'）{//查找关键字
printf（"Enterakey:
"）;
scanf（"%d",&key）;
h=find（key）;
if（h==-1）
printf（"Cannotfoundkey%d.\n",key）;//没有找到
elseprintf（"Key%disinlocation%d\n",key,h）;//输出关键字的存储地址
printf（"Continue?
[y/n]"）;
_flushall（）;
ch=getchar（）;
}
_flushall（）;
while（ch_=='y'）{//删除关键字
_flushall（）;
printf（"Enterthekeyyouwanttodelete:
"）;
scanf（"%d",&key）;//输入要删除的关键字
del（key）;
printf（"continuetodelete?
[y/n]"）;
_flushall（）;
ch_=getchar（）;
}
printf（"DeletedHashTable:
\n"）;//输出删除关键字后的哈希表
for（i=0;iprintf（"%d",HashTable[i]）;
printf（"\n"）;
}
5、总结
这次实验让我认识到一种新的查找方法——哈希查找，哈希查找不同于顺序、折半、分块查找，也不同于二叉树查找，哈希查找是利用关键字进行某种运算后直接确定元素的存储位置，这大大提高了查找速度和效率。
哈希表的建立比较简单，只要构造了一个合适的哈希函数，并能找到一个合适的解决冲突的方法就能水到渠成，哈希查找与建立的思路是一样的，所以学起来比较简单，实验过程中的问题也比较少，自己就能解决。
学会哈希查找法是我本次实验最大的收获。
升级会员 