散列法的課程設(shè)計(jì)說明書

1、中北大學(xué)數(shù) 據(jù) 結(jié) 構(gòu)課 程 設(shè) 計(jì) 說 明 書學(xué)生姓名: 淮華瑞學(xué) 號：1021010908學(xué) 院:軟件學(xué)院專 業(yè):軟件工程題 目:散列表的實(shí)驗(yàn)研究指導(dǎo)教師康珺2011年12月20日1. 設(shè)計(jì)任務(wù)概述（包括系統(tǒng)總體框圖及功能描述）建立散列表系統(tǒng)總體框圖二次探測再散列線性探測再散列鏈地址法鏈地址法查找二次探測再散列查找線性探測再散列查找問題描述 散列法中，散列函數(shù)構(gòu)造方法多種多樣，同時(shí)對于同一散列函數(shù)解決沖突的方法也可以不同。兩者是影響查詢算法性能的關(guān)鍵因素。對于幾種典型的散列函數(shù)構(gòu)造方法，做實(shí)驗(yàn)觀察，不同的解決沖突方法對查詢性能的影響。概要設(shè)計(jì) 散列又稱哈?；螂s湊。散列法（hashing）在

2、表項(xiàng)的存儲(chǔ)位置與它的關(guān)鍵碼之間建立一個(gè)確定的對應(yīng)函數(shù)關(guān)系hash（），以使每個(gè)關(guān)鍵碼與結(jié)構(gòu)中的唯一存儲(chǔ)位置相對應(yīng)，該關(guān)系可用下式表示：address=hash（record.key）相應(yīng)的表稱為哈希表，這種方法的基本思想是：首先在元素的關(guān)鍵字k和元素的存儲(chǔ)位置p之間建立一個(gè)對應(yīng)關(guān)系h，使得p=h(k)，h稱為哈希函數(shù)。創(chuàng)建哈希表時(shí)，把關(guān)鍵字為k的元素直接存入地址為h(k)的單元；以后當(dāng)查找關(guān)鍵字為k的元素時(shí)，再利用哈希函數(shù)計(jì)算出該元素的存儲(chǔ)位置p=h(k)，從而達(dá)到按關(guān)鍵字直接存取元素的目的。 哈希函數(shù)是一個(gè)映象，哈希函數(shù)的設(shè)定靈活，只要使得任何關(guān)鍵字所得的哈希函數(shù)值都落在表長范圍之內(nèi)即可。

3、當(dāng)關(guān)鍵字集合很大時(shí)，關(guān)鍵字值不同的元素可能會(huì)映象到哈希表的同一地址上，即 k1k2，但h(k1)=h(k2)，這種現(xiàn)象稱為沖突，此時(shí)稱k1和k2為同義詞。實(shí)際中，沖突是不可避免的，只能通過改進(jìn)哈希函數(shù)的性能來減少?zèng)_突。 綜上所述，哈希法主要包括以下兩方面的內(nèi)容。 (1）如何構(gòu)造哈希函數(shù)； (2） 如何處理沖突。2. 本設(shè)計(jì)所采用的數(shù)據(jù)結(jié)構(gòu)（如：鏈表、棧、樹、圖等）一、散列函數(shù) 通常，構(gòu)造散列函數(shù)應(yīng)該注意的幾個(gè)問題包括：首先，散列函數(shù)的定義域必須包括需要存儲(chǔ)的全部關(guān)鍵碼，而如果散列表允許有m個(gè)地址，其值域必須在1m-1之間;其次，散列函數(shù)計(jì)算出來的地址應(yīng)能均勻分布在整個(gè)地址空間中；再次，散列函數(shù)

4、應(yīng)當(dāng)是盡量簡單的。1直接定址法 直接定址法藍(lán)顏元素關(guān)鍵碼的某個(gè)線性函數(shù)值作為該元素的散列地址（散列地址，即元素最終在字典中的存儲(chǔ)位置）。如下面的函數(shù)式：hash（key）=akey+b式中，a，b為常數(shù)。采用該種方法，當(dāng)向字典中加入某一新元素時(shí)算法自動(dòng)調(diào)用此函數(shù)，以確定該元素最終的存儲(chǔ)位置。若某元素關(guān)鍵碼key為1，上式中，a=2，b=3則該元素最終會(huì)存儲(chǔ)在字典第5個(gè)位置中。 直接定址法的優(yōu)點(diǎn)是實(shí)現(xiàn)方法簡單，算法時(shí)間復(fù)雜度較小，而且不會(huì)產(chǎn)生沖突。但是，直接定址法要求散列地址空間的大小與關(guān)鍵碼集合的大小一致，而這種要求是苛刻的，一般很難實(shí)現(xiàn)。例如當(dāng)關(guān)鍵碼的范圍為11000000時(shí)，元素散列地址的

5、個(gè)數(shù)也要達(dá)到1000000。這么大的散列地址是不合實(shí)際的。2.除留余數(shù)法 設(shè)散列表中允許的地址數(shù)為m，取一個(gè)不大于m，但最接近或等于m的質(zhì)數(shù)k，或選取一個(gè)不含有小于20的質(zhì)因子的合數(shù)作為除數(shù)。利用下面的式子計(jì)算元素的散列地址的方法稱為除留余數(shù)法。hash（key）=key%k，km其中，“%”是整數(shù)除余法取余的運(yùn)算，要求這時(shí)的質(zhì)數(shù)不是接近2的冪。例如，當(dāng)元素的關(guān)鍵碼key為2008，散列地址總數(shù)為50，這時(shí)取k=47，則散列地址為hash（2008）=2008%47=34，所以運(yùn)算將存儲(chǔ)在字典第47個(gè)位置中。 除留余數(shù)法將有效縮減散列地址空間的大小，例如上例散列地址空間中只有50個(gè)有效的散列地

6、址。除留余數(shù)法的缺點(diǎn)是極易發(fā)生沖突，如關(guān)鍵碼為1914的元素經(jīng)過上述教例函數(shù)計(jì)算后也將獲得散列地址34。此時(shí)出現(xiàn)的兩個(gè)不同元素爭用同一存儲(chǔ)地址的情況就稱為沖突。3.平方取中法 平方取中法是一種常用的實(shí)現(xiàn)散列函數(shù)的方法。 平方取中法是一種先放大再集合的構(gòu)造方法，這種構(gòu)造模式先通過求關(guān)鍵字的平方值擴(kuò)大相近數(shù)的差別，然后根據(jù)表長度取中間的幾位數(shù)作為散列函數(shù)值，這種取中間數(shù)的方法是一種類隨機(jī)方案，因此也可以認(rèn)為平方取中法是一種產(chǎn)生偽隨機(jī)數(shù)的方法。因?yàn)橐粋€(gè)乘積的中間幾位數(shù)和乘數(shù)的每一位都相關(guān)，所以有此產(chǎn)生的散列地址較為均勻。 利用平方取中法實(shí)現(xiàn)散列函數(shù)的過程：首先，利用一定的編碼規(guī)則把元素的關(guān)鍵碼轉(zhuǎn)換成

7、標(biāo)識符。然后，求出標(biāo)識符的內(nèi)碼表示并計(jì)算內(nèi)碼的平方值。最后，取內(nèi)碼平方數(shù)的中間x位作為元素最終的散列地址。簡而言之，即先計(jì)算構(gòu)成關(guān)鍵碼表示符的內(nèi)碼平方，然后按照散列表的大小取中間的若干位作為散列地址。 在平方取中法中，地址空間內(nèi)散列地址的數(shù)目一般為2的k次冪，并在計(jì)算出內(nèi)碼平方的平方后，根據(jù)k的大小決定最終散列地址的位數(shù)。例如某個(gè)地址空間中散列地址的個(gè)數(shù)為128，則最終取內(nèi)碼平方中間7位作為元素最終的散列地址。4.乘余取整法 乘余取整法利用下面的式子計(jì)算元素的散列地址。hash（key）=z（akey%1） 其中，a為一個(gè)常數(shù)且0a1，z為一個(gè)整數(shù)。式akey%1表示akey取小數(shù)部分，即ak

8、ey%1= akey- akey 。例如，當(dāng)元素關(guān)鍵碼為2008， 小數(shù)a為0.6180339，整數(shù)z為10000，則散列地址計(jì)算為hash（2008）=10000（0.61803392008%1）=120。 乘余取整法不但會(huì)縮減散列地址空間的大小，還能極大減小沖突情況的發(fā)生幾率。knuth對常數(shù)a的取法做了仔細(xì)的研究，發(fā)現(xiàn)雖然a取任何值都可以，但一般取黃金分割數(shù)0.6180339比較好。5.折疊法折疊法的工作方式很有趣，此方法把關(guān)鍵嗎從左至右劃分為位數(shù)相等的幾部分，每一部分的位數(shù)與散列地址數(shù)相同。當(dāng)關(guān)鍵碼位數(shù)不能被散列地址位數(shù)整除時(shí)，最后一部分可取得短些。 折疊法有兩種，即位移法和分界法。

9、其中，位移法所采取的具體方式是把各部分的最后一位對齊相加。分界法所采用的具體方式是各部分不折斷，而沿各部分的分界來回折疊，然后對齊相加，并將相加的結(jié)果當(dāng)做散列地址。折疊法適用于關(guān)鍵碼位數(shù)很多，且每一位上數(shù)字分布比較均勻的情況。下面通過實(shí)例演示這兩種方法的工作方式。 設(shè)關(guān)鍵碼key=987654321，散列地址為4位。位移法和分界法計(jì)算散列地址的算式如圖所示。9876 98765432 2345 + 1 + 1 15309 12222 移位法 分界法由式可見，位移法計(jì)算結(jié)果為15309，由于散列地址為4位，所以舍去最高位數(shù)字1，元素最終的散列地址為5309。分界法結(jié)算結(jié)果為12222，同樣舍去最

10、高位數(shù)字1，元素最終的散列地址為2222。二、散列沖突解決方法在構(gòu)造散列函數(shù)的過程中，不可避免地會(huì)出現(xiàn)沖突的情況。所謂處理沖突，就是在有沖突發(fā)生時(shí)，為產(chǎn)生沖突的關(guān)鍵字找到另一個(gè)地址存放該關(guān)鍵字。在解決沖突的過程中，可能會(huì)得到一系列散列地址hi（i=1,2，n),也就是發(fā)生第一沖突時(shí)，經(jīng)過處理后得到第一新地址記作h1，如果h1仍然會(huì)沖突，則處理后得到第二個(gè)地址h2，依此類推，直到hn不產(chǎn)生沖突，將hn作為關(guān)鍵字的儲(chǔ)存地址。處理沖突的方法比較常用的主要有開放定址法、再散列法和鏈地址法。1. 開放定址法開放定址法是解決沖突比較常用的方法。開放定址法就是利用散列表中的空地址存儲(chǔ)產(chǎn)生沖突的關(guān)鍵字。當(dāng)沖突

11、發(fā)生時(shí)，按照下列公式處理沖突：hi=（h（key）+di）%m，其中i=1,2，m-1其中，h（key）為散列函數(shù)，m為散列表長，di為地址增量。地址增量di可以以下三種方法獲得：（1） 線性探測再散列：當(dāng)沖突發(fā)生時(shí)，地址增量di依次取1,2，m-1自然數(shù)列，即di=1,2，m-1。（2） 二次探測再散列：在沖突發(fā)生時(shí)，地址增量di依次取自然數(shù)的平方，即di=12，12,22，22，k2，k2。（3） 偽隨機(jī)數(shù)再散列：在沖突發(fā)生時(shí)，地址增量di依次取隨機(jī)數(shù)序列。例如，在長度為14的散列表中，在將關(guān)鍵字183,123,230,91存放在散列表中的情況如圖所示。hash地址 0 1 2 3 4 5

12、 6 7 8 9 10 11 12 13列表沖突發(fā)生前示意圖當(dāng)要插入關(guān)鍵字149時(shí)，有散列函數(shù)h（149）=149%13=6，而單元6已經(jīng)存在關(guān)鍵字，產(chǎn)生沖突，利用線性探測再散列法解決沖突，即h1=（6+1）%14=7，將149儲(chǔ)存在單元7中，如圖所示。hash地址 0 1 2 3 4 5 6 7 8 9 10 11 12 13 18312314923091插入關(guān)鍵字149后的示意圖當(dāng)要插入關(guān)鍵字227時(shí)，由散列函數(shù)h（227）=227%13=6，而單元6已經(jīng)存在關(guān)鍵字，產(chǎn)生沖突，利用線性探測再散列法解決沖突，即h1=（6+1）%14=7，仍然沖突，繼續(xù)利用線性探測法

13、，即h2=（6+2）%14=8，單元8空閑，因此將227存儲(chǔ)在單元8中，如圖所示。hash地址 0 1 2 3 4 5 6 7 8 9 10 11 12 13 18312314922723091插入關(guān)鍵字227后的示意圖當(dāng)然，在沖突發(fā)生時(shí)，也可以利用二次探測再散列解決沖突。在圖11.33中，如果要插入關(guān)鍵字227，因?yàn)楫a(chǎn)生沖突，利用二次探測再散列法解決沖突，即h1=（6+1）%14=7，再次產(chǎn)生沖突時(shí)，有h2=（61）%14=5，將227儲(chǔ)存在單元5中，如圖所示。hash地址 0 1 2 3 4 5 6 7 8 9 10 11 12 13 18322712314923091利用二次探測再散列解

14、決沖突示意圖2. 再散列法再散列法就是在沖突發(fā)生時(shí)，利用另外一個(gè)散列函數(shù)再次求散列函數(shù)的地址，直到?jīng)_突不再發(fā)生為止，即hi=rehash（key），i=1,2，n其中，rehash表示不同的散列函數(shù)。這種再散列法一般不容易再次發(fā)生沖突，但是需要事先構(gòu)造多個(gè)散列函數(shù)，這是一件不太容易的也不現(xiàn)實(shí)的事情。3. 鏈地址法 數(shù)組的特點(diǎn)是：尋址容易，插入和刪除困難；而鏈表的特點(diǎn)是：尋址困難，插入和刪除容易。那么我們能不能綜合兩者的特性，做出一種尋址容易，插入刪除也容易的數(shù)據(jù)結(jié)構(gòu)？答案是肯定的，這就是我們要提起的哈希表，哈希表有多種不同的實(shí)現(xiàn)方法，我接下來解釋的是最常用的一種方法鏈地址法，我們可以理解為“鏈

15、表的數(shù)組”，如圖： 左邊很明顯是個(gè)數(shù)組，數(shù)組的每個(gè)成員包括一個(gè)指針，指向一個(gè)鏈表的頭，當(dāng)然這個(gè)鏈表可能為空，也可能元素很多。我們根據(jù)元素的一些特征把元素分配到不同的鏈表中去，也是根據(jù)這些特征，找到正確的鏈表，再從鏈表中找出這個(gè)元素。三、 哈希法性能分析由于沖突的存在，哈希法仍需進(jìn)行關(guān)鍵字比較，因此仍需用平均查找長度來評價(jià)哈希法的查找性能。哈希法中影響關(guān)鍵字比較次數(shù)的因素有三個(gè)：哈希函數(shù)、處理沖突的方法以及哈希表的裝填因子。哈希表的裝填因子的定義如下： 線性探測再散列 查找成功時(shí) 查找失敗時(shí) 偽隨機(jī)探測再散列、 二次探測 查找成功時(shí) 查找失敗時(shí) 鏈址法 查找成功時(shí)查找失敗時(shí) 從以上討論可知：哈希

16、表的平均查找長度是裝填因子的函數(shù)，而與待散列元素?cái)?shù)目n無關(guān)。因此，無論元素?cái)?shù)目n有多大，都能通過調(diào)整，使哈希表的平均查找長度較小。 3. 功能模塊詳細(xì)設(shè)計(jì)3.1 詳細(xì)設(shè)計(jì)思想 (1)程序中結(jié)構(gòu)體的定義typedef structint key;int si;hashtable1;typedef struct node int key; int si; struct node *next;node;typedef struct node *link;hashtable2;typedef struct int * elemhashsize; int count; int size;hashtabl

17、e3;(2) 主函數(shù)模塊 void main() int data; hashtable1 hash1hashsize; hashtable2 * hash2hashsize; hashtable3 * ha; ha=(hashtable3 *)malloc(sizeof(hashtable3); for(int i=0;ielemi=null; ha-count=0; ha-size=hashsize; int amaxsize; while(1) printf(n ); printf(n 歡迎使用本系統(tǒng) ); printf(n ); printf(n 散列法的實(shí)驗(yàn)研究 ); printf(

18、n 【1】. 添加數(shù)據(jù)信息 【2】 數(shù)據(jù)的輸出 ); printf(n 【3】. 建立哈希表(線性再散列) ); printf(n 【4】. 建立哈希表(二次探測再散列) ); printf(n 【5】. 建立哈希表(鏈地址法) ); printf(n 【6】. 線性再散列法查找 ); printf(n 【7】. 二次探測再散列法查找 ); printf(n 【8】. 鏈地址法查找 ); printf(n 【0】. 退出程序 ); printf(n ); printf(n); printf(n); printf(請輸入一個(gè)任務(wù)選項(xiàng)); int x; scanf(%d,&x); switch(x

19、) case 1: getin (a);break; case 2: getout(a);break; case 3: createhashtable1(hash1,a,num);break; case 4: createhash3(ha,a,num);break; case 5: createhashtable2(hash2,a,num);break; case 6: printf(請輸入你查找的數(shù)據(jù)：); scanf(%d,&data); searchhash1(hash1,data);break; case 7: printf(請輸入你查找的數(shù)據(jù)：); scanf(%d,&data);

20、searchhash3(ha,data);break; case 8: printf(請輸入你查找的數(shù)據(jù)：); scanf(%d,&data); searchhash2(hash2,data,num);break; case 0:exit(-1); 3.2 核心代碼#include#include#define hashsize 53#define maxsize 20typedef structint key;int si;hashtable1;void createhashtable1(hashtable1 *h,int *a,int num)/哈希表線性探測在散列； int i,d,cn

21、t; for(i=0;ihashsize;i+) hi.key=0; hi.si=0; for(i=0;inum;i+) cnt=1; d=ai%hashsize; if(hd.key=0) hd.key=ai; hd.si=cnt; else do d=(d+1)%hashsize; cnt+; while(hd.key!=0); hd.key=ai; hd.si=cnt; printf(n線性再探索哈希表已建成!);void searchhash1(hashtable1 *h,int data) int d; d=data%hashsize; if(hd.key=data) printf(

22、數(shù)字%d的探查次數(shù)為：%dn,hd.key,hd.si); else do d=(d+1)%hashsize; while(hd.key!=data & dhashsize); if(dhashsize) printf(數(shù)字%d的探查次數(shù)為：%dn,hd.key,hd.si); else printf(沒有查找到你所輸入的數(shù)n); typedef struct node int key; int si; struct node *next;node;typedef struct node *link;hashtable2;void createhashtable2(hashtable2 *ht

23、,int *a,int num)/哈希表鏈地址； int i,d,cnt; node *s,*q; for(i=0;ilink=null; for(i=0;ikey=ai;s-next=null; d=ai%num; if(htd-link=null) htd-link=s; s-si=cnt; else q=htd-link; while(q-next!=null) q=q-next;cnt+; cnt+; s-si=cnt; q-next=s; void searchhash2(hashtable2 * h,int data,int num) int d; node *q; d=data%

24、num; q=hd-link; while(q-key!=data & q-next!=null) q=q-next; if(q-next!=null) printf(數(shù)字%d的查找次數(shù)為：%dn,q-key,q-next); else printf(沒有找到你要查找的那個(gè)數(shù)n);typedef struct int * elemhashsize; int count; int size;hashtable3;int collision(int p,int &c)/二次探測再散列法解決沖突 int i,q; i=c/2+1; while(i=0) return q; else i=c/2+1;

25、 else q=(p-i*i)%hashsize; c+; if(q=0)return q; else i=c/2+1; return (-1);void createhash3(hashtable3 *h,int *a,int num)/二次探索表 int i,p=-1,c,pp; for(i=0;ielempp!=null) pp=collision(p,c); if(ppelempp=&(aai); h-count+; printf(第%d個(gè)記錄沖突次數(shù)為%dn,i+1,c); printf(n建表完成！n此哈希表容量為%d,當(dāng)前表內(nèi)存儲(chǔ)的記錄個(gè)數(shù)%d.n,hashsize,h-coun

26、t);void searchhash3(hashtable3 *h,int data)/哈希表二次探索再散列查找 int c=0,p,pp; p=data%hashsize; pp=p;while(h-elempp!=null)&(*(h-elempp)!=data) pp=collision(p,c);if(h-elempp!=null)&(*(h-elempp)=data) printf(n查找成功!n查找沖突次數(shù)為%d:,c);elseprintf(n沒有查到此數(shù)!n);int num;void getin(int *a) printf(輸入添加的個(gè)數(shù)：); scanf(%d,&num)

27、; for(int i=0;inum;i+) scanf(%d,&ai); printf(數(shù)據(jù)已經(jīng)輸入完畢!n);void getout(int *a) printf(你所輸入的數(shù)據(jù)：); for(int i=0;inum;i+) printf(%d,ai); printf(n輸出已完畢!);void main() int data; hashtable1 hash1hashsize; hashtable2 * hash2hashsize; hashtable3 * ha; ha=(hashtable3 *)malloc(sizeof(hashtable3); for(int i=0;iele

28、mi=null; ha-count=0; ha-size=hashsize; int amaxsize; while(1) printf(n ); printf(n 歡迎使用本系統(tǒng) ); printf(n ); printf(n 散列法的實(shí)驗(yàn)研究 ); printf(n 【1】. 添加數(shù)據(jù)信息 【2】 數(shù)據(jù)的輸出 ); printf(n 【3】. 建立哈希表(線性再散列) ); printf(n 【4】. 建立哈希表(二次探測再散列) ); printf(n 【5】. 建立哈希表(鏈地址法) ); printf(n 【6】. 線性再散列法查找 ); printf(n 【7】. 二次探測再散列法查找 ); printf(n 【8】. 鏈地