數(shù)據(jù)結(jié)構(gòu)-chapter5查找

5查找基本概念檢索查找檢索的效率非常重要尤其對(duì)于大數(shù)據(jù)量需要對(duì)數(shù)據(jù)進(jìn)行特殊的存儲(chǔ)處理在一組記錄集合中找到關(guān)鍵碼值等于給定值的某個(gè)記錄，或者找到關(guān)鍵碼值符合特定條件的某些記錄的過程3提高檢索效率的方法預(yù)排序建立索引散列技術(shù)當(dāng)散列方法不適合于基于磁盤的應(yīng)用程序時(shí)，我們可以選擇B樹方法檢索時(shí)充分利用輔助索引信息犧牲一定的空間從而提率高檢索效率把數(shù)據(jù)組織到一個(gè)表中根據(jù)關(guān)鍵碼的值確定表中記錄的位置缺點(diǎn)：不適合進(jìn)行范圍查詢一般也不允許出現(xiàn)重復(fù)關(guān)鍵碼排序算法本身比較費(fèi)時(shí)只是預(yù)處理（在檢索之前已經(jīng)完成）基本概念查找:查詢某個(gè)關(guān)鍵字是否在（數(shù)據(jù)元素集合）表中的過程。也稱作檢索。主關(guān)鍵字:能夠惟一區(qū)分各個(gè)不同數(shù)據(jù)元素的關(guān)鍵字次關(guān)鍵字:通常不能惟一區(qū)分各個(gè)不同數(shù)據(jù)元素的關(guān)鍵字查找成功:在數(shù)據(jù)元素集合中找到了要查找的數(shù)據(jù)元素查找不成功:在數(shù)據(jù)元素集合中沒有找到要查找的數(shù)據(jù)元素靜態(tài)查找:只查找，不改變數(shù)據(jù)元素集合內(nèi)的數(shù)據(jù)元素動(dòng)態(tài)查找:既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素靜態(tài)查找表:靜態(tài)查找時(shí)構(gòu)造的存儲(chǔ)結(jié)構(gòu)動(dòng)態(tài)查找表:動(dòng)態(tài)查找時(shí)構(gòu)造的存儲(chǔ)結(jié)構(gòu)5平均檢索長(zhǎng)度（ASL）關(guān)鍵碼的比較：檢索運(yùn)算的主要操作平均檢索長(zhǎng)度(AverageSearchLength)檢索過程中對(duì)關(guān)鍵碼的平均比較次數(shù)衡量檢索算法優(yōu)劣的時(shí)間標(biāo)準(zhǔn)ASL是存儲(chǔ)結(jié)構(gòu)中對(duì)象總數(shù)n的函數(shù)Pi

為檢索第i個(gè)元素的概率Ci為找到第i個(gè)元素所需的關(guān)鍵碼值與給定值的比較次數(shù)

平均檢索長(zhǎng)度假設(shè)線性表為（a,b,c）檢索a、b、c的概率分別為0.4、0.1、0.5順序檢索算法的平均檢索長(zhǎng)度為0.4×1+0.1×2+0.5×3=2.1即平均需要2.1次給定值與表中關(guān)鍵碼值的比較才能找到待查元素檢索算法評(píng)估的幾個(gè)問題衡量一個(gè)檢索算法還需要考慮算法所需的存儲(chǔ)量算法的復(fù)雜性...查找分類靜態(tài)查找順序查找二分法查找分塊查找動(dòng)態(tài)查找散列查找5.1靜態(tài)查找5.1.1順序查找5.1.2二分查找5.1.3分塊查找5.1.1順序查找針對(duì)線性表里的所有記錄，逐個(gè)進(jìn)行關(guān)鍵碼和給定值的比較。若某個(gè)記錄的關(guān)鍵碼和給定值比較相等，則檢索成功；否則檢索失敗(找遍了仍找不到)。存儲(chǔ)：可以順序、鏈接排序要求：無12...n-2n-1nTomAnnieJohnRoseJack查找Jack比較2次查找John比較n-1次若查找不存在比較n+1次（設(shè)置監(jiān)哨崗）順序查找順序查找檢索性能分析查找成功

假設(shè)查找每個(gè)關(guān)鍵碼是等概率的，Pi=1/n查找失敗

假設(shè)查找失敗時(shí)都需要比較n+1次（設(shè)置了一個(gè)監(jiān)視哨）順序查找性能分析（續(xù)）平均查找長(zhǎng)度

假設(shè)查找成功的概率為p，查找失敗的概率為q=(1-p)，則平均查找長(zhǎng)度為（n+1)/2<ASL<(n+1)優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：插入元素可以直接加在表尾Θ(1)

缺點(diǎn)：查找時(shí)間太長(zhǎng)Θ(n)

5.1.2二分法查找有序表：線性表中所有數(shù)據(jù)元素按關(guān)鍵碼值遞增（或遞減）的次序排列算法的基本思想：先給數(shù)據(jù)排序（例如按升序排好），形成有序表，然后再將key與正中元素相比，若key小，則縮小至前半部?jī)?nèi)查找；再取其中值比較，每次縮小1/2的范圍，直到查找成功或失敗為止。反之，如果key大，則縮小至后半部?jī)?nèi)查找。表中數(shù)據(jù)元素按照主關(guān)鍵字順序排列。5，13，19，21，37，56，64，75，80，88，92二分查找方法例5，13，19，21，37，56，64，75，80，88，92lowhighmid=(low+high)/2查找211234567891011midmid=6high=mid–1=5highmid=3midlow

=mid+1=4lowmid=4mid找到查找85lowhighmid=6midlow

=mid+1=7lowmid=9midlow

=mid+1=10lowmid=10midhigh=mid–1=9highhigh<low

查找不成功檢索二分法檢索算法template<classType>intBinSearch(vector<Item<Type>*>&dataList,intlength,Typek){//low,high分別記錄數(shù)組首尾位置

intlow=1,high=length,mid;while(low<=high){mid=(low+high)/2;if(k<dataList[mid]->getKey())high=mid-1;//右縮檢索區(qū)間

elseif(k>dataList[mid]->getKey())low=mid+1;//左縮檢索區(qū)間

elsereturnmid;//檢索成功，返回元素位置

} return0;//檢索失敗，返回0}檢索二分法檢索性能分析

最大檢索長(zhǎng)度為失敗的檢索長(zhǎng)度是或檢索19/85二分法檢索性能分析（續(xù)）成功的平均檢索長(zhǎng)度為：

(n>50)優(yōu)缺點(diǎn)優(yōu)點(diǎn)：平均檢索長(zhǎng)度與最大檢索長(zhǎng)度相近，檢索速度快缺點(diǎn)：要排序、順序存儲(chǔ)，不易更新(插/刪)5.1.3分塊查找順序與二分法的折衷既有較快的查找又有較靈活的更改分塊查找思想“按塊有序”設(shè)線性表中共有n個(gè)數(shù)據(jù)元素，將表分成b塊不需要均勻每一塊可能不滿每一塊中的關(guān)鍵碼不一定有序但前一塊中的最大關(guān)鍵碼必須小于后一塊中的最小關(guān)鍵碼分塊查找思想下標(biāo)keylink01401345位置key其他信息081142639410522634718819931索引表各塊中的最大關(guān)鍵碼及各塊起始位置可能還需要塊中元素個(gè)數(shù)（每一塊可能不滿）索引表是一個(gè)遞增有序表由于表是分塊有序的分塊查找——索引順序結(jié)構(gòu)link:Key:0123456789101112131415161752213983342442448608074498653

00612-

2248860556塊起始位置塊內(nèi)最大關(guān)鍵碼塊內(nèi)有效元素個(gè)數(shù)count:分塊查找分兩個(gè)階段（1）確定待查元素所在的塊

（2）在塊內(nèi)查找待查的元素分塊查找性能分析分塊查找為兩級(jí)查找先在索引表中確定待查元素所在的塊；設(shè)在索引表中確定塊號(hào)的時(shí)間開銷是ASLb然后在塊內(nèi)查找待查的元素。在塊中查找記錄的時(shí)間開銷為ASLwASL(n)=ASLb+ASLw檢索26/85分塊檢索性能分析假設(shè)索引表的長(zhǎng)度為b，主表中每個(gè)子表的長(zhǎng)度為s，并假設(shè)在索引表上和在主表上均采取順序查找算法，則索引順序表上查找算法的平均查找長(zhǎng)度為：ASL=(b+1)/2+(s+1)/2=(b+s)/2+1分塊查找性能分析若采用二分法查找確定記錄所在的子表，則查找成功時(shí)的平均檢索長(zhǎng)度為ASL=ASLb

+ASLw

log2(b+1)-1+(s+1)/2

分塊查找的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：插入、刪除相對(duì)較易沒有大量記錄移動(dòng)缺點(diǎn)：增加一個(gè)輔助數(shù)組的存儲(chǔ)空間初始線性表分塊排序當(dāng)大量插入/刪除時(shí)，或結(jié)點(diǎn)分布不均勻時(shí)，速度下降查找分類靜態(tài)查找順序查找二分法查找分塊查找動(dòng)態(tài)查找散列索引索引(indexing)——(關(guān)鍵碼，指針)指針指向“主文件”中的完整記錄索引文件(indexfile)索引技術(shù)是組織大型數(shù)據(jù)庫(kù)的一種重要技術(shù)高效率的檢索插入、更新、刪除(20,a9)(21,a10)(45,a13)(47,a14)(50,a5)(52,a16)線性索引文件按照關(guān)鍵碼的順序進(jìn)行排序文件中的指針指向存儲(chǔ)在磁盤上的文件記錄起始位置或者主索引中主碼的起始位置92733755數(shù)據(jù)庫(kù)記錄線性索引文件基本概念動(dòng)態(tài)索引結(jié)構(gòu)索引結(jié)構(gòu)本身也可能發(fā)生改變?cè)谙到y(tǒng)運(yùn)行過程中插入或刪除記錄時(shí)目的保持較好的性能例如較高的檢索效率B樹B樹(BalancedTree)

一種平衡的多分樹

一棵m階的B—樹，或者是空樹，或者是滿足下列性質(zhì)的m叉樹:(1)樹中每個(gè)結(jié)點(diǎn)至多有m

棵子樹；(2)根結(jié)點(diǎn)至少有兩棵子樹；所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層次，可用來“查找失敗”處理。(3)除根結(jié)點(diǎn)之外的非終端結(jié)點(diǎn)至少有

m/2棵子樹；(5)有k個(gè)子結(jié)點(diǎn)的非根結(jié)點(diǎn)恰好包含k-1個(gè)關(guān)鍵碼。

18

11

27

39

475364

99FFFFFFFFFFFF

4378

35葉子結(jié)點(diǎn)查找失敗的結(jié)點(diǎn)終端結(jié)點(diǎn)在同一層上外結(jié)點(diǎn)指針包含其子女結(jié)點(diǎn)的塊號(hào)B樹B樹的結(jié)點(diǎn)結(jié)構(gòu)B樹的一個(gè)包含j個(gè)關(guān)鍵碼，j+1個(gè)指針的結(jié)點(diǎn)的一般形式為：其中Ki是關(guān)鍵碼值，K1<K2<…<Kj，Pi是指向包括Ki到Ki+1之間的關(guān)鍵碼的子樹的指針。2-3樹：是具有下列特性的樹：⑴一個(gè)結(jié)點(diǎn)包含1個(gè)或者2個(gè)關(guān)鍵碼。⑵每個(gè)內(nèi)部結(jié)點(diǎn)有2個(gè)子女（包含一個(gè)關(guān)鍵碼）或者3個(gè)子女（包含兩個(gè)關(guān)鍵碼）。⑶

所有葉子結(jié)點(diǎn)都在樹的同一層。2-3樹B樹是2－3樹的推廣，2-3樹是一個(gè)3階B樹

。18331223304810152021243145475052形狀上有什么特性?2-3樹示例包含1個(gè)或者2個(gè)關(guān)鍵碼；有2個(gè)子女或者3個(gè)子女；葉子結(jié)點(diǎn)在同一層。183312233048101520212431454750522-3樹示例結(jié)點(diǎn)的值有什么特性?183312233048101520212431454750522-3樹示例左子樹中所有結(jié)點(diǎn)的值均小于第一個(gè)關(guān)鍵碼的值；中間子樹中所有結(jié)點(diǎn)的值均大于第一個(gè)關(guān)鍵碼的值，且小于第二個(gè)關(guān)鍵碼的值；右子樹中所有結(jié)點(diǎn)的值均大于第二個(gè)關(guān)鍵碼的值。183312233048101520212431454750522-3樹示例183312233048101520212431454750522118<21<3321<23比較次數(shù)不超過樹的深度。由于2-3樹是樹高平衡的，而且每一個(gè)內(nèi)部結(jié)點(diǎn)至少有2個(gè)子女，所以樹的最大深度是。??1log2+n2-3樹查找新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。18331223304810152021243145475052葉子結(jié)點(diǎn)只包含1個(gè)記錄插入新記錄

112-3樹插入新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。葉子結(jié)點(diǎn)只包含1個(gè)記錄插入新記錄

18331223304815202124314547505210112-3樹插入新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。18331223304810152021243145475052葉子結(jié)點(diǎn)只包含2個(gè)記錄插入新記錄，分裂－提升

552-3樹插入新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。1833122330481015202124314547505255葉子結(jié)點(diǎn)只包含2個(gè)記錄插入新記錄，分裂－提升

插入2-3樹插入新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。1833122330481015202124314547葉子結(jié)點(diǎn)只包含2個(gè)記錄插入新記錄，分裂－提升

分裂5055522-3樹插入新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。18331223301015202124314547葉子結(jié)點(diǎn)只包含2個(gè)記錄插入新記錄，分裂－提升

提升505548522-3樹插入18331223304810152021243145475052情況1：從包含2個(gè)記錄的葉子結(jié)點(diǎn)刪除1個(gè)記錄。解決方法：直接刪除這個(gè)記錄。2-3樹刪除1833122330481015243145475052情況1：從包含2個(gè)記錄的葉子結(jié)點(diǎn)刪除1個(gè)記錄。解決方法：直接刪除這個(gè)記錄。212-3樹刪除18331223304810152021243145475052情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。解決方法：向兄弟結(jié)點(diǎn)借一個(gè)記錄，同時(shí)修改雙親結(jié)點(diǎn)的記錄。2-3樹刪除183312213048101520233145475052情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。解決方法：向兄弟結(jié)點(diǎn)借一個(gè)記錄，同時(shí)修改雙親結(jié)點(diǎn)的記錄。2-3樹刪除183312213048101520233145475052情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)。2-3樹刪除1833122021481015303145475052情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)。2-3樹刪除1833122021481015303145475052情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)。2-3樹刪除202148333145475052情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。10121830解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)。2-3樹刪除48333045475052情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)，這可能減少樹的高度。25202-3樹刪除情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)，這可能減少樹的高度。45475052334820252-3樹的優(yōu)點(diǎn)：能夠以相對(duì)較低的代價(jià)保持樹高平衡。2-3樹刪除情況3：從內(nèi)部結(jié)點(diǎn)刪除一個(gè)記錄。解決方法：將被刪除記錄用右邊子樹中的最小關(guān)鍵碼Y代替（Y一定在某個(gè)葉子結(jié)點(diǎn)中），然后再刪除Y。183312233048101520212431454750522-3樹刪除情況3：從內(nèi)部結(jié)點(diǎn)刪除一個(gè)記錄。解決方法：將被刪除記錄用右邊子樹中的最小關(guān)鍵碼Y代替（Y一定在某個(gè)葉子結(jié)點(diǎn)中），然后再刪除Y。2033122330481015212431454750522-3樹刪除B+樹是B樹的一種變形在葉結(jié)點(diǎn)上存儲(chǔ)信息的樹所有的關(guān)鍵碼均出現(xiàn)在葉結(jié)點(diǎn)上

各層結(jié)點(diǎn)中的關(guān)鍵碼均是下一層相應(yīng)結(jié)點(diǎn)中最大關(guān)鍵碼（或最小關(guān)鍵碼）的復(fù)寫

B+樹的結(jié)構(gòu)定義m階B+樹的結(jié)構(gòu)定義如下：(1)每個(gè)結(jié)點(diǎn)至多有m個(gè)子結(jié)點(diǎn)；(2)每個(gè)結(jié)點(diǎn)(除根外)至少有個(gè)子結(jié)點(diǎn)；(3)根結(jié)點(diǎn)至少有兩個(gè)子結(jié)點(diǎn)；(4)有k個(gè)子結(jié)點(diǎn)的結(jié)點(diǎn)必有k個(gè)關(guān)鍵碼。2階B+樹的例子B+樹的查找查找應(yīng)該到葉結(jié)點(diǎn)層在上層已找到待查的關(guān)鍵碼，并不停止而是繼續(xù)沿指針向下一直查到葉結(jié)點(diǎn)層的這個(gè)關(guān)鍵碼B+樹的葉結(jié)點(diǎn)一般鏈接起來，形成一個(gè)雙鏈表

適合順序檢索（范圍檢索）實(shí)際應(yīng)用更廣B+樹的插入插入——分裂過程和B樹類似注意保證上一層結(jié)點(diǎn)中有這兩個(gè)結(jié)點(diǎn)的最大關(guān)鍵碼（最小關(guān)鍵碼）3階B+樹插入插入153階B+樹插入插入15后3階B+樹插入插入16結(jié)點(diǎn)滿，需要分裂3階B+樹插入插入173階B+樹插入插入19結(jié)點(diǎn)滿，需要分裂結(jié)點(diǎn)滿，需要分裂樹增加一層B+樹的刪除當(dāng)關(guān)鍵碼不滿時(shí)，與左右兄弟進(jìn)行調(diào)整、合并的處理和B樹類似關(guān)鍵碼在葉結(jié)點(diǎn)層刪除后，其在上層的復(fù)本可以保留，做為一個(gè)“分界關(guān)鍵碼”存在也可以替換為新的最大關(guān)鍵碼（或最小關(guān)鍵碼）23被刪除但上層結(jié)點(diǎn)中的副本保留階m=3刪除23課堂練習(xí)按照以下次序輸入關(guān)鍵字的值建立2-3樹(3階B-樹):(68,54,82,35,75,90，103，22)。(1)請(qǐng)畫出所建的2-3樹。(2)如果此后依次刪除22,75，畫出每一步執(zhí)行后的2-3樹的狀態(tài)。查找分類靜態(tài)查找順序查找二分法查找分塊查找動(dòng)態(tài)查找散列在隨機(jī)存儲(chǔ)中三李四王五192120200305200301200302李四王五張三212019查找某一條記錄需要進(jìn)行一系列的“比較”。查找的效率依賴于比較的次數(shù)。能否在記錄的關(guān)鍵字和存儲(chǔ)地址之間構(gòu)造這樣一種關(guān)系f，使得關(guān)鍵字和存儲(chǔ)地址一一對(duì)應(yīng)？此對(duì)應(yīng)關(guān)系f稱為散列函數(shù)。學(xué)號(hào)姓名年齡010203散列幾個(gè)重要概念負(fù)載因子

α=n/m散列表的空間大小為m填入表中的結(jié)點(diǎn)數(shù)為n沖突某個(gè)散列函數(shù)對(duì)于不相等的關(guān)鍵碼計(jì)算出了相同的散列地址在實(shí)際應(yīng)用中，不產(chǎn)生沖突的散列函數(shù)極少存在同義詞發(fā)生沖突的兩個(gè)關(guān)鍵碼

散列函數(shù)散列函數(shù)：把關(guān)鍵碼值映射到存儲(chǔ)位置的函數(shù)，通常用h

來表示

Address

＝Hash(key)檢索構(gòu)造散列函數(shù)時(shí)的幾點(diǎn)要求：散列函數(shù)的定義域必須包括需要存儲(chǔ)的全部關(guān)鍵碼，如果散列表允許有m個(gè)地址時(shí),其值域必須在0到m-1之間。散列函數(shù)計(jì)算出來的地址應(yīng)能均勻分布在整個(gè)地址空間中：若key是從關(guān)鍵碼集合中隨機(jī)抽取的一個(gè)關(guān)鍵碼，散列函數(shù)應(yīng)能以同等概率取

0到m-1中的每一個(gè)值。散列函數(shù)應(yīng)是簡(jiǎn)單的，能在較短的時(shí)間內(nèi)計(jì)算出結(jié)果。散列函數(shù)常用散列函數(shù)選取方法1.除余法2.折疊法3.平方取中法4.

基數(shù)轉(zhuǎn)換法5.直接定址法散列函數(shù)例1除留余數(shù)法

H(key)=key%p

或H(key)=key%p+c這里p<m；余數(shù)總在0～p-1之間。檢索示例：有一個(gè)關(guān)鍵碼key=962148，散列表大小m=25，即HT[25]。取質(zhì)數(shù)p=23。散列函數(shù)hash(key)=key%p。則散列地址為

hash(962148)=962148%23=12?？梢园从?jì)算出的地址存放記錄。需要注意的是，使用上面的散列函數(shù)計(jì)算出來的地址范圍是0到22，因此，從23到24這幾個(gè)散列地址實(shí)際上在一開始是不可能用散列函數(shù)計(jì)算出來的，只可能在處理沖突時(shí)達(dá)到這些地址。選取p為質(zhì)數(shù)的理由：

設(shè)key值都為奇數(shù)，選p為偶數(shù)；

則H(key)=key%p，結(jié)果為奇數(shù)，一半單元被浪費(fèi)掉。設(shè)key值都為5的倍數(shù)，選p為95；則H(key)=key%p，結(jié)果為：

0、5、10、15、……90。4/5的單元被浪費(fèi)掉。散列函數(shù)例2折疊法（移位法、分界法）key=381，412，975選取768或570作為散列地址。

3814129751768

9752143811570散列函數(shù)例3平方取中法

e.g:（4731）2

＝22382361；選取82（在m＝100情況下）。此方法在詞典處理中使用十分廣泛。它先計(jì)算構(gòu)成關(guān)鍵碼的標(biāo)識(shí)符的內(nèi)碼的平方，然后按照散列表的大小取中間的若干位作為散列地址。設(shè)標(biāo)識(shí)符可以用一個(gè)計(jì)算機(jī)字長(zhǎng)的內(nèi)碼表示。因?yàn)閮?nèi)碼平方數(shù)的中間幾位一般是由標(biāo)識(shí)符所有字符決定，所以對(duì)不同的標(biāo)識(shí)符計(jì)算出的散列地址大多不相同，即使其中有些字符相同。檢索

標(biāo)識(shí)符內(nèi)碼 內(nèi)碼的平方散列地址A 01 01 001A1 0134 20420 042A9 0144 23420 342B 02 4 004DMAX04150130 21526443617100 443DMAX1 5264473522151420 352AMAX01150130 135423617100 236AMAX1 3454246522151420 652標(biāo)識(shí)符的八進(jìn)制內(nèi)碼表示及其平方值散列函數(shù)例4基數(shù)轉(zhuǎn)換法將關(guān)鍵字k轉(zhuǎn)換為另外一種數(shù)字基數(shù)，再對(duì)表的大小取模。如：k=(345)10

(423)9%表的大小

散列函數(shù)例5直接地址法H(key)=key或H(key)=a×key＋b如：k1,k2分別有值10、1000；選10、1000作為存放地址。以上介紹了幾種常用的散列函數(shù)。在實(shí)際工作中應(yīng)根據(jù)關(guān)鍵碼的特點(diǎn)，選用適當(dāng)?shù)姆椒?。有人曾用“輪盤賭”的統(tǒng)計(jì)分析方法對(duì)它們進(jìn)行了模擬分析，結(jié)論是平方取中法最接近于“隨機(jī)化”。檢索88/85對(duì)于不同的關(guān)鍵字可能得到同一哈希地址，即key1≠key2

，而f(key1)＝f(key2)

，這種現(xiàn)象稱為哈希沖突。造成原因:A.主觀設(shè)計(jì)不當(dāng)例，數(shù)字分析法中813465377137224781387422823013678142281781338967沖突！哈希沖突例，除留余數(shù)法中關(guān)鍵字28356377105p=21解決方法:A因地制宜提高素質(zhì)哈希沖突哈希地址7140140B.客觀存在如何設(shè)計(jì)都不可能完全避免沖突的出現(xiàn)？哈希地址是有限的，而記錄是無限的。解決方法:(1)開散列方法（拉鏈法，鏈接法）(2)閉散列方法（開地址法，開放定址法）(3)桶定址法哈希沖突解決方法(1)開散列方法（拉鏈法）(2)閉散列方法（開地址法）(3)桶定址法將具有同一散列地址的記錄存儲(chǔ)在一條線性鏈表中。例，除留余數(shù)法中，設(shè)關(guān)鍵字為(18,14,01,68,27,55,79)TSize=13散列地址為(5,1,1,3,1,3,1)0123456∧01142779∧∧5568∧∧18∧∧開散列方法（拉鏈法）散列表HashTable[0..m-1]，存放無沖突的記錄公共溢出區(qū)OverTable[0..v]，

存放發(fā)生沖突的記錄012345678910∧∧∧∧∧∧∧∧∧A1K2K3A4K5∧∧∧∧∧∧∧∧B1C1B4C4基本區(qū)(M存區(qū))公共溢出區(qū)D1∧開散列方法（鏈接法）哈希沖突解決方法(1)開散列方法（拉鏈法）(2)閉散列方法（開地址法）(3)桶定址法如果h(k)已經(jīng)被占用，按如下序列探查：在h(k)+p(i-1))%TSize的基礎(chǔ)上，若發(fā)現(xiàn)沖突，則使用增量p(i)

進(jìn)行新的探測(cè)，直至無沖突出現(xiàn)為止。h(k)哈希函數(shù)TSize哈希表長(zhǎng)p

探查函數(shù)(h(k)+p(1))%TSize,(h(k)+p(2))%TSize,…,(h(k)+p(i))%TSize,…閉散列方法（開地址法）如何設(shè)計(jì)P？線性探查法二次探查法隨機(jī)探查法雙散列函數(shù)法閉散列方法（開地址法）需要搜索或加入一個(gè)表項(xiàng)時(shí)，使用散列函數(shù)計(jì)算桶號(hào)：

H0=hash(key)一旦發(fā)生沖突，在表中順次向后尋找“下一個(gè)”空桶Hi的遞推公式為：

Hi

=(Hi-1+1)%m，i=1,2,…,m-1

即用以下的線性探查序列在表中尋找“下一個(gè)”空桶的桶號(hào)：

H0+1,H0+2,…,m-1,0,1,2,…,H0-1當(dāng)發(fā)生沖突時(shí),探查下一個(gè)桶。當(dāng)循環(huán)m-1次后就會(huì)回到開始探查時(shí)的位置,說明待查關(guān)鍵碼不在表內(nèi),而且表已滿,不能再插入新關(guān)鍵碼。(1)線性探查法(LinearProbing)

假設(shè)給出一組表項(xiàng)，它們的關(guān)鍵碼為Burke,Ekers,Broad,Blum,Attlee,Alton,Hecht,Ederly。采用的散列函數(shù)是：取其第一個(gè)字母在字母表中的位置。

Hash(x)=ord(x)-ord(‘A’)

//ord()是求字符內(nèi)碼的函數(shù)

設(shè)散列表為HT[26]，m=26。采用線性探查法處理溢出，則上述關(guān)鍵碼在散列表中散列位置如圖所示。01234AttleeBurkeBroadBlumEkersAltonEderlyHecht56789(1)(1)(2)(3)(1)(6)(3)(1)可得

Hash(Burke)=1Hash(Ekers)=4

Hash(Broad)=1Hash(Blum)=1

Hash(Attlee)=0Hash(Hecht)=7Hash(Alton)=0Hash(Ederly)=4用平均搜索長(zhǎng)度ASL(AveragySearchLength)衡量散列方法的搜索性能。根據(jù)搜索成功與否，它又有搜索成功的平均搜索長(zhǎng)度ASLsucc和搜索不成功的平均搜索長(zhǎng)度ASLunsucc之分。搜索成功的平均搜索長(zhǎng)度ASLsucc是指搜索到表中已有表項(xiàng)的平均探查次數(shù)。它是找到表中各個(gè)已有表項(xiàng)的探查次數(shù)的平均值。搜索不成功的平均搜索長(zhǎng)度ASLunsucc是指在表中搜索不到待查的表項(xiàng)，但找到插入位置的平均探查次數(shù)。它是表中所有可能散列到的位置上要插入新元素時(shí)為找到空桶的探查次數(shù)的平均值。在使用線性探查法對(duì)示例進(jìn)行搜索時(shí)，搜索成功的平均搜索長(zhǎng)度為：搜索不成功的平均搜索長(zhǎng)度為：算法分析設(shè)散列表的裝填因子為

=n/(s*m)，其中n是表中已有的表項(xiàng)個(gè)數(shù)，s是每個(gè)桶中最多可容納表項(xiàng)個(gè)數(shù)，m是表中的桶數(shù)?？捎帽砻魃⒘斜淼难b滿程度。越大，表中表項(xiàng)數(shù)越多，表裝得越滿，發(fā)生沖突可能性越大。通過對(duì)線性探查法的分析可知，為搜索一個(gè)關(guān)鍵碼所需進(jìn)行的探查次數(shù)的期望值P大約是(2-)/(2-2)。雖然平均探查次數(shù)較小，但在最壞情況下的探查次數(shù)會(huì)相當(dāng)大。(2)二次探查法(quadraticprobing)為改善“堆積”問題，減少為完成搜索所需的平均探查次數(shù)，可使用二次探查法。通過某一個(gè)散列函數(shù)對(duì)表項(xiàng)的關(guān)鍵碼x進(jìn)行計(jì)算，得到桶號(hào)，它是一個(gè)非負(fù)整數(shù)。

H0=hash(x)二次探查法在表中尋找“下一個(gè)”空桶的公式為：

Hi

=(H0+i2)%m,Hi

=(H0

-

i2)%m,i=1,2,…,(m-1)/2式中的m是表的大小，它應(yīng)是一個(gè)值為4k+3

的質(zhì)數(shù)，其中k是一個(gè)整數(shù)。這樣的質(zhì)數(shù)如3,7,11,19,23,31,43,59,127,251,503,1019,…。探查序列形如H0,H0+1,H0-1,H0+4,H0-4,…。在做(H0-

i2)%m的運(yùn)算時(shí)，當(dāng)H0-

i2<0時(shí)，運(yùn)算結(jié)果也是負(fù)數(shù)。實(shí)際算式可改為

j=(H0-

i2)%m,

while

(j<0)j+=m示例：給出一組關(guān)鍵碼{Burke,Ekers,Broad,Blum,Attlee,Alton,Hecht,Ederly}。散列函數(shù)為：Hash(x)＝ord(x)－ord('A')

用它計(jì)算可得

Hash(Burke)=1Hash(Ekers)=4Hash(Broad)=1Hash(Blum)=1Hash(Attlee)=0Hash(Hecht)=7Hash(Alton)=0Hash(Ederly)=4因?yàn)榭赡芡疤?hào)是025,取滿足4k+3的質(zhì)數(shù)，表的長(zhǎng)度為TableSize=31，利用二次探查法得到的散列結(jié)果如圖所示。012345

BlumBurkeBroadEkersEderly

Hecht

67891011

AltonAttlee

(3)(1)(2)(1)(2)(1)252627282930(5)(3)利用二次探查法處理溢出使用二次探查法處理溢出時(shí)的搜索成功的平均搜索長(zhǎng)度為：搜索不成功的平均搜索長(zhǎng)度為：（3）隨機(jī)探查法（偽隨機(jī)探查）理想的探查函數(shù)應(yīng)當(dāng)在探查序列中隨機(jī)地從未訪問過的空桶中選擇下一個(gè)位置，即探查序列應(yīng)當(dāng)是散列表位置的一個(gè)隨機(jī)序列。但是，實(shí)際上不能隨機(jī)地從探查序列中選擇一個(gè)位置，因?yàn)樵跈z索關(guān)鍵碼的時(shí)候不能建立起同樣的探查序列。例如：

M=13，偽隨機(jī)數(shù)組前三個(gè)值為r1=2,r2=3,r3=7。假定有兩個(gè)關(guān)鍵碼k1和k2，h(k1)=4,h(k2)=2。

K1的探查序列是

K2的探查序列是4，6，7，11；2，4，5，9。(4)雙散列法使用雙散列方法時(shí)，需要兩個(gè)散列函數(shù)。第一個(gè)散列函數(shù)Hash()按表項(xiàng)的關(guān)鍵碼key計(jì)算表項(xiàng)所在的桶號(hào)H0=Hash(key)。一旦沖突，利用第二個(gè)散列函數(shù)ReHash()

計(jì)算該表項(xiàng)到達(dá)“下一個(gè)”桶的移位量。它的取值與key的值有關(guān)，要求它的取值應(yīng)當(dāng)是小于地址空間大小TableSize，且與TableSize互質(zhì)的正整數(shù)。若設(shè)表的長(zhǎng)度為m=TableSize，則在表中尋找“下一個(gè)”桶的公式為：

j=H0=Hash(key)，p=ReHash(key)；

j=(j+p)%m；

p是小于m且與m互質(zhì)的整數(shù)利用雙散列法，按一定的距離，跳躍式地尋找“下一個(gè)”桶，減少了“堆積”的機(jī)會(huì)。雙散列法的探查序列也可寫成：

Hi

=(H0+i*ReHash(key))%m，

i=1,2,…,m-1最多經(jīng)過m-1次探查，它會(huì)遍歷表中所有位置，回到H0

位置。示例：給出一組表項(xiàng)關(guān)鍵碼{22,41,53,46,30,13,01,67}。散列函數(shù)為：

Hash(x)＝(3x)%11。散列表為HT[0..10]，m=11。因此，再散列函數(shù)為ReHash(x)=(7x)%10+1。

Hi=(Hi-1+(7x)%10+1)%11,i=1,2,H0(22)=0H0(41)=2H0(53)=5

H0(46)=6H0(30)=2沖突

H1=(2+1)=3

H0(13)=6沖突H1=(6+2)=8

H0(01)=3沖突

H1=(3+8)=0

沖突H2=(0+8)=8H3=(8+8)=5

沖突H4=(5+8)=2H5=(2+8)=10

H0(67)=3沖突

H1=(3+10)=2H2=(2+10)=1搜索成功的平均搜索長(zhǎng)度搜索不成功的平均搜索長(zhǎng)度每一散列位置的移位量有10種：1,2,,10。先計(jì)算每一散列位置各種移位量情形下找到下一個(gè)空位的比較次數(shù)，求出平均值；再計(jì)算各個(gè)位置的平均比較次數(shù)的總平均值。

226741305346