第七章+查找-數(shù)據(jù)結(jié)構(gòu)教程（C語言版）(王欣欣)

第七章查找表7.2靜態(tài)查找表7.3哈希表7.1基本概念和術(shù)語何謂查找表？

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

“集合”中的數(shù)據(jù)元素之間存在著松散的關(guān)系，因此查找表是一種應(yīng)用靈便的結(jié)構(gòu)。7.1基本概念和術(shù)語對(duì)查找表經(jīng)常進(jìn)行的操作:1）查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中；2）檢索某個(gè)“特定的”數(shù)據(jù)元素的各種屬性；與查詢不同，檢索已知數(shù)據(jù)元素及它的屬性。3）在查找表中插入一個(gè)數(shù)據(jù)元素；4）從查找表中刪去某個(gè)數(shù)據(jù)元素。

查找表的四種操作都在查詢基礎(chǔ)上完成。作查詢和檢索操作的查找表；靜態(tài)查找表若在查找過程中同時(shí)插入查找表中不存在的數(shù)據(jù)元素,或從查找表中刪除已存在的某個(gè)數(shù)據(jù)元素,則稱此類表為動(dòng)態(tài)查找表.動(dòng)態(tài)查找表查找表可分為兩類:(1)基本不改變查找表的結(jié)構(gòu)。(2)“查詢”數(shù)據(jù)元素“不在查找表中”，將其插入；“查詢”數(shù)據(jù)元素“在查找表中”，將其刪除；改變查找表的結(jié)構(gòu)。

在一個(gè)含有眾多數(shù)據(jù)元素(或記錄)的查找表中找出某個(gè)“特定的”數(shù)據(jù)元素(或記錄)。

查找必須給出“特定的”詞的確切含義，首先引入一個(gè)“關(guān)鍵字”的概念。

數(shù)據(jù)元素（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)的值，用以標(biāo)識(shí)（識(shí)別）一個(gè)數(shù)據(jù)元素（或記錄）。關(guān)鍵字:

若此關(guān)鍵字可以唯一地標(biāo)識(shí)一個(gè)數(shù)據(jù)元素（或記錄），則稱之謂“主關(guān)鍵字”。（對(duì)不同的記錄，其主關(guān)鍵字均不同）如：銀行中的帳號(hào)

若此關(guān)鍵字能識(shí)別若干記錄，則稱之謂“次關(guān)鍵字”。如：姓名

假設(shè)關(guān)鍵字是ElemType型，可進(jìn)行比較。

查找:在查找表中確定一個(gè)關(guān)鍵字等于給定的數(shù)據(jù)元素或（記錄）。

若查找表中存在這樣一個(gè)記錄，則稱“查找成功”，查找結(jié)果：給出整個(gè)記錄的信息，或指示該記錄在查找表中的位置；否則稱“查找不成功”，查找結(jié)果：給出“空記錄”或“空指針”。

由于查找表本身是一種松散的集合結(jié)構(gòu)，數(shù)據(jù)元素之間不存在明顯的組織規(guī)律，因此不便于查找。如：修自行車時(shí)，從雜物盒中找鏍釘。為了提高查找的效率，需要在查找表松散的集合元素之間人為地附加某種確定的關(guān)系，以便按某種規(guī)則進(jìn)行查找，即

用另外一種數(shù)據(jù)結(jié)構(gòu)來表示查找表。即：將雜物盒中的鏍釘分類。如何進(jìn)行查找？查找的方法取決于查找表的結(jié)構(gòu)。衡量一個(gè)算法好壞的量度有三條：

時(shí)間復(fù)雜度(衡量算法執(zhí)行的時(shí)間量級(jí))

空間復(fù)雜度(衡量算法的數(shù)據(jù)結(jié)構(gòu)所占存儲(chǔ)以及大量的附加存儲(chǔ))

算法的其它性能查找操作的性能分析:查找算法中的基本操作是“將記錄的關(guān)鍵字和給定值進(jìn)行比較”，因此，通常以“平均查找長(zhǎng)度”作為衡量查找算法的好壞。不再采用時(shí)間復(fù)雜度作依據(jù)。

查找算法的平均查找長(zhǎng)度ASL

(AverageSearchLength)

為確定記錄在表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字次數(shù)的期望值稱為查找算法在查找成功時(shí)的平均查找長(zhǎng)度。查找操作的時(shí)間性能分析對(duì)于含有n個(gè)數(shù)據(jù)元素的表,查找成功時(shí)的平均查找長(zhǎng)度為

:nASL=ΣPiCi

i=1

其中:Pi——為查找第i個(gè)數(shù)據(jù)元素的概率,且Ci——為找到表中其關(guān)鍵字與給定值相等的第i個(gè)記錄時(shí),和給定值已進(jìn)行過比較的關(guān)鍵字個(gè)數(shù)。在等概率查找的情況下，順序表查找的平均查找長(zhǎng)度為：對(duì)順序表每進(jìn)行一次查找，我們需比較的數(shù)據(jù)元素的關(guān)鍵字的個(gè)數(shù)幾乎是表長(zhǎng)的一半。7.2靜態(tài)查找表數(shù)據(jù)對(duì)象D：數(shù)據(jù)關(guān)系R：D是具有相同特性的數(shù)據(jù)元素的集合。每個(gè)數(shù)據(jù)元素含有類型相同的關(guān)鍵字，可唯一標(biāo)識(shí)數(shù)據(jù)元素。

數(shù)據(jù)元素同屬一個(gè)集合。抽象數(shù)據(jù)類型靜態(tài)查找表的定義為:ADTStaticSearchTable{

Create(&ST,n);Destroy(&ST);Search(ST,key);Traverse(ST,Visit());基本操作P：next}ADTStaticSearchTable若ST中存在其關(guān)鍵字等于

key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”。

Search(ST,key);初始條件：操作結(jié)果：靜態(tài)查找表ST存在，key為和查找表中元素的關(guān)鍵字類型相同的給定值；7.2.1順序查找7.2.2折半表的查找7.2.3索引順序表的查找順序查找又稱線性查找。其基本思想是：從靜態(tài)查找表的一端開始，將給定記錄的關(guān)鍵字與表中各記錄的關(guān)鍵字逐一比較，若表中存在要查找的記錄，則查找成功，并給出該記錄在表中的位置；否則，查找失敗，并給出失敗信息。7.2順序查找表ST.elemii例:在順序查找表中查找一個(gè)key=64的給定值在下標(biāo)變量為0處賦值給定值key，叫設(shè)置監(jiān)視哨，所賦的給定值叫哨兵。從表中最后一個(gè)記錄開始,逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較,指針向前移，計(jì)數(shù)器i-1，直到某個(gè)記錄的關(guān)鍵字和給定值比較相等為止,則查找成功,找到所查記錄;iii64監(jiān)視哨

i指針從表長(zhǎng)開始，不相等時(shí)i-1,當(dāng)i指針移到0位置時(shí)，就自然停住了，指針不會(huì)出界,因?yàn)樵诖颂幰欢ㄊ窍嗟鹊?。在整個(gè)查找過程中不需檢驗(yàn)i值是否大于0，這就是順序表查找過程。監(jiān)視哨ST.elemiikey=60iii60i靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)為算法7.1//----------靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)-----------#defineLIST_INIT_SIZE100//線性表存儲(chǔ)空間的初始分配量typedef

struct{

ElemType*elem; //存儲(chǔ)空間基址

intlength; //當(dāng)前線性表長(zhǎng)度

int

listsize; //當(dāng)前分配的存儲(chǔ)容量(以sizeof(ElemType)為單位)}SqList;int

Search_Seq(SSTableST,

KeyTypekey){

//在順序表ST中順序查找其關(guān)鍵字等于

//key的數(shù)據(jù)元素。若找到，則函數(shù)值為

//該元素在表中的位置，否則為0。

ST.elem[0].key=key;//設(shè)置“哨兵”

for(i=ST.length；ST.elem[i].key!=key;--i);

//從后往前找，i的初值是表長(zhǎng)，終值元素是//賦的值，在不相等的情況下i-1。

returni;//找不到時(shí)，i為0；找到時(shí)，i大于0。}//Search_Seqintmain() //主程序用來檢驗(yàn)順序查找算法7.1{

SqList

st;

inti;

st.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));

for(i=1;i<=6;i++)st.elem[i]=i;st.length=6;//構(gòu)造靜態(tài)查找表st=(1,2,3,4,5,6)

i=Search(st,5);

//調(diào)用順序查找方法，在查找表st中查找5是否存在

printf(“位置為：%d\n”,i);i=Search(st,8); //調(diào)用順序查找方法，在查找表st中查找8是否存在

printf(“位置為：%d\n”,i); //不存在位置為0}性能分析：假設(shè)順序表中每個(gè)記錄的查找概率相同，即pi?=?1/n，查找表中第i個(gè)記錄順序查找的平均查找需進(jìn)行n-i+1次比較，即ci?=?n-i+1。當(dāng)查找成功時(shí)順序查找的平均查找長(zhǎng)度為

ASL?==(n?-?i?+?1)?=?(n+1)/2

當(dāng)查找不成功時(shí)，關(guān)鍵字的比較次數(shù)是n+1次。順序查找的基本操作是關(guān)鍵字的比較，因此，查找表的長(zhǎng)度就是查找算法的時(shí)間復(fù)雜度，即為O(n)。

上述順序查找表的查找算法簡(jiǎn)單，但平均查找長(zhǎng)度較大，不太適用于表長(zhǎng)較大的查找表。7.2.2折半查找表

以有序表（按關(guān)鍵字的大小從小到大或從大到小排列的表）表示靜態(tài)查找表，查找過程可以基于“折半”進(jìn)行。ST.elemST.length折半查找的算法：例如:key=64

的查找過程如下lowhighmidlow

mid

high

mid指針low

指示查找區(qū)間的下界;指針high

指示查找區(qū)間的上界;指針mid=(low+high)/2intSearch_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)行查找

else

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

}return0;//順序表中不存在待查元素}//Search_Bin先看一個(gè)具體的情況，假設(shè)：n=11分析折半查找的平均查找長(zhǎng)度122333344440513192137566475808892從上述查找過程可知：找到第⑥個(gè)元素僅需比較1次；找到第③和第⑨個(gè)元素需比較2次；找到第①、④、⑦和⑩個(gè)元素需比較3次；找到第②、⑤、⑧…需比較4次。這個(gè)查找過程可用二叉樹來描述,通常稱這個(gè)描述查找過程的二叉樹為判定樹，從判定樹上可見，(1)查找到給定值21的過程恰好是走了一條從根到結(jié)點(diǎn)④的路徑，(2)與給定值21進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)為該路徑上的結(jié)點(diǎn)數(shù)或結(jié)點(diǎn)④在判定樹上的層次數(shù)。6391425781011判定樹查找成功時(shí)折半查找的平均查找長(zhǎng)度(ASL):假設(shè)n=2h-1并且查找概率相等則在n>50時(shí)，可得近似結(jié)果

折半查找的效率比順序查找高，但折半查找只適用于有序表，且限于順序存儲(chǔ)結(jié)構(gòu)。（對(duì)線性鏈表無法有效地進(jìn)行折半查找）7.2.3索引順序表是順序查找的一種改進(jìn)方法,在建立順序表的同時(shí)，建立一個(gè)索引。012345678910111213……1708211914313322254052617846……2104057810……例：索引順序表=索引+順序表順序表索引一般情況下，索引表是一個(gè)有序表。例：表中含有18個(gè)記錄，可分成三個(gè)子表(Rl，R2，…，R6)、(R7，R8，…，R12)、(R13，R14，…R18)，對(duì)每個(gè)子表(或稱塊)建立一個(gè)索引項(xiàng)

索引表按關(guān)鍵字有序，則表有序或分塊有序?！胺謮K有序”是第i個(gè)子表中所有記錄的關(guān)鍵字均大于第i-1個(gè)子表中的最大關(guān)鍵字。索引表包括兩項(xiàng)內(nèi)容：關(guān)鍵字項(xiàng)：其值為該子表內(nèi)的最大關(guān)鍵字指針項(xiàng)：指示該子表的第一個(gè)記錄在表中位置137186482286745860484442338131222索引表最大關(guān)鍵字

起始地址17

1338244953920

假設(shè)給定值key=38，則先將key依次和索引表中各最大關(guān)鍵字進(jìn)行比較，由于22<key<48，則關(guān)鍵字為38的記錄若存在，必定在第二個(gè)子表中，由于索引表中的指針項(xiàng)指示第二個(gè)子表中的第一個(gè)記錄是表中第7個(gè)記錄，則自第7個(gè)記錄起進(jìn)行順序查找，直到ST.elem[10].key=38為止。137186482286745860384842338131222索引表最大關(guān)鍵字起始地址分塊查找過程需分兩步進(jìn)行：（1）確定待查記錄所在的塊(子表)；（2）在塊中順序查找。17

13137186482286745860384842338131222索引表最大關(guān)鍵字起始地址

索引表是有序的，子表不是有序的但是有限的。

每個(gè)子表中都有空格字符，可直接插入元素而不移動(dòng)其它元素。索引順序查找表由有序表和順序表的簡(jiǎn)單合成17

13例如：在一個(gè)系中有多個(gè)班級(jí)，索引表中是班級(jí)名，子表中是每個(gè)班級(jí)中同學(xué)的名單，是有限的，當(dāng)有插班的同學(xué)時(shí)，可直接將其姓名插入，索引表不變。索引順序查找的平均查找長(zhǎng)度為在索引中進(jìn)行查找的平均查找長(zhǎng)度和在“順序表”中進(jìn)行查找的平均查找長(zhǎng)度之和。

7.3.1哈希表的基本概念7.3.2哈希函數(shù)的構(gòu)造方法

7.3.3

理沖突的方法

7.3.4哈希表的查找7.3哈希表

以上兩節(jié)討論了查找表的查找的過程為給定值依次和關(guān)鍵字集合中各個(gè)關(guān)鍵字進(jìn)行比較。7.3.1哈希表的基本概念共同特點(diǎn)：記錄在表中的位置和它的關(guān)鍵字之間不存在一個(gè)確定的關(guān)系。

不同的表示方法，其差別僅在于：關(guān)鍵字和給定值進(jìn)行比較的順序不同。前幾節(jié)幾種方法表示的查找表，其平均查找長(zhǎng)度都不為零。

查找的效率取決于和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)即平均查找長(zhǎng)度ASL。對(duì)于頻繁使用的查找表，希望平均查找長(zhǎng)度ASL=0。只有一個(gè)辦法：預(yù)先知道所查關(guān)鍵字在表中的位置。

即，要求：記錄在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系。因此，需在關(guān)鍵字與記錄在表中的存儲(chǔ)位置之間建立一個(gè)函數(shù)關(guān)系。以f(key)作為關(guān)鍵字為key的記錄在表中的位置，通常稱這個(gè)函數(shù)f(key)為哈希函數(shù)。{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}例如：對(duì)于如下9個(gè)關(guān)鍵字設(shè)哈希函數(shù)

f(key)=

(Ord(第一個(gè)字母))/2

ChenZhaoQianSunLiWuHanYeDei問題:

若添加關(guān)鍵字Zhou,怎么辦？能否找到另一個(gè)哈希函數(shù)？261917

1)哈希函數(shù)是一個(gè)映象，即：將關(guān)鍵字的集合映射到某個(gè)地址集合上，

它的設(shè)置很靈活，只要這個(gè)地址集合的大小不超出允許范圍即可；從這個(gè)例子可見：

2)由于哈希函數(shù)是一個(gè)壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突”現(xiàn)象，即：

key1

key2，而

f(key1)=f(key2)。

3)

很難找到一個(gè)不產(chǎn)生沖突的哈希函數(shù)。一般情況下，只能選擇恰當(dāng)?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。

因此，在構(gòu)造這種特殊的“查找表”時(shí)，除了需要選擇一個(gè)“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外；還需要找到一種“處理沖突”

的方法。哈希表的定義：

根據(jù)設(shè)定的哈希函數(shù)H(key)

和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個(gè)有限的、地址連續(xù)的地址集(區(qū)間)上，并以關(guān)鍵字在地址集中的“象”作為相應(yīng)記錄在表中的存儲(chǔ)位置，如此構(gòu)造所得的查找表稱之為“哈希表”。對(duì)于哈希表，主要考慮兩個(gè)問題，其一是如何構(gòu)造哈希函數(shù)，其二是如何解決哈希沖突。對(duì)于如何構(gòu)造哈希函數(shù)，應(yīng)解決兩個(gè)主要問題：(1)哈希函數(shù)是一個(gè)壓縮映像函數(shù)，它具有較大的壓縮性，不可避免地產(chǎn)生沖突。(2)哈希函數(shù)具有較好的散列性，盡可能均勻地把記錄映射到各個(gè)存儲(chǔ)地址上，盡量減少?zèng)_突的產(chǎn)生，從而提高查找效率。7.3.2構(gòu)造哈希函數(shù)的方法

構(gòu)造哈希函數(shù)時(shí)，一般都要對(duì)關(guān)鍵字進(jìn)行計(jì)算，為了盡量避免產(chǎn)生相同的哈希函數(shù)值，應(yīng)使關(guān)鍵字的所有組成成分都能起作用。對(duì)數(shù)字的關(guān)鍵字可有下列構(gòu)造方法：

若是非數(shù)字關(guān)鍵字，則需先對(duì)其進(jìn)行數(shù)字化處理。1.

直接定址法4.平方取中法2.除留余數(shù)法3.數(shù)字分析法哈希函數(shù)為關(guān)鍵字的線性函數(shù)

H(key)=key或者

H(key)=a

key+b1.

直接定址法此法僅適合于：地址集合的大小==關(guān)鍵字集合的大小2.除留余數(shù)法

設(shè)定哈希函數(shù)為:

H(key)=keyMODp

其中，

p≤m(表長(zhǎng))

對(duì)P的選擇很重要。

給定一組關(guān)鍵字為：12,39,18,24,33,21，若取p=9,則他們對(duì)應(yīng)的哈希函數(shù)值將為：

3,3,0,6,6,3例如：為什么要對(duì)p加以選擇？

可見，若p中含質(zhì)因子3，

則所有含質(zhì)因子3的關(guān)鍵字均映射到“3的倍數(shù)”的地址上，從而增加了“沖突”的可能。此方法僅適合于：

能哈希表中可能出現(xiàn)的關(guān)鍵字是事先知道的。3.

數(shù)字分析法

假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址。例如，有80個(gè)記錄，要構(gòu)造的哈希表長(zhǎng)度為100。為了不失一般性，取其中8個(gè)記錄的關(guān)鍵字進(jìn)行分析，8個(gè)關(guān)鍵字如下所示：1231034612560783114201282113151712850435222416512178187421600002…..…..

分析：8個(gè)關(guān)鍵字可知，關(guān)鍵字從左到右的第1、2、5位的取值比較集中，不宜作為哈希地址，剩余的第3、4、6、7、8位取值近乎隨機(jī)，可選取其中的兩位作為哈希地址。設(shè)選取第6和7位作為哈希地址，則8個(gè)關(guān)鍵碼的哈希地址為34、78、12、51、43、65、87、02。4．平方取中法

平方取中法是指取關(guān)鍵字平方后的中間幾位作為哈希地址。這是一種較常用的構(gòu)造哈希函數(shù)的方法。但是，在選定哈希函數(shù)時(shí)不一定能知道關(guān)鍵字的全部情況，取其中的哪幾位也不一定合適，而一個(gè)數(shù)平方后的中間幾位數(shù)與數(shù)的每一位都相關(guān)，所以，隨機(jī)分布的關(guān)鍵字得到的，哈希地址也是隨機(jī)的，取的位數(shù)由表長(zhǎng)決定。實(shí)際造表時(shí)，采用何種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小。7.3.3處理沖突的方法

“處理沖突”

的實(shí)際含義是：為產(chǎn)生沖突的地址尋找下一個(gè)哈希地址。1.開放定址法2.鏈表法

為產(chǎn)生沖突的地址H(key)尋找下一個(gè)哈希地址：

H=

H(key)MODm

Hi=(H(key)+di

)MODm

i=1,2,…,s1≤s≤m-11.開放定址法對(duì)增量di

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

di=c

i

最簡(jiǎn)單的情況c=12)平方探測(cè)再散列

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

di

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

或者

di=i×H2(key)

(又稱雙散列函數(shù)探測(cè))例7.3已知9個(gè)記錄的關(guān)鍵字為(12，22，25，38，24，47，29，16，36)，試構(gòu)造哈希表存放這9個(gè)記錄。哈希函數(shù)為H(key)?=?keymod12，哈希表的內(nèi)存空間為12個(gè)存儲(chǔ)單元。采用線性探測(cè)法處理沖突過程如下：

H(key)?=?keymod12?=?12mod12?=?0，不沖突，關(guān)鍵字12放入0號(hào)單元。

H(key)?=?keymod12?=?22mod12?=?10，不沖突，關(guān)鍵字22放入10號(hào)單元。

H(key)?=?keymod12?=?25mod12?=?1，不沖突，關(guān)鍵字25放入1號(hào)單元。

H(key)?=?keymod12?=?38mod12?=?2，不沖突，關(guān)鍵字38放入2號(hào)單元。

H(key)?=?keymod12?=?24mod12?=?0，沖突，按照處理沖突的方法求下一個(gè)哈希地址。

H1?=?0?+?1?=?1，1號(hào)單元有記錄，沖突。

H2?=?0+2?=?2，沖突。

H3?=?0+3?=?3，不沖突，關(guān)鍵字24放入3號(hào)單元。

H(key)?=?keymod12?=?47mod12?=?11，不沖突，關(guān)鍵字47放入11號(hào)單元，

H(key)?=?keymod12?=?29mod12?=?5，不沖突，關(guān)鍵字29放入5號(hào)單元，

H(key)?=?keymod12?=?16mod12?=?4，不沖突，關(guān)鍵字16放入4號(hào)單元，

H(key)?=?keymod12?=?36mod12?=?0，沖突，按照處理沖突的方法求下一個(gè)哈希地址。

H1?=?0+1?=?1，1號(hào)單元有記錄，沖突。

H2?=?0+2?=?2，沖突。

H3?=?0+3?=?3，沖突。

H4?=?0+4?=?4，沖突。

H5?=?0+5?=?5，H6?=?0+6?=?6，不沖突，關(guān)鍵字36放入6號(hào)單元。

最后建成的哈希表如書上表7.2所示

例表長(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線性探測(cè)再散列：平方探測(cè)再散列：隨機(jī)探測(cè)再散列：例如:

關(guān)鍵字集合

{19,01,23,14,55,68,11,82,36}設(shè)定哈希函數(shù)

H(key)=keyMOD11(表長(zhǎng)=11)1901231455681901231468若采用線性探測(cè)再散列處理沖突若采用二次探測(cè)再散列處理沖突118236551182360123456140136198223116855

ASL=(6×1+2×2+3)/9=13/9例如:同前例的關(guān)鍵字，哈希函數(shù)為H(key)=keyMOD7平均查找長(zhǎng)度：2.鏈表法將所有哈希地址相同的記錄都鏈接在同一鏈表中。

例7.5已知12個(gè)記錄的關(guān)鍵字為(12,22,25,38,24,47,29,16,37,44,55,50)，試構(gòu)造哈希表存放這12個(gè)記錄，哈希函數(shù)H(key)=keymod12，用鏈表法處理沖突。

H(key)=keymod12=12mod12=0；

H(key)=keymod12=22mod12=10；

H(key)=keymod12=25mod12=1；