1、 基本概念線性表的查找 樹表的查找 散列(Hash)技術 第八章 查找8.1查找的基本概念 查找（Searching）的定義是：在含有n條記錄的表（文件）中找出關鍵字等于給定值K的記錄。若找到，則查找成功，返回該記錄的信息或該記錄在表（文件）中的位置；否則查找失敗，返回相關的指示信息。 若在查找的同時對表做修改操作（如插入和刪除等），則相應的表稱之為動態查找表（Dynamic Search Table）。否則稱之為靜態查找表(Static Search Table)。 若整個查找過程都在內存進行，則稱之為內查找；反之，若查找過程中需要訪問外存，則稱之為外查找 查找表的數據結構表示 如何分析算法

2、優劣？主要分析算法運算時所需要的時間和其存儲結構占用的內存空間。而對于查找算法，執行的時間通常取決于關鍵字的比較次數，所以本章經常用平均比較次數，即平均查找長度 ASL（Average Search Length）其中：1、n是結點的個數；2、Pi是查找第i個結點的概率。若不特別聲明 ，認為每個結點的查找概率相等，即 pl = p2 = pn = 1/n3、ci是找到第i個結點所需進行的比較次數ASL= 平均查找長度 ASL（Average Search Length）定義為 ：一、順序查找(Sequential Search) 基本思想是：從表的一端開始，順序掃描線性表，依次將掃描到的結點關

3、鍵字和給定值K相比較。若當前掃描到的結點關鍵字與K相等，則查找成功；若掃描結束后，仍未找到關鍵字等于K的結點，則查找失敗。8.2 線性表的查找基于順序結構的順序查找算法 類型說明 typedef struct KeyType key； /*KeyType由用戶定義*/ InfoType otherinfo； /*此類型依賴于應用*/ NodeType； typedef NodeType Seqlistn+1； /*多出0號單元用作監視哨*/具體算法 int SeqSearch(Seqlist R，KeyType K) /*在順序表R1.n中順序查找關鍵字為K的結點，*/ /*成功時返回找到的結

4、點位置，失敗時返回0*/ int i； R0.key=K； /*設置監視哨*/ for(i=n；Ri.key!=K;i-)；/*從表后往前找*/ return i； /*若i為0，表示查找失敗，否則Ri為要找的結點*/ /*SeqSearch*/ 算法分析查找成功時的順序查找的平均查找長度： 在等概率情況下，pi=1/n(1in)，故成功的平均查找長度為 ASL= =(n+2+1)/n=(n+1)/2即查找成功時的平均比較次數約為表長的一半。順序查找的缺點 查找效率低。順序查找的優點 算法簡單，且對表的結構無任何要求，無論是用向量還是用鏈表來存放結點，也無論結點之間是否按關鍵字有序，它都同樣適

5、用。二分查找又稱折半查找，它是一種效率較高的查找方法。二分查找要求：要求線性表是有序表，即表中結點按關鍵字有序，并且要用向量作為表的存儲結構。不妨設有序表是遞增有序的。二、二分查找 （1）首先確定該區間的中點位置 mid = （2）然后將中間位置記錄的鍵值Rmid.key和所給關鍵字K進行比較：若相等，則查找成功并返回此位置，否則須確定新的查找區間，繼續二分查找。 二分查找的基本思想是：例：設算法的輸入實例中有序的關鍵字序列為： 05，13，19，21，37，56，64，75，80，88，92。查找的關鍵字K=21 第一步：這里的n=11,mid=(1+11)/2=605，13，19，21，3

6、7，56，64，75，80，88，92 第二步：mid=(1+5)/2=305，13，19，21，37，56，64，75，80，88，92 第三步： mid=(4+5)/2=405，13，19，21，37，56，64，75，80，88，92此時Rmid.keyK，return mid4。 二分查找算法int BinSearch(SeqList R，KeyType K) int low=1，high=n，mid； while(lowK) high=mid-1; else low=mid+1； return 0； 確定新的查找區間二分查找過程可用二叉樹來描述：把當前查找區間的中間位置上的結點作為根

7、，左子表和右子表中的結點分別作為根的左子樹和右子樹。由此得到的二叉樹，稱為描述二分查找的判定樹(Decision Tree)或比較樹(Comparison Tree)。二分查找判定樹二分查找判定樹的組成如對表R3，7，11，19，30，115，136，141的查找過程： 3 7 11 19 30 115 136 141 3 7 11 19 30 115 136 141Low mid highLow mid high46782135如k=115的記錄結點編號為6，處于第二層，則比較次數只有兩次就可找到（這樣的記錄共有兩個21=2）；查找第三層的記錄需要三次比較（這樣的記錄共有四個22=4 ）；查

8、找第k層的記錄需要k次比較（這樣的記錄共有2k-1個）;等等。假定每個記錄的查找概率相等，即為1/n，則其平均查找次數為：ASL= =1/n ci=1/n(1*20+2*21+3*22+k*2k-1+)= 1/n i*2i-1 ; 而 i*2i-1 =k2k-2k-1 k又根據二叉樹的性質：k=log2(n+1)故： ASL=（n+1）/nlog2(n+1)-1 log2(n) 當n很大時二分查找的平均查找長度 二分查找成功時的平均查找長度為： ASLbnlog2(n) 二分查找在查找失敗時所需比較的關鍵字個數不超過判定樹的深度，在最壞情況下查找成功的比較次數也不超過判定樹的深度。即為：二分查

9、找的優點和缺點 雖然二分查找的效率高，但是要將表按關鍵字排序（有序表）。 二分查找只適用順序存儲結構。為保持表的有序性，在順序結構里插入和刪除都必須移動大量的結點。 三、分塊查找（索引順序查找 ） 分塊查找表存儲結構 分塊查找的特點是：按表內記錄的某種屬性把表（文件）分成b個塊（子表），并建立一個相應的“索引表”，索引表中每個元素對應一個塊，而在索引表中是按其關鍵字有序，但是每一塊中的記錄的存放是任意的，塊與塊之間必須是有序的。即分塊查找的前提是：文件由分塊有序的線性表和索引表組成。分塊查找表由分塊有序的線性表和索引表組成。（1）分塊有序的線性表將表（文件）R1.n平均分為b塊；每一塊中的關鍵

10、字不一定有序，但前一塊中的最大關鍵字必須小于后一塊中的最小關鍵字，即表是分塊有序的。（2）索引表抽取各塊中的最大關鍵字及其起始位置構成一個索引表IDl.b，即：IDi(1ib)中存放第i塊的最大關鍵字及該塊在表R中的起始位置。由于表R是分塊有序的，所以索引表是一個遞增有序表。1、分塊查找表的存儲結構分塊查找的基本思想是：（1）首先查找索引表索引表是有序表，可采用二分查找或順序查找，以確定待查的結點在哪一塊。 （2）然后在已確定的塊中進行順序查找 由于塊內無序（也可有序），只能用順序查找。2、分塊查找的基本思想例： 圖8.2所示的表及其索引表是滿足上述要求的分塊查找表，其中R只有18個結點，被分

11、成3塊，每塊中有6個結點，第一塊中最大關鍵字22小于第二塊中最小關鍵字24，第二塊中最大關鍵字48小于第三塊中最小關鍵字49。 22488617132212138920334244382448605874498653ID塊內最大鍵值塊內第一個元素序號（1）先在索引表中查找,來確定關鍵字等于給定值K=24的結點所在的塊 因為索引表小，不妨用順序查找方法查找索引表。即首先將K依次和索引表中各關鍵字比較，直到找到第1個關鍵字大小等于K的結點，由于K48，所以關鍵字為24的結點若存在的話，則必定在第二塊中；然后，由ID2.addr找到第二塊的起始地址7，從該地址開始在R7.12中進行順序查找，直到R1

12、1.key=K為止。（2）在所確定的塊內查找關鍵字等于給定值K=30的結點 在第二塊內查找。因在該塊中查找不成功，故說明表中不存在關鍵字為30的結點。進行下列查找：算法分析 分塊查找是兩次查找過程。整個查找過程的平均查找長度是兩次查找的平均查找長度之和。 以二分查找來確定塊，分塊查找成功時的平均查找長度(在索引表中用二分查找，在塊內用順序查找) ASLblk= ASLbn+ASLsqlog2(b+1)-1+(s+1)/2log2(n/s+1)+s/2 以順序查找確定塊，分塊查找成功時的平均查找長度 ASLblk=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s) 在表中插入或刪除一個

13、記錄時，只要找到該記錄所屬的塊，就在該塊內進行插入和刪除運算。 因塊內記錄的存放是任意的，所以插入或刪除比較容易，無須移動大量記錄。 分塊查找的優點8.3 樹表的查找1、二叉排序樹的定義 二叉排序樹(Binary Sort Tree)又稱二叉查找(搜索)樹(Binary Search Tree)。其定義為：二叉排序樹或者是空樹，或者是滿足如下性質的二叉樹：（1）若它的左子樹非空，則左子樹上所有結點的值均小于根結點的值；（2）若它的右子樹非空，則右子樹上所有結點的值均大于根結點的值；（3）左、右子樹本身又各是一棵二叉排序樹。 （1） 二叉排序樹中任一結點x，其左(右)子樹中任一結點y(若存在)的

14、關鍵字必小(大)于x的關鍵字。（2） 二叉排序樹中，各結點關鍵字是惟一的。（3） 按中序遍歷該樹所得到的中序序列是一個遞增有序序列。二叉排序樹的特點 要查找鍵值等于k的記錄，最先與根結點的鍵值比較，若二者相等，則查找成功 。若k值小于根結點的鍵值，則繼續查找左子樹，反之查找右子樹。若沿某條路經碰到一個端點（葉子）還末查到，則查找不成功，這也是靜態表的查找。二叉排序樹的查找算法：二叉排序樹的存儲結構typedef int KeyType； typedef struct node KeyType key； /*關鍵字類型*/ infoType otherinfo； /*結點其它信息類型*/ str

15、uct node *lchild，*rchild； BSTNode； /*二叉排序樹的結點類型*/typedef BSTNode *BSTree； lchildkeyotherinforchild在二叉排序樹中插入新結點，要保證插入后仍滿足BST性質。其插入過程是： 1)若二叉排序樹T為空，則為待插入的關鍵字key申請一個新結點，并令其為根； 2)若二叉排序樹T不為空，則將key和根的關鍵字比較：(a)若二者相等，則說明樹中已有此關鍵字key，無須插入。(b)若keyTkey，則將它插入根的右子樹中。 二叉排序樹插入新結點的過程二叉排序樹插入新結點的算法void InsertBST(BSTre

16、e Tptr，Keytype key) BSTNode *f，*p=Tptr； while(p) /*p不空*/ if(p-key=key) return； /*找到了，則不插入*/ f=p； /*f是p的雙親*/ p=(keykey)?p-lchild:p-rchild; p=(BSTNode*)malloc(sizeof(BSTNode)；p-key=key； p-lchild=p-rchild=NULL； if(TPtr=NULL) /*是空樹*/Tptr=p； /*新結點作為根插入*/else /*不是空樹*/if(keykey) f-lchild=p；/*新結點作為左孩子插入*/el

17、se f-rchild=p； /*新結點作為右孩子插入*/ 從空的二叉排序樹開始，每輸入一個結點數據，就調用一次插入算法將它插入到當前已生成的二叉排序樹中。 二叉排序樹的生成 BSTree CreateBST(void) BSTree T=NULL； KeyType key； scanf(“d”，&key)；/*輸入一個鍵值為key的結點*/ while(key) InsertBST(&T，key)；/*將鍵值為key的結點插入到二叉樹中*/ scanf(d，&key)； /*輸入一個鍵值為key的結點*/ return T； 輸入實例(5，3，7，2，4，8)，根據生成二叉排序樹算法生成二叉

18、排序樹的過程 553253753725374253748二叉排序樹的刪除 從二叉排序樹中刪除一個結點，不能把以該結點為根的子樹都刪去，并且還要保證刪除后所得的二叉樹仍然滿足BST性質。1) 進行查找（去找被刪結點） 查找時，令工作指針p指向當前訪問到的結點，parent指向p的雙親(其初值為NULL)。若樹中找不到被刪結點則返回，否則被刪結點是*p。刪除操作的一般步驟2) 刪去*p。 刪*p時，應將*p的子樹(若有)仍連接在樹上且保持BST性質不變。按*p的孩子數目分三種情況進行處理。 刪除*p結點的三種情況 a)*p是葉子(即它的孩子數為0) 無須連接*p的子樹，只需將*p的雙親*paren

19、t中指向被刪結點*p的指針域置空即可。 b)*p只有一個孩子*childi不論是左孩子還是右孩子 只需將*child和*p的雙親直接連接后，即可刪去*p。 c)*p有兩個孩子 先令q = p，將被刪結點的地址保存在q中；然后找*q的中序后繼*p。并在查找過程中仍用p為工作指針，parent記住*p的雙親位置。*q的中序后繼*p一定是*q的右子樹中最左下的結點，它無左子樹。因此，可以將刪去*q的操作轉換為刪去的*p的操作，即在釋放結點*p之前將其數據復制到*q中，就相當于刪去了*q,并將*p的子樹嫁接到樹上.回顧：二叉排序樹的特點1.若它的左子樹非空，則左子樹上所有結點的值均小于根結點的值；2.

20、若它的右子樹非空，則右子樹上所有結點的值均大于根結點的值；3.按中序遍歷該樹所得到的中序序列是一個遞增有序序列。 805012060110150557053中序遍歷（LVR）：50，53，55，60，70，80，110，120，150二叉排序樹的刪除 刪除操作的一般步驟:1. 查找要刪的結點 查找時，令工作指針p指向當前訪問到的結點，parent指向p的雙親(其初值為NULL)。若樹中找不到被刪結點則返回，否則被刪結點是*p。2.如果找到刪除結點*p 應將*p的子樹(若有)仍連接在樹上且保持二叉排序樹的性質不變FPCPRCLQQLSLS堅持的基本原則：刪結點時，保證二叉排序樹的性質不變。想：從

21、一棵二叉排序樹中刪除一個結點會出現哪幾種情況？分析：要刪除二叉排序樹中的*p結點，分三種情況：*p是葉子 *p只有一個子樹FPCPRCLQQLSLS注意：此時有四種情況（*p本身可以為左、右子樹，且*p的子樹也可以為左、右子樹）*p有兩個子樹1*p只有左子樹，用*p的左子樹的根代替*p SQPLP中序遍歷：Q S PL PSQPL中序遍歷：Q S PL(2)SPPLQ中序遍歷：PL P S QSPLQ中序遍歷：PL S Q(1)if(!p-rchild)/右子樹空則只需重接它的左子樹 tmp=p; p=p-lchild ; free(tmp);*p只有一個子樹的情況：中序遍歷：P PR S Q

22、SPRQ中序遍歷：PR S Q(3)SPPRQ中序遍歷：Q S P PRSQPR中序遍歷：Q S PR(4)SQPRP2.*p只有右子樹，用*p的右子樹的根代替*pif(!p-lchild)/左子樹空則只需重接它的右子樹 tmp=p; p=p-rchild ; free(tmp);*p有兩個子樹的情況： 分析： 針對*p有兩個子樹的情況，把*p的兩個子樹合并為一棵樹，然后將其連接到*p的雙親上。 1.刪除問題就轉化為第種情況。 2.要解決的問題轉化為如何將兩棵二叉排序樹合并為一棵二叉排序樹。 FPCPRCLQQLSLS問題：如何將兩棵二叉排序樹合并為一棵二叉排序樹?思考：還有沒有其它的合并方法

23、？SFPCPRCLQQLSLFPCPRCLQQLSLS分析：據二叉排序樹的性質：右子樹的值大于左子樹的值。因此，只要找到左子樹中值最大的結點（左子樹中最右邊的結點，該結點一定沒有右子樹），使其成為右子樹的雙親。SFPCPRCLQQLSLFPCPRCLQQLSLStmp=p-lchild; /1.要刪除結點的左子樹while(tmp-rchild!=0) tmp=tmp-rchild;/2.找到左子樹中最右邊的結/點，即最大的結點 tmp-rchild=p-rchild;/3.左子樹中最右邊的 成為右/子樹的雙親 tmp=p; p=p-lchild;/5.變為第二種情況處理(刪除) free(t

24、mp); /6.釋放要刪除的結點FPCPRCLQQLMS小結：二叉排序樹的刪除要刪除二叉排序樹中的*p結點,分三種情況：*p為葉子結點*p只有左子樹或右子樹*p只有左子樹，用*p的左孩子代替*p*p只有右子樹，用*p的右孩子代替*p*p左、右子樹均非空針對*p有子樹的情況，把*p的兩個子樹合并為一棵樹，然后將其連接到*p的雙親上。二叉排序樹刪除算法 void DelBSTNode(BSTree Tptr，KeyType key) BSTNode *parent=NUll，*p=*Tptr，*q，*child； while(p) if(p-key=key) break； parent=p； p=

25、(keykey)?p-lchild：p-rchild； if(!p) return；/*找不到被刪結點則返回*/ q=p； /*找到時,q記住被刪結點p*/ if(q-lchild&q-rchild) for(parent=q，p=q-rchild； p-lchild； parent=p，p=p-lchild)； /*找被刪結點的后繼*/ if(!parent) Tptr=child； else if(p=parent-lchild) parent-lchild=child； else parent-rchild=child； if(p!=q) q-key=p-key； free(p)； ch

26、ild=(p-lchild)?p-lchild：p-rchild； 二叉排序樹上的查找 在二叉排序樹上進行查找，和二分查找類似，也是一個逐步縮小查找范圍的過程。遞歸的查找算法：BSTNode *SearchBST(BSTree T，KeyType key) if(T=NULL|key=T-key) return T； if(keykey) return SearchBST(T-lchild，key)； else return SearchBST(T-rchild，key)； 在二叉排序樹上進行查找時的平均查找長度和二叉樹的形態有關：(a)在最壞情況下，二叉排序樹是通過把一個有序表的n個結點依次

27、插入而生成的，此時所得的二叉排序樹蛻化為一棵深度為n的單支樹，它的平均查找長度和單鏈表上的順序查找相同，也是(n+1)/2。(b)在最好情況下，二叉排序樹在生成的過程中，樹的形態比較勻稱，最終得到的是一棵形態與二分查找的判定樹相似的二叉排序樹，此時它的平均查找長度大約是log2n。(c)插入、刪除和查找算法的時間復雜度均為O(log2n)。 二叉排序樹和二分查找的比較 就平均時間性能而言，二叉排序樹上的查找和二分查找差不多。 就維護表的有序性而言，二叉排序樹無須移動結點，只需修改指針即可完成插入和刪除操作，且其平均的執行時間均為O(log2n)，因此更有效。二分查找所涉及的有序表是一個向量，若

28、有插入和刪除結點的操作，則維護表的有序性所花的代價是O(n)。當有序表是靜態查找表時，宜用向量作為其存儲結構，而采用二分查找實現其查找操作；若有序表是動態查找表，則應選擇二叉排序樹作為其存儲結構。- 樹 B- 樹的定義一棵m(m3)階的B-樹是滿足如下性質的m叉樹：(1)每個結點至少包含下列數據域： (n，P0，Kl，P1，K2，Ki，Pi)其中： n為關鍵字總數 Ki(1ij)是關鍵字，關鍵字序列遞增有序：K1 K2 key0=k ; for(i=T-keynum；Kkeyi;i-)； if(i0 & T-keyi=1) *pos=i； return T； if(!T-soni) retur

29、n NULL； DiskRead(T-soni)； return SearchBTree(T-Soni，k，pos)； B-樹的查找算法 B-樹上的查找有兩個基本步驟：在B-樹中查找結點，該查找涉及讀盤DiskRead操作，屬外查找；在結點內查找，該查找屬內查找。 查找操作的時間為：外查找的讀盤次數不超過樹高h，故其時間是O(h)；內查找中，每個結點內的關鍵字數目keynumm(m是B-樹的階數)，故其時間為O(nh)。查找操作的時間開銷 B-樹的生成是從空樹起，逐個插入關鍵字而得到的。 （1）插入關鍵字K的方法 首先在樹中查找K，若找到則直接返回(假設不處理相同關鍵字的插入)；否則查找操作必

30、失敗于某個葉子上，然后將K插入該葉子中。若該葉子結點原來是非滿(指keynumkeynumMin，則只需刪去K及其右指針(*x是葉子，K的右指針為空)即可使刪除操作結束。 情形二：若x-keynum=Min，該葉子中的關鍵字個數已是最小值，刪K及其右指針后會破壞B-樹的性質(3)。若*x的左(或右)鄰兄弟結點*y中的關鍵字數目大于Min，則將*y中的最大(或最小)關鍵字上移至雙親結點*parent中，而將*parent中相應的關鍵字下移至x中。 情形三：若*x及其相鄰的左右兄弟(也可能只有一個兄弟)中的關鍵字數目均為最小值Min，則上述的移動操作就不奏效，此時須*x和左或右兄弟合并。 B樹中刪

31、除關鍵字6，7的過程 12 689 75 215 1312 79 85 215 13 1258 9 215 13n個結點的平衡的二叉排序的高度H（即lgn）比B-樹的高度h約大lgt倍。 例如m=1024，則lgt=lg512=9。此時若B-樹高度為4，則平衡的二叉排序樹的高度約為36。顯然，若m越大，則B-樹高度越小。 若要作為內存中的查找表，B-樹卻不一定比平衡的二叉排序樹好，尤其當m較大時更是如此。 因為查找等操作的CPU計算時間在B-樹上是 O(mlogtn)=0(lgn(m/lgt) 性能分析8.4散列(Hash)技術設所有可能出現的關鍵字集合記為U(簡稱全集)。實際發生(即實際存儲

32、)的關鍵字集合記為K（|K|比|U|小得多）。 散列方法是:使用函數h將U映射到表T0.m-1的下標上。 這樣以U中關鍵字為自變量，以h為函數的運算結果就是相應結點的存儲地址。從而達到在O(1)時間內就可完成查找。散列表(Hash Table) 其中： 稱h為散列函數(Hash Function)。散列函數h的作用是壓縮待處理的下標范圍，使待處理的|U|個值減少到m個值，從而降低空間開銷。 T為散列表(Hash Table)。 h(Ki)(KiU)是關鍵字為Ki結點存儲地址(亦稱散列值或散列地址)。 將結點按其關鍵字的散列地址存儲到散列表中的過程稱為散列(Hashing) 沖突： 兩個不同的關

33、鍵字，由于散列函數值相同，因而被映射到同一表位置(存儲地址)上。該現象稱為沖突(Collision)或碰撞。發生沖突的兩個關鍵字稱為該散列函數的同義詞(Synonym)。 散列表的沖突現象 其一是記錄的個數存儲空間的大小 其二是選擇合適的散列函數。怎么樣才能完全避免沖突？最理想的解決沖突的方法是安全避免沖突。要做到這一點必須滿足兩個條件： 通常，哈希函數h是一個壓縮映像。雖然實際發生的鍵值個數|K|m，但|U|m，故無論怎樣設計h，也不可能完全避免沖突。 沖突不可能完全避免 沖突除了與h相關外，還與表的填滿程度相關。 設m為表長，n為表中填入的結點數（記錄數），則將=n/m定義為散列表的裝填因

34、子(Load Factor)。越大，表越滿，沖突的機會也越大。通常取1。 影響沖突的因素 因此：要盡量減少沖突，就要選擇好的哈希函數h(key)和選擇恰當的哈希表的長度m（既選擇好的=n/m ）。常用散列函數 平方取中法 取關鍵字的平方值的中間幾位數 先通過求關鍵字的平方值擴大相近數的差別，然后根據表長度取中間的幾位數作為散列函數值。又因為一個乘積的中間幾位數和乘數的每一位都相關，所以由此產生的散列地址較為均勻。int Hash(int key) /*假設key是4位整數*/key* = key； key/=100； /*先求平方值，后去掉末尾的兩位數*/ return key1000； /*

35、取中間三位數作為散列地址返回*/平方取中法用C程序實現如下：取關鍵字或關鍵字的某個線性函數為哈希地址 即：H(k)=key 或H(k)=a*key+b 其中a，b為常數直接定址法是簡單常用的一種方法。它是以表長m來除關鍵字，取其余數作為散列地址,即 h(key)=keym 該方法的關鍵是選取m。選取的m應使得散列函數值盡可能與關鍵字的各位相關。m最好為素數除余法該方法包括兩個步驟： 首先用關鍵字key乘上某個常數A(0A1)，并抽取出keyA的小數部分； 然后用m乘以該小數后取整。 相乘取整法相乘取整法的C程序如下：int Hash(int key) double d=key *A； /*不妨

36、設A和m已有定義*/ return (int)(m*(d-(int)d)； /* (int)表示強制轉換后面的表達式為整數*/選擇一個隨機函數，取關鍵字的隨機函數值為它的散列地址 即 h(key)=random(key)其中random為偽隨機函數，但要保證函數值是在0到m-1之間。隨機數法處理沖突的方法 一、開放地址法解決沖突的方法 假設哈希表的地址集為0m-1，當沖突發生時，即由關鍵字得到的哈希地址為j(0jm-1)的位置上已存有記錄，則處理沖突就是為該關鍵字的記錄找到另一個“空”的哈希地址。為此在處理沖突的過程中，需采用某種探測技術在散列表中形成一個探測序列Hi ,i=1,2,3,，k(

37、Hi0,m-1) 。沿此序列逐個單元地查找，直到找到給定的或者碰到一個開放的地址(即該地址單元為“空”)為止（若要插入，在探查到開放的地址，則可將待插入的新結點存人該地址單元）。查找時探查到開放的地址則表明表中無待查的關鍵字，即查找失敗。 開放地址法的一般形式為： Hi=(h(key)+di)m 1im-1 其中h(key)為哈希函數，m為哈希表長，d為增量序列，它可有下列幾種取法： di=1，2，3，m-1 di=12，-12,22，-22,32，k2 ;(k=m/2) di=偽隨機數序列按照形成探查序列的方法不同，可將開放定址法區分為線性探查法、二次探查法、雙重散列法等。線性探查法(Lin

38、ear Probing) 該方法的基本思想是：將散列表T0.m-1看成是一個循環向量，若初始探查的地址為d(即h(key)=d)，則最長的探查序列為： d，d+l，d+2，m-1，0，1，d-1即:探查時從地址d開始，首先探查Td，然后依次探查Td+1，直到Tm-1，此后又循環到T0，T1，直到探查到Td-1為止。形成探測序列的方法開放地址法解決沖突 雙重散列法(Double Hashing) 該方法是開放定址法中最好的方法之一，它的探查序列是： hi=(h(key)+i*h1(key)m 0im-1 即 di=i*h1(key) 即探查序列為：d=h(key),(d+h1(key)m ,(d

39、+2h1(key)m，等。開放地址法解決沖突 若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數組T0.m-1。凡是散列地址為i的結點，均插入到以Ti為頭指針的單鏈表中。T中各分量的初值均應為空指針。二、拉鏈法解決沖突是將所有關鍵字為同義詞的結點鏈接在同一個單鏈表中。例：已知一組關鍵字為（26，36，41，38，44，15，68，12，06，51），取表長為13，用拉鏈法解決沖突構造這組關鍵字的散列表如右圖 012345869710111226154112366806384451H（key）=key%13拉鏈法解決沖突012345869710111226 15 68 44

40、06 36 1241363851上題也可以如下做： m個頭指針組成的指針數組T的每個元素改造成兩個域，一個存儲基本哈希表內容；另一個為指針域，指向同義詞的鏈表。拉鏈法解決沖突 拉鏈法解決沖突 拉鏈法的優點(2)由于拉鏈法中各鏈表上的結點空間是動態申請的，故它更適合于造表前無法確定表長的情況；(1)拉鏈法處理沖突簡單，且無堆積現象，即非同義詞決不會發生沖突，因此平均查找長度較短；(3)開放定址法為減少沖突，要求裝填因子較小，故當結點規模較大時會浪費很多空間。而拉鏈法中可取1，且結點較大時，拉鏈法中增加的指針域可忽略不計，因此節省空間；(4)在用拉鏈法構造的散列表中，刪除結點的操作易于實現。只要簡單地刪去鏈表上相應的結點