數(shù)據(jù)結(jié)構(gòu)課程設計---哈希表的設計與實現(xiàn)

1、<p>　　課程名稱：數(shù)據(jù)結(jié)構(gòu) </p><p><b>　　XXXXXXXX</b></p><p>　　本科學生課程設計（論文）</p><p>　　題 目 哈希表的設計與實現(xiàn) </p><p>　　姓 名 XXX </p

2、><p>　　學 號 XXXXXXXXXXXX </p><p>　　學 部 計算機科學與技術 </p><p>　　專業(yè)、年級 計算機科學與技術 大二 </p><p>　　指 導 教 師 XX </p>

3、;<p>　　2010 年 11月 28日</p><p><b>　　摘 要</b></p><p>　　隨著信息技術的發(fā)展，關于各種程序中的數(shù)據(jù)結(jié)構(gòu)也是層出不窮，對于項目某一方面的計算或者是某一方面的研究，出現(xiàn)了專門的數(shù)據(jù)結(jié)構(gòu)，哈希表就是其中之一，哈希表作為另類的一種數(shù)據(jù)結(jié)構(gòu)，其作用也是區(qū)別于其它同類的數(shù)據(jù)結(jié)構(gòu)的，它是由兩部分組成的：鍵(key)和

4、值，通過鍵可以迅速的查找到你需要的值。常見的構(gòu)造哈希函數(shù)的方法有直接定址法 除留余數(shù)法 平方取中法 數(shù)字分析法等。一般創(chuàng)建哈希表時可能會出現(xiàn)很多的沖突，常用的處理沖突的方法為開放定址法 再哈希法 鏈地址法 建立一個公共溢出區(qū)。</p><p>　　關鍵詞: 數(shù)據(jù)結(jié)構(gòu)；哈希表；鍵(key)；</p><p><b>　　目 錄</b></p><p&

5、gt;　　第1章前言與系統(tǒng)實現(xiàn)2</p><p><b>　　1.1前言2</b></p><p><b>　　1.2系統(tǒng)實現(xiàn)3</b></p><p>　　1.2.1 開發(fā)環(huán)境3</p><p>　　1.2.2 Visual C++環(huán)境的安裝3</p><p&g

6、t;　　第2章 系統(tǒng)功能分析4</p><p>　　2.1 系統(tǒng)功能需求分析4</p><p>　　2.2 任務定義4</p><p>　　第3章 總體設計5</p><p>　　3.1系統(tǒng)數(shù)據(jù)結(jié)構(gòu)5</p><p>　　3.2主要算法流程圖6</p><p>　　3.2.1

7、 以姓名為關鍵字的CreateHashList()函數(shù)流程圖6</p><p>　　3.2.2 哈希表查找算法流程圖7</p><p>　　3.2.3主程序流程圖8</p><p>　　第4章 詳細設計和編碼9</p><p>　　4.1節(jié)點的建立9</p><p>　　4.2 對哈希函數(shù)的定義9<

8、;/p><p>　　4.3 創(chuàng)建哈希表算法、代碼如下所示:10</p><p>　　4.3.1 算法10</p><p>　　4.3.2代碼10</p><p>　　4.4哈希查找11</p><p>　　4.5顯示哈希表14</p><p>　　4.6主菜單設計16</p>

9、<p>　　4.7 主函數(shù)設計16</p><p>　　第5章 程序運行測試19</p><p>　　5.1程序主界面19</p><p>　　5.2哈希表初始化19</p><p>　　5.3按姓名查找記錄21</p><p>　　5.4顯示哈希表全部記錄22</p><

10、p><b>　　總結(jié)23</b></p><p><b>　　參考文獻24</b></p><p><b>　　前言與系統(tǒng)實現(xiàn)</b></p><p><b>　　1.1前言</b></p><p>　　在信息化時代的今天，計算機技術已經(jīng)是發(fā)展到

11、一個很可觀的地步了，特別是面向窗口的操作系統(tǒng)的出現(xiàn)，使得程序設計更加的容易了。在過去計算機內(nèi)存容量小，CPU計算速度慢，關于程序設計中的數(shù)據(jù)結(jié)構(gòu)也因此提出來很多的關于解決這方面的問題。哈希表就是其中之一，哈希表是一個由關鍵字與值組成的特殊的一種數(shù)據(jù)結(jié)構(gòu)。它的出現(xiàn)主要是為了解決在結(jié)構(gòu)中查找記錄時需要進行一系列和關鍵字的比較,這一類查找方法是建立在“比較”的基礎上的，在順序等的查找中，查找的效率是依賴于查找過程中所比較的次數(shù)。</p&

12、gt;<p>　　理想的情況是希望不經(jīng)過任何的比較一次存取便能得到所查記錄，那就必須在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系，使得每個關鍵字和結(jié)構(gòu)中一個唯一的存儲位置相對應。因而在查找時只要根據(jù)這個對應關系找到給定的值的像。若結(jié)構(gòu)中存在關鍵字和該值相等的記錄，則所要查找的數(shù)就必定就是這個所查找到的記錄。</p><p>　　哈希函數(shù)是建立哈希表的一個重要的成員，它的構(gòu)造方法分為以下幾種

13、：</p><p>　　直接定址法、數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法、隨機數(shù)法。</p><p>　　本程序中主要用的是除余取留法,除留取余法主要是取關鍵字被某個不大于哈希表表長m的數(shù)p出后所得余數(shù)為哈希地址即:H(key)=key MOD p, p<=m，這是一種最簡單，也是一種最常用的構(gòu)造函數(shù)的方法，它不僅可以對關鍵字直接取模，也可在折疊、平方中等運算之后取模。<

14、/p><p>　　在哈希表的建立中，很容易出現(xiàn)同義詞，這些同義詞的出現(xiàn)也導致了建立哈希表時沖突的出現(xiàn)，如果不解決這些沖突那么建立好的哈希表與預料的哈希表不同。關于處理沖突的方法主要有：開放定址法、再哈希法、鏈地址法。本程序中主要用的就是鏈地址法萊解決沖突的。</p><p><b>　　1.2系統(tǒng)實現(xiàn)</b></p><p>　　本程序是在Vc++

15、6.0環(huán)境下編寫 測試運行的。</p><p>　　1.2.1 開發(fā)環(huán)境</p><p>　　表1-1列出了系統(tǒng)硬件配置，表6-2列出了系統(tǒng)軟件配置。</p><p>　　表1.1 組裝臺式機配置</p><p><b>　　表1.2 軟件環(huán)境</b></p><p>　　1.2.2 Visu

16、al C++環(huán)境的安裝</p><p>　　在計算機中安裝Visual C++安裝程序，Visual C++應用程序的開發(fā)主要有兩種模式，一種是WIN API方式，另一種則是MFC方式，傳統(tǒng)的WIN API開發(fā)方式比較繁瑣，而MFC則是對WIN API再次封裝，所以MFC相對于WIN API開發(fā)更具備效率優(yōu)勢。本軟件中因為程序主要是為了實現(xiàn)某個算法所以這里沒有用到MFC。</p><p>

17、　　第2章 系統(tǒng)功能分析</p><p>　　2.1 系統(tǒng)功能需求分析</p><p>　　實現(xiàn)本程序需要解決以下幾個問題：</p><p>　　1. 設計一個結(jié)點使該結(jié)點包括電話號碼、用戶名、QQ等結(jié)點信息。</p><p>　　2. 利用用戶名為關鍵字建立哈希表，哈希函數(shù)用除留余數(shù)法構(gòu)照。</p><p>　　

18、3. 利用鏈表法處理沖突問題。</p><p>　　4. 實現(xiàn)用哈希法查找并顯示給定姓名的記錄。</p><p>　　5. 顯示哈希表中的全部記錄。</p><p><b>　　2.2 任務定義</b></p><p>　　由功能需求分析知，本設計主要要求以用戶名為關鍵字建立哈希表，并實現(xiàn)查找功能。所以本設計的核心問題

19、是如何解決散列的問題，亦即設計一個良好的哈希表。根據(jù)題目的要求采用鏈地址法散列算法。當出現(xiàn)同義詞沖突時，使用鏈表結(jié)構(gòu)把同義詞鏈接在一起，即同義詞的存儲地址不是散列表中其他的空地址。</p><p>　　首先，解決的是定義鏈表結(jié)點，在鏈地址法中，每個結(jié)點對應一個鏈表結(jié)點，它由六個域組成，而由于該程序需要用用戶名為關鍵字建立哈希表，所以該鏈表結(jié)點它是char strName[20];char strClass[20]

20、;char strPhone[11];char strqq[10]; int num; char strAddress 六個數(shù)據(jù)域和struct Name *next 一個地址域組成。</p><p>　　構(gòu)造哈希表的函數(shù)主要是用除留取余法來構(gòu)造哈希函數(shù)的。</p><p>　　沖突的解決采用鏈地址法，具體的實現(xiàn)思想是，所有同義詞構(gòu)成一個單鏈表，再由一個表頭結(jié)點指向這個單鏈表的第一個結(jié)點。

21、這些表頭結(jié)點組成一個一維數(shù)組，即哈希表。數(shù)組元素的下標對應由散列函數(shù)求出的散列地址。</p><p><b>　　第3章 總體設計</b></p><p><b>　　3.1系統(tǒng)數(shù)據(jù)結(jié)構(gòu)</b></p><p>　　本設計涉及到的數(shù)據(jù)結(jié)構(gòu)為：哈希表。</p><p>　　程序中建立了兩個結(jié)構(gòu)體，要

22、求輸入電話號碼、用戶名、QQ、地址、四個信息，給struct Name結(jié)構(gòu)體變量，在創(chuàng)建哈希表時哈希函數(shù)用除留余數(shù)法構(gòu)照，并把struct Name結(jié)構(gòu)體中的數(shù)據(jù)賦值給哈希表結(jié)構(gòu)體。</p><p>　　在鏈地址法中，每個結(jié)點對應一個鏈表結(jié)點，它由六個域組成，鏈地址法結(jié)點結(jié)構(gòu)如表：</p><p><b>　　表 3.1</b></p><p>

23、;　　其中哈希表是以用戶名為關鍵字 next指針是用來指向下一個結(jié)點的地址。</p><p>　　具體的存儲結(jié)構(gòu)如下圖所示:</p><p>　　圖3.1數(shù)據(jù)結(jié)構(gòu)存儲圖</p><p>　　3.2主要算法流程圖</p><p>　　3.2.1 以姓名為關鍵字的CreateHashList()函數(shù)流程圖</p><p>

24、<b>　　圖 3.2</b></p><p>　　3.2.2 哈希表查找算法流程圖</p><p><b>　　圖 3.3</b></p><p>　　3.2.3主程序流程圖</p><p><b>　　圖 3.4</b></p><p>　　第4章

25、 詳細設計和編碼</p><p><b>　　4.1節(jié)點的建立</b></p><p>　　定義結(jié)構(gòu)體如下所示:</p><p>　　typedef struct Name</p><p><b>　　{</b></p><p>　　char strName[20];//姓名

26、</p><p>　　char strClass[20];//班級</p><p>　　char strPhone[11];//手機號碼</p><p>　　char strAddress[30];//地址</p><p>　　char Nqq[10];//QQ</p><p>　　int num;//關鍵字</

27、p><p>　　struct Name *next;</p><p><b>　　}pName;</b></p><p>　　pName NameList[HASH_LEN];</p><p><b>　　pName k;</b></p><p>　　struct Hlist&l

28、t;/p><p><b>　　{</b></p><p>　　pName *next;</p><p>　　}HashList[HASH_LEN];</p><p>　　4.2 對哈希函數(shù)的定義</p><p>　　本程序設計一個hash()函數(shù)，本設計中按照題意要求知對散列函數(shù)選擇的是除留余數(shù)法，

29、即對關鍵字進行模運算，將計算結(jié)果所得的余數(shù)作為關鍵字（或結(jié)點）的存儲地址，即H(key)=key mod p,在程序中p取的值為范圍內(nèi)的最大的素數(shù)，以用戶名為關鍵字建立哈希函數(shù)CreateHash()，利用強制類型轉(zhuǎn)換將用戶名的每一個字母的ASCLL碼值相加并且除以范圍內(nèi)最大的素數(shù)，將計算出來的數(shù)作為該結(jié)點的地址賦給adr。然后通過以下幾種方式就可以完成哈希表程序的設計了。</p><p>　　4.3 創(chuàng)建哈希表

30、算法、代碼如下所示:</p><p><b>　　4.3.1 算法</b></p><p>　　建立結(jié)點，并添加結(jié)點，利用鏈地址法解決沖突。建立結(jié)點應包括動態(tài)申請內(nèi)存空間。向結(jié)點中輸入信息。同時將結(jié)點中的next指針等于null。添加結(jié)點，首先需要利用哈希函數(shù)計算出地址即關鍵字，其次將該結(jié)點插入以關鍵字為地址的鏈表后。</p><p><

31、b>　　4.3.2代碼</b></p><p>　　void CreateHashList()</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　for(i=0; i<HASH_LEN; i++)</p>

32、<p><b>　　{</b></p><p>　　HashList[i].next=NULL;</p><p><b>　　}</b></p><p>　　for(i=0; i<2; i++)</p><p><b>　　{</b></p>

33、<p>　　struct Hlist *q;</p><p>　　pName *p,*m;</p><p>　　int adr=(NameList[i].num)%M;//哈希函數(shù)</p><p>　　if(HashList[adr].next==NULL)//表明不沖突</p><p><b>　　{</b>

34、</p><p>　　HashList[adr].next=&NameList[i];</p><p><b>　　}</b></p><p>　　else//表明沖突</p><p><b>　　{</b></p><p>　　q=&HashList[adr

35、];</p><p>　　m=q->next;</p><p>　　while(m->next!=NULL)</p><p><b>　　{ </b></p><p>　　m=m->next;</p><p><b>　　}</b></p>

36、<p>　　p=(pName *)malloc(sizeof(pName));</p><p>　　strcpy(p->strName,NameList[i].strName);</p><p>　　strcpy(p->strPhone, NameList[i].strPhone);</p><p>　　strcpy(p->strAdd

37、ress,NameList[i].strAddress);</p><p>　　strcpy(p->Nqq, NameList[i].Nqq);</p><p>　　p->num=NameList[i].num;</p><p>　　m->next=p;//單鏈表向后指</p><p><b>　　}</b&

38、gt;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　4.4哈希查找</b></p><p>　　想要實現(xiàn)查找功能，需要一個查找函數(shù)，以用戶名為關鍵字來實現(xiàn)查找，首先，需要利用hash函數(shù)來計算出地址。再通過比對，如

39、果該地址中的用戶名拼音字符相加的num與查找的相同則輸出該結(jié)點的所有信息，否則輸出“無此記錄”。</p><p>　　具體實現(xiàn)代碼如下所示:</p><p>　　void SearchList()</p><p><b>　　{</b></p><p>　　system("cls");</p&g

40、t;<p><b>　　char *f;</b></p><p>　　printf("\n\n請輸入你要查找姓名（拼音）");//輸入姓名</p><p>　　char name[20];</p><p>　　scanf("%s",name);</p><p><

41、;b>　　f=name;</b></p><p>　　int s=0, r;</p><p>　　for(r=0; *(f+r)!='\0'; r++)//求出姓名的拼音所對應的整數(shù)也就是關鍵字</p><p><b>　　{</b></p><p>　　s+=(int)*(f+r);/

42、/利用字符與整數(shù)的自動轉(zhuǎn)換相加字符的ASCII碼</p><p><b>　　}</b></p><p>　　int adr=s%M;//使用哈希函數(shù)</p><p>　　if(HashList[adr].next==NULL)//通過指針的指向判斷一個單鏈表中是否存在要查找的數(shù)</p><p><b>　　{

43、</b></p><p>　　printf("無該記錄");</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　if((Has

44、hList[adr].next)->next==NULL)</p><p><b>　　{</b></p><p>　　if((HashList[adr].next)->num==s)</p><p><b>　　{</b></p><p><b>　　int i=1;<

45、/b></p><p>　　printf(“\n姓名:%s”, (HashList[adr].next)->strName);</p><p>　　printf(“班級:%s”, (HashList[adr].next)->strClass);</p><p>　　printf(“電話:%s”, (HashList[adr].next)->s

46、trPhone);</p><p>　　printf(“QQ:%s”, HashList[adr].next)->Nqq);</p><p>　　printf(“地址: %s\n”, (HashList[adr].next)->strAddress);</p><p>　　printf(“關鍵字:%d”, (HashList[adr].next)->

47、;num);</p><p>　　printf(“查找長度:%d”, i);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</

48、b></p><p><b>　　pName *m;</b></p><p><b>　　int i=1;</b></p><p>　　m=HashList[adr].next;</p><p>　　while(m->next!=NULL)//循環(huán)該單鏈表查找出你所要查找的數(shù)據(jù)并把他們輸

49、出</p><p><b>　　{</b></p><p>　　if(m->num==s)</p><p><b>　　{</b></p><p>　　Printf(“\n姓名:%s”, m->strName);</p><p>　　Printf(“班級:%s”,

50、 m->strClass);</p><p>　　Printf(“電話:%s”, m->strPhone);</p><p>　　Printf(“QQ：%s”, m->Nqq);</p><p>　　Printf(“地址: %s”, m->strAddress);</p><p>　　Printf(“關鍵字:%d”,

51、m->num);</p><p>　　printf("查找長度:%d", i);</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　m=m->next;</p><p><b&g

52、t;　　i++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>

53、　　4.5顯示哈希表</b></p><p>　　通過姓名關鍵字，循環(huán)查找有值的下標并輸出來,具體設計代碼如下：</p><p>　　void Display()</p><p><b>　　{</b></p><p>　　system("cls");</p><p&g

54、t;　　int i, s, j, adr, n=0;</p><p><b>　　char *f;</b></p><p>　　struct Hlist *m;</p><p>　　struct Name *k;</p><p>　　char name[20];</p><p>　　printf(

55、"\n\n下標地址\t關鍵字\tH(key)\t拼音 班級 QQ 地址 電話 \n"); //顯示的格式</p><p>　　for(i=0; i<2; i++)</p><p><b>　　{</b></p><p><b>　　s=0;</b></p><p&

56、gt;　　strcpy(name,NameList[i].strName);</p><p><b>　　f=name;</b></p><p>　　for(j=0; *(f+j)!='\0'; j++)</p><p><b>　　{</b></p><p>　　s+=(int)*

57、(f+j);</p><p><b>　　}</b></p><p><b>　　adr=s%M;</b></p><p>　　m=&HashList[adr];</p><p>　　if(m->next!=NULL)</p><p><b>　　{&

58、lt;/b></p><p>　　k=m->next;</p><p><b>　　n+=1;</b></p><p>　　while(k->next!=NULL)</p><p><b>　　{</b></p><p>　　printf("下標地

59、址:%d",i);</p><p>　　printf("\t%d ",k->num); </p><p>　　printf("\t%d ",(k->num)%M); </p><p>　　printf("\t %s ",k->strName); </p><p

60、>　　printf(" %s",k->strClass);</p><p>　　printf(" %s",k->Nqq);</p><p>　　printf(" %s",k->strAddress);</p><p>　　printf(" %s",k-

61、>strPhone);</p><p>　　printf("\n"); </p><p>　　k=k->next;</p><p><b>　　}</b></p><p>　　printf("下標地址:%d",i);</p><p>　　prin

62、tf("\t%d ",k->num); </p><p>　　printf("\t%d ",(k->num)%M); </p><p>　　printf("\t %s ",k->strName); </p><p>　　printf(" %s",k->strCl

63、ass);</p><p>　　printf(" %s",k->Nqq);</p><p>　　printf(" %s",k->strAddress);</p><p>　　printf(" %s",k->strPhone);</p><p>　　prin

64、tf("\n"); </p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　4.6主菜單設計</b></p><p>

65、　　根據(jù)題目中的要求我們只要寫出哈希表的初始化 查找 顯示三個功能，代碼如下所示:</p><p>　　void Menu()</p><p><b>　　{</b></p><p>　　printf("\n------------------------哈希表的建立和查找操作----------------------")

66、; </p><p>　　printf("\n\n"); </p><p>　　printf(" 1. 哈希表初始化\n");</p><p>　　printf(" 2. 顯示哈希表\n"); </p><p>　　printf(" 3. 查找\n"); &l

67、t;/p><p>　　printf(" 4. 退出\n");</p><p><b>　　}</b></p><p><b>　　4.7 主函數(shù)設計</b></p><p>　　主函數(shù)是一個軟件運行的入口，其通過調(diào)用自定義函數(shù)來完成相應的功能,其實現(xiàn)代碼如下所示:</p>

68、<p>　　int main(int argc, char *argv[])</p><p><b>　　{</b></p><p>　　int i,f=0;</p><p><b>　　while(1)</b></p><p><b>　　{</b></p

69、><p><b>　　Menu();</b></p><p>　　scanf("%d",&i);</p><p><b>　　switch(i)</b></p><p><b>　　{</b></p><p>　　case 1:

70、InitNameList(); </p><p>　　CreateHashList(); </p><p><b>　　f=1;</b></p><p><b>　　break;</b></p><p>　　case 2: if(f==1)</p><p><b>

71、;　　{</b></p><p>　　Display();</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{<

72、;/b></p><p>　　printf("哈希表未初始化請先初始化再操作");</p><p><b>　　}</b></p><p><b>　　break;</b></p><p>　　case 3: if(f==1)</p><p><

73、;b>　　{</b></p><p>　　SearchList();</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　printf(&qu

74、ot;哈希表未初始化請先初始化再操作");</p><p><b>　　}</b></p><p><b>　　break;</b></p><p>　　case 4:return 0;</p><p>　　default:printf("請輸入正確的選項");<

75、/p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　第5章 程序運行測試</p>&l

76、t;p><b>　　5.1程序主界面</b></p><p>　　圖5.1 程序主界面</p><p><b>　　5.2哈希表初始化</b></p><p>　　測試數(shù)據(jù)(正確): </p><p>　　姓名:kaluo班級:305電話:123456789 地址:長沙涉外 QQ:282265

77、478</p><p>　　姓名:tianxia  班級:306 電話:987654321 地址:長沙理工 QQ:974562228</p><p>　　姓名:xiantu  班級:3076 電話:987654322 地址:長沙學院 QQ:974562222</p><p><b>　　測試數(shù)據(jù)(錯誤):</b></p

78、><p>　　姓名:張三(否拼音)  班級:3077 電話:987654322 地址:長沙學院 QQ:974562222</p><p>　　姓名:李四(否拼音)  班級:3078電話:987654322 地址:長沙學院 QQ:974562222</p><p>　　圖5.2 哈希表正確初始化</p><p>　　圖5.3 哈

79、希表的錯誤初始化</p><p>　　圖5.4 哈希表初始化</p><p>　　5.3按姓名查找記錄</p><p>　　圖5.5 輸入查找條件</p><p>　　圖5.6 查找結(jié)果 </p><p>　　5.4顯示哈希表全部記錄</p><p>　　圖5.7 顯示表中全部記錄</p&

80、gt;<p><b>　　總結(jié)</b></p><p>　　1、語法錯誤及修改：程序是分塊寫的,調(diào)試時可以使用分步調(diào)試的方式進行,以便能查找看程序是在哪出錯了。程序中使用了鏈表結(jié)構(gòu)和鏈地址法解決沖突的問題，以姓名為關鍵字的哈希表中要注意涉及ASCLL碼的類型轉(zhuǎn)換。</p><p>　　2、邏輯問題修改和調(diào)整：鏈表結(jié)構(gòu)方法雖然方便了運行，但是增加了對算法過

81、程的認識難度。在本程序中每一個函數(shù)中都需要涉及到指針的操作。所以需要仔細分析函數(shù)中的指針指向。</p><p>　　3、時間，空間性能分析：散列法本質(zhì)上是一種通過關鍵字直接計算存儲地址的方法。在理想情況下，散列函數(shù)可以把結(jié)點均勻地分布到散列表中，不發(fā)生沖突，則查找過程無需比較，其時間復雜度O（n）=1。但在實際使用過程中，為了將范圍廣泛的關鍵字映射到一組連續(xù)的存儲空間，往往會發(fā)生同義詞沖突，這時在查找過程中就需要

82、進行關鍵字比較。因此散列法的查找性能取決于3個因素：散列函數(shù)、沖突處理方法和填充因子。采用鏈地址法，可以從根本上杜絕“二次聚集”的發(fā)生，從而提高散列表的均勻度，提高查找性能，不過也會“浪費”一部分散列表的空間。當散列函數(shù)和沖突處理辦法固定時，散列法的查找性能就取決于散列表的填充因子。填充因子a=表中已有的結(jié)點數(shù)/表的長度。填充因子a標志表的添滿程度。很顯然，a越小則發(fā)生沖突的機會就越??；反之，a越大沖突的機會就越大，查找的性能也就越低。

83、哈希表鏈地址法查找成功的平均查找長度SNc=1+a/2。鏈地址法查找不成功的平均查找長度Un滿足：Unc=a+e-a.由以上可以看出，散列表的平均查找長度是填充因子的函數(shù)，和散列表的長度沒有關系，因此在實際應用中，我們應該選擇一個適當?shù)奶畛湟蜃?，以便把平均查?lt;/p><p><b>　　參考文獻</b></p><p>　　[1]（美）佛羅贊(Forouzan).計

84、算機科學導論[M].北京：機械工業(yè)出版社,2004.217~219</p><p>　　[2] 嚴蔚敏 吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學出版社,1997.251~259</p><p>　　[3] 王昆侖 李紅.數(shù)據(jù)結(jié)構(gòu)與算法[M].北京：中國鐵道出版社,2007.6</p><p>　　[4] 李春葆.數(shù)據(jù)結(jié)構(gòu)題集[M].北京：清華大學出版社，1992.2&