第9章 查找(上課用)

數(shù)據(jù)結(jié)構(gòu)主講人：張立震E-mail:system0@9.1靜態(tài)查找表9.2動(dòng)態(tài)查找表9.3哈希表第9章查找查找的概念靜態(tài)查找表二叉排序樹(shù)平衡二叉樹(shù)（不講）哈希表本章主要內(nèi)容查找(Search)的概念

查找表:是由同一類(lèi)型的數(shù)據(jù)元素(或記錄)組成的數(shù)據(jù)集合。

在查找表中一般有四個(gè)操作：

(1)查詢(xún)某個(gè)“特定”的數(shù)據(jù)元素是否在查找表中

(2)檢索某個(gè)“特定”的數(shù)據(jù)元素的各種屬性

(3)在查找表中插入一個(gè)元素

(4)在查找表中刪除一個(gè)元素

查找表的分類(lèi)：靜態(tài)查找表動(dòng)態(tài)查找表關(guān)鍵字：數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，用以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素（或記錄）。主關(guān)鍵字：可唯一地標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的關(guān)鍵字。使用基于主關(guān)鍵字的查找，查找結(jié)果應(yīng)是唯一的！查找：就是在數(shù)據(jù)集合中尋找一個(gè)關(guān)鍵字等于某個(gè)給定值的數(shù)據(jù)元素（記錄）。

查找的結(jié)果通常有兩種可能：

查找成功

給出記錄信息或記錄所在的位置信息。

查找不成功

作為結(jié)果，給出“空記錄”或“空指針”表示查找失敗。為在上圖中，如果我們查找主關(guān)鍵字“代碼”的主關(guān)鍵字為“sh601398”的記錄時(shí)就可以得到第二條唯一一個(gè)記錄。如果查找次關(guān)鍵字“漲跌額”為“-0.11”的記錄時(shí)，可以得到兩條記錄。平均查找長(zhǎng)度ASL(AverageSearchLength)

衡量一個(gè)查找算法的時(shí)間效率的標(biāo)準(zhǔn)是：在查找過(guò)程中關(guān)鍵字的平均比較次數(shù)或平均讀寫(xiě)磁盤(pán)次數(shù)。設(shè)查找第i

個(gè)元素的概率為pi，查找到第i

個(gè)元素所需比較次數(shù)為ci，則查找成功的平均查找長(zhǎng)度:

以上討論的是“基本上每次查找都成功”，若查找不成功的情況不可忽略，則應(yīng)是查找成功的平均長(zhǎng)度與查找不成功的平均長(zhǎng)度之和。以后主要討論在查找成功下的ASL(哈希表除外)。此外衡量一個(gè)查找算法還要考慮算法所需要的存儲(chǔ)量和算法的復(fù)雜性等問(wèn)題。

9.1靜態(tài)查找表

靜態(tài)查找表有不同的表示方法，不同的表示方法中查找方法也不同?？煞譃椋?/p>

順序查找表有序查找表靜態(tài)樹(shù)表的查找（不講解）索引查找表

9.1.1順序表的查找

(SequentialSearch)所謂順序查找，又稱(chēng)線(xiàn)性查找，主要用于在線(xiàn)性結(jié)構(gòu)中進(jìn)行查找。其順序存儲(chǔ)結(jié)構(gòu)如下：typedefstruct{//元素類(lèi)型定義KeyTypekey;//元素的關(guān)鍵字InfoTypedata;//元素的其他數(shù)據(jù)}ElemType;typedefstruct{//順序表類(lèi)型定義

ElemType*elem;//存儲(chǔ)空間的基址，建表時(shí)0號(hào)單元留用

intlength;//表的長(zhǎng)度}SSTable;

SSTabletb;i01234567891011

513192137566475808892找6464監(jiān)視哨iiii比較次數(shù)=5比較次數(shù)：查找第n個(gè)元素：1查找第n-1個(gè)元素：2……….查找第1個(gè)元素：n查找第i個(gè)元素：n+1-i查找失?。簄+1查找過(guò)程：從表的一端開(kāi)始逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較。例如：順序查找算法(p217算法9.1)intSearch_Seq(SSTableST,KeyTypekey){

//順序查找的算法，0號(hào)元素為監(jiān)視哨。inti=ST.length;ST.elem[0].key=key;//“哨兵”for(i=ST.length;!EQ(ST.elem[i].key,key);--i)//從后往前找returni;//找不到時(shí),i為0}優(yōu)點(diǎn)：算法簡(jiǎn)單適用，對(duì)表中元素沒(méi)有要求，鏈表中查找可以類(lèi)似思路實(shí)現(xiàn)。缺點(diǎn)：當(dāng)表長(zhǎng)較大時(shí)，平均查找長(zhǎng)度較大。for(i=ST.length;ST.elem[i].key!=key;--i)順序查找成功時(shí)的平均查找長(zhǎng)度在順序查找情形，ci=n-i+1,i=1,,n，因此在等概率情形，pi=1/n,i=0,1,,n-1。

在不等概率情況下：使表中記錄按查找概率由小到大重新排序，以便提高查找效率。若查找概率不確定，則附設(shè)一個(gè)訪(fǎng)問(wèn)頻率，利用頻率大小來(lái)調(diào)整記錄所在位置。9.1.2有序表的查找折半查找：先求位于查找區(qū)間正中的對(duì)象的下標(biāo)mid，用其關(guān)鍵字與給定值x比較:

elem[mid].key==x，查找成功；

elem[mid].key>x，把查找區(qū)間縮小到表的前半部分，再繼續(xù)進(jìn)行折半查找；

elem[mid].key<x，把查找區(qū)間縮小到表的后半部分，再繼續(xù)進(jìn)行折半查找。每比較一次，查找區(qū)間縮小一半。如果查找區(qū)間已縮小到一個(gè)對(duì)象，仍未找到想要查找的對(duì)象，則查找失敗。查找成功的例子 查找失敗的例子有序表查找的例子(1)mid=(low+high)/2」

(2)比較ST.elem[mid].key==key?

如果ST.elem[mid].key==key，則查找成功，返回mid值如果ST.elem[mid].key>key，則置high=mid-1

如果ST.elem[mid].key<key，則置low=mid+1(3)重復(fù)計(jì)算mid

以及比較ST.elem[mid].key與key，當(dāng)low>high時(shí)，表明查找不成功，查找結(jié)束。折半查找算法實(shí)現(xiàn)折半查找遞歸算法intBinSearch(SSTableST,intlow,inthigh,KeyTypekey){if(low>high)return0;//順序表中不存在待查元素else{mid=(low+high)/2;if(key==ST.elem[mid].key)returnmid;//找到待查元素

elseif(key<ST.elem[mid].key))//繼續(xù)在前半?yún)^(qū)間進(jìn)行查找returnBinSearch(ST,low,mid-1,key)

elsereturnBinSearch(ST,mid+1,high,key)

//繼續(xù)在后半?yún)^(qū)間進(jìn)行查找

}}初次調(diào)用時(shí)，BinSearch(ST,1,ST.length,key)折半查找非遞歸算法(p220算法9.2)intSearch_Bin(SSTableST,KeyTypekey){low=1;high=ST.length;//置區(qū)間初值

while(low<=high){mid=(low+high)/2;if(key==ST.elem[mid].key)returnmid;//找到待查元素

elseif(key<ST.elem[mid].key))high=mid-1;//繼續(xù)在前半?yún)^(qū)間進(jìn)行查找

elselow=mid+1;//繼續(xù)在后半?yún)^(qū)間進(jìn)行查找

}return0;//順序表中不存在待查元素}//Search_Bin先看一個(gè)有11個(gè)元素的表的例子：n=11i1234567891011Ci12233334444折半查找的性能分析判定樹(shù)：描述查找過(guò)程的二叉樹(shù)。有n個(gè)結(jié)點(diǎn)的判定樹(shù)的深度為log2n+1折半查找法在查找過(guò)程中進(jìn)行的比較次數(shù)最多不超過(guò)log2n+16391425781011假設(shè)n=2h-1并且查找概率相等，則查找成功時(shí)折半查找的平均查找長(zhǎng)度

在n>50時(shí)，可得近似結(jié)果一般情況下，表長(zhǎng)為n的折半查找的判定樹(shù)的深度和含有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度相同。折半查找的性能分析折半查找的效率比順序查找高。折半查找只能適用于有序表，并且以順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。順序表有序表表的特性無(wú)序有序存儲(chǔ)結(jié)構(gòu)順序或鏈?zhǔn)巾樞虿鍎h操作易于進(jìn)行需移動(dòng)元素ASL的值(n+1)/2大(n+1)/n·log2(n+1)-1小時(shí)間復(fù)雜度O(n)O(log2n)順序表和有序表的比較在建立順序表的同時(shí)，建立一個(gè)索引項(xiàng)，包括兩項(xiàng)：關(guān)鍵字項(xiàng)和指針項(xiàng)。索引表按關(guān)鍵字有序，表則為分塊有序。12345678910111213141516171822121389203342443824486058744986532248861713索引順序表=索引(有序)+順序表(無(wú)序)順序表索引表9.1.4索引順序表的查找——分塊查找最大關(guān)鍵字指針?biāo)饕樞虿檎矣址Q(chēng)分塊查找查找過(guò)程：將表分成幾塊，塊內(nèi)無(wú)序，塊間有序；先確定待查記錄所在塊，再在塊內(nèi)查找。適用條件：分塊有序表算法實(shí)現(xiàn)：用數(shù)組存放待查記錄,每個(gè)數(shù)據(jù)元素至少含有關(guān)鍵字域。建立索引表，每個(gè)索引表結(jié)點(diǎn)含有最大關(guān)鍵字域和指向本塊第一個(gè)結(jié)點(diǎn)的指針12345678910111213141516171822121389203342443824486058745786532248861713索引表查38例如分塊查找方法評(píng)價(jià)容易證明，在給定n的前提下，當(dāng)s取時(shí)，ASLbs取最小值查找方法比較ASL值最大最小兩者之間表結(jié)構(gòu)有序表、無(wú)序表有序表分塊有序表存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)線(xiàn)性鏈表順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)線(xiàn)性鏈表順序查找折半查找分塊查找

9.2動(dòng)態(tài)查找表動(dòng)態(tài)查找表的特點(diǎn):

表結(jié)構(gòu)本身是在查找過(guò)程中動(dòng)態(tài)生成。若表中存在其關(guān)鍵字等于給定值key的記錄，表明查找成功；否則插入關(guān)鍵字等于key的記錄。

二叉排序樹(shù)（二叉查找樹(shù)）或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：

每個(gè)結(jié)點(diǎn)都有一個(gè)作為查找依據(jù)的關(guān)鍵字(key)，所有結(jié)點(diǎn)的關(guān)鍵字互不相同。

左子樹(shù)(若非空)上所有結(jié)點(diǎn)的關(guān)鍵字都小于根結(jié)點(diǎn)的關(guān)鍵字。

右子樹(shù)(若非空)上所有結(jié)點(diǎn)的關(guān)鍵字都大于根結(jié)點(diǎn)的關(guān)鍵字。

左子樹(shù)和右子樹(shù)也是二叉排序樹(shù)。二叉排序樹(shù)(BinarySortTree)50308020901085406625238835是二叉排序樹(shù)嗎？例如：以二叉鏈表形式存儲(chǔ)typedefstruct{//元素類(lèi)型定義KeyTypekey;//元素的關(guān)鍵字InfoTypedata;//元素的其他數(shù)據(jù)}TElemType;typedefstructBiTNode{//結(jié)點(diǎn)結(jié)構(gòu)

TElemTypedata;//元素structBiTNode*lchild,*rchild;//左右指針

}BiTNode,*BiTree;BiTreeT;二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu)1.二叉排序樹(shù)的查找算法若二叉排序樹(shù)為空，則查找不成功；否則

(1)若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功；

(2)若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹(shù)上進(jìn)行查找；

(3)若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹(shù)上進(jìn)行查找。在二叉排序樹(shù)中查找關(guān)鍵字值分別為50,35,90,955030802090854035883250505030403550508090查找失敗BiTreeSearchBST(BiTreeT,KeyTypekey){//

在根指針T所指二叉排序樹(shù)中遞歸查找關(guān)鍵字等于key的數(shù)據(jù)元素,

//若查找成功,則返回指向該數(shù)據(jù)元素結(jié)點(diǎn)的指針,否則返回空指針。

if((!T)||EQ(key,T->data.key))returnT; elseifLT(key,T->data.key)returnSearchBST(T->lchild,key); elsereturnSearchBST(T->rchild,key);}二叉排序樹(shù)的遞歸查找算法(P228算法9.5(a))2.二叉排序樹(shù)的插入算法二叉排序樹(shù)是一種動(dòng)態(tài)數(shù)表，樹(shù)的結(jié)構(gòu)不是一次生成，而是在查找過(guò)程中，當(dāng)樹(shù)中不存在關(guān)鍵字等于給定值時(shí)再進(jìn)行插入。若二叉排序樹(shù)為空樹(shù)，則新插入的結(jié)點(diǎn)為新的根結(jié)點(diǎn)；否則，新插入的結(jié)點(diǎn)必為一個(gè)新的葉子結(jié)點(diǎn)，其插入位置是查找不成功時(shí)查找路徑上訪(fǎng)問(wèn)的最后一個(gè)結(jié)點(diǎn)的左孩子或右孩子結(jié)點(diǎn)。intSearchBST(BiTreeT,KeyTypekey,BiTreef,

BiTree&p){

//二叉排序樹(shù)的遞歸查找算法

if(!T){p=f;returnFALSE;} elseif(EQ(key,T->data.key)){p=T;

returnTRUE;} elseif(LT(key,T->data.key))

returnSearchBST(T->lchild,key,T,p); else

returnSearchBST(T->rchild,key,T,p);}

P

即為位置形參，查找成功返回?cái)?shù)據(jù)結(jié)點(diǎn)所在位置，不成功則返回查找路徑上訪(fǎng)問(wèn)的最后一個(gè)結(jié)點(diǎn)的指針。f

指向

T

的雙親結(jié)點(diǎn)，即

p

的上一步結(jié)點(diǎn)指針。二叉排序樹(shù)的改進(jìn)查找算法(P228算法9.5(b))intInsertBST(BiTree&T,ElemTypee){if(!SearchBST(T,e.key,NULL,p)){ s=newBiTNode;//為新結(jié)點(diǎn)分配空間

s->data=e; s->lchild=s->rchild=NULL; if(!p)T=s;//插入s為新的根結(jié)點(diǎn)

elseif(LT(e.key,p->data.key)) p->lchild=s;//插入*s為*p的左孩子

elsep->rchild=s;//插入*s為*p的右孩子

returnTRUE;//插入成功

}elsereturnFALSE;}//InsertBST在以T為根節(jié)點(diǎn)的BST上插入一個(gè)關(guān)鍵字等于e.key的元素——非遞歸算法intInsert_BST(BiTree&T,BiTreeS){BiTreep,q;if(!T)T=S;else{p=T;while(p){q=p;//q指向p結(jié)點(diǎn)的雙親結(jié)點(diǎn)

if(S->data.key<p->data.key)p=p->lchild;elseif(S->data.key>p->data.key)p=p->rchild; elsep=NULL;} if(S->data.key==q->data.key)return0;if(S->data.key<q->data.key)q->lchild=S;elseq->rchild=S; }return1;}將指針S所指的結(jié)點(diǎn)插入到根結(jié)點(diǎn)指針為T(mén)的

二叉排序樹(shù)中的非遞歸算法從空樹(shù)出發(fā)，依次插入R1～Rn各數(shù)據(jù)值：

(1)如果二叉排序樹(shù)是空樹(shù)，則插入結(jié)點(diǎn)就是二叉排序樹(shù)的根結(jié)點(diǎn)；

(2)如果二叉排序樹(shù)是非空的，則插入值與根結(jié)點(diǎn)比較，若小于根結(jié)點(diǎn)的值，就插入到左子樹(shù)中去；否則插入到右子樹(shù)中。構(gòu)造二叉排序樹(shù)過(guò)程輸入數(shù)據(jù)，建立二叉排序樹(shù)的過(guò)程輸入數(shù)據(jù)序列

{53,78,65,17,87,09,81,45,23}構(gòu)造二叉排序樹(shù)的算法voidCreat_BST(BiTree&T){intx;BiTreeS;T=NULL;scanf(“%d”,&x),while(x!=0){S=(BiTNode*)malloc(sizeof(BitNode));S->data.key=x;S->lchild=NULL;S->rchild=NULL;Insert_BST(T,S);}return;}一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵二叉排序樹(shù)而變成一個(gè)有序序列；每次插入的新結(jié)點(diǎn)都是二叉排序樹(shù)上新的葉子結(jié)點(diǎn)；插入時(shí)不必移動(dòng)其它結(jié)點(diǎn)，僅需修改某個(gè)結(jié)點(diǎn)的指針；中序遍歷二叉排序樹(shù)可得到一個(gè)關(guān)鍵字有序序列。結(jié)論3.二叉排序樹(shù)的刪除算法

和插入相反，刪除在查找成功之后進(jìn)行，并且要求在刪除二叉排序樹(shù)上某個(gè)結(jié)點(diǎn)之后，仍然保持二叉排序樹(shù)的特性?？煞秩N情況討論：

(1)被刪除的結(jié)點(diǎn)是葉子；

(2)被刪除的結(jié)點(diǎn)只有左子樹(shù)或者只有右子樹(shù)；

(3)被刪除的結(jié)點(diǎn)既有左子樹(shù)，也有右子樹(shù)。其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為“空”50308020908540358832(1)被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)key=88其雙親結(jié)點(diǎn)的相應(yīng)指針域的值改為“指向被刪除結(jié)點(diǎn)的左子樹(shù)或右子樹(shù)”。50308020908540358832(2)被刪除的結(jié)點(diǎn)只有左子樹(shù)或者只有右子樹(shù)key=80以其前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點(diǎn)50308020908540883532(2)被刪除的結(jié)點(diǎn)既有左子樹(shù)，也有右子樹(shù)key=50二叉排序樹(shù)查找性能的分析在二叉排序樹(shù)上查找關(guān)鍵字等于給定值的結(jié)點(diǎn)的過(guò)程，恰走了一條從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑的過(guò)程。和給定值比較的關(guān)鍵字個(gè)數(shù)等于給定結(jié)點(diǎn)所在的層數(shù)，不超過(guò)樹(shù)的深度（類(lèi)似判定樹(shù)）由值相同的n個(gè)關(guān)鍵字，由于輸入的序列順序不一樣，構(gòu)造所得不同形態(tài)的二叉排序樹(shù)，平均查找長(zhǎng)度的值不同，甚至可能差別很大。由關(guān)鍵字序列3，1，2，5，4構(gòu)造而得的二叉排序樹(shù)由關(guān)鍵字序列1，2，3，4，5構(gòu)造而得的二叉排序樹(shù)，例如：2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2結(jié)論：n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)的平均查找長(zhǎng)度和樹(shù)的形態(tài)有關(guān)；若插入的關(guān)鍵字有序，則構(gòu)成的二叉排序樹(shù)蛻變?yōu)閱沃?shù)，即為順序表的查找，平均查找長(zhǎng)度為(n+1)/2；最好情況下，二叉樹(shù)的形態(tài)和折半查找的判定樹(shù)相同，ASL和log2n成正比。前面兩節(jié)討論的表示查找表的各種結(jié)構(gòu)的共同特點(diǎn)：記錄在表中的位置和它的關(guān)鍵字之間不存在一個(gè)確定的關(guān)系。這類(lèi)查找方法建立在“比較”的基礎(chǔ)上順序查找折半查找、二叉排序樹(shù)查找==><≠查找效率依賴(lài)于比較次數(shù)能否不經(jīng)過(guò)任何比較呢？只有一個(gè)辦法：

預(yù)先知道所查關(guān)鍵字在表中的位置。即，要求記錄在表中的位置和其關(guān)鍵字之間存在一種確定的關(guān)系。

9.3哈希表9.3.1什么是哈希表9.3.2哈希函數(shù)的構(gòu)造方法9.3.3處理沖突的方法9.3.4哈希表的查找及其分析9.3.1什么是哈希表

只有一個(gè)辦法：預(yù)先知道所查關(guān)鍵字在表中的位置。即，要求：記錄在表中的位置和其關(guān)鍵字之間存在一種確定的關(guān)系。對(duì)于頻繁使用的查找表，希望ASL=0。哈希函數(shù)：在記錄的關(guān)鍵字與記錄的存儲(chǔ)地址之間建立的一種對(duì)應(yīng)關(guān)系，以H(key)作為關(guān)鍵字為key的記錄在表中的位置，通常稱(chēng)這個(gè)函數(shù)H(key)為哈希函數(shù)。哈希查找：又叫散列查找，利用哈希函數(shù)進(jìn)行查找的過(guò)程。

012345678910111213{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Du

}例如：對(duì)于如下9個(gè)關(guān)鍵字設(shè)哈希函數(shù)

H(key)=

(Ord(第一個(gè)字母)-Ord('A')+1)/2ChenZhaoQianSunLiWuHanYeDu從例子可見(jiàn)，哈希函數(shù)只是一種映象，即：將關(guān)鍵字的集合映射到某個(gè)地址集合上，所以哈希函數(shù)的設(shè)定很靈活，只要使任何關(guān)鍵字的哈希函數(shù)值都落在表長(zhǎng)允許的范圍之內(nèi)即可。261719122338254

012345678910111213{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Du

}例如：對(duì)于如下9個(gè)關(guān)鍵字設(shè)哈希函數(shù)

H(key)=

(Ord(第一個(gè)字母)-Ord('A')+1)/2ChenZhaoQianSunLiWuHanYeDu261719122338254問(wèn)題:

若添加關(guān)鍵字Lu,怎么辦？沖突：key1key2，但H(key1)=H(key2)

的現(xiàn)象。哈希表：根據(jù)設(shè)定的哈希函數(shù)

H(key)和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個(gè)有限的、地址連續(xù)的地址集(區(qū)間)上，并以關(guān)鍵字在地址集中的“象”作為相應(yīng)記錄在表中的存儲(chǔ)位置，如此構(gòu)造所得的查找表稱(chēng)之為“哈希表”。這一映象過(guò)程稱(chēng)為哈希造表或散列，所得的位置為哈希地址或散列地址。9.3.1什么是哈希表9.3.2哈希函數(shù)的構(gòu)造方法直接定址法

數(shù)字分析法平方取中法折疊法除留余數(shù)法(最常用*)隨機(jī)數(shù)法對(duì)數(shù)字的關(guān)鍵字可有下列構(gòu)造方法：若是非數(shù)字關(guān)鍵字，則需先對(duì)其進(jìn)行數(shù)字化處理。哈希函數(shù)為關(guān)鍵字的線(xiàn)性函數(shù)H(key)=key或者H(key)=akey+b1.

直接定址法此法僅適合于：地址集合的大小==關(guān)鍵字集合的大小2.數(shù)字分析法此方法僅適合于：能預(yù)先估計(jì)出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。

假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址。例：

H1(key)=首字母序號(hào)H2(key)=首字母序號(hào)+尾字母序號(hào)以關(guān)鍵字的平方值的中間幾位作為存儲(chǔ)地址。求“關(guān)鍵字的平方值”的目的是“擴(kuò)大差別”，同時(shí)平方值的中間各位又能受到整個(gè)關(guān)鍵字中各位的影響。此方法在詞典處理中使用十分廣泛。它先計(jì)算構(gòu)成關(guān)鍵字的標(biāo)識(shí)符的內(nèi)碼的平方，然后按照散列表的大小取中間的若干位作為散列地址。此方法適合于:

關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象。3.

平方取中法

4.折疊法

例

關(guān)鍵字為：0442205864，哈希地址位數(shù)為458644220041

0088H(key)=0088移位疊加5864022404

6092H(key)=6092間接疊加將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈希地址。兩種疊加處理的方法：

移位疊加：將分割后的幾部分低位對(duì)齊相加。間接疊加：從一端沿分割界來(lái)回折送，然后對(duì)齊相加。此法適合于：關(guān)鍵字的數(shù)字位數(shù)特別多，而且關(guān)鍵字中每一位上數(shù)字分布大致均勻。5.除留余數(shù)法----常用方法設(shè)定哈希函數(shù)為:H(key)=keyMOD

p

(p≤m)其中，m

為表長(zhǎng)，p

為不大于m

的素?cái)?shù)或是不含20以下的質(zhì)因子。為什么要對(duì)p

加限制？例如：給定一組關(guān)鍵字為:12,39,18,24,33,21，若取p=9,則他們對(duì)應(yīng)的哈希函數(shù)值將為:3,3,0,6,6,3?？梢?jiàn)，若p

中含質(zhì)因子3,則所有含質(zhì)因子3的關(guān)鍵字均映射到“3的倍數(shù)”的地址上，從而增加了“沖突”的可能。6.隨機(jī)數(shù)法設(shè)定哈希函數(shù)為:H(key)=Random(key)其中，Random為偽隨機(jī)函數(shù)。此法適用于：對(duì)長(zhǎng)度不等的關(guān)鍵字構(gòu)造哈希函數(shù)。選取哈希函數(shù)考慮的因素：計(jì)算哈希函數(shù)所需時(shí)間關(guān)鍵字長(zhǎng)度哈希表長(zhǎng)度（哈希地址范圍）關(guān)鍵字分布情況記錄的查找頻率

9.3.3處理沖突的方法開(kāi)放定址法（閉散列*）再哈希法（雙散列）鏈地址法（開(kāi)散列*）“處理沖突”的實(shí)際含義是：為產(chǎn)生沖突的地址尋找下一個(gè)哈希地址。通常有下列幾種方法：1.開(kāi)放定址法(閉散列)——是處理溢出的一種常用的方法為產(chǎn)生沖突的地址H(key)求得一個(gè)地址序列：H0,H1,H2,…,Hs1≤s≤m-1Hi=(H(key)+di)MODm

其中：i=1,2,…,s；

H(key)為哈希函數(shù)；

m為哈希表長(zhǎng)；

di為增量序列。1.開(kāi)放定址法(閉散列)對(duì)增量di

有三種取法：(1)線(xiàn)性探測(cè)再散列

di=1，2，3，…，m-1(2)二次探測(cè)再散列

di=12,-12,22,-22,…,(3)偽隨機(jī)探測(cè)再散列

di

是一組偽隨機(jī)數(shù)列或者

di=i×H2(key)(又稱(chēng)雙散列函數(shù)探測(cè))例

表長(zhǎng)為11的哈希表中已填有關(guān)鍵字為17，60，29的記錄，H(key)=keyMOD11，現(xiàn)有第4個(gè)記錄，其關(guān)鍵字為38，按三種處理沖突的方法，將它填入表中012345678910601729(1)H(38)=38MOD11=5沖突

H1=(5+1)MOD11=6沖突

H2=(5+2)MOD11=7沖突

H3=(5+3)MOD11=8不沖突38(2)H(38)=38MOD11=5沖突

H1=(5+12)MOD11=6沖突

H2=(5-12)MOD11=4不沖突38(3)H(38)=38MOD11=5沖突設(shè)偽隨機(jī)數(shù)序列為9，則：

H1=(5+9)MOD11=3不沖突38線(xiàn)性探測(cè)二次探測(cè)偽隨機(jī)探測(cè)例如:

關(guān)鍵字集合{19,01,23,14,55,68,11,82,36}設(shè)定哈希函數(shù)H(key)=keyMOD11(表長(zhǎng)=11)1901231455681901231468若采用線(xiàn)性探測(cè)再散列處理沖突若采用二次探測(cè)再散列處理沖突118236551182361121362511121214

132.再哈希