《軟件技術(shù)基礎(chǔ)》課件第8章

8.1線性表查找8.2散列技術(shù)習(xí)題8第8章查找8.1.1順序查找

順序查找(SequentialSearch)是一種最簡(jiǎn)單的查找方法，即從表頭開始查找，直到找到為止。這種方法適用于較小的順序表或鏈表。順序查找的過(guò)程為：從表的一端開始，逐個(gè)將記錄的關(guān)鍵字與給定值進(jìn)行比較，若某個(gè)記錄的關(guān)鍵字與給定值相等，則查找成功；反之，若直至最后一個(gè)記錄，都沒(méi)有找到與給定值相等的關(guān)鍵字，則表明表中沒(méi)有所查的記錄，查找失敗。

算法8.1是以一維數(shù)組作為存儲(chǔ)結(jié)構(gòu)的順序查找算法，該算法可以很容易地修改為基于鏈表結(jié)構(gòu)的順序查找算法。

算法8.1是以一維數(shù)組作為存儲(chǔ)結(jié)構(gòu)的順序查找算法，該算法可以很容易地修改為基于鏈表結(jié)構(gòu)的順序查找算法。8.1線性表查找給定關(guān)鍵字序列(21，9，33，64，15，59，75，47)，現(xiàn)要查找的關(guān)鍵字為9，根據(jù)算法8.1，經(jīng)過(guò)7次比較得到的查找結(jié)果為：要查的關(guān)鍵字在表中的下標(biāo)為2。如果待查找的關(guān)鍵字為3，那么查找失敗，返回i=0。

在算法8.1中，監(jiān)視哨R[0]的作用是為了在for循環(huán)中省去下標(biāo)i的判斷條件i>0。這一改進(jìn)可以減少約一半的比較次數(shù)，從而節(jié)省時(shí)間。同理，監(jiān)視哨也可設(shè)在數(shù)組高端。

下面分析順序查找的性能。查找算法的平均查找長(zhǎng)度定義為：查找給定值所需進(jìn)行的關(guān)鍵字比較次數(shù)的期望值。

在等概率情況下，順序查找成功時(shí)的平均查找長(zhǎng)度為

(8-1)

若待查找的關(guān)鍵字k不在表中，則必須進(jìn)行n+1次比較才能確定查找失敗。順序查找的平均查找長(zhǎng)度應(yīng)當(dāng)綜合考慮查找成功時(shí)的平均查找長(zhǎng)度和查找失敗時(shí)的平均查找長(zhǎng)度。

通常情況下，表中各記錄被查找的可能性并不相等，例如漢字中常用字、詞的使用頻率就比較高，而一些偏僻字則使用極少。那么，為了減少平均查找長(zhǎng)度，在事先知道查找概率或它們的分布情況下，可將表中記錄按查找概率的大小順序存放。若無(wú)法確定各記錄的查找概率，則可對(duì)算法做如下修改：每當(dāng)查找成功，就將找到的記錄位置提前一位或若干位。這樣，查找概率大的記錄在查找過(guò)程中能不斷向前移，在以后的查找過(guò)程中就能減少比較次數(shù)。常用的漢字輸入法就是基于這個(gè)原理。

順序查找的優(yōu)點(diǎn)非常明顯，其算法簡(jiǎn)單，并且對(duì)線性表的存儲(chǔ)結(jié)構(gòu)和關(guān)鍵字的有序性無(wú)任何要求，但是當(dāng)n很大時(shí)，這種方法的查找效率較低。因此，順序查找只適用于長(zhǎng)度較小的線性表。8.1.2折半查找

折半查找(BinarySearch)又稱為二分查找，它是一種效率較高的查找方法。查找的對(duì)象必須是順序存儲(chǔ)結(jié)構(gòu)的有序表，即表中記錄按關(guān)鍵字有序。假設(shè)有序的記錄序列為{R1,R2,…,Rn}，其關(guān)鍵字值分別是k1,k2,

…,kn。利用折半查找算法查找關(guān)鍵字值k的過(guò)程是：每次將k先與表的中間記錄相比較，如果未找到，則判斷k是在表的左半部還是右半部，以縮小查找范圍；逐步縮小查找區(qū)間，直至查找成功或查找區(qū)間不存在時(shí)結(jié)束。

折半查找的過(guò)程如算法8.2所示。

在算法8.2中，low和high分別表示當(dāng)前查找區(qū)間的下界和上界，當(dāng)前查找區(qū)間的中值設(shè)為mid=?

(low+high)/2

。如果關(guān)鍵字k與中值不相等，則將查找區(qū)間縮小為上一次的一半。那么在第i次比較時(shí)，最多只剩下

n/2i

個(gè)記錄，故折半查找又稱為二分查找。

下面舉例說(shuō)明。已知有序表中關(guān)鍵字序列為：9,15,21,33,47,59,64,77,84,91，現(xiàn)要查找關(guān)鍵字為15及80的記錄，其查找過(guò)程如下：

再取mid=

(low+high)/2

=9，由于k=80<R[9].key，取high=mid

1=8，由于low>high，因此查找區(qū)間不存在，查找失敗。

折半查找的性能分析可通過(guò)折半查找判定樹來(lái)描述。

折半查找判定樹定義如下：利用當(dāng)前查找區(qū)間的中值記錄作為根，將有序表的左子表和右子表的記錄分別作為根的左子樹和右子樹，由此得到的二叉樹稱為折半查找判定樹。上例有序表的折半查找判定樹如圖8.1所示。樹中的圓形結(jié)點(diǎn)稱為內(nèi)部結(jié)點(diǎn)，結(jié)點(diǎn)內(nèi)的數(shù)字表示該結(jié)點(diǎn)在有序表中的位置。所有內(nèi)部結(jié)點(diǎn)的空指針域相當(dāng)于指向一個(gè)方形結(jié)點(diǎn)，稱為外部結(jié)點(diǎn)，可用于表示兩個(gè)內(nèi)部結(jié)點(diǎn)之間的有效關(guān)鍵字區(qū)間。

圖8.1具有10個(gè)結(jié)點(diǎn)的折半查找判定樹那么，折半查找的平均查找長(zhǎng)度是多少呢？為討論方便，不妨設(shè)結(jié)點(diǎn)總數(shù)n=2h

1，則判定樹是滿二叉樹，其深度為h=lb(n+1)。在等概率條件下，折半查找的平均查找長(zhǎng)度為

(8-2)

當(dāng)n較大時(shí)，可以用近似公式：

(8-3)

對(duì)于有序表，折半查找的效率顯然高于順序查找。但是，為得到有序表，必須進(jìn)行排序，而排序本身是一種很費(fèi)時(shí)的運(yùn)算，其時(shí)間復(fù)雜度至少是O(lb?n)。因此，折半查找只適用于順序存儲(chǔ)結(jié)構(gòu)，且表不易變動(dòng)而又經(jīng)常查找的情況。對(duì)那些查找少、經(jīng)常進(jìn)行插入或刪除操作的線性表，宜采用鏈表作為存儲(chǔ)結(jié)構(gòu)。

8.1.3分塊查找

分塊查找(BlockingSearch)又稱索引順序查找，是順序查找的一種改進(jìn)方法。分塊查找的對(duì)象是分塊有序表及其索引表，如圖8.2所示。其中線性表含有18個(gè)記錄，被分為三個(gè)子表(R1,R2,

…,R6)、(R7,R8,…,R12)、(R13,R14,…,R18)。對(duì)每個(gè)子表(或稱塊)建立一個(gè)索引項(xiàng)，其中包含兩項(xiàng)內(nèi)容：關(guān)鍵字值項(xiàng)(為該子表內(nèi)的最大關(guān)鍵字值)和指針項(xiàng)(指示該子表的第一個(gè)記錄在表中的位置)。

“分塊有序”是指對(duì)任意兩個(gè)相鄰子表，后面子表中所有記錄的關(guān)鍵字值均大于前一個(gè)子表中的最大關(guān)鍵字值。由此得到的索引表是按關(guān)鍵字值有序的，而子表內(nèi)的關(guān)鍵字不一定有序。

圖8.2分塊有序表及其索引表

因此，分塊查找需分兩步進(jìn)行：首先可用順序查找或折半查找索引表，確定待查記錄所在的塊，然后在塊中順序查找所需的記錄。例如在圖8.2所示的存儲(chǔ)結(jié)構(gòu)中，查找關(guān)鍵字值為k=44的結(jié)點(diǎn)，由于索引表小，因此可用順序查找法查找索引表，直至找到第一個(gè)關(guān)鍵字大于等于k的結(jié)點(diǎn)，即關(guān)鍵字為48的結(jié)點(diǎn)。由于22<k<48，關(guān)鍵字為44的結(jié)點(diǎn)若存在的話，則必定在第二個(gè)子表中，因此根據(jù)同一索引項(xiàng)中的指針指示，從第二個(gè)子表中的第一個(gè)記錄，也即分塊有序表中的第7個(gè)記錄起進(jìn)行順序查找，直到R[9].key=k為止。若此子表中沒(méi)有關(guān)鍵字值等于k的記錄，即在第7～12個(gè)記錄這段區(qū)間沒(méi)有關(guān)鍵字和k相等，則查找不成功。

當(dāng)索引表較長(zhǎng)時(shí)，亦可用折半查找來(lái)確定關(guān)鍵字所在的塊。塊中記錄可以是任意排列的，因此在塊中只能進(jìn)行順序查找。由此，分塊查找的算法即為這兩種算法的簡(jiǎn)單合成。

分塊查找的平均查找長(zhǎng)度為

ASLbs?=?Lb?+?Ls

(8-4)

其中：Lb為查找索引表確定所在塊的平均查找長(zhǎng)度；Ls為在塊中查找元素的平均查找長(zhǎng)度。

一般情況下，為進(jìn)行分塊查找，可將長(zhǎng)度為n的表均勻地分成b塊，每塊含有s個(gè)記錄，即b=n/s；又假定表中的每個(gè)記錄的查找概率相等，則每塊查找的概率為1/b，塊中每個(gè)記錄的查找概率為1/s。

若用順序查找法確定所在塊，則分塊查找的平均查找長(zhǎng)度為

(8-5)

若用折半查找確定所在塊，則分塊查找的平均查找長(zhǎng)度為

(8-6)

在實(shí)際應(yīng)用中，線性表不一定要均勻分塊，而應(yīng)該根據(jù)表的實(shí)際特征進(jìn)行分塊。例如學(xué)校的學(xué)生登記表，不同院系、班級(jí)的人數(shù)可能不一樣。另外，所有子塊的結(jié)點(diǎn)可以存放在一個(gè)向量中，也可單獨(dú)存放，例如每一塊用不同的向量或單鏈表來(lái)存放。

散列(Hash)是一種重要的存儲(chǔ)方法。與前面討論的各種結(jié)構(gòu)相比，散列結(jié)構(gòu)最大的特點(diǎn)是：記錄在表中的存儲(chǔ)位置與其關(guān)鍵字是相關(guān)的。換句話說(shuō)，我們可以根據(jù)關(guān)鍵字直接計(jì)算得到該記錄的存儲(chǔ)地址。因此，在散列結(jié)構(gòu)中進(jìn)行查找可以省去大量的關(guān)鍵字比較操作，從而提高查找效率。

8.2散列技術(shù)8.2.1散列表的概念

散列表的理想情況是：不經(jīng)過(guò)任何比較而一次就能直接存取所查的記錄。其基本思想是：在記錄的關(guān)鍵字k和結(jié)點(diǎn)的存儲(chǔ)地址d之間，建立一個(gè)確定的函數(shù)映射關(guān)系H，即d=H(k)，那么查找時(shí)利用該函數(shù)H，就可以根據(jù)要查找的關(guān)鍵字直接計(jì)算記錄所在的單元。因此，散列法又稱為關(guān)鍵字—地址轉(zhuǎn)換法。這個(gè)函數(shù)H就稱為散列函數(shù)，H(k)則稱為散列地址。用散列法存儲(chǔ)的線性表叫散列表或哈希表。

下面舉一個(gè)簡(jiǎn)單的例子。假設(shè)要建立一張30個(gè)地區(qū)民族人口統(tǒng)計(jì)表，每個(gè)地區(qū)為一個(gè)記錄，記錄的各數(shù)據(jù)項(xiàng)為：

如果以一維數(shù)組R[30]作為散列表的存儲(chǔ)空間，那么散列地址就是數(shù)組的下標(biāo)。假設(shè)以地區(qū)編號(hào)作為該記錄的關(guān)鍵字，i＝0～29，則很容易得到散列函數(shù)為H(i)=i，由散列函數(shù)值可以唯一地確定記錄R[i]，從而查找到編號(hào)為i的地區(qū)的人口情況。例如，要查看編號(hào)3的地區(qū)記錄，利用散列函數(shù)可知，其數(shù)組單元的下標(biāo)為3。

在很多情況下，散列函數(shù)并不容易得到。上例中，如果選取總?cè)丝?、漢族人口等其他數(shù)據(jù)項(xiàng)作為關(guān)鍵字，或者將地區(qū)編號(hào)改為該地區(qū)的漢語(yǔ)拼音，則散列函數(shù)就會(huì)比較復(fù)雜。在8.2.2節(jié)中將介紹常用散列函數(shù)的構(gòu)造方法。

從上面的例子可知：

(1)對(duì)任意數(shù)據(jù)類型的關(guān)鍵字，總可以靈活地設(shè)計(jì)散列函數(shù)將得到的散列地址控制在表長(zhǎng)允許的范圍內(nèi)。設(shè)計(jì)散列函數(shù)時(shí)，應(yīng)使其盡可能簡(jiǎn)單。

(2)若散列函數(shù)是一對(duì)一映射函數(shù)，則在查找時(shí)只需根據(jù)給定關(guān)鍵字計(jì)算散列地址，即可得到待查記錄的存儲(chǔ)位置，查找過(guò)程無(wú)須進(jìn)行關(guān)鍵字比較。若該地址非空，則查找成功；否則該記錄不存在。

(3)大多數(shù)情況下，散列函數(shù)并非一對(duì)一映射函數(shù)，即對(duì)于不相等的關(guān)鍵字k1和k2，有可能計(jì)算得到相同的散列地址。該現(xiàn)象稱為沖突(Collision)，發(fā)生沖突的這兩個(gè)關(guān)鍵字稱為該散列函數(shù)的同義詞(Synonym)。例如，對(duì)于關(guān)鍵字序列{at,as,be,can,cat,for,face,force}，如果取散列函數(shù)為H(key)=key[0]

'a'，其中key[0]存放關(guān)鍵字的第一個(gè)字母，可見關(guān)鍵字at、as互為同義詞，它們的散列地址都是0，即產(chǎn)生沖突。

對(duì)于上例我們應(yīng)重新構(gòu)造一個(gè)散列函數(shù)。但在實(shí)際應(yīng)用中，關(guān)鍵字的取值集合遠(yuǎn)遠(yuǎn)大于表空間的地址集，因此理想化的、不產(chǎn)生沖突的散列函數(shù)極少存在。例如，我們要為1000個(gè)人設(shè)置個(gè)人標(biāo)識(shí)符，要求標(biāo)識(shí)符的長(zhǎng)度為8、以字母打頭(區(qū)分大小寫)的字母數(shù)字串，因此關(guān)鍵字(即標(biāo)識(shí)符)取值的集合大小為

可見，設(shè)表長(zhǎng)為1000即可滿足需要。但是要將1.09388

1012個(gè)可能的標(biāo)識(shí)符映射到這1000個(gè)地址上，難免產(chǎn)生沖突。因此，通常的散列函數(shù)是一個(gè)多對(duì)一的映射函數(shù)，散列法查找時(shí)的沖突現(xiàn)象也是不可避免的。一旦發(fā)生沖突，就必須采取相應(yīng)措施及時(shí)予以解決。

發(fā)生沖突的頻繁程度除了與散列函數(shù)H相關(guān)外，還與表的填滿程度相關(guān)。為了減少?zèng)_突，散列表的空間一般大于所有記錄所需的容量，此時(shí)雖然浪費(fèi)了一定空間，但換取的是查找效率。設(shè)散列表空間大小為m，表中存儲(chǔ)的記錄個(gè)數(shù)是n，則稱

=n/m為散列表的裝填因子(LoadFactor)。

的取值區(qū)間一般設(shè)為[0.65,0.9]。

下面主要討論散列法查找時(shí)的兩個(gè)主要問(wèn)題：

(1)設(shè)計(jì)一個(gè)計(jì)算簡(jiǎn)單且沖突盡量少的“均勻”的散列函數(shù)；

(2)尋求解決沖突的方法，即如何存儲(chǔ)產(chǎn)生沖突的同義詞。

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

如何設(shè)計(jì)一個(gè)計(jì)算簡(jiǎn)單且沖突盡量少的“均勻”的散列函數(shù)呢？

前面已經(jīng)介紹，散列函數(shù)的運(yùn)算應(yīng)盡可能簡(jiǎn)單，且任何關(guān)鍵字的散列函數(shù)值都出現(xiàn)在表長(zhǎng)允許的范圍內(nèi)。這里要重點(diǎn)理解“均勻”的概念。所謂均勻，是指任意給定一個(gè)關(guān)鍵字，散列函數(shù)將其映射到任何一個(gè)存儲(chǔ)地址的概率是相等的。換句話說(shuō)，經(jīng)散列函數(shù)映射得到的存儲(chǔ)地址越隨機(jī)越好。這樣，一組不同的關(guān)鍵字就能夠均勻地存儲(chǔ)到表中，從而減少相互之間的沖突。為此有下面常用的構(gòu)造散列函數(shù)的方法。

1．直接定址法

直接選取某個(gè)關(guān)鍵字或關(guān)鍵字的某個(gè)函數(shù)值作為散列地址，如下所示：

其中a和b為常數(shù)。當(dāng)a=1,b=0時(shí)，散列函數(shù)值為關(guān)鍵字本身。

表8.1中給出了直接定址法的示例。取學(xué)號(hào)作為關(guān)鍵字k，散列函數(shù)H(k)=k+(

206000)。

若要查找學(xué)號(hào)是206056的記錄，只需查第206056-206000=56項(xiàng)即可。直接定址法比較簡(jiǎn)單，而且所得到的地址集合與關(guān)鍵字集合的大小相同，所以不會(huì)發(fā)生沖突，但實(shí)際場(chǎng)合中適用的情況較少。

2．?dāng)?shù)字選擇法

若關(guān)鍵字為數(shù)字且已知散列表中可能出現(xiàn)的關(guān)鍵字集合，則可選取其中數(shù)字分布比較均勻的若干位作為散列地址。

例如，有一組由7位數(shù)字組成的關(guān)鍵字，如表8.2第一列所示。

分析這8個(gè)關(guān)鍵字就會(huì)發(fā)現(xiàn)：第①②③位都是020，顯然不均勻；第④⑤⑥⑦位的取值范圍較大，有一定的均勻性。因此，可根據(jù)散列表的長(zhǎng)度取其中幾位或它們的組合作為散列地址。若表長(zhǎng)為100(即地址為0～99)，則可取④⑤⑥⑦中的任意兩位數(shù)字作為散列地址；若表長(zhǎng)為1000(即地址為0～999)，則可?、堍茛蔻咧械娜我馊蛔鳛樯⒘械刂返?。為了增加隨機(jī)性，還可以取散列地址中的若干位分成多組，取其和并舍去進(jìn)位作為散列地址。表8.2中給出了一種選取方式，散列函數(shù)的實(shí)現(xiàn)如下：

3．平方取中法

通常情況下，關(guān)鍵字的數(shù)字分布未知或很難準(zhǔn)確估計(jì)，因此要找到若干位均勻分布的數(shù)字并不容易。平方取中法的思路是通過(guò)關(guān)鍵字的平方來(lái)擴(kuò)大差別。因?yàn)橐粋€(gè)數(shù)的平方值與關(guān)鍵字的每一位都相關(guān)，由此使得產(chǎn)生的散列地址隨機(jī)性增加，從而較為均勻。然后，可以用數(shù)字選擇法來(lái)選取散列地址。

例如，給定一組關(guān)鍵字如表8.3所示，可見無(wú)法直接選取三位數(shù)字作為散列地址。取平方后，關(guān)鍵字的差別擴(kuò)大，當(dāng)表長(zhǎng)為1000時(shí)，可取其中間三位作為散列地址。相應(yīng)的散列函數(shù)如下：

4．折疊法

折疊法是指將關(guān)鍵字分割成位數(shù)相同的幾段(最后一段的位數(shù)可以不同)，將各段的疊加和(舍去進(jìn)位)作為散列地址。其中段的長(zhǎng)度取決于散列表的地址位數(shù)。當(dāng)關(guān)鍵字位數(shù)較多且數(shù)字分布較均勻時(shí)，可采用此方法。

折疊法又分移位疊加和邊界疊加兩種。移位疊加是指將各段的最低位對(duì)齊，然后相加；邊界疊加是指將相鄰的段沿邊界來(lái)回折疊，然后對(duì)齊相加。例如關(guān)鍵字key=35726，散列表長(zhǎng)度為100，可將關(guān)鍵字每?jī)晌环殖梢欢?，兩種疊加結(jié)果如下：

5．除留余數(shù)法

在除留余數(shù)法中，假設(shè)散列表長(zhǎng)為m，選取適當(dāng)?shù)恼麛?shù)p去除關(guān)鍵字，將所得余數(shù)作為散列地址，即

H(key)=key％p(p≤m)

這是一種最簡(jiǎn)單、最常用的散列函數(shù)構(gòu)造方法。它可以直接對(duì)關(guān)鍵字取模，也可以對(duì)折疊、平方取中等運(yùn)算的結(jié)果進(jìn)行操作。該方法的關(guān)鍵是取適當(dāng)?shù)膒。

舉幾個(gè)簡(jiǎn)單的例子。例如取p為偶數(shù)，則它奇數(shù)的關(guān)鍵字經(jīng)轉(zhuǎn)換后的地址仍為奇數(shù)，而偶數(shù)的關(guān)鍵字也只能轉(zhuǎn)換到偶數(shù)地址，這當(dāng)然不好。又如，取p為關(guān)鍵字的基數(shù)的冪次，若關(guān)鍵字是十進(jìn)制整數(shù)，其基數(shù)為10，取p=100，則關(guān)鍵字159，259，359…均互為同義詞。

一般情況下，p應(yīng)該選為小于或等于散列表長(zhǎng)度m的某個(gè)最大素?cái)?shù)。下面給出一些常用取值：

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

p=7,13,31,61,127,251,503,1019

除留余數(shù)法較為簡(jiǎn)單，我們無(wú)需將它定義為一個(gè)C的函數(shù)，而是將它直接寫到相應(yīng)的程序里。除留余數(shù)法也可以與其他散列方法組合在一起使用，例如設(shè)關(guān)鍵字是字符串，散列函數(shù)是通過(guò)將字符串的首、尾兩個(gè)字符相加之和轉(zhuǎn)換為整數(shù)，然后用除留余數(shù)法求散列地址。該散列函數(shù)的定義如下：

6．基數(shù)轉(zhuǎn)換法

基數(shù)轉(zhuǎn)換法的思路是把某一進(jìn)制的關(guān)鍵字看成是另一個(gè)進(jìn)制上的數(shù)，再把它轉(zhuǎn)換成原來(lái)進(jìn)制上的數(shù)，取其中的若干位作為散列地址。一般要求兩個(gè)基數(shù)互素，其所取的基數(shù)大于原基數(shù)。進(jìn)制轉(zhuǎn)換后，關(guān)鍵字的隨機(jī)性一般會(huì)增大，從而減少?zèng)_突。

例如，把一個(gè)十進(jìn)制數(shù)的關(guān)鍵字(360495)10看做十六進(jìn)制數(shù)(360495)16，再把它轉(zhuǎn)換為十進(jìn)制數(shù)，(360495)16＝(3540117)10，此時(shí)可根據(jù)散列表的長(zhǎng)度選取若干位數(shù)字作為散列地址，也可應(yīng)用其他方法。

7．隨機(jī)數(shù)法

隨機(jī)數(shù)法取決于隨機(jī)函數(shù)random的構(gòu)造，即

H(key)=random(key)

其中random為偽隨機(jī)函數(shù)。若產(chǎn)生的是一個(gè)隨機(jī)整數(shù)，則通常采用以下方法保證函數(shù)值在0～m?-1之間：

H(key)=random(key)％m

實(shí)際上，上述各種方法都具有一定的隨機(jī)性。隨機(jī)性的強(qiáng)弱直接決定散列函數(shù)的均勻性。通常，當(dāng)關(guān)鍵字長(zhǎng)度不等時(shí)，采用隨機(jī)數(shù)法構(gòu)造散列函數(shù)較合適。

8.2.3處理沖突的方法

構(gòu)造合適的散列函數(shù)只能夠減少?zèng)_突，不可能避免沖突，因此，如何處理沖突問(wèn)題是構(gòu)造散列表的另一個(gè)重要方面。通常有兩種方法處理沖突：開放地址法和拉鏈法。前者是將所有記錄均勻地存放在散列表HT[m]中；后者是將互為同義詞的記錄鏈接成一個(gè)單鏈表，而把單鏈表的頭指針存放在散列表HT[m]中。

1．開放地址法

開放地址法又稱為開放定址法，其基本思路是：首先將表置空，并根據(jù)某種方法在散列表中定義一個(gè)探查序列，當(dāng)發(fā)生沖突時(shí)，沿此序列逐個(gè)單元查找空單元，一旦找到，則將新記錄放入。好的探查序列能夠保證所有沖突的記錄都能迅速地找到相應(yīng)的空單元。

設(shè)表長(zhǎng)為m，關(guān)鍵字個(gè)數(shù)為n，探查序列設(shè)為di,i=1~m

1，則開放地址的公式為

hi=(H(key)?+?di)％m

(8-7)

其中H(key)為散列函數(shù)。那么如何形成探查序列呢？

1)線性探查法

線性探查法的基本思想是：將散列表看成是一個(gè)環(huán)形表，若發(fā)生沖突的單元地址為d，則依次探查d+1,d+2,

…,m

1,0,1,…,d

1，直至找到一個(gè)空單元為止。

例如，已知一組關(guān)鍵字集(21,32,11,43,35,05,51,12,07)，用線性探查法解決沖突，試構(gòu)造這組關(guān)鍵字的散列表。

通常令裝填因子

<1，這里取

=0.75。由于關(guān)鍵字個(gè)數(shù)為n=9，可以確定散列表長(zhǎng)m=

n/

=12，因此可以設(shè)置一維數(shù)組HT[12]為散列表。我們采用除留余數(shù)法構(gòu)造散列函數(shù)，并選p=11，則開放地址為

hi?=?(H(key)?+?di)％m?=?(key％11?+?i)％12

其中i=1～m

1。由此可以計(jì)算關(guān)鍵字的散列地址及開放地址。如果散列地址為空，則散列地址即為開放地址，記錄可直接存入；否則根據(jù)di查找下一個(gè)開放地址。結(jié)果如表8.4所示。

插入第二個(gè)關(guān)鍵字32時(shí)，散列地址d=H(21)=10已被關(guān)鍵字21占用(即發(fā)生沖突)，利用探查序列得到h1=(10+1)%12=11為開放地址，因此可將32插入HT[11]中。與此類似，關(guān)鍵字43的散列地址也為10，經(jīng)過(guò)三次探查后，找到開放地址h3=(10+3)%12=1。依次類推，可以插入所有關(guān)鍵字。表8.4中最末一行的數(shù)字表示查找該記錄時(shí)所需進(jìn)行的關(guān)鍵字比較

次數(shù)。

可見，只要散列表仍有空單元，線性探查法就總能找到一個(gè)不發(fā)生沖突的地址。表8.4中還出現(xiàn)了一種現(xiàn)象。雖然關(guān)鍵字12和43并非同義詞，但是散列地址H(12)=1卻被關(guān)鍵字43占用，也即發(fā)生了沖突。一般地，用線性探查法解決沖突時(shí)，當(dāng)表中i,i+1,…,i+k位置上非空時(shí)，散列地址為i,i+1,…,i+k+1的記錄都將插入在位置i+k+1上，我們把這種散列地址不同的結(jié)點(diǎn)爭(zhēng)奪同一個(gè)后繼散列地址的現(xiàn)象稱為“堆積”。這種現(xiàn)象的后果是，不是同義詞的結(jié)點(diǎn)處在同一個(gè)探查序列之中，從而增加了探查序列的長(zhǎng)度。若裝填因子過(guò)大或散列函數(shù)選擇不當(dāng)，都可能使堆積的機(jī)會(huì)增加。后面的兩種方法可解決這一問(wèn)題。

2)二次探查法

二次探查法的探查序列依次是：12,

12,22,

22,…。發(fā)生沖突時(shí)，求下一個(gè)開放地址的公式為

h2i

1?=?(H(key)?+?i2)％m

h2i?=?(H(key)?

?i2)％m

(8-8)

其中1≤i≤(m

1)/2。分析式(8-8)可知，發(fā)生沖突時(shí)，同義詞將來(lái)回在其散列地址H(key)的兩端尋找開放地址。

二次探查法可以減少堆積現(xiàn)象，但是不容易探查到整個(gè)散列表空間。僅當(dāng)表長(zhǎng)m為4j+3(j為正整數(shù))的素?cái)?shù)時(shí)，才能探查到整個(gè)表空間。

3)隨機(jī)探查法

隨機(jī)探查法的探查序列將隨機(jī)產(chǎn)生，求下一個(gè)開放地址的公式可以表示為

hi?=?(H(key)?+?Ri)%m

(8-9)

其中1≤i≤m

1，R1,R2，…,Rm－1是1,2,…，m

1的一個(gè)隨機(jī)排列。隨機(jī)排列的產(chǎn)生有很多種方法，實(shí)用中常用移位寄存器序列代替隨機(jī)數(shù)序列。

2．拉鏈法

拉鏈法也稱為鏈地址法，假設(shè)散列函數(shù)的值域?yàn)?～m

1，則可將散列表定義為一個(gè)指針數(shù)組HTP[m]，凡是散列地址為i的結(jié)點(diǎn)，均插入到以HTP[i]為頭指針的單鏈表中?？梢?，拉鏈法解決沖突的思路是：將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)鏈接到同一個(gè)單鏈表中。

以表8.4中的關(guān)鍵字集(21,32,11,43,35,05,51,12,07)為例，用拉鏈法解決沖突以構(gòu)造這組關(guān)鍵字的散列表。首先，這里設(shè)置散列函數(shù)為H(key)=key%11，其值域?yàn)?～10，則散列表為HTP[11]。對(duì)于所有散列地址為H(key)=i的關(guān)鍵字，都要接到第i個(gè)單鏈表中。我們采用尾插法建立單鏈表，則可得到如圖8.3所示的散列表。

圖8.3拉鏈法構(gòu)造散列表示例當(dāng)裝填因子

較大時(shí)，開放地址法所需的探查次數(shù)比較多。雖然拉鏈法所用的空間比開放地址法多，但是不會(huì)產(chǎn)生堆積現(xiàn)象，其平均查找長(zhǎng)度也較短。所以，拉鏈法所增加的空間開銷是合算的。利用單鏈表結(jié)點(diǎn)的動(dòng)態(tài)申請(qǐng)?zhí)攸c(diǎn)，拉鏈法還適合于無(wú)法確定表長(zhǎng)的情況。

另一方面，對(duì)于用拉鏈法構(gòu)造的散列表，簡(jiǎn)單地在鏈表上刪除結(jié)點(diǎn)即可實(shí)現(xiàn)散列表的刪除操作。而在開放地址法構(gòu)造的散列表中，不能簡(jiǎn)單地將被刪結(jié)點(diǎn)的空間置空來(lái)刪除結(jié)點(diǎn)，因?yàn)榭盏刂穯卧?即開放地址)都是查找失敗的條件，這樣做會(huì)截?cái)嘣谒筇钊肷⒘斜淼耐x詞結(jié)點(diǎn)的查找路徑。正確的做法是在被刪結(jié)點(diǎn)上做刪除標(biāo)記，而不能真正刪除結(jié)點(diǎn)。

8.2.4散列表的查找及分析

散列表的查找過(guò)程和建表過(guò)程基本一致。假設(shè)給定值為k，根據(jù)建表時(shí)設(shè)定的散列函數(shù)H可計(jì)算得到散列地址H(k)。若表中該地址空間未被占用，則查找失敗；否則，進(jìn)行關(guān)鍵字值的比較。若相等，則查找成功；否則，根據(jù)建表時(shí)處理沖突的方法查找下一個(gè)地址，直至某個(gè)地址空間為空(查找失敗)或者關(guān)鍵字比較相等(查找成功)為止。

下面以線性探查法和拉鏈法為例，給出相應(yīng)的散列表查找和插入算法。利用線性探查法解決沖突的有關(guān)說(shuō)明及查找和插入操作如算法8.3及算法8.4所示，利用拉鏈法解決沖突的有關(guān)說(shuō)明及查找和插入操作如算法8.5和算法8.6所示。

由于沖突和堆積現(xiàn)象的存在，在記錄及其存儲(chǔ)位置之間建立相應(yīng)的映射關(guān)系仍然需要關(guān)鍵字的比較操作，這可以從散列表的查找和插入算法中看出。但是，散列表的平均查找長(zhǎng)度比順序查找要小，甚至比折半查找也要小。下面以表8.4和圖8.3的散列表為例分析散列表的平均查找長(zhǎng)度。

1)等概率情況下查找成功時(shí)的平均查找長(zhǎng)度

線性探查法：

ASL=(1+4+1+3+1+1+2+1+2)/9=16/9≈1.78

拉鏈法：

ASL=(1×6+2×2+3×1)/9=13/9≈1.44

而當(dāng)n=9時(shí)，順序查找和折半查找的平均查找長(zhǎng)度為

ASLsq(9)=(9+1)/2=5

ASLbn(9)=(1×1+2×2+3×4+4×2/9=25/9≈2.78

2)等概率情況下查找不成功時(shí)的平均查找長(zhǎng)度

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

線性探查法：假設(shè)待查關(guān)鍵字k不在表8.4中，若H(k)=0，則必須依次將HT[0]～HT[4]中的關(guān)鍵字與k進(jìn)行比較，經(jīng)過(guò)5次比較后才能發(fā)現(xiàn)HT[7]為空；若H(k)=1，則需比較4次才能確定查找不成功。依次類推，由于散列函數(shù)H(key)%11的值域?yàn)?～10，可得查找不成功時(shí)的平均查找長(zhǎng)度為

ASLunsucc=(5+4+3+2+1+2+1+3+2+1+7)/11=31/11≈2.82

拉鏈法：設(shè)待查關(guān)鍵字k的散列地址為d=H(k)，在圖8.3所示的鏈地址法中，若第d個(gè)鏈表上具有t個(gè)結(jié)點(diǎn)，則需經(jīng)過(guò)t次關(guān)鍵字比較(不包括空指針判定)才能確定查找不成功。因此，查找不成功時(shí)的平均查找長(zhǎng)度為

ASLunsucc=(1+1+1+0+0+1+0+2+0+0+3)/11=9/11≈0.82

綜上可知，由同一個(gè)散列函數(shù)、不同解決沖突方法構(gòu)成的散列表，其平均查找長(zhǎng)度是不相同的。假設(shè)散列函數(shù)是均勻的，可以證明在一般情況下這一結(jié)論是成立的。表8.5給出了幾種不同的沖突處理方法在等概率情況下得到的散列表的平均查找長(zhǎng)度。

由表8.5可見，散列表的平均查找長(zhǎng)度是裝填因子

的函數(shù)，與記錄個(gè)數(shù)n無(wú)關(guān)。因此，通過(guò)選擇合適的

可以將散列表的查找長(zhǎng)度限定于某個(gè)范圍。顯然，

越小產(chǎn)生沖突的機(jī)會(huì)就越小，但過(guò)小的

會(huì)造成較大的空間浪費(fèi)。例如，當(dāng)

=0.9時(shí)，對(duì)于成功的查找，線性探查法的平均查找長(zhǎng)度是5.5，二次探查、隨機(jī)探查及雙散列函數(shù)探查法的平均查找長(zhǎng)度是2.56，拉鏈法的平均查找長(zhǎng)度為1.45。

一、名詞解釋

查找表，查找長(zhǎng)度，有序表，散列表，散列函數(shù)，同義詞，沖突，拉鏈法，堆積

二、填空題

1．查找表中主關(guān)鍵字指的是

，次關(guān)鍵字指的是

。

2．二分查找在查找成功時(shí)的查找長(zhǎng)度不超過(guò)

，其平均查找長(zhǎng)度為

，當(dāng)n較大時(shí)約等于

。

3．在散列存儲(chǔ)中，裝填因子

的值越大，則

。

習(xí)題8

4．二分查找法僅適用于這樣的表：表中的記錄必須

，其存儲(chǔ)結(jié)構(gòu)必須是

。

5．靜態(tài)查找表的三種不同實(shí)現(xiàn)各有優(yōu)缺點(diǎn)。其中，

查找效率最低但限制最少，

查找效率最高但限制最強(qiáng)，而

查找則介于上述二者之間。

6．設(shè)有一個(gè)已按各元素的值排好序的線性表，長(zhǎng)度為125，對(duì)給定的k值，用二分法查找與k相等的元素，若查找成功，則至少需比較

次，至多需比較

次。

7．在采用開放地址法解決沖突的散列表中刪除一個(gè)記錄，則對(duì)該元素所在存儲(chǔ)單元的操作是

。

8．以下算法在散列表HP中查找鍵值等于K的結(jié)點(diǎn)，成功時(shí)返回指向該結(jié)點(diǎn)的指針，不成功時(shí)返回空指針。請(qǐng)分析程序，并在

上填充合適的語(yǔ)句。

pointerresearch_openhash(keytypeK,openhashHP)

{

i=H(K);//計(jì)算K的散列地址

p=HP[i];//i的同義詞子表表頭指針傳給p

while(

)p=p->next;//未達(dá)表尾且未找到時(shí)，繼續(xù)掃描

___________;

}

9．以下算法假定以線性探測(cè)法解決沖突，在散列表HL中查找鍵值為K的結(jié)點(diǎn)，成功時(shí)回送該位置，不成功時(shí)回送標(biāo)志?-1。請(qǐng)分析程序，并在

上填充合適的語(yǔ)句。

intsearch_cloxehash(keytypeK,closehashHL)

{

d=H(K);//計(jì)算散列地址

i=d;

while(HL[i].key!=K&&(i!=d-1)i=

; //未成功且未查遍整個(gè)HL時(shí)繼續(xù)掃描

if(

)reurn(i); //查找成功

elsereturn(-1); //查找失敗

}

三、選擇題

1．順序查找法適合于()存儲(chǔ)結(jié)構(gòu)的查找表。

A.壓縮

B.散列

C.索引

D.順序或鏈?zhǔn)?/p>

2．對(duì)采用折半查找法進(jìn)行查找運(yùn)算的查找表，要求按()方式進(jìn)行存儲(chǔ)。

A.順序存儲(chǔ)

B.鏈?zhǔn)酱鎯?chǔ)

C.順序存儲(chǔ)且結(jié)點(diǎn)按關(guān)鍵字有序

D.鏈?zhǔn)酱鎯?chǔ)且結(jié)點(diǎn)按關(guān)鍵字有序

3．設(shè)順序表的長(zhǎng)為n，則其每個(gè)元素的平均查找長(zhǎng)度是()。

A.?n B.?(n-1)/2 C.?n/2 D.?(n+1)/2

4．分塊查找的時(shí)間性能()。

A.低于二分查找