《數(shù)據(jù)結(jié)構(gòu)與算法分析》課件第7章-索引結(jié)構(gòu)與散列技術(shù)

第七章

索引結(jié)構(gòu)與散列技術(shù)索引結(jié)構(gòu)及查找散列技術(shù)

應(yīng)用實(shí)例索引結(jié)構(gòu)和散列技術(shù)是在實(shí)際應(yīng)用中大量使用的存儲方法，在進(jìn)行數(shù)據(jù)查找運(yùn)算時(shí)會(huì)經(jīng)常用到這兩種存儲技術(shù)。索引結(jié)構(gòu)基本概念索引結(jié)構(gòu)包括兩部分：索引表和數(shù)據(jù)表。指明結(jié)點(diǎn)與其存儲位置之間的對應(yīng)關(guān)系的表就叫做索引表；數(shù)據(jù)表是存儲結(jié)點(diǎn)信息的，索引結(jié)構(gòu)中常用的數(shù)據(jù)表是線性表。索引表中的每一項(xiàng)稱作索引項(xiàng)，索引項(xiàng)的一般形式是：（關(guān)鍵字，地址）。其中關(guān)鍵字是能唯一標(biāo)識一個(gè)結(jié)點(diǎn)的那些數(shù)據(jù)項(xiàng)。如果數(shù)據(jù)表中的記錄按關(guān)鍵字順序排列，這時(shí)的索引結(jié)構(gòu)稱索引順序結(jié)構(gòu)。反之，若數(shù)據(jù)表中的數(shù)據(jù)未按關(guān)鍵字順序排列時(shí)，則稱索引非順序結(jié)構(gòu)。線性索引

對于索引非順序結(jié)構(gòu)，由于數(shù)據(jù)表中的記錄是無序的，則必須為每個(gè)記錄建立一個(gè)索引項(xiàng)，這種一個(gè)索引項(xiàng)對應(yīng)數(shù)據(jù)表中一個(gè)對象的索引結(jié)構(gòu)稱為稠密索引。兩種線性索引的比較對于索引順序結(jié)構(gòu)，由于數(shù)據(jù)表中的記錄按關(guān)鍵字有序，則可對一組記錄建立一個(gè)索引項(xiàng)，這種索引稱為稀疏索引。在稠密索引中，索引項(xiàng)中的地址將指出結(jié)點(diǎn)所在的存儲位置。而在稀疏索引中，索引項(xiàng)中的地址指出的則是一組結(jié)點(diǎn)的起始存儲位置。無論是稠密索引還是稀疏索引，都屬于線性索引索引結(jié)構(gòu)上的檢索查找索引表，若索引表上存在該記錄，則根據(jù)索引項(xiàng)的指示在數(shù)據(jù)表中讀取數(shù)據(jù)；否則說明數(shù)據(jù)表中不存在該記錄，也就不需要訪問數(shù)據(jù)表。由于索引表是有序的，則索引表的查找既可順序查找，又可使用折半查找。索引結(jié)構(gòu)查找方法——分塊查找分塊查找性能介于順序查找和二分查找之間的查找方法，又稱索引順序查找。構(gòu)造方法：(1)將數(shù)據(jù)表R[n]均分成b塊，前b-1塊中記錄數(shù)為S=

n/b

，第b塊的記錄數(shù)小于等于S；(2)前一塊中的最大關(guān)鍵字必須小于后一塊中的最小關(guān)鍵字，即要求表是“分塊有序”的；(3)抽取各塊中的最大關(guān)鍵字及其起始位置構(gòu)成一個(gè)索引表ID[i]，即ID[i](0≤i＜b)中存放著第i塊的最大關(guān)鍵字及該塊在表R中的起始位置。由于表是分塊有序的，所以索引表是遞增有序表分塊查找的存儲結(jié)構(gòu)示例下圖表R中只有18個(gè)記錄，被分成3塊，每塊中有6個(gè)記錄，第一塊中最大關(guān)鍵字22小于第二塊中最小關(guān)鍵字24，第二塊中最大關(guān)鍵字48小于第三塊中最小關(guān)鍵字49。分塊查找的存儲結(jié)構(gòu)示例(1)由于索引表有序，故可采用順序查找或折半查找索引表，以確定待查找的記錄在哪一塊；(2)在已確定的那一塊中進(jìn)行順序查找。typedefstruct{//索引表的結(jié)點(diǎn)類型

Keytypekey;

intaddr;}Idtable;IdtableID[b];//索引表說明：由于分塊查找是兩次查找過程，故分塊查找的算法即為這兩種算法的簡單合成，而整個(gè)算法的平均查找長度，即是兩次查找的平均查找長度之和。

多級索引二級索引中一個(gè)索引項(xiàng)對應(yīng)一個(gè)索引塊，登記該索引塊的最大關(guān)鍵字及該索引塊的存儲地址。在搜索時(shí)，先在二級索引中搜索，確定索引塊地址；再把該索引塊讀入內(nèi)存，確定數(shù)據(jù)結(jié)點(diǎn)的地址；最后讀入該數(shù)據(jù)結(jié)點(diǎn)。二級索引（建立索引的索引）結(jié)構(gòu)的示例：多級索引建立二級索引的索引，叫做三級索引。在三級索引情況下，訪問外存次數(shù)等于讀入索引次數(shù)再加上1次讀取數(shù)據(jù)。也可以建四級索引，五級索引，…。這種多級索引結(jié)構(gòu)形成一種m叉樹，也稱m路搜索樹。多級索引是一種靜態(tài)結(jié)構(gòu)，各級索引均為順序表，每次修改都要重組索引。因此，當(dāng)數(shù)據(jù)表在使用過程中記錄變動(dòng)較多時(shí)，應(yīng)采用動(dòng)態(tài)索引，例如二叉排序樹，它本身是層次結(jié)構(gòu)，無需建立多級索引，而且建立索引表的過程即排序過程。倒排表在實(shí)際應(yīng)用中有時(shí)需要針對其它非關(guān)鍵字的屬性進(jìn)行檢索。例如，查詢?nèi)缦碌膶W(xué)生信息：

1）列出所有籍貫為陜西的學(xué)生名單；2）列出所有的女生名單?？梢园岩恍┙?jīng)常查詢的屬性設(shè)定為次關(guān)鍵字，并針對每一個(gè)次關(guān)鍵字屬性，建立一個(gè)稱為次索引的索引表：列出該屬性的所有取值，并對每一個(gè)取值建立有序鏈表，并按存放地址遞增的順序或按關(guān)鍵字遞增的順序鏈接在一起。倒排表是一種次索引的實(shí)現(xiàn)。在倒排表中所有次關(guān)鍵字的鏈都保存在次索引中，僅通過搜索次索引就能找到所有具有相同屬性值的記錄。倒排表查找時(shí)：先通過搜索次索引以確定該記錄的主關(guān)鍵字，再通過搜索主索引確定記錄的存放地址。這樣在記錄的存放地址發(fā)生變化時(shí)，只需修改主索引，次索引可以不用改動(dòng)。倒排表散列表的查找問題

能否構(gòu)造一種查找方法與比較次數(shù)無關(guān)或關(guān)系較小?散列表查找的基礎(chǔ)是散列存儲結(jié)構(gòu)。散列表查找可達(dá)到這一要求：不用比較而直接計(jì)算出記錄所在地址，從而可直接進(jìn)行存取的方法。以結(jié)點(diǎn)的關(guān)鍵字k為自變量，通過一個(gè)確定的函數(shù)關(guān)系f，計(jì)算出對應(yīng)的函數(shù)值，把這個(gè)值解釋為結(jié)點(diǎn)的存儲地址，將結(jié)點(diǎn)存入f(k)所指的存儲位置上。該方法稱為散列法；又稱關(guān)鍵字——地址轉(zhuǎn)換法。用散列法存儲的線性表叫散列表（HushTable）或哈希表。函數(shù)f()稱為散列函數(shù)或哈希函數(shù)，f(k)的值則稱為散列地址或哈希地址。通常散列表的存儲空間是一個(gè)一維數(shù)組，散列地址是數(shù)組的下標(biāo)，在不致于混淆之處，我們將這個(gè)一維數(shù)組空間就簡稱為散列表。散列表的概念散列表實(shí)例【例1】假設(shè)要建立一張全國30個(gè)地區(qū)的各民族人口統(tǒng)計(jì)表，每個(gè)地區(qū)為一個(gè)記錄，記錄的各數(shù)據(jù)項(xiàng)為：

可用數(shù)組R[30]存放這張表，其中R[i]是編號為i的地區(qū)的人口情況。編號i便為記錄的關(guān)鍵字，由它惟一確定記錄的存儲位置R[i]，即散列函數(shù)

：H(key)=key【例2】已知一個(gè)含有70個(gè)結(jié)點(diǎn)的線性表，其關(guān)鍵字都由兩位十進(jìn)制數(shù)字組成，則可將此線性表存儲在如下說明的散列表中。

DatatypeHT1[100];

其中，HT1[i]存放關(guān)鍵字為i的結(jié)點(diǎn)，即散列函數(shù)為

H(key)=key【例3】已知線性表的關(guān)鍵字集合為：S={and,begin,do,end,for,go,if,repeat,then,until,while}

則可設(shè)散列表為：

charHT2[26][8];

散列函數(shù)H(key)的值，取為關(guān)鍵字key中第一個(gè)字母在字母表{a,b,…,z}中的序號（序號范圍是0至25），即

H(key)=key[0]-

a

其中，key的類型是長度為8的字符數(shù)組，散列表如表7.1所示。散列表實(shí)例討論散列表實(shí)例裝填因子

散列表空間大小m，填入表中結(jié)點(diǎn)數(shù)n，則稱

=n/m為散列表的裝填因子。實(shí)用時(shí)，常在區(qū)間[0.65,0.9]上取

的適當(dāng)值。散列函數(shù)是一個(gè)一對一的函數(shù)。散列函數(shù)的選取原則是：運(yùn)算應(yīng)盡可能簡單；函數(shù)的值域必須在表長的范圍之內(nèi)；盡可能使得關(guān)鍵字不同時(shí)，其散列函數(shù)值亦不相同。沖突

若某個(gè)散列函數(shù)H對于不相等的關(guān)鍵字key1和key2得到相同的散列地址（即H(key1)=H(key2)），則將該現(xiàn)象稱為沖突，而發(fā)生沖突的這兩個(gè)關(guān)鍵字則稱為該散列函數(shù)H的同義詞。散列法查找必須解決下面兩個(gè)主要問題：散列表實(shí)例(1)選擇計(jì)算簡單且沖突盡量少的“均勻”的散列函數(shù)；(2)確定解決沖突的方法，即尋求方法以存儲產(chǎn)生沖突的同義詞。散列函數(shù)的構(gòu)造-1數(shù)字選擇法若關(guān)鍵字的位數(shù)比散列表的地址位數(shù)多，則可選取數(shù)字分布比較均勻的若干位作為散列地址。（必須能預(yù)先估計(jì)到所有關(guān)鍵字的每一位上各種數(shù)字的分布情況）關(guān)鍵字散列地址1(0

999)散列地址2(0

99)871426534659987172232723048718274587422871071560155787127281228038715739453947散列函數(shù)的構(gòu)造-2隨機(jī)數(shù)法選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的散列地址，即H(key)=random(key)

其中：random為隨機(jī)函數(shù)。（當(dāng)關(guān)鍵字長度不等時(shí)采用此法構(gòu)造散列地址較恰當(dāng)）平方取中法先通過關(guān)鍵字的平方值擴(kuò)大差別，然后再取中間幾位或其組合作為散列地址?！纠?】

(0100,0110,1010,1001,0111)關(guān)鍵字的平方結(jié)果是：

(0010000,0012100,1020100,1002001,0012321)若表長為1000，則可取中間三位作為散列地址集：

(100,121,201,020,123)散列函數(shù)的構(gòu)造-3除留余數(shù)法選擇適當(dāng)?shù)恼麛?shù)p，用p去除關(guān)鍵字，取所得余數(shù)作為散列地址，即：H(key)=key%p

一般地選p為小于或等于散列表長度m的某個(gè)最大素?cái)?shù)較好?！纠?】

m=8,16,32,64,128,256,512,1024

p=7,13,31,61,127,251,503,1019散列函數(shù)的構(gòu)造-4折疊法若關(guān)鍵字位數(shù)較多，可將關(guān)鍵字分割成位數(shù)相同的幾段(最后一段位數(shù)可不同)，段長度取決于散列表的地址位數(shù)，將各段的疊加和(舍去進(jìn)位)作為散列地址。折疊法分移位疊加和邊界疊加。移位疊加是將各段的最低位對齊然后相加；邊界疊加則是兩個(gè)相鄰的段沿邊界來回折疊，然后對齊相加。【例6】

關(guān)鍵字key=58242324169，散列表長度為1000，則將關(guān)鍵字分成三位一段，兩種疊加結(jié)果如下：

移位疊加邊界疊加

582582

423324

241241

+69

+96

[1]315[1]243

H(key)=315H(key)=243散列函數(shù)的構(gòu)造-5基數(shù)轉(zhuǎn)換法把關(guān)鍵字看成是另一個(gè)進(jìn)制上的數(shù)后，再把它轉(zhuǎn)換成原來進(jìn)制上的數(shù)，取其中的若干位作為散列地址。一般取大于原來基數(shù)的數(shù)作為轉(zhuǎn)換的基數(shù)，并且兩個(gè)基數(shù)要互素?！纠?】給定一個(gè)十進(jìn)制數(shù)關(guān)鍵字為(210485)10，我們把它看成以13為基數(shù)的十三進(jìn)制(210485)13，再把它轉(zhuǎn)換為十進(jìn)制：(210485)13=2

135+1

134+0

133+4

132+8

13+5

=(771932)10假設(shè)散列表長度10000，則可取低四位1932作為散列地址。解決沖突的方法基本思想：當(dāng)發(fā)生沖突時(shí)，使用某種方法在散列表中形成一個(gè)探查序列，沿著此序列逐個(gè)單元進(jìn)行查找，直到找到一個(gè)空的單元時(shí)將新結(jié)點(diǎn)放入。開放地址法拉鏈法基本思想：將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)鏈接到同一個(gè)單鏈表中。若選定的散列函數(shù)的值域?yàn)?到m-1，則可將散列表定義為一個(gè)由m個(gè)頭指針組成的指針數(shù)組HTP[m]，凡是散列地址為i的結(jié)點(diǎn)，均插入到以HTP[i]為頭指針的單鏈表中。開放地址法當(dāng)發(fā)生沖突時(shí)，使用某種方法在散列表中形成一個(gè)探查序列，沿著此序列逐個(gè)單元進(jìn)行查找，直到找到一個(gè)空的單元時(shí)將新結(jié)點(diǎn)放入。待解決的問題是——探查序列探查序列包括：線性探查法二次探查法隨機(jī)探查法線性探查法基本思想將散列表看成是環(huán)形表，若發(fā)生沖突的單元地址為d，則依次探查d+1,d+2,…,m

1,0,1,…,d

1，直到找到一個(gè)空單元為止。開放地址公式為：

di=(d+i)%m(1≤i≤m

1)，其中d=H(key)【例8】已知關(guān)鍵字集(26,36,41,38,44,15,68,12,06,51,25)，用線性探查法解決沖突，試構(gòu)造這組關(guān)鍵字的散列表。分析：

取

=0.75，m=

n/

=15，散列表為HT[15]。

散列函數(shù)為：H(key)%13(15)散列地址01234567891011121314關(guān)鍵字26254115684406

36

381251比較次數(shù)1512211

1

123關(guān)鍵字1525

3668685126411244比較次數(shù)17

121221221堆積現(xiàn)象？二次探查法二次探查法的探查序列依次是：12,

12,22,

22,…等，也就是說，發(fā)生沖突時(shí)，將同義詞來回散列在第一個(gè)地址d=H(key)的兩端。由此可知，發(fā)生沖突時(shí)，求下一個(gè)開放地址的公式為：

d2i

1=(d+i2)%m

d2i=(d

i2)%m(1≤i≤(m

1)/2)隨機(jī)探查法采用一個(gè)隨機(jī)數(shù)作為地址位移計(jì)算下一個(gè)單元地址，即求下一個(gè)開放地址的公式為：

di=(d+Ri)%m(1≤i≤m

1)其中：d=H(key)，R1,R2，…,Rm-1是1,2,…，m

1的一個(gè)隨機(jī)排列。隨機(jī)探查法在實(shí)際應(yīng)用中，常常用移位寄存器序列代替隨機(jī)數(shù)序列。將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)鏈接到同一個(gè)單鏈表中。若選定的散列函數(shù)的值域?yàn)?到m-1，則可將散列表定義為一個(gè)由m個(gè)頭指針組成的指針數(shù)組HTP[m]，凡是散列地址為i的結(jié)點(diǎn)，均插入到以HTP[i]為頭指針的單鏈表中。拉鏈法【例9】已知關(guān)鍵字集(26,36,41,38,44,15,68,12,06,51,25)，用拉鏈法解決沖突，試構(gòu)造這組關(guān)鍵字的散列表?！纠?】已知關(guān)鍵字集(26,36,41,38,44,15,68,12,06,51,25)，用拉鏈法解決沖突，試構(gòu)造這組關(guān)鍵字的散列表。拉鏈法分析：

散列表為：HTP[13]散列函數(shù)為：H(key)%13拉鏈法構(gòu)造散列表的優(yōu)點(diǎn)拉鏈法不會(huì)產(chǎn)生堆積現(xiàn)象，因而平均查找長度較短；由于拉鏈法中各單鏈表的結(jié)點(diǎn)是動(dòng)態(tài)申請的，故它更適合于造表前無法確定表長的情況；在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點(diǎn)的操作易于實(shí)現(xiàn)，只要簡單地刪去鏈表上相應(yīng)的結(jié)點(diǎn)即可；當(dāng)裝填因子

較大時(shí)，拉鏈法所用的空間比開放地址法多，但是

越大，開放地址法所需的探查次數(shù)越多，所以，拉鏈法所增加的空間開銷是合算的。散列表的查找算法-1#definenil0

//nil為空結(jié)點(diǎn)標(biāo)記

#definem18

//假設(shè)表長m為18

typedefstruct{//散列表結(jié)點(diǎn)結(jié)構(gòu)

Keytypekey;

Datatypeother;

}

hashtable;

hashtable

HT(m);//散列表利用線性探查法解決沖突的查找和插入算法如下：散列表的查找算法-1intLINSRCH(HT,k)

//在散列表HT[m]中查找關(guān)鍵字為k的結(jié)點(diǎn)hashtableHT[];keytypek;

{intd,i=0;//i為沖突時(shí)的地址增量

d=H[k];//d為散列地址

while((i<m)&&(HT[d].key!=k)&&(HT[d].key!=nil))

{i++;d=(d+i)%m}

return(d);//若HT[d].key=k查找成功，否則失敗

}

//LINSRCHLINSERT(HT,s)

//將結(jié)點(diǎn)s插入散列表HT[m]中hashtables,HT[];

{intd;

d=LINSRCH(HT[],s.key)//查找s的插入位置

if(HT[d].key==nil)HT[d]=s;//d為開放地址，插入s

elseprintf(“ERROR”);//結(jié)點(diǎn)存在或表滿

}

//LINSERTtypedefstructnodetype{

Keytypekey;

Datatypeother;

structnodetype*next;

}

chainhash;

chainhash

*HTC[m];

chainhash*CHNSRCH(HTC,k)//在HTC[m]中查找關(guān)鍵字為k的結(jié)點(diǎn)

chainhash*HTC[];keytypek;

{

chainhash*p;

p=HTC[H(k)];//取k所在鏈表的頭指針

while(p&&(p→key!=k))p=p→next;//順序查找

returnp;//查找成功，返回結(jié)點(diǎn)指針，否則返回空指針

}

//CHNSRCH散列表的查找算法-2利用鏈地址法解決沖突的查找和插入算法如下：CINSERT(HTC,s)//將結(jié)點(diǎn)*s插入散列表HTC[m]中

chainhash*s,*HTC[];

{

intd;chsinhash*p;

p=CHNSRCH(HTC,s→key);//查看表中有無待插結(jié)點(diǎn)

if(p)

printf(“ERROR”);//表中已有該結(jié)點(diǎn)

else{d=H[s→key];s→next=HTC[d];HTC[d]=s;}//插入*s

}

//CINSERT散列表的查找算法-2查找成功的平均查找長度比較線性探查法(參見表7-3)：ASL=(1+5+1+2+2+1+1+1+1+2+3)/11=20/11≈1.82拉鏈法(參見圖7-5)：

ASL=(1

7+2

2+3

1+4

1)/11=18/11≈1.64而當(dāng)n=11時(shí)，順序查找和折半查找的平均查找長度為：

ASLsq(11)=(11+1)/2=6

ASLbn(11)=(1

1+2

2+3

4+4

4)/11=33/11=3散列表不成功查找分析順序查找和折半查找所需進(jìn)行的關(guān)鍵字比較次數(shù)僅取決于表長；而散列查找所需進(jìn)行的關(guān)鍵字比較次數(shù)和待查結(jié)點(diǎn)有關(guān)，在等概率情況下，散列表在查找不成功的平均查找長度定義為對關(guān)鍵字需要執(zhí)行的平均比較次數(shù)。

1）線性探查法：

ASKunsucc=(8+7+6+5+4+3+2+1+1+1+2+1+11)/13

=52/13=42）鏈地址法：

ASLunsucc=(1+0+2+1+0+1+1+0+0+0+1+0+4)/13

=11/13≈0.85同一個(gè)散列函數(shù)、不同解決沖突方法構(gòu)成的散列表，平均查找長度是不相同。散列表技術(shù)具有很好的平均性能。散列表的查找說明散列表的平均查找長度不是結(jié)點(diǎn)個(gè)數(shù)n或表長m的函數(shù)，而是裝填因子

的函數(shù)。

越大，說明表越滿，再插入新元素時(shí)發(fā)生沖突的可能性就越大，但

過小，空間的浪費(fèi)就會(huì)過多。要選擇一個(gè)合適的裝填因子，可以把平均查找長度限制在一定范圍內(nèi)。應(yīng)用實(shí)例——銀行賬戶的管理問題要求設(shè)計(jì)一個(gè)支持銀行帳戶管理的應(yīng)用軟件，軟件可添加或刪除顧客帳戶，并實(shí)現(xiàn)顧客查詢帳戶以及存款、取款等業(yè)務(wù)。數(shù)據(jù)結(jié)構(gòu)由于對插入或刪除的效率要求不高，但對查找和修改的效率卻有較高的要求，因此用散列表存儲賬戶信息。散列函數(shù)采用除留余數(shù)法。應(yīng)用實(shí)例——銀行賬戶的管理#defineM1000//散列表的大小#defineP997//散列函數(shù)中的質(zhì)數(shù)Ptypedefstruct{

charID[20];//身份證號

charname[20];//客戶姓名

doublebalance;//余額}Customer;typedefstruct{

Customerclient;

intstatus;//0-空1-非空-1刪除標(biāo)記

}HashTable;HashTableHTC[M];假設(shè)銀行開戶客戶不超過1000人，則散列表的具體定義如下：應(yīng)用實(shí)例——銀行賬戶的管理算法設(shè)計(jì)由于最多有103個(gè)身份證號，故可選擇3位隨機(jī)性較好的數(shù)字。排除地域、年份、月份重復(fù)比例較高的數(shù)字，日期的第二位（身份證的第14位）、轄區(qū)序號的第二位（身份證的第16位）和校驗(yàn)碼的隨機(jī)性較好，因此選取這3位組成一個(gè)十進(jìn)制數(shù)，其范圍是[0,103]。利用除留余數(shù)法將這個(gè)整數(shù)映射到散列表內(nèi)：

key=(ID[13]-'0')*10+(ID[15]-'0')

key=key*10+(ID[17]=='x')?10:(ID[17]-'0')應(yīng)用實(shí)例——銀行賬戶的管理(4)CheckBalance函數(shù)：根據(jù)身份證號查詢余額

voidCheckBalance(char*id)(5)DepositDraw函數(shù):根據(jù)身份證號進(jìn)行存、取款操作

voidDepositDraw(char*id)(6)DeleAccount函數(shù)：銷戶voidDeleAccount(char*id);程序的主要功能由以下函數(shù)實(shí)現(xiàn)：(1)Hash函數(shù)：除留余數(shù)函數(shù)

intHash(intkey)(2)Insert函數(shù)：

結(jié)點(diǎn)插入散列表intInsert(intkey)(3)OpenA