數(shù)據(jù)結構-chapter5查找

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

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

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

假設查找每個關鍵碼是等概率的，Pi=1/n查找失敗

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

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

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

缺點：查找時間太長Θ(n)

5.1.2二分法查找有序表：線性表中所有數(shù)據(jù)元素按關鍵碼值遞增（或遞減）的次序排列算法的基本思想：先給數(shù)據(jù)排序（例如按升序排好），形成有序表，然后再將key與正中元素相比，若key小，則縮小至前半部內查找；再取其中值比較，每次縮小1/2的范圍，直到查找成功或失敗為止。反之，如果key大，則縮小至后半部內查找。表中數(shù)據(jù)元素按照主關鍵字順序排列。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}檢索二分法檢索性能分析

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

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

00612-

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

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

+ASLw

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

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

一種平衡的多分樹

一棵m階的B—樹，或者是空樹，或者是滿足下列性質的m叉樹:(1)樹中每個結點至多有m

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

m/2棵子樹；(5)有k個子結點的非根結點恰好包含k-1個關鍵碼。

18

11

27

39

475364

99FFFFFFFFFFFF

4378

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

所有葉子結點都在樹的同一層。2-3樹B樹是2－3樹的推廣，2-3樹是一個3階B樹

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

112-3樹插入新記錄將插入到相應的葉子結點中。葉子結點只包含1個記錄插入新記錄

18331223304815202124314547505210112-3樹插入新記錄將插入到相應的葉子結點中。18331223304810152021243145475052葉子結點只包含2個記錄插入新記錄，分裂－提升

552-3樹插入新記錄將插入到相應的葉子結點中。1833122330481015202124314547505255葉子結點只包含2個記錄插入新記錄，分裂－提升

插入2-3樹插入新記錄將插入到相應的葉子結點中。1833122330481015202124314547葉子結點只包含2個記錄插入新記錄，分裂－提升

分裂5055522-3樹插入新記錄將插入到相應的葉子結點中。18331223301015202124314547葉子結點只包含2個記錄插入新記錄，分裂－提升

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

各層結點中的關鍵碼均是下一層相應結點中最大關鍵碼（或最小關鍵碼）的復寫

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

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

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

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

來表示

Address

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

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

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

H(key)=key%p

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

hash(962148)=962148%23=12?？梢园从嬎愠龅牡刂反娣庞涗?。需要注意的是，使用上面的散列函數(shù)計算出來的地址范圍是0到22，因此，從23到24這幾個散列地址實際上在一開始是不可能用散列函數(shù)計算出來的，只可能在處理沖突時達到這些地址。選取p為質數(shù)的理由：

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

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

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

3814129751768

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

e.g:（4731）2

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

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

(423)9%表的大小

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

，而f(key1)＝f(key2)

，這種現(xiàn)象稱為哈希沖突。造成原因:A.主觀設計不當例，數(shù)字分析法中813465377137224781387422823013678142281781338967沖突！哈希沖突例，除留余數(shù)法中關鍵字28356377105p=21解決方法:A因地制宜提高素質哈希沖突哈希地址7140140B.客觀存在如何設計都不可能完全避免沖突的出現(xiàn)？哈希地址是有限的，而記錄是無限的。解決方法:(1)開散列方法（拉鏈法，鏈接法）(2)閉散列方法（開地址法，開放定址法）(3)桶定址法哈希沖突解決方法(1)開散列方法（拉鏈法）(2)閉散列方法（開地址法）(3)桶定址法將具有同一散列地址的記錄存儲在一條線性鏈表中。例，除留余數(shù)法中，設關鍵字為(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)已經被占用，按如下序列探查：在h(k)+p(i-1))%TSize的基礎上，若發(fā)現(xiàn)沖突，則使用增量p(i)

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

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

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

Hi

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

即用以下的線性探查序列在表中尋找“下一個”空桶的桶號：

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

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

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

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

設散列表為HT[26]，m=26。采用線性探查法處理溢出，則上述關鍵碼在散列表中散列位置如圖所示。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用平均搜索長度ASL(AveragySearchLength)衡量散列方法的搜索性能。根據(jù)搜索成功與否，它又有搜索成功的平均搜索長度ASLsucc和搜索不成功的平均搜索長度ASLunsucc之分。搜索成功的平均搜索長度ASLsucc是指搜索到表中已有表項的平均探查次數(shù)。它是找到表中各個已有表項的探查次數(shù)的平均值。搜索不成功的平均搜索長度ASLunsucc是指在表中搜索不到待查的表項，但找到插入位置的平均探查次數(shù)。它是表中所有可能散列到的位置上要插入新元素時為找到空桶的探查次數(shù)的平均值。在使用線性探查法對示例進行搜索時，搜索成功的平均搜索長度為：搜索不成功的平均搜索長度為：算法分析設散列表的裝填因子為

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

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

Hi

=(H0+i2)%m,Hi

=(H0

-

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

的質數(shù)，其中k是一個整數(shù)。這樣的質數(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的運算時，當H0-

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

j=(H0-

i2)%m,

while

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

用它計算可得

Hash(Burke)=1Hash(Ekers)=4Hash(Broad)=1Hash(Blum)=1Hash(Attlee)=0Hash(Hecht)=7Hash(Alton)=0Hash(Ederly)=4因為可能桶號是025,取滿足4k+3的質數(shù)，表的長度為TableSize=31，利用二次探查法得到的散列結果如圖所示。012345

BlumBurkeBroadEkersEderly

Hecht

67891011

AltonAttlee

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

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

K1的探查序列是

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

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

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

j=(j+p)%m；

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

Hi

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

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

位置。示例：給出一組表項關鍵碼{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搜索成功的平均搜索長度搜索不成功的平均搜索長度每一散列位置的移位量有10種：1,2,,10。先計算每一散列位置各種移位量情形下找到下一個空位的比較次數(shù)，求出平均值；再計算各個位置的平均比較次數(shù)的總平均值。

226741305346