數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容 (2)

1、數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容18.1 基本概念8.2 靜態(tài)查找表8.3 動(dòng)態(tài)查找表8.4 哈希表第8章 查找教材第8、11和12章省略，因操作系統(tǒng)課程會(huì)涉及。28.1 基本概念若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄；否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置）查找表查 找查找成功查找不成功靜態(tài)查找動(dòng)態(tài)查找關(guān)鍵字主關(guān)鍵字次關(guān)鍵字由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。查詢(Searching)特定元素是否在表中。只查找，不改變集合內(nèi)的數(shù)據(jù)元素。既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素。記錄中某個(gè)數(shù)據(jù)項(xiàng)的值，可用來識(shí)別一個(gè)記錄 ( 預(yù)先確定的記錄的某種標(biāo)志 ) 可以唯一標(biāo)識(shí)一個(gè)記錄的關(guān)鍵字例如“學(xué)

2、號(hào)”例如“女”是一種數(shù)據(jù)結(jié)構(gòu)識(shí)別若干記錄的關(guān)鍵字3（2）對(duì)查找表常用的操作有哪些？ 查詢某個(gè)“特定的”數(shù)據(jù)元素是否在表中；查詢某個(gè)“特定的”數(shù)據(jù)元素的各種屬性；在查找表中插入一元素；從查找表中刪除一元素。 （3) 有哪些查找方法？ 查找方法取決于表中數(shù)據(jù)的排列方式;討論：（1）查找的過程是怎樣的？ 給定一個(gè)值K，在含有n個(gè)記錄的文件中進(jìn)行搜索，尋找一個(gè)關(guān)鍵字值等于K的記錄，如找到則輸出該記錄，否則輸出查找不成功的信息。例如查字典針對(duì)靜態(tài)查找表和動(dòng)態(tài)查找表的查找方法也有所不同?！疤囟ǖ摹?關(guān)鍵字4（4）如何評(píng)估查找方法的優(yōu)劣？明確：查找的過程就是將給定的K值與文件中各記錄的關(guān)鍵字項(xiàng)進(jìn)行比較的過程

3、。所以用比較次數(shù)的平均值來評(píng)估算法的優(yōu)劣。稱為平均查找長度（ASL：average search length）。其中：n是文件記錄個(gè)數(shù)；Pi是查找第i個(gè)記錄的查找概率（通常取等概率,即Pi =1/n）;Ci是找到第i個(gè)記錄時(shí)所經(jīng)歷的比較次數(shù)。統(tǒng)計(jì)意義上的數(shù)學(xué)期望值物理意義：假設(shè)每一元素被查找的概率相同，則查找每一元素所需的比較次數(shù)之總和再取平均，即為ASL。顯然，ASL值越小，時(shí)間效率越高。 5針對(duì)靜態(tài)查找表的查找算法主要有： 8.2 靜態(tài)查找表靜態(tài)查找表的抽象數(shù)據(jù)類型參見教材P216。一、順序查找（線性查找）二、折半查找（二分或?qū)Ψ植檎遥┤?、靜態(tài)樹表的查找四、分塊查找（索引順序查找）6一、

4、順序查找（ Linear search，又稱線性查找 ）（1）順序表的機(jī)內(nèi)存儲(chǔ)結(jié)構(gòu)：typedef struct ElemType *elem; /表基址，0號(hào)單元留空。表容量為全部元素 int length; /表長，即表中數(shù)據(jù)元素個(gè)數(shù)SSTable;順序查找：即用逐一比較的辦法順序查找關(guān)鍵字，這顯然是最直接的辦法。 對(duì)順序結(jié)構(gòu)如何線性查找？見下頁之例或教材P216；對(duì)單鏈表結(jié)構(gòu)如何線性查找？函數(shù)雖未給出，但也很容易編寫；只要知道頭指針head就可以“順藤摸瓜”；對(duì)非線性樹結(jié)構(gòu)如何順序查找?可借助各種遍歷操作！7（2）算法的實(shí)現(xiàn)：技巧：把待查關(guān)鍵字key存入表頭或表尾（俗稱“哨兵”），這樣可

5、以加快執(zhí)行速度。例：若將待查找的特定值key存入順序表的首部（如0號(hào)單元），則順序查找的實(shí)現(xiàn)方案為：從后向前逐個(gè)比較！int Search_Seq( SSTable ST , KeyType key ) /在順序表ST中，查找關(guān)鍵字與key相同的元素；若成功，返回其位置信息，否則返回0 ST.elem0.key =key; /設(shè)立哨兵，可免去查找過程中每一步都要檢測是否查找完畢。當(dāng)n1000時(shí)，查找時(shí)間將減少一半。 for( i=ST.length; ST.elem i .key!=key; - - i ); /不要用for(i=n; i0; - -i) 或 for(i=1; i=n; i+)

6、 return i; /若到達(dá)0號(hào)單元才結(jié)束循環(huán)，說明不成功，返回0值(i=0)。成功時(shí)則返回找到的那個(gè)元素的位置i。 / Search_Seq8返回特殊標(biāo)志，例如返回空記錄或空指針。前例中設(shè)立了“哨兵”，就是將關(guān)鍵字送入末地址ST.elem0.key使之結(jié)束并返回 i=0。討論 查找效率怎樣計(jì)算？用平均查找長度ASL衡量。討論 查不到怎么辦？討論 如何計(jì)算ASL？分析：查找第1個(gè)元素所需的比較次數(shù)為1；查找第2個(gè)元素所需的比較次數(shù)為2；查找第n個(gè)元素所需的比較次數(shù)為n；總計(jì)全部比較次數(shù)為：12n = (1+n)n/2未考慮查找不成功的情況：查找哨兵所需的比較次數(shù)為n+1這是查找成功的情況若求

7、某一個(gè)元素的平均查找次數(shù)，還應(yīng)當(dāng)除以n（等概率），即： ASL（1n）/2 ，時(shí)間效率為 O(n)9二、折半查找（又稱二分查找或?qū)Ψ植檎遥﹥?yōu)點(diǎn)：算法簡單，且對(duì)順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。缺點(diǎn)： ASL 太長，時(shí)間效率太低。這是一種容易想到的查找方法。先給數(shù)據(jù)排序（例如按升序排好），形成有序表，然后再將key與正中元素相比，若key小，則縮小至右半部內(nèi)查找；再取其中值比較，每次縮小1/2的范圍，直到查找成功或失敗為止。對(duì)順序表結(jié)構(gòu)如何編程實(shí)現(xiàn)折半查找算法？ 見下頁之例，或見教材（P219）對(duì)單鏈表結(jié)構(gòu)如何折半查找？ 無法實(shí)現(xiàn)！因全部元素的定位只能從頭指針head開始對(duì)非線性(樹)結(jié)構(gòu)如何折半查找？

8、 可借助二叉排序樹來查找（屬動(dòng)態(tài)查找表形式）。 如何改進(jìn)？討論 順序查找的特點(diǎn)：10 運(yùn)算步驟：(1) low =1,high =11 ,mid =6 ，待查范圍是 1,11；(2) 若 ST.elemmid.key key，說明keylow ,mid-1， 則令：high =mid1;重算 mid ；(4)若 ST.elem mid .key = key，說明查找成功，元素序號(hào)=mid;結(jié)束條件： （1）查找成功 ： ST.elemmid.key = key （2）查找不成功 ： highlow （意即區(qū)間長度小于0）解： 先設(shè)定3個(gè)輔助標(biāo)志: low,high,mid，折半查找舉例：Low

9、指向待查元素所在區(qū)間的下界high指向待查元素所在區(qū)間的上界mid指向待查元素所在區(qū)間的中間位置 已知如下11個(gè)元素的有序表：（05 13 19 21 37 56 64 75 80 88 92）, 請(qǐng)查找關(guān)鍵字為21 和85的數(shù)據(jù)元素。顯然有：mid= (low+high)/2此例作為自測卷的算法題之一，建議上機(jī)驗(yàn)證。11討論 若關(guān)鍵字不在表中，怎樣得知和停止？典型標(biāo)志是：當(dāng)查找范圍的上界下界時(shí)停止查找。討論 二分查找的效率（ASL）1次比較就查找成功的元素有1個(gè)（20），即中間值；2次比較就查找成功的元素有2個(gè)（21），即1/4處（或3/4）處；3次比較就查找成功的元素有4個(gè)（22），即1/

10、8處（或3/8）處 4次比較就查找成功的元素有8個(gè)（23），即1/16處（或3/16）處 則第m次比較時(shí)查找成功的元素會(huì)有（2m-1）個(gè)；為方便起見，假設(shè)表中全部n個(gè)元素 2m-1個(gè)，此時(shí)就不討論第m次比較后還有剩余元素的情況了。全部比較總次數(shù)為120221322423m2m1 推導(dǎo)過程12平均每個(gè)數(shù)據(jù)的查找時(shí)間還要除以n，所以：（詳細(xì)推導(dǎo)過程見教材P221的附錄1）課堂練習(xí)（多項(xiàng)選擇）：采用鏈?zhǔn)酱尜A結(jié)構(gòu) 記錄的長度128 采用順序存貯結(jié)構(gòu) 記錄按關(guān)鍵字遞增有序使用折半查找算法時(shí)，要求被查文件：思考：假設(shè)在有序線性表a20上進(jìn)行折半查找，則平均查找長度為 。13查找過程可用二叉樹描述：每個(gè)記錄

11、用一個(gè)結(jié)點(diǎn)表示；結(jié)點(diǎn)中值為該記錄在表中位置，這個(gè)描述查找過程的二叉樹稱為判定樹。n個(gè)元素的表的折半查找的判定樹是唯一的，即：判定樹由表中元素個(gè)數(shù)決定。 找到有序表中任一記錄的過程就是：走了一條從根結(jié)點(diǎn)到與該記錄相應(yīng)的結(jié)點(diǎn)的路徑。 比較的關(guān)鍵字個(gè)數(shù)：為該結(jié)點(diǎn)在判定樹上的層次數(shù)。 查找成功時(shí)比較的關(guān)鍵字個(gè)數(shù)最多不超過樹的深度 d : d = log2 n + 1 若所有結(jié)點(diǎn)的空指針域設(shè)置為一個(gè)指向一個(gè)方形結(jié)點(diǎn)的指針，稱方形結(jié)點(diǎn)為判定樹的外部結(jié)點(diǎn)；對(duì)應(yīng)的，圓形結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)。 查找不成功的過程 就是走了一條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑。折半查找效率分析法2（參見教材P220）：14三、靜態(tài)樹表的查找討論

12、2：當(dāng)有序表中各記錄的查找概率不相等時(shí)，該如何查找？首先要明確，此時(shí)用折半查找法未必最優(yōu)?。▍⒁娊滩腜222例）改進(jìn)：若將各記錄概率看作是二叉樹之權(quán)值，則轉(zhuǎn)為研究帶權(quán)路徑長度最小的二叉樹（類似最優(yōu)二叉樹）。討論1：對(duì)有序表還有其他查找算法嗎？靜態(tài)最優(yōu)查找樹算法時(shí)間代價(jià)高；實(shí)用算法：近似最優(yōu)查找樹（次優(yōu)查找樹） （參見教材P222225）有，如斐波那契查找和插值查找等（參見教材P221222）15四、分塊查找（索引順序查找）這是一種順序查找的另一種改進(jìn)方法。先讓數(shù)據(jù)分塊有序，即分成若干子表，要求每個(gè)子表中的數(shù)值（用關(guān)鍵字更準(zhǔn)確）都比后一塊中數(shù)值?。ǖ颖韮?nèi)部未必有序）。然后將各子表中的最大關(guān)鍵字

13、構(gòu)成一個(gè)索引表，表中還要包含每個(gè)子表的起始地址（即頭指針）。索引表最大關(guān)鍵字起始地址2212138920334244382448605874498653第1塊第2塊第3塊224886例：2248861713特點(diǎn)：塊間有序，塊內(nèi)無序16查找步驟分兩步進(jìn)行： 對(duì)索引表使用折半查找法（因?yàn)樗饕硎怯行虮恚?確定了待查關(guān)鍵字所在的子表后，在子表內(nèi)采用順序查找法（因?yàn)楦髯颖韮?nèi)部是無序表）；查找效率：ASL=Lb+Lw對(duì)索引表查找的ASL對(duì)塊內(nèi)查找的ASLS為每塊內(nèi)部的記錄個(gè)數(shù)，n/s即塊的數(shù)目例如當(dāng)n=9，s=3時(shí)，ASLbs=3.5,而折半法為3.1,順序法為517特點(diǎn)：一、二叉排序樹的定義二、二叉

14、排序樹的插入與刪除三、二叉排序樹的查找分析四、平衡二叉樹8.3 動(dòng)態(tài)查找表表結(jié)構(gòu)在查找過程中動(dòng)態(tài)生成。要求：對(duì)于給定值key,若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回；否則插入關(guān)鍵字等于key 的記錄。典型的動(dòng)態(tài)表二叉排序樹18一、二叉排序樹的定義（a）（b）練：下列2種圖形中，哪個(gè)不是二叉排序樹 ？-或是一棵空樹；或者是具有如下性質(zhì)的非空二叉樹： （1）左子樹的所有結(jié)點(diǎn)均小于根的值； （2）右子樹的所有結(jié)點(diǎn)均大于根的值； （3）它的左右子樹也分別為二叉排序樹。討論：對(duì)(a)中序遍歷后的結(jié)果是什么？19二、二叉排序樹的插入與刪除將數(shù)據(jù)元素構(gòu)造成二叉排序樹的優(yōu)點(diǎn)： 查找過程與順序結(jié)構(gòu)有

15、序表中的折半查找相似，查找效率高； 中序遍歷此二叉樹，將會(huì)得到一個(gè)關(guān)鍵字的有序序列（即實(shí)現(xiàn)了排序運(yùn)算）； 如果查找不成功，能夠方便地將被查元素插入到二叉樹的葉子結(jié)點(diǎn)上，而且插入或刪除時(shí)只需修改指針而不需移動(dòng)元素。注：若數(shù)據(jù)元素的輸入順序不同，則得到的二叉排序樹形態(tài)也不同！這種既查找又插入的過程稱為動(dòng)態(tài)查找。二叉排序樹既有類似于折半查找的特性，又采用了鏈表存儲(chǔ)，它是動(dòng)態(tài)查找表的一種適宜表示。204524531290如果待查找的關(guān)鍵字序列輸入順序?yàn)椋海?4，53， 45，45，12，24，90），2453451290查找成功，返回查找成功，返回討論1：二叉排序樹的插入和查找操作 則生成二叉排序樹的

16、過程為：例：輸入待查找的關(guān)鍵字序列=（45，24，53，45，12，24，90）則生成的二叉排序樹形態(tài)不同：查找成功，返回查找成功，返回21二叉排序樹的查找&插入算法如何實(shí)現(xiàn)？查找算法參見教材P228算法9.5（a）;插入算法參見教材P228算法9.5（b）;一種“二合一”的算法如下：22BSTSEARCH(K, t) /K為待查關(guān)鍵字，t為根結(jié)點(diǎn)指針p=t; /p為查找過程中進(jìn)行掃描的指針while(p!=NULL) case K=data(p): 查找成功，return Kdata(p): q=p；p=R_child(p) /繼續(xù)向右搜索 Get(s); data(s)=K; L_chil

17、d(s)=NULL; R_child(s)=NULL; /查找不成功，生成一個(gè)新結(jié)點(diǎn)s，插入到二叉排序樹中case t=NULL： p=s; /若t為空，則插入的結(jié)點(diǎn)s作為根結(jié)點(diǎn)Kdata(q): R_child(q)=s; return OK23對(duì)于二叉排序樹，刪除樹上一個(gè)結(jié)點(diǎn)相當(dāng)于刪除有序序列中的一個(gè)記錄，刪除后仍需保持二叉排序樹的特性。（對(duì)鏈表進(jìn)行刪除操作是很方便的）討論2：二叉排序樹的刪除操作如何刪除一個(gè)結(jié)點(diǎn)？假設(shè)：*p表示被刪結(jié)點(diǎn)的指針； PL和PR 分別表示*P的左、右孩子指針；*f表示*p的雙親結(jié)點(diǎn)指針；并假定*p是*f的左孩子；則可能有三種情況：PR 為 * S 的右子樹； S

18、L 為 Q（ * S的雙親結(jié)點(diǎn)）右孩子*p為葉子： 刪除此結(jié)點(diǎn)時(shí)，直接修改*f指針域即可；*p只有一棵子樹（或左或右）：令PL或PR為*f的左孩子即可；*p有兩棵子樹：情況最復(fù)雜 24*p有兩棵子樹時(shí)，如何進(jìn)行刪除操作？分析：設(shè)刪除前的中序遍歷序列為：. s p PR . /顯然p的直接前驅(qū)是s希望刪除p后，其它元素的相對(duì)位置不變。有兩種解決方法：法1：令*p的左子樹為 *f的左子樹，*p的右子樹為*s的右子樹； /即FL=PL ; FR=PR ;法2：令*s代替*p / *s為*p左子樹最右下的葉子25FCCLSSLQLPPRQPRFCCLSSLQLPPRQ法2:FCCLSSLQLPPRQ法

19、1:例：請(qǐng)從下面的二叉排序樹中刪除結(jié)點(diǎn)P。SSL261) 二叉排序樹上查找某關(guān)鍵字等于給定值的結(jié)點(diǎn)過程，其實(shí)就是走了一條從根到該結(jié)點(diǎn)的路徑。 比較的關(guān)鍵字次數(shù)此結(jié)點(diǎn)的層次數(shù); 最多的比較次數(shù)樹的深度（或高度），即 log2 n+12) 一棵二叉排序樹的平均查找長度為： 三、二叉排序樹的查找分析其中：ni 是每層結(jié)點(diǎn)個(gè)數(shù)； Ci 是結(jié)點(diǎn)所在層次數(shù)；m 為樹深。最壞情況：即插入的n個(gè)元素從一開始就有序， 變成單支樹的形態(tài)！ 此時(shí)樹的深度為n ; ASL= (n+1)/2 此時(shí)查找效率與順序查找情況相同。27最好情況：即：與折半查找中的判定樹相同（形態(tài)比較均衡）3）對(duì)有 n 個(gè)關(guān)鍵字的二叉排序樹的平

20、均查找長度: 設(shè)每種樹態(tài)出現(xiàn)概率相 同 ，查找每個(gè)關(guān)鍵字也是等概率的。則ASL求解過程可推導(dǎo)。 （詳見教材P232）樹的深度為：log 2n +1 ；ASL=log 2(n+1) 1 ；與折半查找相同。結(jié)論：二叉排序樹的ASL2（11/n）ln n28四、平衡二叉樹平衡二叉樹又稱AVL樹，它是具有如下性質(zhì)的二叉樹：為了方便起見，給每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字，給出該結(jié)點(diǎn)左子樹與右子樹的高度差。這個(gè)數(shù)字稱為結(jié)點(diǎn)的平衡因子balance。這樣，可以得到AVL樹的其它性質(zhì)：即|左子樹深度-右子樹深度| 1左、右子樹是平衡二叉樹；所有結(jié)點(diǎn)的左、右子樹深度之差的絕對(duì)值 129(a) 平衡樹 (b) 不平衡樹例：

21、判斷下列二叉樹是否AVL樹？任一結(jié)點(diǎn)的平衡因子只能?。?1、0 或 1；如果樹中任意一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則這棵二叉樹就失去平衡，不再是AVL樹；對(duì)于一棵有n個(gè)結(jié)點(diǎn)的AVL樹，其高度保持在O(log2n)數(shù)量級(jí)，ASL也保持在O(log2n)量級(jí)。00011-1-120001-130如果在一棵AVL樹中插入一個(gè)新結(jié)點(diǎn)，就有可能造成失衡，此時(shí)必須重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)平衡。我們稱調(diào)整平衡過程為平衡旋轉(zhuǎn)?，F(xiàn)分別介紹這四種平衡旋轉(zhuǎn)。平衡旋轉(zhuǎn)可以歸納為四類： LL平衡旋轉(zhuǎn) RR平衡旋轉(zhuǎn) LR平衡旋轉(zhuǎn) RL平衡旋轉(zhuǎn)31若在A的左子樹的左子樹上插入結(jié)點(diǎn)，使A的平衡因子從1增加至2，需要進(jìn)行

22、一次順時(shí)針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）ABCABC若在A的右子樹的右子樹上插入結(jié)點(diǎn)，使A的平衡因子從-1增加至-2，需要進(jìn)行一次逆時(shí)針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）2）RR平衡旋轉(zhuǎn)：ABCABC1）LL平衡旋轉(zhuǎn)：32若在A的右子樹的左子樹上插入結(jié)點(diǎn)，使A的平衡因子從-1增加至-2，需要先進(jìn)行順時(shí)針旋轉(zhuǎn)，再逆時(shí)針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）4）RL平衡旋轉(zhuǎn)：ABCABCABC若在A的左子樹的右子樹上插入結(jié)點(diǎn)，使A的平衡因子從1增加至2，需要先進(jìn)行逆時(shí)針旋轉(zhuǎn)，再順時(shí)針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）ABCABCABC3）LR平衡旋轉(zhuǎn)：這種調(diào)整規(guī)則可以保證二叉排序樹的次序不變33013037024例：請(qǐng)將下面

23、序列構(gòu)成一棵平衡二叉排序樹： （ 13，24，37，90，53）013037-113024-124-213需要RR平衡旋轉(zhuǎn)(繞B逆轉(zhuǎn),B為根）090-124-137053190-237需要RL平衡旋轉(zhuǎn)(繞C先順后逆）037090053037090053 348.4 哈希查找表一、哈希表的概念二、哈希函數(shù)的構(gòu)造方法三、沖突處理方法四、哈希表的查找及分析35一、哈希表的概念哈希表：即散列存儲(chǔ)結(jié)構(gòu)。 散列法存儲(chǔ)的基本思想：建立關(guān)鍵碼字與其存儲(chǔ)位置的對(duì)應(yīng)關(guān)系，或者說，由關(guān)鍵碼的值決定數(shù)據(jù)的存儲(chǔ)地址。 優(yōu)點(diǎn)：查找速度極快（O(1)）,查找效率與元素個(gè)數(shù)n無關(guān)！例1：若將學(xué)生信息按如下方式存入計(jì)算機(jī)，如：

24、將2001011810201的所有信息存入V01單元；將2001011810202的所有信息存入V02單元；將2001011810231的所有信息存入V31單元。欲查找學(xué)號(hào)為2001011810216的信息，便可直接訪問V16！36例2 ： 有數(shù)據(jù)元素序列(14，23，39，9，25，11)，若規(guī)定每個(gè)元素k的存儲(chǔ)地址H（k）k，請(qǐng)畫出存儲(chǔ)結(jié)構(gòu)圖。（注：H（k）k稱為散列函數(shù)）解：根據(jù)散列函數(shù)H（k）k ，可知元素14應(yīng)當(dāng)存入地址為14的單元，元素23應(yīng)當(dāng)存入地址為23的單元，對(duì)應(yīng)散列存儲(chǔ)表（哈希表）如下：討論：如何進(jìn)行散列查找？根據(jù)存儲(chǔ)時(shí)用到的散列函數(shù)H(k)表達(dá)式，迅即可查到結(jié)果！例如，查

25、找key=9,則訪問H(9)=9號(hào)地址，若內(nèi)容為9則成功；若查不到，應(yīng)當(dāng)設(shè)法返回一個(gè)特殊值，例如空指針或空記錄。 地址9111423242539內(nèi)點(diǎn)：空間效率低！37選取某個(gè)函數(shù)，依該函數(shù)按關(guān)鍵字計(jì)算元素的存儲(chǔ)位置，并按此存放；查找時(shí)，由同一個(gè)函數(shù)對(duì)給定值k計(jì)算地址，將k與地址單元中元素關(guān)鍵碼進(jìn)行比，確定查找是否成功。通常關(guān)鍵碼的集合比哈希地址集合大得多，因而經(jīng)過哈希函數(shù)變換后，可能將不同的關(guān)鍵碼映射到同一個(gè)哈希地址上，這種現(xiàn)象稱為沖突。若干術(shù)語 哈希方法 (雜湊法) 哈希函數(shù)(雜湊函數(shù)) 哈 希 表 (雜湊表) 沖 突哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)(雜湊函數(shù))

26、按上述思想構(gòu)造的表稱為哈希表(雜湊表) 38有6個(gè)元素的關(guān)鍵碼分別為：（14，23，39，9，25，11）。選取關(guān)鍵碼與元素位置間的函數(shù)為H(k)=k mod 7通過哈希函數(shù)對(duì)6個(gè)元素建立哈希表：253923914沖突現(xiàn)象舉例：6個(gè)元素用7個(gè)地址應(yīng)該足夠!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有沖突！ 0 1 2 3 4 5 639所以，哈希方法必須解決以下兩個(gè)問題：1）構(gòu)造好的哈希函數(shù)（a）所選函數(shù)盡可能簡單，以便提高轉(zhuǎn)換速度；（b）所選函數(shù)對(duì)關(guān)鍵碼計(jì)算出的地址，應(yīng)在哈希地址集中大致均勻分布，以減少空間浪費(fèi)。2）制定一個(gè)好的解決沖突的方案查找時(shí)，如果從哈

27、希函數(shù)計(jì)算出的地址中查不到關(guān)鍵碼，則應(yīng)當(dāng)依據(jù)解決沖突的規(guī)則，有規(guī)律地查詢其它相關(guān)單元。在哈希查找方法中，沖突是不可能避免的，只能盡可能減少。40二、哈希函數(shù)的構(gòu)造方法常用的哈希函數(shù)構(gòu)造方法有：直接定址法 除留余數(shù)法 乘余取整法數(shù)字分析法 平方取中法 折疊法 隨機(jī)數(shù)法 要求一：n個(gè)數(shù)據(jù)原僅占用n個(gè)地址，雖然散列查找是以空間換時(shí)間，但仍希望散列的地址空間盡量小。要求二：無論用什么方法存儲(chǔ)，目的都是盡量均勻地存放元素，以避免沖突。41Hash(key) = akey + b (a、b為常數(shù))優(yōu)點(diǎn)：以關(guān)鍵碼key的某個(gè)線性函數(shù)值為哈希地址，不會(huì)產(chǎn)生沖突.缺點(diǎn)：要占用連續(xù)地址空間，空間效率低。 例：關(guān)鍵

28、碼集合為100，300，500，700，800，900， 選取哈希函數(shù)為Hash(key)=key/100， 則存儲(chǔ)結(jié)構(gòu)（哈希表）如下：0 1 2 3 4 5 6 7 8 99008007005003001001、直接定址法42Hash(key)= B*( A*key mod 1 ) (A、B均為常數(shù)，且0A 724+518+69 =13115、平方取中法457、隨機(jī)數(shù)法Hash(key) = random ( key ) (random為偽隨機(jī)函數(shù))適用于：關(guān)鍵字長度不等的情況。造表和查找都很方便。 執(zhí)行速度（即計(jì)算哈希函數(shù)所需時(shí)間）； 關(guān)鍵字的長度； 哈希表的大??； 關(guān)鍵字的分布情況； 查

29、找頻率。小結(jié)：構(gòu)造哈希函數(shù)的原則：46三、沖突處理方法常見的沖突處理方法有：開放定址法（開地址法） 鏈地址法（拉鏈法） 再哈希法（雙哈希函數(shù)法）建立一個(gè)公共溢出區(qū) 471、開放定址法（開地址法） 設(shè)計(jì)思路：有沖突時(shí)就去尋找下一個(gè)空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。 具體實(shí)現(xiàn)：Hi=(Hash(key)+di) mod m ( 1i m ) 其中： Hash(key)為哈希函數(shù) m為哈希表長度 di 為增量序列 1，2，m-1，且di=i 1.線性探測法含義：一旦沖突，就找附近（下一個(gè)）空地址存入。48關(guān)鍵碼集為 47，7，29，11，16，92，22，8，3

30、，設(shè)：哈希表表長為m=11； 哈希函數(shù)為Hash(key)=key mod 11； 擬用線性探測法處理沖突。建哈希表如下：解釋： 47、7（以及11、16、92）均是由哈希函數(shù)得到的沒有沖突的哈希地址；0 1 2 3 4 5 6 7 8 9 10477 例：291116922283 Hash(29)=7，哈希地址有沖突，需尋找下一個(gè)空的哈希地址：由H1=(Hash(29)+1) mod 11=8，哈希地址8為空，因此將29存入。 另外，22、8、3同樣在哈希地址上有沖突，也是由H1找到空的哈希地址的。其中3 還連續(xù)移動(dòng)了兩次（二次聚集）49線性探測法的優(yōu)點(diǎn)：只要哈希表未被填滿，保證能找到一個(gè)空地址單元存放有沖突的元素；線性探測法的缺點(diǎn)：可能使第i個(gè)哈希地址的同義詞存入第i+1個(gè)哈希地址，這樣本應(yīng)存入第i+1個(gè)哈希地址的元素變成了第i+2個(gè)哈希地址的同義詞， 因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來，大大降低了查找效率。解決方案：可采用二次探測法或偽隨機(jī)探測法，以改善“堆積”問題。 討論：50仍舉上例，改用二次探測法處理沖突，建表如下： 0 1 2 3 4 5 6 7 8 9 10112234792167298 注：只有3這個(gè)關(guān)鍵碼的沖突處理與上例不同，Hash(3)=3，哈希地址上沖突，由H1=(Hash(3)+12