第9章 查找(上課用)

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

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

在查找表中一般有四個操作：

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

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

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

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

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

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

查找成功

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

查找不成功

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

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

個元素的概率為pi，查找到第i

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

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

9.1靜態(tài)查找表

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

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

9.1.1順序表的查找

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

ElemType*elem;//存儲空間的基址，建表時0號單元留用

intlength;//表的長度}SSTable;

SSTabletb;i01234567891011

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

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

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

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

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

elem[mid].key<x，把查找區(qū)間縮小到表的后半部分，再繼續(xù)進行折半查找。每比較一次，查找區(qū)間縮小一半。如果查找區(qū)間已縮小到一個對象，仍未找到想要查找的對象，則查找失敗。查找成功的例子 查找失敗的例子有序表查找的例子(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ù)計算mid

以及比較ST.elem[mid].key與key，當low>high時，表明查找不成功，查找結(jié)束。折半查找算法實現(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ū)間進行查找returnBinSearch(ST,low,mid-1,key)

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

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

}}初次調(diào)用時，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ū)間進行查找

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

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

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

9.2動態(tài)查找表動態(tài)查找表的特點:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

BiTree&p){

//二叉排序樹的遞歸查找算法

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

即為位置形參，查找成功返回數(shù)據(jù)結(jié)點所在位置，不成功則返回查找路徑上訪問的最后一個結(jié)點的指針。f

指向

T

的雙親結(jié)點，即

p

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

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

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

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

returnTRUE;//插入成功

}elsereturnFALSE;}//InsertBST在以T為根節(jié)點的BST上插入一個關(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é)點的雙親結(jié)點

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é)點插入到根結(jié)點指針為T的

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

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

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

{53,78,65,17,87,09,81,45,23}構(gòu)造二叉排序樹的算法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òu)造一棵二叉排序樹而變成一個有序序列；每次插入的新結(jié)點都是二叉排序樹上新的葉子結(jié)點；插入時不必移動其它結(jié)點，僅需修改某個結(jié)點的指針；中序遍歷二叉排序樹可得到一個關(guān)鍵字有序序列。結(jié)論3.二叉排序樹的刪除算法

和插入相反，刪除在查找成功之后進行，并且要求在刪除二叉排序樹上某個結(jié)點之后，仍然保持二叉排序樹的特性。可分三種情況討論：

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

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

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

預(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什么是哈希表

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

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

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

H(key)=

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

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

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

H(key)=

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

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

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

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

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

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

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

H1(key)=首字母序號H2(key)=首字母序號+尾字母序號以關(guān)鍵字的平方值的中間幾位作為存儲地址。求“關(guān)鍵字的平方值”的目的是“擴大差別”，同時平方值的中間各位又能受到整個關(guān)鍵字中各位的影響。此方法在詞典處理中使用十分廣泛。它先計算構(gòu)成關(guān)鍵字的標識符的內(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)鍵字分割成若干部分，然后取它們的疊加和為哈希地址。兩種疊加處理的方法：

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

p

(p≤m)其中，m

為表長，p

為不大于m

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

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

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

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

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

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

m為哈希表長；

di為增量序列。1.開放定址法(閉散列)對增量di

有三種取法：(1)線性探測再散列

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

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

di

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

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

表長為11的哈希表中已填有關(guān)鍵字為17，60，29的記錄，H(key)=keyMOD11，現(xiàn)有第4個記錄，其關(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è)偽隨機數(shù)序列為9，則：

H1=(5+9)MOD11=3不沖突38線性探測二次探測偽隨機探測例如:

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

132.再哈希