哈希表的设计与运用

目录第1章需求分析……………………………………………………第2章概要设计……………………………………………………第3章详细设计……………………………………………………第4章调试分析……………………………………..........................第5章核心源程序清单和执行结果……………………………....第6章设计体会………………………………………….................第7章附录…………………………………………………...........第一章需求分析1.问题描述：针对某个集体（比如你所在的班级）中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序；2.人名为中国人姓名的汉语拼音，人名有30个，平均查找长度的上限为2；3.用伪随机探测再散列法处理冲突；4.输入为所要查询的人姓名（拼音）；输出为该关键字的查找信息；5.测试数据：输入：lihaojie输出：姓名：lihaojie关键字：837查找长度：1输入：wangzhou输出：姓名：wangzhou关键字：查找长度：3输入：d输出：显示哈希表6.本程序用C++语言编写，在vc++6.0环境下运行。第二章概要设计2.1算法思想：1定义：哈希表是为了便于快速搜索而组织的键/值组合的集合。HashTable是一种数组，可以用任意简单变量值来访问其元素，这种数组叫哈希表。2优点：哈希表最大的优点就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。3基本原理：使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标，hash值）存在一一对应的关系，于是用这个数组单元来存储这个元素。也可以简单的理解为，按照关键字为每一个元素“分类”。4哈希表的不可避免冲突(collision)现象：对不同的关键字可能得到同一个哈希地址即key1≠key2，而f(key1)=f(key2)。因此，在建造哈希表时不仅要设定一个好的哈希函数，而且要设定一种处理冲突的方法。用伪随机探测法。求下一个开放地址的公式为：Hi=(H(k)+di)MODm注意：Di=伪随机数序列；2.2关于程序设计的基本操作：1.对哈希表的操作InitNameList()操作结果：姓名（结构体数组）初始化CreateHashList()操作结果：建立哈希表FindList()操作结果：在哈希表中查找Display()操作结果：显示哈希表2.主程序intmain(){初始化；InitNameList()；CreateHashList()；do{接受命令；处理命令；}while（“命令”=“退出”）；return0;}3.本程序包含的模块}1）初始化操作，结构体定义；2）姓名结构体建立模块；3）建立哈希表模块；4）查找模块；5）显示哈希表模块；4）主程序模块4程序流程图建立哈希表初始化姓名显示哈希表表查找主程序第三章详细设计主要功能模块：模块一：建立哈希表voidCreateHashList()//建立哈希表{inti;for(i=0;iHASH_LENGTH;i++){HashList[i].py=;HashList[i].k=0;HashList[i].si=0;}for(i=0;iHASH_LENGTH;i++){intsum=0;intadr=(NameList[i].k)%M;//哈希函数intd=adr;if(HashList[adr].si==0)//如果不冲突{HashList[adr].k=NameList[i].k;HashList[adr].py=NameList[i].py;HashList[adr].si=1;}else//冲突{do{d=(d+NameList[i].k%10+1)%M;//伪随机探测再散列法处理冲突sum=sum+1;//查找次数加1}while(HashList[d].k!=0);HashList[d].k=NameList[i].k;HashList[d].py=NameList[i].py;HashList[d].si=sum+1;}}}模块二：查找voidFindList()//查找{charname[20]={0};ints0=0,r,sum=1,adr,d;printf(请输入姓名的拼音:);scanf(%s,name);for(r=0;r20;r++)//求出姓名的拼音所对应的整数(关键字)s0+=name[r];adr=s0%M;//使用哈希函数d=adr;if(HashList[adr].k==s0)//分3种情况进行判断printf(\n姓名:%s关键字:%d查找长度为:1,HashList[d].py,s0);elseif(HashList[adr].k==0)printf(无此记录!);else{intg=0;do{d=(d+s0%10+1)%M;//伪随机探测再散列法处理冲突sum=sum+1;if(HashList[d].k==0){printf(无此记录!);g=1;}if(HashList[d].k==s0){printf(\n姓名:%s关键字:%d查找长度为:%d,HashList[d].py,s0,sum);g=1;}}while(g==0);}}模块三：显示哈希表voidDisplay()//显示哈希表{inti;floataverage=0;printf(\n地址\t关键字\t\t搜索长度\tH(key)\t姓名\n);//显示的格式for(i=0;i50;i++){printf(%d,i);printf(\t%d,HashList[i].k);printf(\t\t%d,HashList[i].si);printf(\t\t%d,HashList[i].k%M);printf(\t%s,HashList[i].py);printf(\n);}for(i=0;iHASH_LENGTH;i++)average+=HashList[i].si;average/=NAME_NO;printf(\n平均查找长度：ASL(%d)=%f\n,NAME_NO,average);}第四章调试分析由于本程序的思路较简单，主要是对哈希表的建立，查找和输出，在写程序时最重要的是正确书写哈希函数和选择合适的处理冲突方法，可以有效减少查找长度，提高程序运行效率。下面本人就针对哈希函数的选择以及冲突方法的选择做一下简单的论述：4.1哈希函数的选择本人设计了如下几种哈希函数：1.利用人名首字母的ASCII值-97作为该人名的关键字，而后后建立哈希函数hash(k)=k分析：利用此类哈希函数的优点是比较简单，可行而且易于想到，但是其也有比较明显的缺点，就是产生冲突的几率比较的大，因为可能有很多人的人名的首字母是相同的，因此此种方法要求建立的hash冲突比较完善实用。2.将人名所有的字母的ASCII码值进行相加作为关键字，而后建立哈希函数hash(k)=k%m[m为其随机数]分析：此类哈希函数的思想相对来说比较的复杂，利用所有字母的ASCII码值的相加作为其关键字，但是其有一个很好的优点，就是产生冲突的几率比较的少，从而可以有效的减少信息的查找长度。3.去掉姓氏，利用人名的首字母的ASCII码值-97作为关键字，而后建立哈希函数hash(k)=k分析：这种hash函数的建立是根据第一种函数改进而来的，它弥补了以前的不足：即产生冲突的几率比较的大，但同时它又极大的增加了此程序的复杂度。增加了程序运行的时间。4.去掉姓氏，将人名的所有字母的ASCII码值进行相加作为关键字，而后建立哈希函数hash(k)=k%m[m为其随机数]分析：此种哈希函数综合了第二，第三种hash函数，它的思想比较复杂不易想到，但是其可以将hash地址冲突率减少到一个很低的概率。极大的提高查找的效率，但是由于程序的复杂度较大，所以它所需要的运行时间也是很大的。4.2关于冲突处理的选择本人设计了如下几种冲突方法：1.针对于第一，第三种hash函数，本人认为可以利用双hash函数探测法来处理冲突：即是略去第一个字母从下一个字母开始寻找关键字，建立hash函数，来处理冲突。分析：此种冲突处理方法比较简单，而且的确可行性比较的高，但是由于hash函数的关系，此种冲突处理方法并不怎么使用。2.针对于第二，第四种hash函数，本人认为可以利用伪随机数线性探测法来处理冲突：即是利用公式(k%m+1)%m来处理冲突。分析：此种冲突处理方法操作起来相对的比较麻烦，而且还需要一个随机数，但是其有一个比较好的优点，它的处理后的冲突率几乎为零，同时能有效的减少哈希表设计的长度。第五章核心源程序清单和执行结果1.源程序代码：#includeiostream#includestringusingnamespacestd;#defineHASH_LENGTH50//哈希表的长度#defineM47//取余随机数#defineNAME_NO30//人名的个数typedefstruct{char*py;//名字的拼音intk;//名字所对应的关键字}NAME;NAMENameList[HASH_LENGTH];//全局变量NAMEtypedefstruct//哈希表{char*py;//名字的拼音intk;//拼音所对应的整数intsi;//查找长度}HASH;HASHHashList[HASH_LENGTH];//全局变量HASH/*姓名（结构体数组）初始化*/voidInitNameList(){char*f;intr,s0,i;for(i=0;iHASH_LENGTH;i++){NameList[i].py=newchar[64];NameList[i].py[0]=0;}strcpy(NameList[0].py,lihaojie);strcpy(NameList[1].py,zhaona);strcpy(NameList[2].py,shangqingfu);strcpy(NameList[3].py,changqiongfang);strcpy(NameList[4].py,liaobangyu);strcpy(NameList[5].py,fenghao);strcpy(NameList[6].py,huangtianyuan);strcpy(NameList[7].py,luxiwu);strcpy(NameList[8].py,huangxinglong);strcpy(NameList[9].py,jiangxiaojia);strcpy(NameList[10].py,guojie);strcpy(NameList[11].py,liyexiao);strcpy(NameList[12].py,lidaohui);strcpy(NameList[13].py,lijue);strcpy(NameList[14].py,lizhuoqun);strcpy(NameList[15].py,linfujun);strcpy(NameList[16].py,luobingbiao);strcpy(NameList[17].py,luokeqing);strcpy(NameList[18].py,nichao);strcpy(NameList[19].py,panhuafeng);strcpy(NameList[20].py,lixiaolong);strcpy(NameList[21].py,songzhanhui);strcpy(NameList[22].py,lichao);strcpy(NameList[23].py,wanghaofeng);strcpy(NameList[24].py,wangzhou);strcpy(Name