老師課件-第九章查找

第九章查找數(shù)據(jù)結(jié)構(gòu)9.1查找的基本概念9.2基于線性表的查找法9.3基于樹(shù)的查找法9.4散列表的查找—哈希法主要內(nèi)容列表：由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合，可利用任意數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。關(guān)鍵碼：可以標(biāo)識(shí)一個(gè)記錄的某個(gè)數(shù)據(jù)項(xiàng)。鍵值：關(guān)鍵碼的值。主關(guān)鍵碼：可以唯一地標(biāo)識(shí)一個(gè)記錄的關(guān)鍵碼。次關(guān)鍵碼：不能唯一地標(biāo)識(shí)一個(gè)記錄的關(guān)鍵碼。50女李爽000525女齊梅000447女劉楠000325男張亮000238男王剛0001年齡性別姓名職工號(hào)1972年9月2003年7月1979年9月2003年7月1990年4月參加工作基本概念查找：在具有相同類型的記錄構(gòu)成的集合中找出滿足給定條件的記錄。查找的結(jié)果：若在查找集合中找到了與給定值相匹配的記錄，則稱查找成功；否則，稱查找失敗。50女李爽000525女齊梅000447女劉楠000325男張亮000238男王剛0001年齡性別姓名職工號(hào)1972年9月2003年7月1979年9月2003年7月1990年4月參加工作基本概念靜態(tài)查找：不涉及插入和刪除操作的查找。動(dòng)態(tài)查找：涉及插入和刪除操作的查找。

靜態(tài)查找適用于：查找集合一經(jīng)生成，便只對(duì)其進(jìn)行查找，而不進(jìn)行插入和刪除操作，或經(jīng)過(guò)一段時(shí)間的查找之后，集中地進(jìn)行插入和刪除等修改操作。動(dòng)態(tài)查找適用于：查找與插入和刪除操作在同一個(gè)階段進(jìn)行，例如當(dāng)查找成功時(shí)，要?jiǎng)h除查找到的記錄，當(dāng)查找不成功時(shí)，要插入被查找的記錄。基本概念線性表：適用于靜態(tài)查找，主要采用順序查找技術(shù)、折半查找技術(shù)。樹(shù)

表：適用于動(dòng)態(tài)查找，主要采用二叉排序樹(shù)的查找技術(shù)。散列表：靜態(tài)查找和動(dòng)態(tài)查找均適用，主要采用散列技術(shù)。結(jié)構(gòu)線性表樹(shù)表散列表基本概念查找算法時(shí)間性能通過(guò)關(guān)鍵碼的比較次數(shù)來(lái)度量。關(guān)鍵碼的比較次數(shù)與哪些因素有關(guān)呢？⑴算法；⑵問(wèn)題規(guī)模；⑶待查關(guān)鍵碼在查找集合中的位置；查找算法的時(shí)間復(fù)雜度是問(wèn)題規(guī)模n

和待查關(guān)鍵碼在查找集合中的位置k

的函數(shù)，記為T(mén)(n，k)。同一查找集合、同一查找算法，關(guān)鍵碼的比較次數(shù)與哪些因素有關(guān)呢？基本概念平均查找長(zhǎng)度：將查找算法進(jìn)行的關(guān)鍵碼的比較次數(shù)的數(shù)學(xué)期望值定義為平均查找長(zhǎng)度。計(jì)算公式為：

其中：n

：?jiǎn)栴}規(guī)模，查找集合中的記錄個(gè)數(shù)；

pi

：查找第i個(gè)記錄的概率；

ci

：查找第i個(gè)記錄所需的關(guān)鍵碼的比較次數(shù)。結(jié)論：ci取決于算法；pi與算法無(wú)關(guān)，取決于具體應(yīng)用。如果pi是已知的，則平均查找長(zhǎng)度只是問(wèn)題規(guī)模的函數(shù)。查找算法的性能ASL?==niiicp1基本思想：從線性表的一端向另一端逐個(gè)將關(guān)鍵碼與給定值進(jìn)行比較，若相等，則查找成功，給出該記錄在表中的位置；若整個(gè)表檢測(cè)完仍未找到與給定值相等的關(guān)鍵碼，則查找失敗，給出失敗信息。

101524612354098550123456789i例：查找key＝35iii

靜態(tài)查找表——順序表的查找以順序表或線性鏈表表示靜態(tài)查找表typedefstruct{keyTypekey;//關(guān)鍵字域

……//其它屬性域}ElemType;typedefstruct{ElemType*elem;intlength;}SSTable;intSearch(SSTableST,KeyTypekey){for(i=ST.length;i>0&&ST.elem[i].key!=key;--i);returni;}

順序查找法(線性查找)基本思想：設(shè)置“哨兵”。哨兵就是所要查找的值，將它放在查找方向的盡頭處，免去了在查找過(guò)程中每一次比較后都要判斷查找位置是否越界，從而提高查找速度。

101524612354098550123456789i例：查找k＝35iii哨兵35查找方向

改進(jìn)的順序查找法intSearch(SSTableST,KeyTypekey){ST.elem[0].key=key;for(i=ST.length;ST.elem[i].key!=key;--i);returni;}

改進(jìn)的順序查找法

列表長(zhǎng)度為n，查找第i個(gè)數(shù)據(jù)元素時(shí)需進(jìn)行n-i+1次比較，即ci=n-i+1。又假設(shè)查找每個(gè)數(shù)據(jù)元素的概率相等，即pi=1/n。

平均查找長(zhǎng)度較大，特別是當(dāng)待查找集合中元素較多時(shí)，查找效率較低。順序查找的缺點(diǎn)：算法簡(jiǎn)單而且使用面廣。對(duì)表中記錄的存儲(chǔ)沒(méi)有任何要求，順序存儲(chǔ)和鏈接存儲(chǔ)均可；對(duì)表中記錄的有序性也沒(méi)有要求，無(wú)論記錄是否按關(guān)鍵碼有序均可。順序查找的優(yōu)點(diǎn)：

順序查找法的優(yōu)缺點(diǎn)使用條件：

在有序表中，取中間元素作為比較對(duì)象，1、若給定值與中間記錄的關(guān)鍵字相等，則查找成功；2、若給定值小于中間記錄的關(guān)鍵字，則在中間記錄的左半?yún)^(qū)繼續(xù)查找；3、若給定值大于中間記錄的關(guān)鍵字，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過(guò)程，直到查找成功，或所查找的區(qū)域無(wú)記錄（low>high），查找失敗。

有序表的查找——折半查找

線性表中的記錄必須按關(guān)鍵字有序；必須采用順序存儲(chǔ)?；舅枷耄豪翰檎抑禐?4的記錄的過(guò)程：012345678910111213

7141821232931353842464952low=1high=13mid=7

high=6mid=3

high=2

mid=1

31>1418>147<14low=2mid=2

14=14例：查找值為22的記錄的過(guò)程：012345678910111213

7141821232931353842464952low=1high=13mid=7

high=6mid=3

high=4

mid=5

31>2218<2223>22low=4mid=4

21<22low=5low>highintSearch_Bin(SSTableST,KeyTypekey){low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(key==ST.elem[mid].key)returnmid;elseif(key<ST.elem[mid].key)high=mid-1;elselow=mid+1;}return0;}

折半查找的算法折半查找成功時(shí)的平均查找長(zhǎng)度為：ASLbs＝i=1nPiCi＝n1j=1nj×2j-1＝nn+1log2(n+1)-1優(yōu)點(diǎn)：

比較次數(shù)少，查找速度快，平均性能好。缺點(diǎn)：

要求待查的表為有序表。

折半查找的性能分析動(dòng)態(tài)查找表：結(jié)構(gòu)本身是在查找過(guò)程中動(dòng)態(tài)生成的，即對(duì)于給定值key，若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回，否則插入關(guān)鍵字等于key的記錄。動(dòng)態(tài)查找表二叉排序樹(shù)平衡二叉樹(shù)B樹(shù)

動(dòng)態(tài)查找表二叉排序樹(shù)(二叉查找樹(shù))：或者是一棵空的二叉樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：⑴若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；⑵若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；⑶它的左右子樹(shù)也都是二叉排序樹(shù)。二叉排序樹(shù)的定義采用的是遞歸方法。

二叉排序樹(shù)二叉排序樹(shù)非二叉排序樹(shù)6390554258104567837063605582581045678370中序遍歷二叉排序樹(shù)可以得到一個(gè)關(guān)鍵碼有序序列。

二叉排序樹(shù)typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;

二叉排序樹(shù)—存儲(chǔ)結(jié)構(gòu)通常，取二叉鏈表作為二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu)。在二叉排序樹(shù)中查找給定值的過(guò)程是：⑴若二叉排序樹(shù)是空樹(shù)，則查找失敗；(2)若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功；(3)若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹(shù)上進(jìn)行查找；(4)若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹(shù)上進(jìn)行查找。

二叉排序樹(shù)的查找50308020908540358832例如:二叉排序樹(shù)查找關(guān)鍵字==50,505035,503040355090,50809095,BitTreeSearchBST(BiTreeT,KeyTypekey){

if((!T)||(key==T->data.key))return(T);

else

if(key<T->data.key

)return(SearchBST(T->lchild,key));

elsereturn(SearchBST(T->rchild,key));}二叉排序樹(shù)的查找二叉排序樹(shù)的查找性能分析由序列{3,1,2,5,4}得到二叉排序樹(shù)：由序列{1,2,3,4,5}得到二叉排序樹(shù)：ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.21234531254二叉排序樹(shù)的查找性能分析由此可見(jiàn)，在二叉排序樹(shù)上進(jìn)行查找時(shí)的平均查找長(zhǎng)度和二叉排序樹(shù)的形態(tài)有關(guān)。最壞情況：二叉排序樹(shù)是通過(guò)把一個(gè)有序表的n個(gè)結(jié)點(diǎn)一次插入生成的，由此得到的二叉排序樹(shù)為一顆深度為n的單支樹(shù)，它的平均查找長(zhǎng)度和單鏈表上的順序查找相同，也是(n+1)/2。最好情況：二叉排序樹(shù)在生成過(guò)程中，樹(shù)的形態(tài)比較均勻，即樹(shù)中各結(jié)點(diǎn)的左右子樹(shù)的深度差距不大的樹(shù)，此時(shí)他的平均查找長(zhǎng)度大約是log2n。1、若二叉排序樹(shù)是空樹(shù)，結(jié)點(diǎn)s成為二叉排序樹(shù)的根；2、若二叉樹(shù)排序樹(shù)非空，則將s的關(guān)鍵字值key與二叉樹(shù)排序樹(shù)的根進(jìn)行比較，①如果s的值等于根結(jié)點(diǎn)的值，則停止插入；②如果s的值小于根結(jié)點(diǎn)的值，則將s插入左子樹(shù)；③如果s的值大于根結(jié)點(diǎn)的值，則將s插入右子樹(shù)。插入一個(gè)關(guān)鍵字值為key的結(jié)點(diǎn)s，插入的方法：

二叉排序樹(shù)的插入6355905870985563root∧9058∧∧70∧∧98∧∧sroot∧

二叉排序樹(shù)的插入

給定一個(gè)元素序列，可以利用插入算法創(chuàng)建一棵二叉排序樹(shù)。將二叉排序樹(shù)初始化為一棵空樹(shù)，然后逐個(gè)讀入元素，每讀入一個(gè)元素，就建立一個(gè)新的結(jié)點(diǎn)插入到當(dāng)前已生成的二叉排序樹(shù)中，即調(diào)用上述二叉排序樹(shù)的插入算法將新結(jié)點(diǎn)插入。直到所有結(jié)點(diǎn)插入完成，二叉排序樹(shù)就構(gòu)造完成了。分析：若二叉排序樹(shù)為空樹(shù)，則新插入的結(jié)點(diǎn)為新的根結(jié)點(diǎn)；否則，新插入的結(jié)點(diǎn)必為一個(gè)新的葉子結(jié)點(diǎn)，其插入位置由查找過(guò)程得到。

二叉排序樹(shù)的構(gòu)造從空的二叉排序樹(shù)開(kāi)始，依次插入一個(gè)個(gè)結(jié)點(diǎn)。例：關(guān)鍵碼集合為

{63，90，70，55，58}7.3樹(shù)表的查找技術(shù)6355905870

二叉排序樹(shù)的構(gòu)造1、關(guān)鍵字的輸入順序?yàn)椋?5,24,53,12,28,90，構(gòu)造二叉排序樹(shù)4524531228902、關(guān)鍵字的輸入順序?yàn)椋?4,53,

90,

12,

28,

45

，構(gòu)造二叉排序樹(shù)241228539045結(jié)論：對(duì)同樣一組數(shù)據(jù)元素，如果輸入的順序不同，則所建的二叉樹(shù)形態(tài)也不同。一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵二叉排序樹(shù)而變成一個(gè)有序序列;每次插入的新結(jié)點(diǎn)都是二叉排序樹(shù)上新的葉子結(jié)點(diǎn);找到插入位置后，不必移動(dòng)其它結(jié)點(diǎn)，僅需修改某個(gè)結(jié)點(diǎn)的指針；在左子樹(shù)/右子樹(shù)的查找過(guò)程與在整棵樹(shù)上查找過(guò)程相同；新插入的結(jié)點(diǎn)沒(méi)有破壞原有結(jié)點(diǎn)之間的關(guān)系。小結(jié)：

二叉排序樹(shù)的構(gòu)造二叉排序樹(shù)的刪除

在二叉排序樹(shù)上刪除某個(gè)結(jié)點(diǎn)之后，仍然保持二叉排序樹(shù)的特性。分三種情況討論：被刪除的結(jié)點(diǎn)是葉子；被刪除的結(jié)點(diǎn)只有左子樹(shù)或者只有右子樹(shù)；被刪除的結(jié)點(diǎn)既有左子樹(shù)，也有右子樹(shù)。

二叉排序樹(shù)的刪除1.若結(jié)點(diǎn)p是葉子，則直接刪除結(jié)點(diǎn)p；2.若p結(jié)點(diǎn)只有左子樹(shù)，或只有右子樹(shù)，則因?yàn)樵摻Y(jié)點(diǎn)只有左子樹(shù)或只有右子樹(shù)，也就是說(shuō)，其后繼只有一個(gè)分支。刪除該結(jié)點(diǎn)時(shí)，只要將被刪除結(jié)點(diǎn)的唯一后繼（左子樹(shù)或右子樹(shù)）直接鏈接到被刪除結(jié)點(diǎn)的位置即可。3.若結(jié)點(diǎn)p的左右子樹(shù)均不空：首先找到p結(jié)點(diǎn)在中序序列中的直接前驅(qū)s結(jié)點(diǎn)，然后用s結(jié)點(diǎn)的值，替代p結(jié)點(diǎn)的值，再將s結(jié)點(diǎn)刪除,因?yàn)閟的右指針一定為空，所以只要把s的左孩子鏈接到s結(jié)點(diǎn)本身的位置即可。

二叉排序樹(shù)的刪除50308020403590858832（2）被刪除的結(jié)點(diǎn)只有左子樹(shù)或者只有右子樹(shù)

其雙親結(jié)點(diǎn)的相應(yīng)指針域的值改為“指向被刪除結(jié)點(diǎn)的左子樹(shù)或右子樹(shù)”。被刪關(guān)鍵字=3580503080209085883532（3）被刪除的結(jié)點(diǎn)既有左子樹(shù)，也有右子樹(shù)4040以其前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點(diǎn)被刪關(guān)鍵字=50StatusDeleteBST(BiTree&T,KeyTypekey){if(!T)returnFALSE;else{if(key==T->data.key){Delete(T);returnTRUE;} elseif(key<T->data.key)DeleteBST(T->lchild,key);elseDeleteBST(T->rchild,key);}}平衡二叉樹(shù)：或者是一棵空的二叉排序樹(shù)，或者是具有下列性質(zhì)的二叉排序樹(shù)：⑴根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的深度最多相差1;⑵根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)也都是平衡二叉樹(shù)。平衡因子：結(jié)點(diǎn)的平衡因子是該結(jié)點(diǎn)的左子樹(shù)的深度與右子樹(shù)的深度之差。在平衡二叉樹(shù)中，結(jié)點(diǎn)的平衡因子可以是1，0，-1。

平衡二叉樹(shù)548254821

平衡樹(shù)非平衡樹(shù)在平衡樹(shù)中，結(jié)點(diǎn)的平衡因子可以是1，0，-1。結(jié)點(diǎn)的平衡因子＝HL-HR

平衡二叉樹(shù)最小不平衡子樹(shù)：

在平衡二叉樹(shù)的構(gòu)造過(guò)程中，以距離插入結(jié)點(diǎn)最近的、且平衡因子絕對(duì)值大于1的祖先結(jié)點(diǎn)為根的子樹(shù)。542814

最小不平衡子樹(shù)

在構(gòu)造二叉排序樹(shù)的過(guò)程中，每插入一個(gè)結(jié)點(diǎn)時(shí)，首先檢查是否因插入新結(jié)點(diǎn)而破壞了樹(shù)的平衡性，若是，則找出最小不平衡子樹(shù)，在保持二叉排序樹(shù)特性的前提下，調(diào)整最小不平衡子樹(shù)中各結(jié)點(diǎn)之間的鏈接關(guān)系，進(jìn)行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹(shù)。

平衡二叉樹(shù)構(gòu)造【基本思想】

設(shè)結(jié)點(diǎn)A為最小不平衡子樹(shù)的根結(jié)點(diǎn)，則失去平衡后進(jìn)行調(diào)整的規(guī)律可歸納為下列四種情況：

1.LL型：由于在A的左子樹(shù)根結(jié)點(diǎn)B的左子樹(shù)上插入結(jié)點(diǎn)，A的平衡因子由1變?yōu)?。

2.RR型：由于在A的右子樹(shù)根結(jié)點(diǎn)B的右子樹(shù)上插入結(jié)點(diǎn)，A的平衡因子由-1變?yōu)?2。

3.LR型：由于在A的左子樹(shù)根結(jié)點(diǎn)B的右子樹(shù)上插入結(jié)點(diǎn)，A的平衡因子由1變?yōu)?。

4.RL型：由于在A的右子樹(shù)根結(jié)點(diǎn)B的左子樹(shù)上插入結(jié)點(diǎn)，A的平衡因子由1變?yōu)?。

平衡二叉樹(shù)的調(diào)整插入前插入后、調(diào)整前順時(shí)針平衡二叉樹(shù)——LL型A1BLhBRh0ARhBh2BLhBRh1ARABXh+1BLhARBRh00BAX

以B為軸，對(duì)A做了一次順時(shí)針旋轉(zhuǎn)，即將A改為B的右孩子，B原來(lái)的右孩子改為A的左孩子61→2例:LL型

108791291012876平衡二叉樹(shù)——RR型插入前插入后，調(diào)整前逆時(shí)針A-1BLhBRh0ALhBXA-2BLhBRh-1ALhBBALhBLh0BRh+1AX0

以B為軸，對(duì)A做了一次逆時(shí)針旋轉(zhuǎn)，即將A改為B的左孩子，B原來(lái)的左孩子改為A的右孩子插入后，調(diào)整前先逆時(shí)針旋轉(zhuǎn)再順時(shí)針旋轉(zhuǎn)A2CLh-1BLh-1ARhBCCRh-1XXACLh-1CBCRh-1ARhBLhARhCACRh-1BCLh-1X0-10BLh平衡二叉樹(shù)——LR型1、將B改為其右子樹(shù)根結(jié)點(diǎn)C的左孩子，而C原來(lái)的左孩子改為B的右孩子，相當(dāng)于以C為軸，對(duì)B作了一次逆時(shí)針旋轉(zhuǎn)；

2、將A改為C的右孩子，C原來(lái)的右孩子改為A的左孩子，相當(dāng)于以C為軸，對(duì)A進(jìn)行了一次順時(shí)針旋轉(zhuǎn)。插入后，調(diào)整前先順時(shí)針旋轉(zhuǎn)再逆時(shí)針旋轉(zhuǎn)XACLh-1BRhCBCRh-1ALhA-2CLh-1BRh1ALhBCCRh-1XBRhCBCRh-1AALhCLh-1X001平衡二叉樹(shù)——RL型1、將B改為其左子樹(shù)根結(jié)點(diǎn)C的右孩子，而C原來(lái)的右孩子改為B的左孩子，相當(dāng)于以C為軸，對(duì)B作了一次順時(shí)針旋轉(zhuǎn)；

2、將A改為C的左孩子，C原來(lái)的左孩子改為A的右孩子，相當(dāng)于以C為軸，對(duì)A進(jìn)行了一次逆時(shí)針旋轉(zhuǎn)。課堂練習(xí)：設(shè)有關(guān)鍵碼序列{5,4,2,8,6,9}，構(gòu)造平衡樹(shù)542LL型42586864256842585642課堂練習(xí)：設(shè)有關(guān)鍵碼序列{5,4,2,8,6,9}，構(gòu)造平衡樹(shù)RL型旋轉(zhuǎn)1次RL型旋轉(zhuǎn)2次856429RR型846529課堂練習(xí)：設(shè)有關(guān)鍵碼序列{5,4,2,8,6,9}，構(gòu)造平衡樹(shù)例：設(shè)序列{20，35，40，15，30，25}，構(gòu)造平衡樹(shù)。203540352040153025352040153025202515354030354030202515例：設(shè)序列{20，35，40，15，30，25}，構(gòu)造平衡樹(shù)。（1）查找應(yīng)插位置，同時(shí)記錄離插入位置最近的可能失衡結(jié)點(diǎn)A（A的平衡因子不等于0）。（2）插入新結(jié)點(diǎn)S，并修改從A到S路徑上各結(jié)點(diǎn)的平衡因子。（3）根據(jù)A、B的平衡因子，判斷是否失衡以及失衡類型，并做相應(yīng)處理。

平衡二叉樹(shù)的調(diào)整

綜上所述，在一個(gè)平衡二叉排序樹(shù)上插入一個(gè)新結(jié)點(diǎn)S時(shí)，主要包括以下三步：查找操作要完成什么任務(wù)？待查值k確定k在存儲(chǔ)結(jié)構(gòu)中的位置

散列表的查找—哈希表若以下標(biāo)為000~999的順序表表示之。例如：為每年招收的1000名新生建立一張查找表，其關(guān)鍵字為學(xué)號(hào)，其值的范圍為xx000~xx999(前兩位為年份)。

則查找過(guò)程可以簡(jiǎn)單進(jìn)行：取給定值（學(xué)號(hào)）的后三位，不需要經(jīng)過(guò)比較便可直接從順序表中找到待查關(guān)鍵字。哈希法：又稱散列法、雜湊法以及關(guān)鍵字地址計(jì)算法等，相應(yīng)的表稱為哈希表。哈希法的基本思想：首先在元素的關(guān)鍵字k和元素的存儲(chǔ)位置p之間建立一個(gè)對(duì)應(yīng)關(guān)系H，使得p=H(k)，H稱為哈希函數(shù)。創(chuàng)建哈希表時(shí)，把關(guān)鍵字為k的元素直接存入地址為H(k)的單元；以后當(dāng)查找關(guān)鍵字為k的元素時(shí)，再利用哈希函數(shù)計(jì)算出該元素的存儲(chǔ)位置p=H(k)，從而達(dá)到按關(guān)鍵字直接存取元素的目的。

散列表的查找—哈希表設(shè)計(jì)哈希函數(shù)一般應(yīng)遵循以下原則：⑴計(jì)算簡(jiǎn)單。哈希函數(shù)不應(yīng)該有很大的計(jì)算量，否則會(huì)降低查找效率。⑵函數(shù)值即哈希地址分布均勻。函數(shù)值要盡量均勻散布在地址空間，這樣才能保證存儲(chǔ)空間的有效利用并減少?zèng)_突。沖突：對(duì)于兩個(gè)不同關(guān)鍵碼ki≠kj，有H(ki)＝H(kj)，即兩個(gè)不同的記錄需要存放在同一個(gè)存儲(chǔ)位置，ki和kj相對(duì)于f稱做同義詞。

哈希函數(shù)的構(gòu)造【直接定址法】散列函數(shù)是關(guān)鍵碼的線性函數(shù)，即：H(key)=a

key+b（a，b為常數(shù)）例：關(guān)鍵碼集合為{10,30,50,70,80,90}，選取的散列函數(shù)為H(key)=key/10，則散列表為：0123456789103050708090適用情況？事先知道關(guān)鍵碼，關(guān)鍵碼集合不是很大且連續(xù)性較好。

哈希函數(shù)的構(gòu)造方法H(key)=keymodp