數(shù)據(jù)結(jié)構(gòu)第13講9章查找表44節(jié)

9.2靜態(tài)查找表9.3動(dòng)態(tài)查找樹表9.4哈希表9.1基本概念第九章查找表無序——有序（順序查找表——有序表）線性——非線性（靜態(tài)查找樹表）靜態(tài)——?jiǎng)討B(tài)（動(dòng)態(tài)查找樹表）二叉——多叉（B樹）內(nèi)存——外存（B樹）關(guān)鍵字為單位——以組成關(guān)鍵字的字符為單位（鍵樹）利用關(guān)鍵字之間的關(guān)系——利用關(guān)鍵字本身特性（哈希表）

一、哈希(Hash)表是什么？二、哈希函數(shù)的構(gòu)造方法三、處理沖突的方法

四、哈希表的查找9.3哈希表以上兩節(jié)討論的各種查找表的共同特點(diǎn)：一、哈希（Hash）表是什么？數(shù)據(jù)元素在表中的位置與關(guān)鍵字有關(guān)，但是這種關(guān)系是不確定的。準(zhǔn)考證號姓名各科成績總分政治語文外語數(shù)學(xué)物理化學(xué)生物...179321179322179333..145321...陳紅陸華張平...張平...847685...76...768488..64....746573...75...938779...88...876962...66...765763...67...877178...81...635455..73準(zhǔn)考證號姓名政治語文外語數(shù)學(xué)物理化學(xué)生物總分物理地址80108230824082508700關(guān)鍵字存放位置用這類方法表示的查找表，其平均查找長度都不為零。對不同的查找表，差別僅在于：關(guān)鍵字與給定值進(jìn)行比較的次序不同。查找的過程為：將給定值依次與關(guān)鍵字集合中各個(gè)關(guān)鍵字進(jìn)行比較，查找的效率取決于和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)。只有一個(gè)辦法：預(yù)先知道所查關(guān)鍵字在表中的物理存儲(chǔ)位置，對于頻繁使用的查找表，希望ASL=0即，要求：數(shù)據(jù)元素在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系。

哈希查找的基本思想：以查找表中的每個(gè)元素的關(guān)鍵字key為自變量，通過一種函數(shù)H(key)計(jì)算出函數(shù)值，把這個(gè)值

解釋為一塊連續(xù)存儲(chǔ)空間的地址單元，并將該元素直接存儲(chǔ)到這個(gè)地址單元中。這種函數(shù)H(key)就稱為哈希（Hash）函數(shù)。在哈希表上進(jìn)行查找時(shí)，首先根據(jù)給定的關(guān)鍵字key，用哈希函數(shù)H(key)計(jì)算出存儲(chǔ)地址，然后按此地址直接取出對應(yīng)的元素。如果以學(xué)號的后三位000~999作為每個(gè)元素的存儲(chǔ)地址,建立順序查找表。

例1：為某校每年招收的1000名新生建立一張查找表，其關(guān)鍵字為學(xué)號，其值的范圍為xx000~xx999(前兩位為年份)。則查找過程可以簡單進(jìn)行：取給定值（學(xué)號）的后三位，不需要經(jīng)過比較便可直接從順序表中找到待查關(guān)鍵字。此時(shí)的哈希函數(shù)H(key)=key{Zhao,Qian,

Sun,Li,Wu,Chen,Han,Ye,Deng}

例2：對于如下9個(gè)關(guān)鍵字設(shè)哈希函數(shù)f(key)=

(關(guān)鍵字的第一個(gè)字母的序號)/2ChenZhaoQianSunLiWuHanYeDeng問題:

若添加關(guān)鍵字Zhou,沖突，怎么辦？能否找到另一個(gè)哈希函數(shù)？1234567891011121314151617181920212223242526ABCDEFGHIJKLMNOPQRSTUVWXYZ1)哈希函數(shù)是一個(gè)映象，即：

將關(guān)鍵字的集合映射到某個(gè)地址集合上，

條件是這個(gè)映射的地址集合的大小不超出某個(gè)允許的范圍;從前面兩個(gè)例子可見，2)由于哈希函數(shù)是一個(gè)壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突”現(xiàn)象，即:key1key2

但：f(key1)=f(key2)。3)很難找到一個(gè)不產(chǎn)生沖突的哈希函數(shù)。一般情況下，只能選擇恰當(dāng)?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。因此，在構(gòu)造這種特殊的“查找表”時(shí)，除了需要選擇一個(gè)“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外;還需要找到一種“處理沖突”的方法。哈希表的定義:根據(jù)設(shè)定的哈希函數(shù)H(key)

和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個(gè)有限的、連續(xù)的地址空間

(區(qū)間)上，并以關(guān)鍵字在地址空間中的“象”作為相應(yīng)數(shù)據(jù)元素在表中的存儲(chǔ)位置，如此構(gòu)造所得的查找表稱之為“哈希表”。

一、哈希表是什么？二、哈希函數(shù)的構(gòu)造方法三、處理沖突的方法

四、哈希表的查找9.3哈希表二、構(gòu)造哈希函數(shù)的方法

對類型為數(shù)字的關(guān)鍵字有下列構(gòu)造方法:1.

直接定址法3.平方取中法5.除留余數(shù)法4.折疊法2.數(shù)字分析法哈希函數(shù)為關(guān)鍵字的線性函數(shù)

H(key)=key

或者

H(key)=akey+b1.

直接定址法

此法僅適合于：關(guān)鍵字分布基本連續(xù)的情況，且此時(shí)

地址集合的大小=關(guān)鍵字集合的大小地址010203…22…年份194919501951…1972…人數(shù)……120000…750000…H(key)=key+(-1948)地址010203…22…年份194919501951…1972…人數(shù)……120000…750000…此方法僅適合于：

能預(yù)先估計(jì)出全體關(guān)鍵字的每一位上各種

數(shù)字出現(xiàn)的頻度。2.

數(shù)字分析法假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關(guān)鍵字,并從中提取分布均勻的若干位或它們的組合作為地址。例：哈希表長100，取關(guān)鍵字中的2位數(shù)字作為地址。81346542813726328138091781372487814465378131370781432875

①②③④⑤⑥⑦⑧

……54639148537087存儲(chǔ)地址以關(guān)鍵字的平方值的中間幾位作為存儲(chǔ)地址.求“關(guān)鍵字的平方值”的目的是“擴(kuò)大差別”3.平方取中法此方法適合于:

關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象。關(guān)鍵字(字母)

關(guān)鍵字(數(shù)字)

（關(guān)鍵字）2

哈希表地址

A01000010000

010

I11001210000

210

J12001440000

440

I111611347921347

P120614310542

314

Q121614734741734

Q221624745651

745將關(guān)鍵字分割成若干部分，然后取它們的疊加之和為哈希地址。有兩種疊加處理的方法：移位疊加和間界疊加。4.折疊法此方法適合于:

關(guān)鍵字的數(shù)字位數(shù)特別多，所需地址位數(shù)較少。國際圖書號編碼0－442－20586－458644220+）0410088H(key)=008858640224+）046092H(key)=60925.除留余數(shù)法

設(shè)定哈希函數(shù)為:H(key)=keyMODp其中，

p≤m(表長)

例如：表長m＝11，取p=11,則關(guān)鍵字集合

{19,01,24,17,54,68,11,82,37}

被映射為：

8136102054

如何取p?m?例如：已知關(guān)鍵字集合

{12,39,18,24,33,21}

1672010

p

應(yīng)為不大于m的素?cái)?shù)或不含20以下的質(zhì)因子

（2，3，5，7，11，13，17，19）因?yàn)?，p=9中含質(zhì)因子3,

故所有含質(zhì)因子3的關(guān)鍵字均映射到“3的倍數(shù)”的地址上，從而增加了“沖突”的可能。如果取p=9:330663如果取p=11:

實(shí)際構(gòu)造哈希表時(shí)，采用何種哈希函數(shù)取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))，總的原則是：使映射分布盡可能均勻，使產(chǎn)生沖突的可能性降到盡可能地小。

一、哈希表是什么？二、哈希函數(shù)的構(gòu)造方法三、處理沖突的方法

四、哈希表的查找9.3哈希表三、處理沖突的方法

“處理沖突”的實(shí)際含義是：為產(chǎn)生沖突的地址尋找下一個(gè)空的哈希地址1.開放定址法2.鏈地址法為產(chǎn)生沖突的地址H(key)求下一個(gè)哈希地址，如果該地址還沖突，則再給出下一個(gè)地址，由此得到一個(gè)地址序列：

H0,H1,H2,…,Hs

1≤s≤m-1其中：H0=H(key)Hi=(H(key)+

di

)MODm

i=1,2,…,s1.開放定址法對增量di

有三種取法：1)線性探測再散列

di=ci2)平方探測再散列

di=12,-12,22,-22,…,3)隨機(jī)探測再散列di

是一組偽隨機(jī)數(shù)列

或者di=i×Hh(key)(又稱雙散列函數(shù)探測)Hi=(H(key)+

di

)MODm，i=1,2,…,s1)線性探測再散列

di=ci

最簡單的情況c=1例如:

關(guān)鍵字集合

{19,01,23,14,55,68,11,82,36}設(shè)定哈希函數(shù)H(key)=keyMOD11(表長=11)190123145568118236112136251二次聚集能否增加表長？怎樣查找？能否解決沖突？Hi=(H(key)+

di

)MODm，i=1,2,…,s設(shè)定哈希函數(shù)H(key)=keyMOD11(表長=11)190123145568118236112136251查找成功時(shí)的平均查找長度ASL成功=（1+1+2+1+3+6+2+5+1)/9＝22/9查找不成功時(shí)的平均查找長度:ASL不成功=（1+2+3+4+5+6+7+8+9)/11＝36/11

假定不成功時(shí)，產(chǎn)生每一個(gè)哈希地址的概率相等。2)平方探測再散列

di=12,-12,22,-22,…,190123146855118236例如:

關(guān)鍵字集合

{19,01,23,14,55,68,11,82,36}設(shè)定哈希函數(shù)H(key)=keyMOD11(表長=11)112121413Hi=(H(key)+

di

)MODm，i=1,2,…,s190123146855118236設(shè)定哈希函數(shù)H(key)=keyMOD11(表長=11)112121413Hi=(H(key)+

di

)MODm，i=1,2,…,s查找成功時(shí)的平均查找長度:ASL成功=（1+1+2+1+2+1+4+1+3)/9＝16/9能否解決沖突？2)平方探測再散列

di=12,-12,22,-22,…,01515例如:

關(guān)鍵字集合

{5,01,15,7,20}設(shè)定哈希函數(shù)H(key)=keyMOD

5(表長=5)Hi=(H(key)+

di

)MODm，i=1,2,…,s

012347表長應(yīng)是一個(gè)值為4k+3

的質(zhì)數(shù)，其中k是一個(gè)整數(shù)。如3,7,11,19,23,31,43,59,127,251,503,…能否增加表長？3)隨機(jī)探測再散列

di

是一組偽隨機(jī)數(shù)列

或者

di=i×Hh(key)(又稱雙散列函數(shù)探測)例如:

關(guān)鍵字集合

{19,01,23,14,55,68,11,82,36}設(shè)定哈希函數(shù)H(key)=keyMOD

11(表長=11)

設(shè)Hh(key)=(3key)MOD10+1190123145568118236211121213Hi=(H(key)+

di

)MODm，i=1,2,…,s三、處理沖突的方法

“處理沖突”的實(shí)際含義是：為產(chǎn)生沖突的地址尋找下一個(gè)空的哈希地址1.開放定址法2.鏈地址法將所有哈希地址相同的記錄都鏈接在同一鏈表中。

2.鏈地址法0123456111982685514360123ASL成功=(6×1+2×2+3)/9=13/9例如:關(guān)鍵字集合，{19,01,23,14,55,68,11,82,36}

哈希函數(shù)為H(key)=keyMOD7ASL不成功=(1×4+2+3)/7=9/7容量限制嗎？可以動(dòng)態(tài)擴(kuò)展嗎？查找成功時(shí)的平均查找長度:ASL成功=（1+1+2+1+2+1+4+1+3)/9＝16/9ASL成功=（1+1+2+1+3+6+2+5+1)/9＝22/9ASL成功=（2+1+1+1+2+1+2+1+3)/9＝14/9線性探測:平方探測:隨機(jī)探測:二叉平衡樹：ASL成功=（4+4+3+3+3+3+2+2+1)/9＝25/9關(guān)鍵字集合

{19,01,23,14,55,68,11,82,36}ASL成功=（1+1+1+1+1+1+2+2+3)/9＝13/9鏈地址法:例：在地址空間為0－16的散列區(qū)中，對以下關(guān)鍵字序列構(gòu)造兩個(gè)哈希表:{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec}

（1）用線性探測開放定址法處理沖突； （2）用鏈地址法處理沖突；并分別求這兩個(gè)哈希表在等概率情況下查找成功和查找不成功的平均查找長度。

設(shè)哈希函數(shù)為H(x)=i/2,其中i為關(guān)鍵字中第一個(gè)字母在字母表中的序號。121111245256Aug012345678910111213141516JanFebMarAprMayJuneJulySepOctNovDecASL成功＝31/12ASL不成功＝46/14Aug012345678910111213JanFebMarAprMayJuneJulySepOctNovDecASL成功＝18/12ASL不成功＝12/14

例題：

已知長度為12的表：(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)ASL=(1×1+2×2+3×3+4×3+5×2+6×1)/12=42/121.二叉排序樹2.有序表，排序后采用折半查找ASL=(1×1+2×2+3×4+4×5

)/12=37/123.平衡二叉排序樹ASL=(1×1+2×2+3×4+4×4+5×1

)/12=38/12

一、哈希表是什么？二、哈希函數(shù)的構(gòu)造方法三、處理沖突的方法

四、哈希表的查找，插入和刪除9.3哈希表查找過程和造表過程一致。假設(shè)采用開放定址處理沖突，則查找過程為:

四、哈希表的查找

對于給定值K,計(jì)算哈希地址Hi=H(K)若r[Hi].key=NULL

則查找不成功若

r[Hi].key=K

則查找成功否則“求下一地址Hi”，直至

r[Hi].key=NULL(查找不成功)

或

r[Hi].key=K(查找成功)為止。inthashsize[]={251,503,997,...};

//一個(gè)素?cái)?shù)序列typedefstruct{ElemType*elem;//數(shù)據(jù)元素存儲(chǔ)基址

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

intsizeindex;

//hashsize[sizeindex]為當(dāng)前容量}HashTable;#defineSUCCESS1#defineUNSUCCESS0#defineDUPLICATE-1//---開放定址哈希表的存儲(chǔ)結(jié)構(gòu)---StatusHashSearch(HashTableH,KeyTypeK,int&p,int&c)

{//p指示待查數(shù)據(jù)元素K在表中的位置，c為沖突計(jì)數(shù)

}//SearchHashp=Hash(K);

//求得哈希地址while(H.elem[p].key!=NULL&&

//該位置有記錄

!EQ(K,H.elem[p].key)）//且不等于K

collision(p,++c);

//處理沖突,求得下一探查地址pif(EQ(K,H.elem[p].key))returnSUCCESS;

//查找成功，返回待查數(shù)據(jù)元素位置pelsereturnUNSUCCESS;//查找不成功，

//返回插入位置p查找算法StatusInsertHash(HashTable&H,Elemtypee){c=0;if(HashSearch(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;

//查找不成功時(shí)，返回p為插入位置

}

elseRecreateHashTable(H);

//重建哈希表}//InsertHash插入算法//將待刪除位置用探測序列//的下一個(gè)關(guān)鍵字順序遞補(bǔ).StatusDeleteHash(HashTable&H,Elemtypee){}//DeleteHash