1、第8章 查找 第第8章章 查找查找 8.1 查找的基本概念查找的基本概念8.2 靜態(tài)查找表靜態(tài)查找表 8.3 動態(tài)查找表動態(tài)查找表 8.4 哈希表哈希表 第8章 查找 8.1 查找的基本概念查找的基本概念 關鍵字關鍵字：數(shù)據(jù)元素的某個數(shù)據(jù)項的值，用它可以標識列表：數(shù)據(jù)元素的某個數(shù)據(jù)項的值，用它可以標識列表中的一個或一組數(shù)據(jù)元素。如果一個關鍵字可以唯一標識列表中的一個或一組數(shù)據(jù)元素。如果一個關鍵字可以唯一標識列表中的一個數(shù)據(jù)元素，中的一個數(shù)據(jù)元素， 則稱其為則稱其為主關鍵字主關鍵字，否則，否則為為次關鍵字次關鍵字。當數(shù)據(jù)元素僅有一個數(shù)據(jù)項時，當數(shù)據(jù)元素僅有一個數(shù)據(jù)項時， 數(shù)據(jù)元素的值就是關鍵字。

2、數(shù)據(jù)元素的值就是關鍵字。 第8章 查找 查找查找：根據(jù)給定的關鍵字值，在查找表中確定一個其關鍵：根據(jù)給定的關鍵字值，在查找表中確定一個其關鍵字與給定值相同的數(shù)據(jù)元素，并返回該數(shù)據(jù)元素在查找表中的字與給定值相同的數(shù)據(jù)元素，并返回該數(shù)據(jù)元素在查找表中的位置。若找到相應的數(shù)據(jù)元素，則稱查找是成功的，否則稱查位置。若找到相應的數(shù)據(jù)元素，則稱查找是成功的，否則稱查找是失敗的，此時應返回空地址及失敗信息，并可根據(jù)要求插找是失敗的，此時應返回空地址及失敗信息，并可根據(jù)要求插入這個不存在的數(shù)據(jù)元素。入這個不存在的數(shù)據(jù)元素。 第8章 查找 8.2 靜態(tài)查找表靜態(tài)查找表 8.2.1 順序查找法順序查找法 順序查找

3、法的過程是：從表中最后一個記錄開始，逐個進順序查找法的過程是：從表中最后一個記錄開始，逐個進行記錄的關鍵字和給定值的比較，若某個記錄的關鍵字和給定行記錄的關鍵字和給定值的比較，若某個記錄的關鍵字和給定值比較相等，則查找成功，否則查找失敗。存儲結構通常為順值比較相等，則查找成功，否則查找失敗。存儲結構通常為順序結構，也可為鏈式結構。序結構，也可為鏈式結構。 第8章 查找 /靜態(tài)查找表的順序存儲結構靜態(tài)查找表的順序存儲結構typedef struct ElemType *elem; /數(shù)據(jù)元素存儲空間基址，建數(shù)據(jù)元素存儲空間基址，建 /表時按實際長度分配，表時按實際長度分配，0號單元留空號單元留空

4、 int length; /表長度表長度 SSTable; 第8章 查找 基于順序結構的算法如下：基于順序結構的算法如下： int Search_Seq(SSTable ST, KeyType key) / 在順序表在順序表ST中順序查找其關鍵字等于中順序查找其關鍵字等于key的數(shù)據(jù)元素。若的數(shù)據(jù)元素。若 找到，則函數(shù)值為該元素在表中的位置，否則為找到，則函數(shù)值為該元素在表中的位置，否則為0。算法。算法9.1 int i; ST.elem0.key=key; / 哨兵哨兵 for(i=ST.length;!EQ(ST.elemi.key,key);-i); / 從后往前找從后往前找 retur

5、n i; / 找不到時，找不到時，i為為0 其中其中ST.elem0稱為監(jiān)視哨，可以起到防止越界的作用。稱為監(jiān)視哨，可以起到防止越界的作用。第8章 查找 8.2.2 有序表的查找有序表的查找 折半查找法又稱二分法查找法，這種方法適用于有序表。折半查找法又稱二分法查找法，這種方法適用于有序表。其基本過程是其基本過程是：將表中間位置記錄的關鍵字與查找關鍵字比較，：將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，前、后兩個子表，如果中間位置記錄

6、的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復以上則進一步查找前一子表，否則進一步查找后一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。存在為止，此時查找不成功。 第8章 查找 圖圖8.1 折半查找示意圖折半查找示意圖 第8章 查找 折半查找的算法如下：折半查找的算法如下： int Search_Bin(SSTable ST, KeyType key) / 在有序表在有序表ST中折半查找其關鍵字等于中折半查找其關鍵字等于key的數(shù)據(jù)元素。若的數(shù)據(jù)元素。若找到，則函數(shù)

7、值為該元素在表中的位置，否則為找到，則函數(shù)值為該元素在表中的位置，否則為0。算法。算法9.2 low=1 ; high=ST.length; / 置區(qū)間初值置區(qū)間初值 while(lowlchild=NULL； free(p)； (2) 若若p結點只有左子樹，或只有右子樹，則可將結點只有左子樹，或只有右子樹，則可將p的左的左子樹或右子樹直接改為其雙親結點子樹或右子樹直接改為其雙親結點f的左子樹，即：的左子樹，即：f-lchild=p-lchild（或（或f-lchild=p-rchild）；）； free(p)； (3) 若若p既有左子樹，既有左子樹， 又有右子樹，又有右子樹， 如圖如圖8.6

8、 (a) 所示。所示。 此時有兩種處理方法：此時有兩種處理方法： 第8章 查找 方法方法1: 首先找到首先找到p結點在中序序列中的直接前驅結點在中序序列中的直接前驅s結點，結點，如圖如圖8.6 (b) 所示，然后將所示，然后將p的左子樹改為的左子樹改為f的左子樹，而將的左子樹，而將p的右子樹改為的右子樹改為s的右子樹：的右子樹：f-lchild=p-lchild；s-rchild= p-rchild； free(p)；結果如圖；結果如圖8.6 (c) 所示。所示。 方法方法2 : 首先找到首先找到p結點在中序序列中的直接前驅結點在中序序列中的直接前驅s結點，結點， 如圖如圖8.6 (b) 所示

9、，然后用所示，然后用s結點的值替代結點的值替代p結點的值，再將結點的值，再將s結結點刪除，原點刪除，原s結點的左子樹改為結點的左子樹改為s的雙親結點的雙親結點q的右的右子樹：子樹：p-data=s-data；q-rchild= s-lchild；free(s)；結果如圖；結果如圖8.6 (d) 所示。所示。 第8章 查找 fPLPRPFfp(a) P的左右子樹均不空QLSLCFfp(d) 將原P結點的值改為S結點的值，刪除原S結點 并將原S的左子樹改為Q的右子樹QqCLSPRcSLPRCf(c) 將P的 左子樹改為F的左子樹，將P的右子樹改為S的右子樹SCLFcQLSLCFpQqCLPPRcS

10、s(b) S為P的直接前驅 圖圖8.6 二叉排序樹刪除示意二叉排序樹刪除示意 第8章 查找 3. 二叉排序樹的查找二叉排序樹的查找 因為二叉排序樹可看作是一個有序表，所以在二叉排因為二叉排序樹可看作是一個有序表，所以在二叉排序樹上進行查找與折半查找類似，也是一個逐步縮小查找序樹上進行查找與折半查找類似，也是一個逐步縮小查找范圍的過程。范圍的過程。 根據(jù)二叉排序樹的特點，首先將待查關鍵字根據(jù)二叉排序樹的特點，首先將待查關鍵字k與根結點關鍵字與根結點關鍵字t進行比較，如果：進行比較，如果： (1） k=t， 則返回根結點地址；則返回根結點地址； (2） kt， 則進一步查右子樹。則進一步查右子樹。

11、 第8章 查找 8.3.2 平衡二叉樹平衡二叉樹 平衡二叉樹又稱為平衡二叉樹又稱為AVL樹樹。一棵平衡二叉樹或者是空樹，。一棵平衡二叉樹或者是空樹，或者具有下列性質的二叉排序樹：或者具有下列性質的二叉排序樹： 左子樹與右子樹的高度之左子樹與右子樹的高度之差的絕對值小于等于差的絕對值小于等于1； 左子樹和右子樹也是平衡二叉樹。左子樹和右子樹也是平衡二叉樹。 平衡因子平衡因子：結點的左子樹深度與右子樹深度之差。：結點的左子樹深度與右子樹深度之差。 顯然，對一棵平衡二叉排序樹而言，顯然，對一棵平衡二叉排序樹而言， 其所有結點的平衡因其所有結點的平衡因子只能是子只能是-1、 0，或，或1。當我們在一個

12、平衡二叉排序樹上插入一。當我們在一個平衡二叉排序樹上插入一個結點時，有可能導致失衡，即出現(xiàn)絕對值大于個結點時，有可能導致失衡，即出現(xiàn)絕對值大于1的平衡因子，的平衡因子，如如2、-2。圖。圖8.7中給出了一棵平衡二叉排序樹和一棵失去平衡中給出了一棵平衡二叉排序樹和一棵失去平衡的二叉的二叉排序樹。排序樹。 第8章 查找 圖圖8.7 平衡與不平衡的二叉排序樹平衡與不平衡的二叉排序樹 208070302560405011110006030255040120058100(a) 一棵平衡二叉排序樹(b) 一棵失去平衡的二叉排序樹第8章 查找 u 已知一棵平衡二叉排序樹如圖已知一棵平衡二叉排序樹如圖8.9（

13、a）所示。在）所示。在A的左子樹的左子樹的左子樹上插入的左子樹上插入15后，導致失衡，如圖后，導致失衡，如圖8.9（b）所示。為恢復）所示。為恢復平衡并保持二叉排序樹的特性，可將平衡并保持二叉排序樹的特性，可將A改為改為B的右子，的右子，B原來原來的右子改為的右子改為A的左子，如圖的左子，如圖8.9（c）所示。這相當于以）所示。這相當于以B為軸，為軸，對對A做了一次順時針旋轉做了一次順時針旋轉。 圖圖8.9 不平衡二叉樹的調整不平衡二叉樹的調整(1) 6015302025604010000AB(a) 一棵平衡二叉排序樹(b) 插入15后 失去平衡302025604020110AB0301520

14、40250000BA01(c) 調整后的二叉排序樹第8章 查找 u 已知一棵平衡二叉排序樹如圖已知一棵平衡二叉排序樹如圖8.10（a）所示。在）所示。在A的右子樹的右子樹B的右子樹上插入的右子樹上插入70后，導致失衡，如圖后，導致失衡，如圖8.10（b）所示。為恢復）所示。為恢復平衡并保持二叉排序樹的特性，平衡并保持二叉排序樹的特性， 可將可將A改為改為B的左子，的左子，B原來的原來的左子改為左子改為A的右子，如圖的右子，如圖8.10（c）所示。這相當于以）所示。這相當于以B為軸，為軸， 對對A做了一次逆時針旋做了一次逆時針旋轉。轉。 圖圖8.10 不平衡二叉樹的調整不平衡二叉樹的調整(2)

15、30607060302040251000AB(a) 一棵平衡二叉排序樹(b) 插入70后失去平衡204025200AB0202560400000BA0(c) 調整后的二叉排序樹70111300第8章 查找 u 已知一棵平衡二叉排序樹如圖已知一棵平衡二叉排序樹如圖8.11（a）所示。）所示。 在在A的的左子樹左子樹B的右子樹上插入的右子樹上插入45后，導致失衡，如圖后，導致失衡，如圖8.11（b）所示。為恢復平衡并保持二叉排序樹的特性，可所示。為恢復平衡并保持二叉排序樹的特性，可首先將首先將B改為改為C的左子，而的左子，而C原來的左子改為原來的左子改為B的右子；然后將的右子；然后將A改改為為C的

16、右子，的右子， C原來的右子改為原來的右子改為A的左子，的左子， 如圖如圖8.11（c）所示。所示。這相當于對這相當于對B做了一次逆時針旋轉，做了一次逆時針旋轉， 對對A做了一次做了一次順時針旋轉。順時針旋轉。 第8章 查找 圖圖8.11 不平衡二叉樹的調整不平衡二叉樹的調整(3) (a) 一棵平衡二叉排序樹507000103095204090801000B06085AC0000(b) 插入45后失去平衡507010103095204090802101B06085AC00000458595(c) 調整后的二叉排序樹45103090204080600001B05070C00001A00第8章 查

17、找 u 已知一棵平衡二叉排序樹如圖已知一棵平衡二叉排序樹如圖8.12（a）所示。）所示。 在在A的右的右子樹的左子樹上插入子樹的左子樹上插入55后，導致失衡，如圖后，導致失衡，如圖8.12（b）所示。）所示。 為恢復平衡并保持二叉排序樹的特性，可首先將為恢復平衡并保持二叉排序樹的特性，可首先將B改為改為C的的右子，右子， 而而C原來的右子改為原來的右子改為B的左子；然后將的左子；然后將A改為改為C的左子，的左子，C原來的左子改為原來的左子改為A的右子，如的右子，如圖圖8.12（c）所示。這相當于）所示。這相當于對對B做了一次順時針旋轉，做了一次順時針旋轉， 對對A做了一次逆時針旋轉。做了一次逆

18、時針旋轉。 第8章 查找 圖8.12 不平衡二叉樹的調整(4) (c) 調整后的二叉排序樹(a) 一棵平衡二叉排序樹(b) 插入55后失去平衡859550709010208040100003060A00B0000C859550709010208040200003060A11B000C15508595551030902040806000A05070C0001B00100第8章 查找 1） LL型型 圖圖8.13 二叉排序樹的二叉排序樹的LL型平衡旋轉型平衡旋轉 (a) 插入新結點S后 失去平衡(b) 調整后恢復平衡ABBLBRARS21BABLARBRS00第8章 查找 2） LR型型 圖8.1

19、4 二叉排序樹的LR型平衡旋轉 (a) 插入新結點S后失去平衡(b) 調整后恢復平衡ABCLARS21CCR1BLCACLARCRS01B0BL第8章 查找 圖8.15 二叉排序樹的RR型平衡旋轉 (a) 插入新結點S后失去平衡(b) 調整后恢復平衡ABBRBLALS21BABRALBLS003） RR型型第8章 查找 4） RL型型 圖8.16 二叉排序樹的RL型平衡旋轉 (b) 調整后恢復平衡(a) 插入新結點S后失去平衡ABBRCRS21CCL1ALCACRALCLS01B0BR第8章 查找 8.4 哈希表哈希表 哈希法又稱散列法、雜湊法或關鍵字地址計算法哈希法又稱散列法、雜湊法或關鍵字

20、地址計算法等，相應等，相應的表稱為哈希表。這種方法的基本思想：首先在元素的關鍵字的表稱為哈希表。這種方法的基本思想：首先在元素的關鍵字k和元素的存儲位置和元素的存儲位置p之間建立一個對應關系之間建立一個對應關系H，使得，使得p=H(k)，H稱為哈希函數(shù)。創(chuàng)建哈希表時，把關鍵字為稱為哈希函數(shù)。創(chuàng)建哈希表時，把關鍵字為k的元素直接存的元素直接存入地址為入地址為H(k)的單元；以后當查找關鍵字為的單元；以后當查找關鍵字為k的元素時，再利的元素時，再利用哈希函數(shù)計算出該元素的存儲位置用哈希函數(shù)計算出該元素的存儲位置p=H(k)，從，從而達到按關而達到按關鍵字直接存取元素的目的。鍵字直接存取元素的目的。

21、 第8章 查找 當關鍵字集合很大時，關鍵字值不同的元素可能會映象當關鍵字集合很大時，關鍵字值不同的元素可能會映象到哈希表的同一地址上，到哈希表的同一地址上，即即 k1k2，但，但 H（k1）=H（k2），），這種現(xiàn)象稱為沖突，此時稱這種現(xiàn)象稱為沖突，此時稱k1和和k2為同義詞為同義詞。實際中，沖突實際中，沖突是不可避免的，是不可避免的， 只能通過改進哈希函數(shù)的性能來減少沖突。只能通過改進哈希函數(shù)的性能來減少沖突。 綜上所述，綜上所述， 哈希法主要包括以下兩方面的內(nèi)容：哈希法主要包括以下兩方面的內(nèi)容： (1） 如何構造哈希函數(shù)；如何構造哈希函數(shù)； (2） 如何處理沖突。如何處理沖突。 第8章 查

22、找 8.4.1 哈希函數(shù)的構造方法哈希函數(shù)的構造方法 1. 直接定址法直接定址法 哈希函數(shù)為關鍵字的線性函數(shù)，即哈希函數(shù)為關鍵字的線性函數(shù)，即H(key)=key或者或者H(key)=akey+b (a和和b為常數(shù)為常數(shù))。 此方法適合于此方法適合于地址集合的大小地址集合的大小=關鍵字集合的大小關鍵字集合的大小。 例：例：P253 解放后出生的人口調查表解放后出生的人口調查表第8章 查找 2. 數(shù)字分析法數(shù)字分析法 如果事先知道關鍵字集合，并且每個關鍵字的位數(shù)比哈希如果事先知道關鍵字集合，并且每個關鍵字的位數(shù)比哈希表的地址碼位數(shù)多時，可以從關鍵字中選出分布較均勻的若干表的地址碼位數(shù)多時，可以從

23、關鍵字中選出分布較均勻的若干位，構成哈希地址。位，構成哈希地址。第8章 查找 例如有例如有80個記錄，關鍵字為個記錄，關鍵字為8位十進制整數(shù)位十進制整數(shù)d1d2d3d7d8，如哈，如哈希表長取希表長取100，則哈希表的地址空間為：，則哈希表的地址空間為： 0099。假設經(jīng)過分。假設經(jīng)過分析，各關鍵字中析，各關鍵字中d4和和d7的取值分布較均勻，的取值分布較均勻， 則哈希函數(shù)為：則哈希函數(shù)為：H(key)=H(d1d2d3d7d8)=d4d7。例如，。例如， H(81346532)=43，H(81301367)=06。 8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8

24、7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 78 1 3 3 8 9 6 78 1 3 5 4 1 5 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5 數(shù)字分布近乎隨機數(shù)字分布近乎隨機,可取其中任意兩位或取其中可取其中任意兩位或取其中兩位與另兩位的疊加求和后兩位與另兩位的疊加求和后舍去進位作哈希地址舍去進位作哈希地址第8章 查找 3. 平方取中法平方取中法 當無法確定關鍵字中哪幾位分布較均勻時，當無法確定關鍵字中哪幾位分布較均勻時， 可以先求出關鍵可以先求出關鍵字的平方值，然后按需要取平方值的中間幾位作為哈希地址。字的平方值，然后按需要取平方值的中間

25、幾位作為哈希地址。這這是因為：平方后中間幾位和關鍵字中每一位都相關，故不同關鍵是因為：平方后中間幾位和關鍵字中每一位都相關，故不同關鍵字會以較高的概率產(chǎn)生不同的哈希地址。字會以較高的概率產(chǎn)生不同的哈希地址。 第8章 查找 例：我們把英文字母在字母表中的位置序號作為該英文字母的內(nèi)例：我們把英文字母在字母表中的位置序號作為該英文字母的內(nèi)部編碼。例部編碼。例K的內(nèi)部編碼為的內(nèi)部編碼為11，E的內(nèi)部編碼為的內(nèi)部編碼為05，Y的內(nèi)部編的內(nèi)部編碼為碼為25，A的內(nèi)部編碼為的內(nèi)部編碼為01, B的內(nèi)部編碼為的內(nèi)部編碼為02。 由此組成關鍵字由此組成關鍵字“KEYA”的內(nèi)部代碼為的內(nèi)部代碼為11052501，

26、同理我，同理我們可以得到關鍵字們可以得到關鍵字“KYAB”、“AKEY”、 “BKEY”的內(nèi)部編的內(nèi)部編碼。之后對關鍵字進行平方運算后，取出第碼。之后對關鍵字進行平方運算后，取出第7到第到第9位作為該關鍵位作為該關鍵字哈希字哈希地址，地址， 如表如表8 - 1所示。所示。 第8章 查找 表表8-1 平方取中法求得的哈希地址平方取中法求得的哈希地址 關鍵字關鍵字 內(nèi)部編碼內(nèi)部編碼 內(nèi)部編碼的平方值內(nèi)部編碼的平方值 H(k)關鍵字的哈希地址關鍵字的哈希地址 KEYA 11052501 122157778355001 778 KYAB 11250102 126564795010404 795AKEY

27、 01110525 001233265775625 265BKEY 02110525 004454315775625 315第8章 查找 4. 折疊法折疊法 將關鍵字分割成位數(shù)相同的幾部分將關鍵字分割成位數(shù)相同的幾部分(最后一部分位數(shù)可不最后一部分位數(shù)可不同同)，然后取這幾部分的疊加和，然后取這幾部分的疊加和(舍去進位舍去進位)作為哈希地址。作為哈希地址。圖圖8.23 由疊加法求哈希地址由疊加法求哈希地址 12 360 324 711 20 2 0+)1 1 0 512 33 0 624 72 1 10 2 0+) 9 0 7(a) 移位疊加移位疊加 (b) 間界疊加間界疊加 第8章 查找 5

28、. 除留余數(shù)法除留余數(shù)法 假設哈希表長為假設哈希表長為m，p為小于等于為小于等于m的最大素數(shù)，則哈希函的最大素數(shù)，則哈希函數(shù)為：數(shù)為： H(key)= key % p， 其中其中%為模為模p取余運算。取余運算。 例如，已知待散列元素為（例如，已知待散列元素為（18，75，60，43，54，90，46），表長），表長m=10， p=7， 則有則有H(18)=18 % 7=4 H(75)=75 % 7=5 H(60)=60 % 7=4 H(43)=43 % 7=1 H(54)=54 % 7=5 H(90)=90 % 7=6 H(46)=46 % 7=4 第8章 查找 圖8.24 除留余數(shù)法求哈希地

29、址 此時沖突較多。此時沖突較多。 為減少沖突，為減少沖突， 可取較大的可取較大的m值和值和p值，值， 如如m=p=13， 結果如下：結果如下： H(18)=18 % 13=5 H(75)=75 % 13=10 H(60)=60 % 13=8 H(43)=43 % 13=4 H(54)=54 % 13=2 H(90)=90 % 13=12 H(46)=46 % 13=7 544318466075900 1 2 3 4 5 6 7 8 9 10 11 12 第8章 查找 6. 隨機數(shù)法隨機數(shù)法 采用一個隨機函數(shù)作哈希函數(shù)，即采用一個隨機函數(shù)作哈希函數(shù)，即H(key)=random(key)。 在實

30、際應用中，在實際應用中， 應根據(jù)具體情況，采用不同的哈希函數(shù)。應根據(jù)具體情況，采用不同的哈希函數(shù)。通常應考慮以下五個因素：通常應考慮以下五個因素： 計算哈希函數(shù)所需的時間計算哈希函數(shù)所需的時間 關鍵字的長度。關鍵字的長度。 哈希表的大小。哈希表的大小。 關鍵字的分布情況。關鍵字的分布情況。 記錄查找的頻率。記錄查找的頻率。 第8章 查找 8.4.2 處理沖突的方法處理沖突的方法 1. 開放定址法開放定址法 這種方法也稱再散列法，其基本思想是：當關鍵字這種方法也稱再散列法，其基本思想是：當關鍵字key的的哈希地址哈希地址p= H（key）出現(xiàn)沖突時，以）出現(xiàn)沖突時，以p為基礎，產(chǎn)生另一個為基礎，

31、產(chǎn)生另一個哈希地址哈希地址p1，如果，如果p1仍然沖突，再以仍然沖突，再以p為基礎，產(chǎn)生另一個哈為基礎，產(chǎn)生另一個哈希地址希地址p2，直到找出一個不沖突的哈希地址，直到找出一個不沖突的哈希地址pi，將相應，將相應元素存入其中。這種方法有元素存入其中。這種方法有一個通用的再散列函數(shù)形式：一個通用的再散列函數(shù)形式： ,)%)(mdkeyHHiii=1， 2， ， n 第8章 查找 其中其中H(key)為哈希函數(shù)，為哈希函數(shù)，m為表長，為表長，di稱為增量序列。增量稱為增量序列。增量序列的取值方式不同，相應的再散列方式也不同。主要有以下三序列的取值方式不同，相應的再散列方式也不同。主要有以下三種：種

32、： 線性探測再散列線性探測再散列 di=1，2，3， m-1 這種方法的特點這種方法的特點是：是： 沖突發(fā)生時，順序查看表中下一單元，沖突發(fā)生時，順序查看表中下一單元， 直到找出一個空單元或查遍全表。直到找出一個空單元或查遍全表。 二次探測再散列二次探測再散列 di= 12，-12， 22，-22，k2，-k2 (km/2) 這種方法的特點這種方法的特點是：沖突發(fā)生時，在表的左右進行跳躍式探是：沖突發(fā)生時，在表的左右進行跳躍式探測，測， 比較靈活。比較靈活。 第8章 查找 偽隨機探測再散列偽隨機探測再散列 di=偽隨機數(shù)序列。偽隨機數(shù)序列。 具體實現(xiàn)時，應建立一個偽隨機數(shù)發(fā)生器，（如具體實現(xiàn)時

33、，應建立一個偽隨機數(shù)發(fā)生器，（如i=(i+p) % m），）， 并給定一個隨機數(shù)做起并給定一個隨機數(shù)做起點。點。 第8章 查找 例，已知哈希表長度例，已知哈希表長度m=11，哈希函數(shù)為：，哈希函數(shù)為：H(key)= key % 11， 則則H(47)=3，H(26)=4，H(60)=5，假設下一個關鍵字為，假設下一個關鍵字為69，則，則H(69)=3，與，與47沖突。如果用線性探測再散列處理沖突，沖突。如果用線性探測再散列處理沖突，下一個哈希地址為下一個哈希地址為H1=（3+1）% 11=4， 仍然沖突，再找下一仍然沖突，再找下一個哈希地址為個哈希地址為H2=(3+2）% 11=5，還是沖突，

34、繼續(xù)找下一個哈，還是沖突，繼續(xù)找下一個哈希地址為希地址為H3=（3+3）% 11=6，此時不，此時不再沖突，將再沖突，將69填入填入6號單號單元，參見圖元，參見圖8.25(a)。 第8章 查找 如果用二次探測再散列處理沖突，下一個哈希地址為如果用二次探測再散列處理沖突，下一個哈希地址為H1=（3+12）% 11=4， 仍然沖突，再找下一個哈希地址為仍然沖突，再找下一個哈希地址為H2=（3-12）% 11=2，此時不再沖突，將，此時不再沖突，將69填入填入2號單元，參號單元，參見圖見圖8.25(b)。 如果用偽隨機探測再散列處理沖突，且偽隨機如果用偽隨機探測再散列處理沖突，且偽隨機數(shù)序列為：數(shù)序列為：2，5，9則下一個哈希地址為則下一個哈希地址為H1=（3+2）% 11=5，仍然沖突，再找下一個哈希地址為，仍然沖突，再找下一個哈希地址為H2=（3+5）% 11=8，此時