大學《數(shù)據(jù)結(jié)構(gòu)》第八章：查找-第四節(jié)-散列表查找

第四節(jié)散列表蟄找

一、散列表的概念

1、散列的概念

"散列”既是一種存儲方式，又是一種查找方法。這種查找方法稱為

散列查找。散列的基本思想是通過由散列函數(shù)決定的鍵值與散列地址

之間的對應(yīng)關(guān)系來實現(xiàn)存儲組織和查找運算。

2、實例分析

【例】有個線性表A=(31,62,74,36,49,77),散列函數(shù)為

H(key)=key%m即用元素的關(guān)鍵字key整除m,取其余數(shù)作為存儲

該元素的散列地址，m一般取小于或等于散列表長的最大素數(shù)，在這

里取m=ll,表長也為II,因此可得到每個元素的的散列地址：

H(31)=31%11=9;H(62)=62%ll=7;H(74)=74%ll=8;

H(36)=36%11=3;H(49)=49%11=5;H(77)=77%ll=0;

0123456789K)

散列表口7|88||36||49||62|74|31|7

若在上面散列表中插入元素88、7等會出現(xiàn)沖突。

采用散列技術(shù)時需要考慮的兩個主要問題是：①如何構(gòu)造(選擇)

“均勻的"散列函數(shù)？②用什么方法解決沖突？

二、散列函數(shù)的構(gòu)造方法

1、直接地址法

直接地址法是以關(guān)鍵字key本身或關(guān)鍵字加上某個常量C作為散列

地址的方法。對應(yīng)的散列函數(shù)H(key)為：H(key)=key+C

特點：方法計算簡單，并且沒有沖突。它適合于關(guān)鍵字的分布基本

連續(xù)的情況，若關(guān)鍵字分布不連續(xù)，空號較多，將會造成較大的空間

浪費。

2、數(shù)字分析法

數(shù)字分析法是假設(shè)有一組關(guān)鍵字，每個關(guān)鍵字由n位數(shù)字組成，數(shù)

字分析法是從中提取數(shù)字分布比較均勻的若干位作為散列地址。

3、除余數(shù)法

除余數(shù)法是一種最簡單也最常用的一種散列函數(shù)構(gòu)造方法。散列函

數(shù):H（k）=k%p

其中，p最好選取小于或等于表長m的最大素數(shù)。

4、平方取中法

平方取中法是取關(guān)鍵字平方的中間幾位作為散列地址的方法

5、折疊法

折疊法是首先把關(guān)鍵字分割成位數(shù)相同的幾段（最后一段的位數(shù)可少

一些），段的位數(shù)取決于散列地址的位數(shù)，由實際情況而定，然后將它

們的疊加和倍去最高進位）作為散列地址的方法。

【例】關(guān)鍵字k=98123658,散列地址為3位，則將關(guān)鍵字從左

到右每三位一段進行劃分，得到的三個段為981、236和58,疊加后

值為1275,取低3位275作為關(guān)鍵字98123658的元素的散列地址

三、處理沖突的方法

1、開放定址法

開放定址法的思想：使用某種方法在散列表中形成一個探查序列，

沿著此序列逐個單元進行查找，直到找到一個空閑的單元時將新結(jié)點

存入其中。

開放定址法又分為線性探插法、二次探查法和雙重散列法。

(1)線性探插法

探查序列可以由下述公式得到：di=(d+i)%m

其中：di表示第i次探查的地址，m表示散列表的長度。

【例】設(shè)散列函數(shù)為h(key)=key%ll;散列地址表空間為0~

10,對關(guān)鍵字序列｛27,13,55,32,18,49,24,38,43),利用

線性探測法解決沖突，構(gòu)造散列表。并計算查找成功時的平均查找長

度。

【解答】首先根據(jù)散列函數(shù)計算散列地址

h(27)=5;h(13)=2;h(55)=0;h(32)=10;

h(18)=7;h(49)=5;h(24)=2;h(38)=5;

h(43)=10;

散列表

下標01234567891a

554313242749183832

探查次數(shù)131212141

查找成功時的平均查找長度ASL=(lx5+2x2+3xl+4xl)/9?

1.78

(2)二次探直法

二次探查法的探查序列為：

do=H(K),

di=(do+12)%m

d2=(do-I2)%m,

ds=(do+22)%m,

d4=(do-22)%m,

(3)雙重散列法

雙重散列法是幾種方法中最好的方法，它的探查序列為：hi二(H

(key)+i*Hl(key))%m(0<i<m-l)

即探查序列為：d=H(key),(d+l*Hi(key))%m,

(d+2*Hi(key))%m,…等。

2、拉鏈法(鏈地址法)

用拉鏈法處理沖突的辦法是：把具有相同散列地址的關(guān)鍵字(同義

詞)值放在同一個單鏈表中，稱為同義詞鏈表。

【例】設(shè)散列函數(shù)為h(key)=key%ll;,對關(guān)鍵字序列｛27,

13,55,32,18,49,24,38,43),用拉鏈法構(gòu)造散列表,并計

算查找成功時的平均查找長度。

【解答】首先根據(jù)散列函數(shù)計算散列地址

h(27)=5;h(13)=2;h(55)=0;h(32)=10;

h(18)=7;h(49)=5;h(24)=2;h(38)=5;

h(43)=10;

四、散列表的查找

1、線性探查法解決沖突的直找和插入算法

采用開放定值法構(gòu)造散列表的類型定義：

#defineM997//M定義為表長，一般

M為一個素數(shù)

typedefstruct〃定義散列表結(jié)點類型

{KeyTypekey;

DataTypedata;

}NodeType;

typedefNodeTypeHashTable[M];〃散列表類型

(1)采用線性探直法的散列表有找算法

intHashSearchl(HashTableHT,KeyTypeK,intm)

{〃在長度為m的散列表HT中查找關(guān)鍵字值為K的元素位置

intd,temp;

d=K%m;〃計算散列地址

temp=d;//temp作為哨卡,

防止進入重復循環(huán)

while(HT[d].key!=-32768)〃當散列地址中的

key域不為空，則循環(huán)

{if(HT[d].key==K)

returnd;〃查找成功返回其下

標d

else

d=(d+l)%m;〃計算下一個地址

if(d==temp)

return-I;〃直找一周仍無空位

置，返回-1表示失敗

)

returnd;〃遇到空單元，直找失

敗

)

(2)在散列表上插入一個結(jié)點的算法

intHashlnsertl(HashTableHT,NodeTypes,intm)

〃在HT表上插入一個新結(jié)點s

intd;

d=HashSearchl(HT,s.key,m);〃查找插入

位置

if(d==-l)return-1;〃表滿，不能

插入

else

{if(HT[d].key==s.key)

return0;〃表中已有該結(jié)

占

/\\\*i

else〃找到一個開放的

地址

{HT[d]=s;〃插入新結(jié)點S

return1;〃插入成功

)

)

)

2、拉鏈法建立散列表上的查找和插入運算

采用拉鏈法的散列表類定義：

typedefstructnode{〃定義結(jié)點類型

KeyTypekey;

DataTypedata;

structnode*next;

}HTNode;

typedefHTNode*HT[M];〃定義散列表類型

(1)直找算法

HTNode*HashSearch2(HTT,KeyTypeK,intm)

{〃在長度為m的散列表T中查找關(guān)鍵字值為K的元素位置

HTNode*p=T[K%m];〃取K所在鏈表的頭指針

while(p!=NULL&&p->key!=K)

p=p->next;〃順鏈查找

returnp;〃查找成功p指向K結(jié)點的位置，不成功返回

NULL

(2)插入算法

intHashlnsert2(HTT,HTNode*s,intm)

{〃采用頭插法在T表上插入一個新結(jié)點

intd;

HTNode*p=HashSearch2(T,s->key,m);〃查找

表中有無待插結(jié)點

if(P!=NULL)return0;〃說明表

中已有該結(jié)點

else〃將*s插入

在相應(yīng)鏈表的表頭上

{d=s->key%m;

s->next=T[d];

T[d]=s;

return1;〃說明插入

成功

)

)

3、幾種處理沖突方法的散列表的平均查找長度比較

【例】設(shè)散列函數(shù)h(k)=k%13,散列表地址空間為0~12,對給

定的關(guān)鍵字序列(19,14,01,68,20,84,27,26,50,36)分

別以拉鏈法和線性探查法解決沖突構(gòu)造散列表，畫出所構(gòu)造的散列

表，指出在這兩個散列表中查找每一個關(guān)鍵字時進行比較的次數(shù)，并

分析在等概率情況下查找成功和不成功時的平均查找長度以及當結(jié)點

數(shù)為n=10時的順序查找和二分查找成功與不成功的情況。

【解答】首先根據(jù)散列函數(shù)計算散列地址

h(19)=6;h(14)=1;h(01)=1;h(68)=3;

h(20)=7;h(84)=6;h(27)=1;h(26)=0;

h(50)=11;h(36)=10;

(1)線性探直法解決沖突構(gòu)造散列表：

下標012345678910n12

26140168271920843650

探查次數(shù)1121411311

查找成功的平均查找長度=(lx7+2xl+3xl+4xl)/10=1.6

查找不成功的平均查找長度=(6+5+4+3+2+1+4+3+2+1

+3+2+1)/13-2.85

(2)拉鏈法解決沖突構(gòu)造散列表

1

查找成功的平均查找長度=(Ix7+2x2+3xl)/10=1.4

查找不成功的平均查找長度(不包括空指針的比較)

=(1+3+0+14-0+0+2+1+0+0+1+1+0)/13-0.7

當n=10時，順序查找成功的平均查找長度=(10+1)/2=5.5

順序查找不成功的平均查找長度=10+1=11

n=10的有序表的判定樹：

當n=10時，二分查找成功的平均查找長度=(Ixl+2x2+3x3

+4x3)/10~3

二分查找不成功的平均查找長度=(3x2+3xl+4x2

+3x1+4x23x1+4x2)/11~3.2

注意：結(jié)點