《數(shù)據(jù)結(jié)構(gòu)與算法分析》課件第7章

第7章索引結(jié)構(gòu)與散列技術(shù)7.1索引結(jié)構(gòu)7.2散列技術(shù)

7.1索引結(jié)構(gòu)

7.1.1線性索引

1．線性索引的定義

對于索引非順序結(jié)構(gòu)，由于數(shù)據(jù)表中的記錄是無序的，因此必須為每個記錄建立一個索引項。這種一個索引項對應(yīng)數(shù)據(jù)表中一個對象的索引結(jié)構(gòu)稱為稠密索引，如圖7-1所示。圖7-1學(xué)生數(shù)據(jù)表的稠密索引結(jié)構(gòu)例如，圖7-2就是滿足上述要求的存儲結(jié)構(gòu)，其中，表R只有18個記錄，被分成3塊，每塊中有6個記錄；第一塊中最大關(guān)鍵字22小于第二塊中最小關(guān)鍵字24；第二塊中最大關(guān)鍵字48小于第三塊中最小關(guān)鍵字49。圖7-2分塊有序表的索引存儲結(jié)構(gòu)

2.多級索引

若數(shù)據(jù)表中的記錄數(shù)n很大，索引表也很大，在內(nèi)存中放不下時，需要分批多次讀取外存才能把索引表搜索一遍。在這種情況下，可以建立索引的索引，稱為二級索引，如圖7-3所示。二級索引可以常駐內(nèi)存。在二級索引中，一個索引項對應(yīng)一個索引塊，用于登記該索引塊的最大關(guān)鍵字及該索引塊的存儲地址。在搜索時，先在二級索引中搜索，確定索引塊地址；再把該索引塊讀入內(nèi)存，確定數(shù)據(jù)結(jié)點的地址；最后讀入該數(shù)據(jù)結(jié)點。圖7-3二級索引結(jié)構(gòu)的示例7.1.2倒排表

在對含有大量記錄的數(shù)據(jù)表進行檢索時，最常用的是針對記錄的主關(guān)鍵字(關(guān)鍵字)建立索引，如圖7-1中的“學(xué)號”。因為每個學(xué)生的學(xué)號不會重復(fù)，所以用它作為關(guān)鍵字可以保證在檢索時能夠找到唯一的對象。

但是，在實際應(yīng)用中有時需要針對其他屬性進行檢索。例如，查詢?nèi)缦碌膶W(xué)生信息：

(1)列出所有籍貫為陜西的學(xué)生名單。

(2)列出所有的女生名單。圖7-4次索引示例

7.2散列技術(shù)

7.2.1散列表的概念

散列(Hashing)是一種重要的存儲方法，也是一種常見的查找方法。散列的基本思想是：以結(jié)點的關(guān)鍵字k為自變量，通過一個確定的函數(shù)關(guān)系f，計算出對應(yīng)的函數(shù)值，把這個函數(shù)值解釋為結(jié)點的存儲地址，將結(jié)點存入f(k)所指示的存儲位置上，在查找時再根據(jù)要查找的關(guān)鍵字，用同樣的函數(shù)計算地址，然后到相應(yīng)的單元里讀取。

例7-1

假設(shè)要建立一張全國30個地區(qū)各民族人口統(tǒng)計表，每個地區(qū)為一個記錄，記錄的各數(shù)據(jù)項為

顯然，可用一個一維數(shù)組R[30]來存放這張表，其中R[i]?是編號為i地區(qū)的人口情況，那么編號i便為記錄的關(guān)鍵字，由它唯一地確定記錄的存儲位置R[i]。

例7-2

已知一個含有70個結(jié)點的線性表，其關(guān)鍵字都由兩位十進制數(shù)字組成，則可將此線性表存儲在做如下說明的散列表中：

datatypeHT1[100]

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

H1(key)?=?key

(7-1)

例7-3

已知線性表的關(guān)鍵字集合為

S={and,begin,do,end,for,go,if,repeat,then,until,while}

則設(shè)散列表為

charHT2[26][8]

散列函數(shù)H2(key)的值取關(guān)鍵字key中第一個字母在字母表{a,b,

,z}中的序號(序號范圍是0至25)，即

H2(key)?=?key[0]

‘a(chǎn)’(7-2)

其中，key的類型是長度為8的字符數(shù)組。利用散列函數(shù)H2構(gòu)造的散列表如表7-1所示。綜上所述，散列法查找必須解決下面兩個主要問題：

(1)選擇一個計算簡單且沖突盡量少的“均勻”的散列函數(shù)。

(2)確定一個解決沖突的方法，即尋求一種方法存儲產(chǎn)生沖突的同義詞。7.2.2散列函數(shù)的構(gòu)造

1.數(shù)字選擇法

若事先已知關(guān)鍵字集合，且關(guān)鍵字的位數(shù)比散列表的地址位數(shù)多，則可選取數(shù)字分布比較均勻的若干位作為散列地址。

例如，有一組由8位數(shù)字組成的關(guān)鍵字及其相應(yīng)的散列地址表，如表7-2所示。

2.平方取中法

通常，要預(yù)先估計關(guān)鍵字的數(shù)字分布并不容易，要找出數(shù)字均勻分布的位數(shù)則更難。例如，下一組關(guān)鍵字(0100，0110，1010，1001，0111)就無法使用數(shù)字選擇法得到較均勻的散列函數(shù)。例如，上述一組關(guān)鍵字的平方結(jié)果是：

(0010000,0012100,1020100,1002001,0012321)

若表長為1000，則可取中間三位作為散列地址集：

(100,121,201,020,123)

3.折疊法

若關(guān)鍵字位數(shù)較多，也可將關(guān)鍵字分割成位數(shù)相同的幾段(最后一段的位數(shù)可以不同)，段的長度取決于散列表的地址位數(shù)，然后將各段的疊加和(舍去進位)作為散列地址。折疊法又分移位疊加和邊界疊加兩種。移位疊加是將各段的最低位對齊，然后相加；邊界疊加則是將兩個相鄰的段沿邊界來回折疊，然后對齊相加。例如關(guān)鍵字key?=?58242324169，散列表長度為1000，則將此關(guān)鍵字分成三位一段，兩種疊加結(jié)果如下：

4.除留余數(shù)法

選擇適當(dāng)?shù)恼麛?shù)p，用p去除關(guān)鍵字，取所得余數(shù)作為散列地址，即

H(key)?=?key%p

(7-3)

這是一種最簡單，也最常用的散列函數(shù)構(gòu)造方法，它可以對關(guān)鍵字直接取模，也可以結(jié)合折疊法、平方取中法等運算方法。

5.基數(shù)轉(zhuǎn)換法

把關(guān)鍵字看成是另一種進制的數(shù)后，再把它轉(zhuǎn)換成原來進制的數(shù)，取其中的若干位作為散列地址。一般取大于原來基數(shù)的數(shù)作為轉(zhuǎn)換的基數(shù)，并且兩個基數(shù)要互為素數(shù)。例如，給定一個十進制數(shù)的關(guān)鍵字為(210485)10，我們把它看成以13為基數(shù)的十三進制(210485)13，再把它轉(zhuǎn)換為十進制：

(210485)13=2

135+1

134+0

133+4

132+8

13+5

=(771932)10

假設(shè)散列表長度10000，則可取低四位1932作為散列地址。

6.隨機數(shù)法

選擇一個隨機函數(shù)，取關(guān)鍵字的隨機函數(shù)值為它的散列地址，即

H(key)=random(key)(7-4)

其中，random為隨機函數(shù)。

通常，當(dāng)關(guān)鍵字長度不相等時，采用隨機數(shù)法構(gòu)造散列地址較為恰當(dāng)。7.2.3解決沖突的幾種方法

1.開放地址法

用開放地址法解決沖突的方法是：當(dāng)發(fā)生沖突時，使用某種方法在散列表中形成一個探查序列，沿著此序列逐個單元進行查找，直至找到一個空的單元時將新結(jié)點放入為止，因此在造表開始時先將表置空。那么如何形成探查序列呢？

(1)線性探查法。設(shè)表長為m，關(guān)鍵字個數(shù)為n。線性探查法的基本思想是：將散列表看成是一個環(huán)形表，若發(fā)生沖突的單元地址為d，則依次探查d+1,d+2,…,m-1,0,1,…,d-1,直至找到一個空單元為止。開放地址公式為

di=(d+i)%m1≤i≤m-1(7-5)

其中，d=H(key)。

例7-4

已知一組關(guān)鍵字集(26,36,41,38,44,15,68,12,06,51,25)，用線性探查法解決沖突，試構(gòu)造這組關(guān)鍵字的散列表。

為了減少沖突，通常令裝填因子

<1，在此取

=0.75。因為n=11，所以，散列表長m=?

n/

?=15，即散列表為HT[15]。利用除留余數(shù)法構(gòu)造散列函數(shù)，選p=13，即散列函數(shù)為

H(key)%13

(2)二次探查法。二次探查法的探查序列依次是：12，

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

(7-6)

(3)隨機探查法。采用一個隨機數(shù)作為地址位移計算下一個單元地址，即求下一個開放地址的公式為

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

其中，d=H(key)；R1，R2，…，Rm-1是1，2，…，m-1的一個隨機序列。如何得到隨機序列，涉及隨機數(shù)的產(chǎn)生問題。在實際應(yīng)用中，常常用移位寄存器序列代替隨機數(shù)序列。

2.拉鏈法

拉鏈法解決沖突的方法是：將所有關(guān)鍵字為同義詞的結(jié)點鏈接到同一個單鏈表中。若選定的散列函數(shù)的值域為0～m-1，則可將散列表定義為一個由m個頭指針組成的指針數(shù)組HTP[m]，凡是散列地址為i的結(jié)點，均插入到以HTP[i]?為頭指針的單鏈表之中。

例7-5

已知一組關(guān)鍵字和選定的散列函數(shù)和例7-4相同，用拉鏈法解決沖突并構(gòu)造這組關(guān)鍵字的散列表。

因為散列函數(shù)H(key)=key%13的值域為0至12，所以散列表為HTP[13]。當(dāng)把H(key)=i的關(guān)鍵字插入第i個單鏈表中時，既可插在鏈表的頭上，也可以插在鏈表的尾上。若采用將新關(guān)鍵字插入鏈尾的方式，依次把給定的這組關(guān)鍵字插入表中，則得到的散列表如圖7-5所示。圖7-5拉鏈法構(gòu)造散列表與開放地址法相比，拉鏈法的優(yōu)點如下：

(1)拉鏈法不會產(chǎn)生堆積現(xiàn)象，平均查找長度較短。

(2)拉鏈法中各單鏈表的結(jié)點是動態(tài)申請的，它更適合于造表前無法確定表長的情況。

(3)在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點的操作易于實現(xiàn)，只要簡單地刪去鏈表上相應(yīng)的結(jié)點即可。7.2.4散列表的查找及分析

散列表的查找過程和建表過程相似。假設(shè)給定的值為k，根據(jù)建表時設(shè)定的散列函數(shù)H，計算出散列地址H(k)，

若表中該地址對應(yīng)的空間未被占用，則查找失?。环駝t將該地址中的結(jié)點與給定值k比較。若它們相等則查找成功；否則按建表時設(shè)定的處理沖突方法找下一個地址，如此反復(fù)下去，直到某個地址空間未被占用(查找失敗)或者關(guān)鍵字比較相等(查找成功)為止。例如，在例7-4和例7-5的散列表中，在等概率的情況下查找成功的平均查找長度分別為

線性探查法(參見表7-3)：

ASL=(1+5+1+2+2+1+1+1+1+2+3)/11=20/11

≈1.82(7-8)

拉鏈法(參見圖7-5)：

ASL=(1×7+2×2+3×1+4×1)/11=18/11≈1.64(7-9)

當(dāng)n=11時，順序查找和折半查找的平均查找長度分別為

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

(7-10)

ASLbn(11)=(1×1+2×2+3×4+4×4)/11=33/11=3

(7-11)下面仍以表7-3和圖7-5為例，分析在等概率的情況下，查找不成功時線性探查法和拉鏈法的平均查找長度。

在表7-3所示的線性探查法中，假設(shè)待查關(guān)鍵字k不在該表中，H(k)=0，則必須依次將HT[0]到HT[7]中的關(guān)鍵字和k或nil進行比較后，才發(fā)現(xiàn)HT[7]為空，即比較次數(shù)為8；若H(k)=1，則需比較7次才能確定查找不成功。類似地對H(k)=

2，3，…，12進行分析，可得不成功的平均查找長度為

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

=52/13=4(7-12)在圖7-5所示的拉鏈法中，若待查關(guān)鍵字k的散列地址為d=H(k)，且第d個鏈表上具有k個結(jié)點