哈希表的設(shè)計與運用

目錄第1章需求分析……………………第2章概要設(shè)計……………………第3章詳細設(shè)計……………………第4章調(diào)試分析……..........................第5章核心源程序清單和執(zhí)行結(jié)果……………....第6章設(shè)計體會………….................第7章附錄…………………...........需求分析1.問題描述：針對某個集體〔比方你所在的班級〕中的人名設(shè)計一個哈希表，使得平均查找長度不超過R，完成相應(yīng)的建表和查表程序；2.人名為中國人姓名的漢語拼音，人名有30個，平均查找長度的上限為2；3.用偽隨機探測再散列法處理沖突；4.輸入為所要查詢的人姓名〔拼音〕；輸出為該關(guān)鍵字的查找信息；5.測試數(shù)據(jù)：輸入：lihaojie輸出：姓名：lihaojie關(guān)鍵字：837查找長度：1輸入：wangzhou輸出：姓名：wangzhou關(guān)鍵字：查找長度：3輸入：d輸出：顯示哈希表6.本程序用C++語言編寫，在vc++6.0環(huán)境下運行。概要設(shè)計2.1算法思想：1定義：哈希表是為了便于快速搜索而組織的鍵/值組合的集合。HashTable是一種數(shù)組，可以用任意簡單變量值來訪問其元素，這種數(shù)組叫哈希表。2優(yōu)點：哈希表最大的優(yōu)點就是把數(shù)據(jù)的存儲和查找消耗的時間大大降低，幾乎可以看成是常數(shù)時間；而代價僅僅是消耗比擬多的內(nèi)存。然而在當前可利用內(nèi)存越來越多的情況下，用空間換時間的做法是值得的。另外，編碼比擬容易也是它的特點之一。3根本原理：使用一個下標范圍比擬大的數(shù)組來存儲元素。可以設(shè)計一個函數(shù)〔哈希函數(shù)，也叫做散列函數(shù)〕，使得每個元素的關(guān)鍵字都與一個函數(shù)值〔即數(shù)組下標，hash值〕存在一一對應(yīng)的關(guān)系，于是用這個數(shù)組單元來存儲這個元素。也可以簡單的理解為，按照關(guān)鍵字為每一個元素“分類〞。4哈希表的不可防止沖突(collision)現(xiàn)象：對不同的關(guān)鍵字可能得到同一個哈希地址即key1≠key2，而f(key1)=f(key2)。因此，在建造哈希表時不僅要設(shè)定一個好的哈希函數(shù)，而且要設(shè)定一種處理沖突的方法。用偽隨機探測法。求下一個開放地址的公式為：Hi=(H(k)+di)MODm注意：Di=偽隨機數(shù)序列；2.2關(guān)于程序設(shè)計的根本操作：1.對哈希表的操作InitNameList()操作結(jié)果：姓名〔結(jié)構(gòu)體數(shù)組〕初始化CreateHashList()操作結(jié)果：建立哈希表FindList()操作結(jié)果：在哈希表中查找Display()操作結(jié)果：顯示哈希表2.主程序intmain(){初始化；InitNameList()；CreateHashList()；do{接受命令；處理命令；}while〔“命令〞=“退出〞〕；return0;}3.本程序包含的模塊}1〕初始化操作，結(jié)構(gòu)體定義；2〕姓名結(jié)構(gòu)體建立模塊；3〕建立哈希表模塊；4〕查找模塊；5〕顯示哈希表模塊；4〕主程序模塊4程序流程圖主程序主程序初始化姓名建立哈希表查找初始化姓名建立哈希表查找顯示哈希表表詳細設(shè)計主要功能模塊：模塊一：建立哈希表voidCreateHashList()//建立哈希表{ inti;for(i=0;i<HASH_LENGTH;i++) {HashList[i].py="";HashList[i].k=0;HashList[i].si=0; }for(i=0;i<HASH_LENGTH;i++) {intsum=0;intadr=(NameList[i].k)%M;//哈希函數(shù)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;//查找次數(shù)加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;r<20;r++)//求出姓名的拼音所對應(yīng)的整數(shù)(關(guān)鍵字)s0+=name[r];adr=s0%M;//使用哈希函數(shù)d=adr;if(HashList[adr].k==s0)//分3種情況進行判斷printf("\n姓名:%s關(guān)鍵字:%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關(guān)鍵字:%d查找長度為:%d",HashList[d].py,s0,sum);g=1; } }while(g==0); }}模塊三：顯示哈希表voidDisplay()//顯示哈希表{ inti;floataverage=0;printf("\n地址\t關(guān)鍵字\t\t搜索長度\tH(key)\t姓名\n");//顯示的格式for(i=0;i<50;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;i<HASH_LENGTH;i++)average+=HashList[i].si;average/=NAME_NO;printf("\n平均查找長度：ASL(%d)=%f\n",NAME_NO,average);}調(diào)試分析由于本程序的思路較簡單，主要是對哈希表的建立，查找和輸出，在寫程序時最重要的是正確書寫哈希函數(shù)和選擇適宜的處理沖突方法，可以有效減少查找長度，提高程序運行效率。下面本人就針對哈希函數(shù)的選擇以及沖突方法的選擇做一下簡單的論述：4.1哈希函數(shù)的選擇本人設(shè)計了如下幾種哈希函數(shù)：利用人名首字母的ASCII值-97作為該人名的關(guān)鍵字，而后后建立哈希函數(shù)hash(k)=k分析：利用此類哈希函數(shù)的優(yōu)點是比擬簡單，可行而且易于想到，但是其也有比擬明顯的缺點，就是產(chǎn)生沖突的幾率比擬的大，因為可能有很多人的人名的首字母是相同的，因此此種方法要求建立的hash沖突比擬完善實用。將人名所有的字母的ASCII碼值進行相加作為關(guān)鍵字，而后建立哈希函數(shù)hash(k)=k%m[m為其隨機數(shù)]分析：此類哈希函數(shù)的思想相對來說比擬的復(fù)雜，利用所有字母的ASCII碼值的相加作為其關(guān)鍵字，但是其有一個很好的優(yōu)點，就是產(chǎn)生沖突的幾率比擬的少，從而可以有效的減少信息的查找長度。去掉姓氏，利用人名的首字母的ASCII碼值-97作為關(guān)鍵字，而后建立哈希函數(shù)hash(k)=k分析：這種hash函數(shù)的建立是根據(jù)第一種函數(shù)改良而來的，它彌補了以前的缺乏：即產(chǎn)生沖突的幾率比擬的大，但同時它又極大的增加了此程序的復(fù)雜度。增加了程序運行的時間。去掉姓氏，將人名的所有字母的ASCII碼值進行相加作為關(guān)鍵字，而后建立哈希函數(shù)hash(k)=k%m[m為其隨機數(shù)]分析：此種哈希函數(shù)綜合了第二，第三種hash函數(shù)，它的思想比擬復(fù)雜不易想到，但是其可以將hash地址沖突率減少到一個很低的概率。極大的提高查找的效率，但是由于程序的復(fù)雜度較大，所以它所需要的運行時間也是很大的。4.2關(guān)于沖突處理的選擇本人設(shè)計了如下幾種沖突方法：針對于第一，第三種hash函數(shù)，本人認為可以利用雙hash函數(shù)探測法來處理沖突：即是略去第一個字母從下一個字母開始尋找關(guān)鍵字，建立hash函數(shù)，來處理沖突。分析：此種沖突處理方法比擬簡單，而且確實可行性比擬的高，但是由于hash函數(shù)的關(guān)系，此種沖突處理方法并不怎么使用。針對于第二，第四種hash函數(shù)，本人認為可以利用偽隨機數(shù)線性探測法來處理沖突：即是利用公式(k%m+1)%m來處理沖突。分析：此種沖突處理方法操作起來相對的比擬麻煩，而且還需要一個隨機數(shù)，但是其有一個比擬好的優(yōu)點，它的處理后的沖突率幾乎為零，同時能有效的減少哈希表設(shè)計的長度。核心源程序清單和執(zhí)行結(jié)果1.源程序代碼：#include<iostream>#include<string>usingnamespacestd;#defineHASH_LENGTH50//哈希表的長度#defineM47//取余隨機數(shù)#defineNAME_NO30//人名的個數(shù)typedefstruct{char*py;//名字的拼音intk;//名字所對應(yīng)的關(guān)鍵字}NAME;NAMENameList[HASH_LENGTH];//全局變量NAMEtypedefstruct//哈希表{char*py;//名字的拼音intk;//拼音所對應(yīng)的整數(shù)intsi;//查找長度}HASH;HASHHashList[HASH_LENGTH];//全局變量HASH/*姓名〔結(jié)構(gòu)體數(shù)組〕初始化*/voidInitNameList(){char*f;intr,s0,i;for(i=0;i<HASH_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(NameList[25].py,"wangqinde");strcpy(NameList[26].py,"wangzejun");strcpy(NameList[27].py,"wangkeke");strcpy(NameList[28].py,"weixing");strcpy(NameList[29].py,"wurenke");for(i=0;i<NAME_NO;i++){s0=0;f=NameList[i].py;for(r=0;*(f+r)!='\0';r++)/*方法：將字符串的各個字符所對應(yīng)的ASCII碼相加，所得的整數(shù)做為哈希表的關(guān)鍵字*/s0=*(f+r)+s0;NameList[i].k=s0;}}/*建立哈希表*/voidCreateHashList(){inti;for(i=0;i<HASH_LENGTH;i++){HashList[i].py=newchar[64];HashList[i].py[0]=0;HashList[i].k=0;HashList[i].si=0;}for(i=0;i<HASH_LENGTH;i++){intsum=0;intadr=(NameList[i].k)%M;//哈希函數(shù)intd=adr;if(HashList[adr].si==0)//如果不沖突{HashList[adr].k=NameList[i].k;HashList[adr].py=NameList[i].py;HashList[adr].si=1;}else//沖突{while(HashList[d].k!=0){d=(d+NameList[i].k%10+1)%M;//處理沖突sum=sum+1;//查找次數(shù)加1};HashList[d].k=NameList[i].k;HashList[d].py=NameList[i].py;HashList[d].si=sum+1;}}}/*查找模塊*/voidFindList(){stringname;ints0=0,r,sum=1,adr,d;cout<<"請輸入姓名的拼音:"<<endl;cin>>name;for(r=0;r<20;r++)//求出姓名的拼音所對應(yīng)的整數(shù)(關(guān)鍵字)s0+=name[r];adr=s0%M;//使用哈希函數(shù)d=adr;if(HashList[adr].k==s0)//分3種情況進行判斷cout<<"姓名:"<<HashList[d].py<<""<<"關(guān)鍵字:"<<s0<<""<<"查找長度為:1"<<endl;elseif(HashList[adr].k==0)cout<<"無此記錄!"<<endl;else{intg=0;while(g==0){d=(d+s0%10+1)%M;//處理沖突sum=sum+1;if(HashList[d].k==0){cout<<"無此記錄!"<<endl;g=1;}if(HashList[d].k==s0){cout<<"姓名:"<<HashList[d].py<<""<<"關(guān)鍵字:"<<s0<<""<<"查找長度為:"<<sum<<endl;g=1;}};}}/*顯示哈希表*/voidDisplay(){inti;floataverage=0;cout<<"\n地址\t關(guān)鍵字\t\t搜索長度\tH(key)\t姓名\n";//顯示的格式for(i=0;i<50;i++){cout<<i<<"";cout<<"\t"<<HashList[i].k<<"";cout<<"\t\t"<<HashList[i].si<<"";cout<<"\t\t"<<(HashList[i].k%M)<<"";cout<<"\t"<<HashList[i].py<<"";cout<<"\n";}for(i=0;i<HASH_LENGTH;i++)average+=HashList[i].si;average/=NAME_NO;cout<<"平均查找長度：ASL("<<NAME_NO<<")="<<average<<endl;}/*主函數(shù)，調(diào)用其他功能函數(shù)*/intmain(){charx;InitNameList();CreateHashList();cout<<"d.顯示哈希表f.查找任意鍵退出請選擇："<<endl;while(cin>>x){if(x=='d'){Display();cout<<endl;}elseif(x=='f'){FindList();cout<<endl;}elsebreak;}for(inti=0;i<HASH_LENGTH;i++){free(NameList[i].py);free(HashList[i].py);}return0;}