數(shù)據(jù)結(jié)構(gòu)-哈希表課件

哈希表什么是哈希表哈希函數(shù)的構(gòu)造方法處理沖突的方法哈希表的查找哈希表的查找分析小結(jié)和作業(yè)課堂練習(xí)1A哈希表什么是哈希表哈希函數(shù)的構(gòu)造方法處理沖突的方法哈希表的查A[0]A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]A[9]A[10]例1:有一批考試成績，統(tǒng)計各分?jǐn)?shù)段的人數(shù)。對成績Grade，執(zhí)行：A[grade/10]++什么是哈希表2AA[0]A[1]A[2]A[3]A[4]A[5]A[6]A[例2:Ord(Char)=asc(char)–asc(‘a(chǎn)’)+1什么是哈希表01(A)345(E)9(I)……

268(H)4(D)19(S)22(V)018(R)7(G)1905(E)HADHASHAVHEHERHEREHIGHIS3A例2:Ord(Char)=asc(char)–asc(‘將1000個學(xué)生的信息存放在數(shù)組A[0]—A[999]中例3:為每年招收的1000名新生建立一張查找表，其關(guān)鍵字為學(xué)號，其值的范圍為xx000~xx999(前兩位為年份)。什么是哈希表number(substring(學(xué)號,3,3))4A將1000個學(xué)生的信息存放在數(shù)組A[0]—A[999]中例3建立查找表：給定關(guān)鍵字key計算f(key)數(shù)組下標(biāo)查找表：使用數(shù)組存放n個關(guān)鍵字，數(shù)組的下標(biāo)0n-1什么是哈希表查找時：給定關(guān)鍵字key計算f(key)數(shù)組下標(biāo)5A建立查找表：查找表：什么是哈希表查找時：5A建立查找表：給定grade計算f(grade)數(shù)組下標(biāo)例4：統(tǒng)計學(xué)生成績各分?jǐn)?shù)段的人數(shù)什么是哈希表查找時：給定grade計算f(grade)數(shù)組下標(biāo)Hash函數(shù)：f(grade)=grade/106A建立查找表：例4：統(tǒng)計學(xué)生成績各分?jǐn)?shù)段的人數(shù)什么是什么是哈希表{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}例5：對于如下9個關(guān)鍵字設(shè)哈希函數(shù)f(key)=

(Ord(第一個字母)-Ord('A')+1)/27A什么是哈希表{Zhao,Qian,Sun,Li,Wu什么是哈希表字母ABCDEFGHIJKLM序號12345678910111213字母NOPQRSTUVWXYZ序號14151617181920212223242526ChenZhaoQianSunLiWuHanYeDei序號012345678910111213問題:若添加關(guān)鍵字Zhou,怎么辦？8A什么是哈希表字母ABCDEFGHIJKLM序號1234567什么是哈希表由此可見，1)哈希(Hash)函數(shù)是一個映象，即：將關(guān)鍵字的集合映射到某個地址集合上，它的設(shè)置很靈活，只要這個地址集合的大小不超出允許范圍即可；2)對不同的關(guān)鍵字可能得到同一哈希地址，即：key1≠key2，而f(key1)=f(key2),因此，很容易產(chǎn)生“沖突”現(xiàn)象；9A什么是哈希表由此可見，1)哈希(Hash)函數(shù)是一個映什么是哈希表3)很難找到一個不產(chǎn)生沖突的哈希函數(shù)。一般情況下，只能選擇恰當(dāng)?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。因此，在構(gòu)造這種特殊的“查找表”時，除了需要選擇一個“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外；還需要找到一種“處理沖突”的方法。10A什么是哈希表3)很難找到一個不產(chǎn)生沖突的哈希函數(shù)。一般情哈希表的定義根據(jù)設(shè)定的哈希函數(shù)H(key)和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個有限的、地址連續(xù)的地址集(區(qū)間)上，并以關(guān)鍵字在地址集中的“象”作為相應(yīng)記錄在表中的存儲位置，如此構(gòu)造所得的查找表稱之為“哈希表”。這一過程稱為哈希造表或者散列，所得的存儲位置成為哈希地址或者散列地址。11A哈希表的定義根據(jù)設(shè)定的哈希函數(shù)H(key)和所選中的處理哈希函數(shù)的構(gòu)造方法對數(shù)字的關(guān)鍵字可有下列構(gòu)造方法:若是非數(shù)字關(guān)鍵字，則需先對其進(jìn)行數(shù)字化處理。1.直接定址法3.平方取中法5.除留余數(shù)法4.折疊法6.隨機數(shù)法2.數(shù)字分析法12A哈希函數(shù)的構(gòu)造方法對數(shù)字的關(guān)鍵字可有下列構(gòu)造方法:若是哈希函數(shù)為關(guān)鍵字的線性函數(shù)H(key)=key或者H(key)=akey+b1.直接定址法哈希函數(shù)的構(gòu)造方法13A哈希函數(shù)為關(guān)鍵字的線性函數(shù)1.直接定址法哈希函數(shù)的構(gòu)造方法哈希函數(shù)的構(gòu)造方法2.數(shù)字分析法假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址。此方法僅適合于：

能預(yù)先估計出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。14A哈希函數(shù)的構(gòu)造方法2.數(shù)字分析法假設(shè)關(guān)鍵字集合中的每個關(guān)鍵哈希函數(shù)的構(gòu)造方法有80個記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地址為2位十進(jìn)制數(shù)8134653281372242813874228130136781322817813389678136853781419355…..…..分析：只取8只取1只取3、4只取2、7、5數(shù)字分布近乎隨機所以：取任意兩位或兩位與另兩位的疊加作哈希地址15A哈希函數(shù)的構(gòu)造方法有80個記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地哈希函數(shù)的構(gòu)造方法以關(guān)鍵字的平方值的中間幾位作為存儲地址。求“關(guān)鍵字的平方值”的目的是“擴大差別”，同時平方值的中間各位又能受到整個關(guān)鍵字中各位的影響。3.平方取中法此方法適合于:關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象。16A哈希函數(shù)的構(gòu)造方法以關(guān)鍵字的平方值的中間幾位作為存儲地址。求哈希函數(shù)的構(gòu)造方法4.折疊法將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈希地址。有兩種疊加處理的方法：移位疊加和間界疊加。此方法適合于:關(guān)鍵字的數(shù)字位數(shù)特別多，而且關(guān)鍵字在每一位上的數(shù)字分布大致均勻的情況。17A哈希函數(shù)的構(gòu)造方法4.折疊法將關(guān)鍵字分割成若干部分，然后取哈希函數(shù)的構(gòu)造方法例關(guān)鍵字為：0442205864，哈希地址位數(shù)為4586442200410088H(key)=0088移位疊加5864022404

6092H(key)=6092間界疊加4.折疊法18A哈希函數(shù)的構(gòu)造方法例關(guān)鍵字為：0442205864，哈希函數(shù)的構(gòu)造方法5.除留余數(shù)法設(shè)定哈希函數(shù)為:

H(key)=keyMODp

其中，p≤m(表長)并且p應(yīng)為不大于m的素數(shù)或是不含20以下的質(zhì)因子19A哈希函數(shù)的構(gòu)造方法5.除留余數(shù)法設(shè)定哈希函數(shù)為:19A哈希函數(shù)的構(gòu)造方法給定一組關(guān)鍵字為:12,39,18,24,33,21若取p=9,則它們對應(yīng)的哈希函數(shù)值將為:3,3,0,6,6,3為什么要對p加限制？可見，若p中含質(zhì)因子3,則所有含質(zhì)因子3的關(guān)鍵字均映射到“3的倍數(shù)”的地址上，從而增加了“沖突”的可能。20A哈希函數(shù)的構(gòu)造方法給定一組關(guān)鍵字為:12,39,18,哈希函數(shù)的構(gòu)造方法6.隨機數(shù)法設(shè)定哈希函數(shù)為:H(key)=Random(key)其中Random為隨機函數(shù)此方法通常用于對長度不等的關(guān)鍵字構(gòu)造哈希函數(shù)。21A哈希函數(shù)的構(gòu)造方法6.隨機數(shù)法設(shè)定哈希函數(shù)為:此方法通常用哈希函數(shù)的構(gòu)造方法實際構(gòu)造哈希表時1.采用哪種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))2.總的原則是使產(chǎn)生沖突的可能性盡可能的小。3.如果哈希造表過程中產(chǎn)生沖突，應(yīng)當(dāng)如何處理這些沖突呢？22A哈希函數(shù)的構(gòu)造方法實際構(gòu)造哈希表時22A處理沖突的方法沖突：由關(guān)鍵字得到的哈希地址為j（0≤j≤n-1）的位置上已存有記錄處理沖突：為產(chǎn)生沖突的地址尋找下一個空的哈希地址1.開放定址法2.再哈希法3.鏈地址法處理沖突方法4.建立一個公共溢出區(qū)23A處理沖突的方法沖突：由關(guān)鍵字得到的哈希地址為j（0≤j≤n-處理沖突的方法1.開放定址法為產(chǎn)生沖突的地址H(key)求得一個地址序列：H0,H1,H2,…,Hs1≤s≤m-1其中：H0=H(key)Hi=(H(key)+di)MODm

i=1,2,…,s

m為哈希表表長24A處理沖突的方法1.開放定址法為產(chǎn)生沖突的地址H(key)處理沖突的方法1.線性探測再散列法2.二次探測再散列法3.隨機探測再散列法增量di的三種取法25A處理沖突的方法1.線性探測再散列法2.二次探測再散列法3處理沖突的方法1.開放定址法對增量di

的三種取法---①：1)線性探測再散列

di=ci

最簡單的情況c=1

即

di=1,2,3,……m-126A處理沖突的方法1.開放定址法對增量di的三種取法--處理沖突的方法例如:關(guān)鍵字集合{19,01,23,14,55,68,11,82,36}設(shè)定哈希函數(shù)H(key)=keyMOD11(表長=11)采用線性探測再散列法來構(gòu)造哈希表。19012345678910190101232323141455556868681182113611823611213625127A處理沖突的方法例如:關(guān)鍵字集合設(shè)定哈希函數(shù)H(key)處理沖突的方法1.開放定址法對增量di

有三種取法---②：2)平方（二次）探測再散列

di=12,-12,22,-22,…,28A處理沖突的方法1.開放定址法對增量di有三種取法--處理沖突的方法例如:關(guān)鍵字集合{19,01,23,14,55,68,11,82,36}19012345678910190101232323141455556868681182113611823636設(shè)定哈希函數(shù)H(key)=keyMOD11(表長=11)采用二次探測再散列法來構(gòu)造哈希表。11212141329A處理沖突的方法例如:關(guān)鍵字集合190處理沖突的方法1.開放定址法對增量di

有三種取法---③：3)隨機探測再散列

di是一組隨機數(shù)列或者

di=i×H2(key)(又稱雙散列函數(shù)探測)30A處理沖突的方法1.開放定址法對增量di有三種取法--處理沖突的方法即：產(chǎn)生的Hi均不相同，且所產(chǎn)生的m-1個Hi值能覆蓋哈希表中所有地址。則要求：注意：增量di

應(yīng)具有“完備性”※

隨機探測時的m

和di沒有公因子?！?/p>

平方探測時的表長

m必為形如

4j+3

的素數(shù)（如:7,11,19,23,…等）；31A處理沖突的方法即：產(chǎn)生的Hi均不相同，且所產(chǎn)生的注意：增處理沖突的方法H2(key)是另設(shè)定的一個哈希函數(shù)，它的函數(shù)值應(yīng)和m互為素數(shù)。若m為素數(shù)，則H2(key)可以是1至m-1之間的任意數(shù);若m為2的冪次，則H2(key)應(yīng)是1至m-1之間的任意奇數(shù)。32A處理沖突的方法H2(key)是另設(shè)定的一個哈希函數(shù)，它的處理沖突的方法例如，當(dāng)m=11時，可設(shè)H2(key)=(3key)MOD10+119012314556811823611112112233A處理沖突的方法例如，當(dāng)m=11時，190123145568處理沖突的方法2.再哈希法Hi=RHi(key)i=1,2,3,……，kRHi均是不同的哈希函數(shù)，在同義詞產(chǎn)生地址沖突時計算另一個哈希函數(shù)地址，直到?jīng)_突不再發(fā)生。缺點：增加了計算時間。34A處理沖突的方法2.再哈希法Hi=RHi(key)i=1處理沖突的方法3.鏈地址法所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中。定義指針型向量ChainChainHash[m];凡是哈希地址為i的記錄都插入到頭指針為ChainHash[i]的鏈表中。35A處理沖突的方法3.鏈地址法所有關(guān)鍵字為同義詞的記錄存儲在同處理沖突的方法例如:關(guān)鍵字集合{19,01,23,14,55,68,11,82,36}采用鏈地址法來構(gòu)造哈希表。哈希函數(shù)為H(key)=keyMOD71119826855140136231901231455681182360123456ASL=(6×1+2×2+3×1)/9=13/936A處理沖突的方法例如:關(guān)鍵字集合采用鏈地址法來構(gòu)造哈希表。處理沖突的方法4.建立一個公共溢出區(qū)哈希函數(shù)的值域[0,m-1]向量HashTable[0..m-1]為基本表，每個分量存放一個記錄向量OverTable[0..v]為溢出表對于關(guān)鍵字和基本表HashTable中關(guān)鍵字為同義詞的記錄，只要發(fā)生沖突，都填入溢出表。37A處理沖突的方法4.建立一個公共溢出區(qū)哈希函數(shù)的值域[0,m哈希表的查找算法查找過程和造表過程一致。假設(shè)采用開放定址處理沖突，則查找過程為:

1.對于給定值K,計算哈希地址i=H(K)2.若r[i]=NULL則查找不成功3.若

r[i].key=K則查找成功4.否則“求下一地址Hi”，直至r[Hi]=NULL(查找不成功)或r[Hi].key=K(查找成功)為止。38A哈希表的查找算法查找過程和造表過程一致。假設(shè)采用開放定址處理哈希表的查找算法inthashsize[]={997,...};typedefstruct{ElemType*elem;

intcount;//當(dāng)前數(shù)據(jù)元素個數(shù)

intsizeindex;//為當(dāng)前容量}HashTable;#defineSUCCESS1#defineUNSUCCESS0#defineDUPLICATE-1//---開放定址哈希表的存儲結(jié)構(gòu)---//39A哈希表的查找算法inthashsize[]={99哈希表的查找算法StatusSearchHash(HashTableH,KeyTypeK,

int&p,int&c){//在開放定址哈希表H中查找關(guān)鍵碼為K的記錄}//SearchHashp=Hash(K);//求得哈希地址while(H.elem[p].key!=NULLKEY&&

!EQ(K,H.elem[p].key)）

collision(p,++c);//求得下一探查地址pif(EQ(K,H.elem[p].key))returnSUCCESS;//查找成功，返回待查數(shù)據(jù)元素位置pelsereturnUNSUCCESS;//查找不成功40A哈希表的查找算法StatusSearchHash(Has哈希表的維護(hù)算法StatusInsertHash(HashTable&H,Elemtypee){

}//InsertHashc=0;if(SearchHash(H,e.key,p,c)==SUCCESS)returnDUPLICATE;//表中已有與e有相同關(guān)鍵字的元素elseif(c<hashsize[H.sizeindex]/2){

//沖突次數(shù)c未達(dá)到上限，（閥值c可調(diào)） H.elem[p]=e;++H.count;returnOK;}

else{RecreateHashTable(H); returnUNSUCCESS;}//重建哈希表41A哈希表的維護(hù)算法StatusInsertHash(Has哈希表的查找分析從查找過程得知：1、由于沖突的產(chǎn)生，哈希表的查找過程仍然是一個給定值和關(guān)鍵字進(jìn)行比較的過程。2、哈希表查找的平均查找長度實際上并不等于零。42A哈希表的查找分析從查找過程得知：1、由于沖突的產(chǎn)生，哈希表的哈希表的查找分析1)選用的哈希函數(shù);2)選用的處理沖突的方法;3）哈希表飽和的程度，裝載因子

α=n/m值的大?。╪—記錄數(shù)，m—表的長度）決定哈希表查找的ASL的因素：43A哈希表的查找分析1)選用的哈希函數(shù);決定哈希表查找的AS哈希表的查找分析一般情況下，可以認(rèn)為選用的哈希函數(shù)是“均勻”的，則在討論ASL時，可以不考慮它的因素。因此，哈希表的ASL是處理沖突方法和裝載因子的函數(shù)。例如：前述例子線性探測處理沖突時，ASL=鏈地址法處理沖突時，ASL=22/913/944A哈希表的查找分析一般情況下，可以認(rèn)為選用的哈希函數(shù)是“均勻”哈希表的查找分析線性探測再散列可以證明：查找成功時有下列結(jié)果：隨機探測再散列鏈地址法45A哈希表的查找分析線性探測再散列可以證明：查找成功時有下列結(jié)果哈希表的查找分析從以上結(jié)果可見，哈希表的平均查找長度是

的函數(shù)，而不是n的函數(shù)。這說明，用哈希表構(gòu)造查找表時，可以選擇一個適當(dāng)?shù)难b填因子，使得平均查找長度限定在某個范圍內(nèi)。46A哈希表的查找分析從以上結(jié)果可見，哈希表的平均查找長度是哈希表的刪除操作從哈希表中刪除記錄時，要作特殊處理，相應(yīng)地，需要修改查找的算法。47A哈希表的刪除操作從哈希表中刪除記錄時，要作特殊處理，相應(yīng)地，小結(jié)和作業(yè)哈希表

1．哈希原理2．哈希函數(shù)的構(gòu)造方法3．處理沖突的方法4．哈希表的查找及分析作業(yè)：9.19，9.20，9.2148A小結(jié)和作業(yè)哈希表1．哈希原理2．哈希函數(shù)的構(gòu)造方法3．課堂練習(xí)設(shè)有一組關(guān)鍵字{11，54，36，89，51，47，38，59，63，94，15}，采用哈希函數(shù)：H(key)=key%13。采用開放地址法的線性探測再散列方法解決沖突，試在0～15的散列地址空間中對該關(guān)鍵字序列構(gòu)造哈希表。49A課堂練習(xí)設(shè)有一組關(guān)鍵字{11，54，36，89，51，47，哈希表什么是哈希表哈希函數(shù)的構(gòu)造方法處理沖突的方法哈希表的查找哈希表的查找分析小結(jié)和作業(yè)課堂練習(xí)50A哈希表什么是哈希表哈希函數(shù)的構(gòu)造方法處理沖突的方法哈希表的查A[0]A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]A[9]A[10]例1:有一批考試成績，統(tǒng)計各分?jǐn)?shù)段的人數(shù)。對成績Grade，執(zhí)行：A[grade/10]++什么是哈希表51AA[0]A[1]A[2]A[3]A[4]A[5]A[6]A[例2:Ord(Char)=asc(char)–asc(‘a(chǎn)’)+1什么是哈希表01(A)345(E)9(I)……

268(H)4(D)19(S)22(V)018(R)7(G)1905(E)HADHASHAVHEHERHEREHIGHIS52A例2:Ord(Char)=asc(char)–asc(‘將1000個學(xué)生的信息存放在數(shù)組A[0]—A[999]中例3:為每年招收的1000名新生建立一張查找表，其關(guān)鍵字為學(xué)號，其值的范圍為xx000~xx999(前兩位為年份)。什么是哈希表number(substring(學(xué)號,3,3))53A將1000個學(xué)生的信息存放在數(shù)組A[0]—A[999]中例3建立查找表：給定關(guān)鍵字key計算f(key)數(shù)組下標(biāo)查找表：使用數(shù)組存放n個關(guān)鍵字，數(shù)組的下標(biāo)0n-1什么是哈希表查找時：給定關(guān)鍵字key計算f(key)數(shù)組下標(biāo)54A建立查找表：查找表：什么是哈希表查找時：5A建立查找表：給定grade計算f(grade)數(shù)組下標(biāo)例4：統(tǒng)計學(xué)生成績各分?jǐn)?shù)段的人數(shù)什么是哈希表查找時：給定grade計算f(grade)數(shù)組下標(biāo)Hash函數(shù)：f(grade)=grade/1055A建立查找表：例4：統(tǒng)計學(xué)生成績各分?jǐn)?shù)段的人數(shù)什么是什么是哈希表{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}例5：對于如下9個關(guān)鍵字設(shè)哈希函數(shù)f(key)=

(Ord(第一個字母)-Ord('A')+1)/256A什么是哈希表{Zhao,Qian,Sun,Li,Wu什么是哈希表字母ABCDEFGHIJKLM序號12345678910111213字母NOPQRSTUVWXYZ序號14151617181920212223242526ChenZhaoQianSunLiWuHanYeDei序號012345678910111213問題:若添加關(guān)鍵字Zhou,怎么辦？57A什么是哈希表字母ABCDEFGHIJKLM序號1234567什么是哈希表由此可見，1)哈希(Hash)函數(shù)是一個映象，即：將關(guān)鍵字的集合映射到某個地址集合上，它的設(shè)置很靈活，只要這個地址集合的大小不超出允許范圍即可；2)對不同的關(guān)鍵字可能得到同一哈希地址，即：key1≠key2，而f(key1)=f(key2),因此，很容易產(chǎn)生“沖突”現(xiàn)象；58A什么是哈希表由此可見，1)哈希(Hash)函數(shù)是一個映什么是哈希表3)很難找到一個不產(chǎn)生沖突的哈希函數(shù)。一般情況下，只能選擇恰當(dāng)?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。因此，在構(gòu)造這種特殊的“查找表”時，除了需要選擇一個“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外；還需要找到一種“處理沖突”的方法。59A什么是哈希表3)很難找到一個不產(chǎn)生沖突的哈希函數(shù)。一般情哈希表的定義根據(jù)設(shè)定的哈希函數(shù)H(key)和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個有限的、地址連續(xù)的地址集(區(qū)間)上，并以關(guān)鍵字在地址集中的“象”作為相應(yīng)記錄在表中的存儲位置，如此構(gòu)造所得的查找表稱之為“哈希表”。這一過程稱為哈希造表或者散列，所得的存儲位置成為哈希地址或者散列地址。60A哈希表的定義根據(jù)設(shè)定的哈希函數(shù)H(key)和所選中的處理哈希函數(shù)的構(gòu)造方法對數(shù)字的關(guān)鍵字可有下列構(gòu)造方法:若是非數(shù)字關(guān)鍵字，則需先對其進(jìn)行數(shù)字化處理。1.直接定址法3.平方取中法5.除留余數(shù)法4.折疊法6.隨機數(shù)法2.數(shù)字分析法61A哈希函數(shù)的構(gòu)造方法對數(shù)字的關(guān)鍵字可有下列構(gòu)造方法:若是哈希函數(shù)為關(guān)鍵字的線性函數(shù)H(key)=key或者H(key)=akey+b1.直接定址法哈希函數(shù)的構(gòu)造方法62A哈希函數(shù)為關(guān)鍵字的線性函數(shù)1.直接定址法哈希函數(shù)的構(gòu)造方法哈希函數(shù)的構(gòu)造方法2.數(shù)字分析法假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址。此方法僅適合于：

能預(yù)先估計出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。63A哈希函數(shù)的構(gòu)造方法2.數(shù)字分析法假設(shè)關(guān)鍵字集合中的每個關(guān)鍵哈希函數(shù)的構(gòu)造方法有80個記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地址為2位十進(jìn)制數(shù)8134653281372242813874228130136781322817813389678136853781419355…..…..分析：只取8只取1只取3、4只取2、7、5數(shù)字分布近乎隨機所以：取任意兩位或兩位與另兩位的疊加作哈希地址64A哈希函數(shù)的構(gòu)造方法有80個記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地哈希函數(shù)的構(gòu)造方法以關(guān)鍵字的平方值的中間幾位作為存儲地址。求“關(guān)鍵字的平方值”的目的是“擴大差別”，同時平方值的中間各位又能受到整個關(guān)鍵字中各位的影響。3.平方取中法此方法適合于:關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象。65A哈希函數(shù)的構(gòu)造方法以關(guān)鍵字的平方值的中間幾位作為存儲地址。求哈希函數(shù)的構(gòu)造方法4.折疊法將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈希地址。有兩種疊加處理的方法：移位疊加和間界疊加。此方法適合于:關(guān)鍵字的數(shù)字位數(shù)特別多，而且關(guān)鍵字在每一位上的數(shù)字分布大致均勻的情況。66A哈希函數(shù)的構(gòu)造方法4.折疊法將關(guān)鍵字分割成若干部分，然后取哈希函數(shù)的構(gòu)造方法例關(guān)鍵字為：0442205864，哈希地址位數(shù)為4586442200410088H(key)=0088移位疊加5864022404

6092H(key)=6092間界疊加4.折疊法67A哈希函數(shù)的構(gòu)造方法例關(guān)鍵字為：0442205864，哈希函數(shù)的構(gòu)造方法5.除留余數(shù)法設(shè)定哈希函數(shù)為:

H(key)=keyMODp

其中，p≤m(表長)并且p應(yīng)為不大于m的素數(shù)或是不含20以下的質(zhì)因子68A哈希函數(shù)的構(gòu)造方法5.除留余數(shù)法設(shè)定哈希函數(shù)為:19A哈希函數(shù)的構(gòu)造方法給定一組關(guān)鍵字為:12,39,18,24,33,21若取p=9,則它們對應(yīng)的哈希函數(shù)值將為:3,3,0,6,6,3為什么要對p加限制？可見，若p中含質(zhì)因子3,則所有含質(zhì)因子3的關(guān)鍵字均映射到“3的倍數(shù)”的地址上，從而增加了“沖突”的可能。69A哈希函數(shù)的構(gòu)造方法給定一組關(guān)鍵字為:12,39,18,哈希函數(shù)的構(gòu)造方法6.隨機數(shù)法設(shè)定哈希函數(shù)為:H(key)=Random(key)其中Random為隨機函數(shù)此方法通常用于對長度不等的關(guān)鍵字構(gòu)造哈希函數(shù)。70A哈希函數(shù)的構(gòu)造方法6.隨機數(shù)法設(shè)定哈希函數(shù)為:此方法通常用哈希函數(shù)的構(gòu)造方法實際構(gòu)造哈希表時1.采用哪種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))2.總的原則是使產(chǎn)生沖突的可能性盡可能的小。3.如果哈希造表過程中產(chǎn)生沖突，應(yīng)當(dāng)如何處理這些沖突呢？71A哈希函數(shù)的構(gòu)造方法實際構(gòu)造哈希表時22A處理沖突的方法沖突：由關(guān)鍵字得到的哈希地址為j（0≤j≤n-1）的位置上已存有記錄處理沖突：為產(chǎn)生沖突的地址尋找下一個空的哈希地址1.開放定址法2.再哈希法3.鏈地址法處理沖突方法4.建立一個公共溢出區(qū)72A處理沖突的方法沖突：由關(guān)鍵字得到的哈希地址為j（0≤j≤n-處理沖突的方法1.開放定址法為產(chǎn)生沖突的地址H(key)求得一個地址序列：H0,H1,H2,…,Hs1≤s≤m-1其中：H0=H(key)Hi=(H(key)+di)MODm

i=1,2,…,s

m為哈希表表長73A處理沖突的方法1.開放定址法為產(chǎn)生沖突的地址H(key)處理沖突的方法1.線性探測再散列法2.二次探測再散列法3.隨機探測再散列法增量di的三種取法74A處理沖突的方法1.線性探測再散列法2.二次探測再散列法3處理沖突的方法1.開放定址法對增量di

的三種取法---①：1)線性探測再散列

di=ci

最簡單的情況c=1

即

di=1,2,3,……m-175A處理沖突的方法1.開放定址法對增量di的三種取法--處理沖突的方法例如:關(guān)鍵字集合{19,01,23,14,55,68,11,82,36}設(shè)定哈希函數(shù)H(key)=keyMOD11(表長=11)采用線性探測再散列法來構(gòu)造哈希表。19012345678910190101232323141455556868681182113611823611213625176A處理沖突的方法例如:關(guān)鍵字集合設(shè)定哈希函數(shù)H(key)處理沖突的方法1.開放定址法對增量di

有三種取法---②：2)平方（二次）探測再散列

di=12,-12,22,-22,…,77A處理沖突的方法1.開放定址法對增量di有三種取法--處理沖突的方法例如:關(guān)鍵字集合{19,01,23,14,55,68,11,82,36}19012345678910190101232323141455556868681182113611823636設(shè)定哈希函數(shù)H(key)=keyMOD11(表長=11)采用二次探測再散列法來構(gòu)造哈希表。11212141378A處理沖突的方法例如:關(guān)鍵字集合190處理沖突的方法1.開放定址法對增量di

有三種取法---③：3)隨機探測再散列

di是一組隨機數(shù)列或者

di=i×H2(key)(又稱雙散列函數(shù)探測)79A處理沖突的方法1.開放定址法對增量di有三種取法--處理沖突的方法即：產(chǎn)生的Hi均不相同，且所產(chǎn)生的m-1個Hi值能覆蓋哈希表中所有地址。則要求：注意：增量di

應(yīng)具有“完備性”※

隨機探測時的m

和di沒有公因子?！?/p>

平方探測時的表長

m必為形如

4j+3

的素數(shù)（如:7,11,19,23,…等）；80A處理沖突的方法即：產(chǎn)生的Hi均不相同，且所產(chǎn)生的注意：增處理沖突的方法H2(key)是另設(shè)定的一個哈希函數(shù)，它的函數(shù)值應(yīng)和m互為素數(shù)。若m為素數(shù)，則H2(key)可以是1至m-1之間的任意數(shù);若m為2的冪次，則H2(key)應(yīng)是1至m-1之間的任意奇數(shù)。81A處理沖突的方法H2(key)是另設(shè)定的一個哈希函數(shù)，它的處理沖突的方法例如，當(dāng)m=11時，可設(shè)H2(key)=(3key)MOD10+119012314556811823611112112282A處理沖突的方法例如，當(dāng)m=11時，190123145568處理沖突的方法2.再哈希法Hi=RHi(key)i=1,2,3,……，kRHi均是不同的哈希函數(shù)，在同義詞產(chǎn)生地址沖突時計算另一個哈希函數(shù)地址，直到?jīng)_突不再發(fā)生。缺點：增加了計算時間。83A處理沖突的方法2.再哈希法Hi=RHi(key)i=1處理沖突的方法3.鏈地址法所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中。定義指針型向量ChainChainHash[m];凡是哈希地址為i的記錄都插入到頭指針為ChainHash[i]的鏈表中。84A處理沖突的方法3.鏈地址法所有關(guān)鍵字為同義詞的記錄存儲在同處理沖突的方法例如:關(guān)鍵字集合{19,01,23,14,55,68,11,82,36}采用鏈地址法來構(gòu)造哈希表。哈希函數(shù)為H(key)=keyMOD71119826855140136231901231455681182360123456ASL=(6×1+2×2+3×1)/9=13/985A處理沖突的方法例如:關(guān)鍵字集合采用鏈地址法來構(gòu)造哈希表。處理沖突的方法4.建立一個公共溢出區(qū)哈希函數(shù)的值域[0,m-1]向量HashTable[0..m-1]為基本表，每個分量存放一個記錄向量OverTable[0..v]為溢出表對于關(guān)鍵字和基本表HashTable中關(guān)鍵字為同義詞的記錄，只要發(fā)生沖突，都填入溢出表。86A處理沖突的方法4.建立一個公共溢出區(qū)哈希函數(shù)的值域[0,m哈希表的查找算法查找過程和造表過程一致。假設(shè)采用開放定址處理沖突，則查找過程為:

1.對于給定值K,計算哈希地址i=H(K)2.若r[i]=NULL則查找不成功3.若

r[i].key=K則查找成功4.否則“求下一地址Hi”，直至r[Hi]=NULL(查找不成功)或r[Hi].key=K(查找成功)為止。87A哈希表的查找算法查找過程和造表過程一致。假設(shè)采用開放定址處理哈希表的查找算法inthashsize[]={997,...};typedefstruct{ElemType*elem;

intcount;//當(dāng)前數(shù)據(jù)元素個數(shù)

intsizeindex;//為當(dāng)前容量}HashTable;#defineSUCCESS1#defineUNSUCCESS0#defineDUPLICATE-1//---開放定址哈希表的存儲結(jié)構(gòu)---//88A哈希表的查找算法inthashsize[]={99哈希表的查找算法StatusSearchHash(HashTableH,KeyTypeK,