數(shù)據(jù)結(jié)構(gòu)第7章查找

1、 2022年3月17日 2022年3月17日 2022年3月17日 第第7 7章查找章查找7.17.1查找的基本概念查找的基本概念7.27.2線性表的查找線性表的查找7.37.3樹表的查找樹表的查找7.47.4哈希表的查找哈希表的查找教學(xué)內(nèi)容教學(xué)內(nèi)容 2022年3月17日 1.熟練掌握順序表和有序表（熟練掌握順序表和有序表（折半查找折半查找）的查找算）的查找算法及其性能分析方法；法及其性能分析方法；2.熟練掌握熟練掌握二叉排序樹的構(gòu)造和查找二叉排序樹的構(gòu)造和查找算法及其性能算法及其性能分析方法；分析方法；3.掌握二叉排序樹的掌握二叉排序樹的插入插入算法，了解二叉排序樹的算法，了解二叉排序樹的刪

2、除算法；刪除算法；4.熟練掌握哈希函數(shù)熟練掌握哈希函數(shù)（除留余數(shù)法）（除留余數(shù)法）的構(gòu)造的構(gòu)造5.熟練掌握哈希函數(shù)熟練掌握哈希函數(shù)解決沖突的方法解決沖突的方法及其特點及其特點 教學(xué)目標教學(xué)目標 2022年3月17日 7.1 7.1 查找的基本概念查找的基本概念 查找表查找表: :由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合 靜態(tài)查找表：靜態(tài)查找表：對查找表沒有修改操作對查找表沒有修改操作 動態(tài)查找表：動態(tài)查找表：對查找表具有修改操作對查找表具有修改操作 關(guān)鍵字關(guān)鍵字記錄中某個數(shù)據(jù)項的值，可用來識別一個記錄記錄中某個數(shù)據(jù)項的值，可用來識別一個記錄 主關(guān)鍵字：主

3、關(guān)鍵字：唯一標識數(shù)據(jù)元素唯一標識數(shù)據(jù)元素 次關(guān)鍵字：次關(guān)鍵字：可以標識若干個數(shù)據(jù)元素可以標識若干個數(shù)據(jù)元素是一種數(shù)據(jù)結(jié)構(gòu)是一種數(shù)據(jù)結(jié)構(gòu) 2022年3月17日 關(guān)鍵字的平均比較次數(shù)關(guān)鍵字的平均比較次數(shù)，也稱，也稱平均搜索長度平均搜索長度ASLASL( (Average Search LengthAverage Search Length) )n n：記錄的個數(shù)：記錄的個數(shù)pipi：查找第：查找第i i個記錄的概率個記錄的概率 ( ( 通常認為通常認為pi =1/n )pi =1/n )cici：找到第：找到第i i個記錄所需的比較次數(shù)個記錄所需的比較次數(shù)niiicpASL1查找算法的評價指標查找

4、算法的評價指標 2022年3月17日 7.2 7.2 線性表的查找線性表的查找一、順序查找（線性查找）一、順序查找（線性查找）二、折半查找（二分或?qū)Ψ植檎遥┒?、折半查找（二分或?qū)Ψ植檎遥?2022年3月17日 順序查找順序查找應(yīng)用范圍：應(yīng)用范圍：順序表或線性鏈表表示的靜態(tài)查找表順序表或線性鏈表表示的靜態(tài)查找表表內(nèi)元素之間無序表內(nèi)元素之間無序typedef struct ElemType *R; /表基址表基址 int length; /表長表長SSTable;順序表的表示順序表的表示 2022年3月17日 int LocateELem(SqList L,ElemType e) for (i=0

5、;i0; - -i) for(i=n; i0; - -i) 或或 for(i=1; i=n; i+)for(i=1; i=n; i+) return i; 2022年3月17日 空間復(fù)雜度：一個輔助空間?？臻g復(fù)雜度：一個輔助空間。 時間復(fù)雜度：時間復(fù)雜度：1) 1) 查找成功時的平均查找長度查找成功時的平均查找長度 設(shè)表中各記錄查找概率相等設(shè)表中各記錄查找概率相等 ASLASLs s(n)=(1+2+ . +n)/n =(n+1)/2(n)=(1+2+ . +n)/n =(n+1)/22)2)查找不成功時的平均查找長度查找不成功時的平均查找長度 ASLASLf f =n+1=n+1順序查找的性

6、能分析順序查找的性能分析 2022年3月17日 算法簡單，對表結(jié)構(gòu)無任何要求（順序和鏈式）算法簡單，對表結(jié)構(gòu)無任何要求（順序和鏈式） n n很大時查找效率較低很大時查找效率較低 改進措施：改進措施：非等概率非等概率查找時，可按照查找概率進查找時，可按照查找概率進行排序。行排序。順序查找算法有特點順序查找算法有特點 2022年3月17日 n n個數(shù)存在一維數(shù)組個數(shù)存在一維數(shù)組A1.nA1.n中，在進行順序查找時，中，在進行順序查找時，這這n n個數(shù)的排列個數(shù)的排列有序或無序有序或無序其平均查找長度其平均查找長度ASLASL不同不同。 練習(xí)練習(xí): :判斷對錯判斷對錯查找概率相等時，查找概率相等時，

7、ASL相同；相同；查找概率不等時，如果從前向后查找，則按查找概率查找概率不等時，如果從前向后查找，則按查找概率由大到小排列的有序表其由大到小排列的有序表其ASL要比無序表要比無序表ASL小。小。 2022年3月17日 lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhi

8、ghmid折半查找折半查找若若k=Rmid.key，查找成功，查找成功若若kRmid.key，則，則low=mid+1 2022年3月17日 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid若若k=Rmid.key，查找成功，查找成功若若kRmid.key

9、，則，則low=mid+1 2022年3月17日 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92low highmid直至直至lowhigh時，查找失敗時，查找失敗 2022年3月17日 折半查找（非遞歸算法）折半查找（非遞歸算法） 設(shè)表長為設(shè)表長為n n，lowlow、highhigh和和midmid分別指向待查元素所分別指向待查元素所在區(qū)間的上界、下界和中點在區(qū)間的上界、下界和中點, ,k k為給定值為給定值

10、 初始時，令初始時，令low=1,high=n,mid=low=1,high=n,mid= (low+high)/2(low+high)/2 讓讓k k與與midmid指向的記錄比較指向的記錄比較若若k=Rmid.keyk=Rmid.key，查找成功查找成功若若kRmid.keykRmid.keykRmid.key，則則low=mid+1low=mid+1 重復(fù)上述操作，直至重復(fù)上述操作，直至lowhighlowhigh時，查找失敗時，查找失敗 2022年3月17日 折半查找（遞歸算法）折半查找（遞歸算法）int Search_Bin (SSTable ST, keyType key, int

11、 low, int high) if(lowhigh) return 0; /查找不到時返回查找不到時返回0 mid=(low+high)/2; if(key與與ST.elemmid.key) return mid; else if(key小于小于ST.elemmid.key) ./遞歸遞歸 else. /遞歸遞歸 2022年3月17日 -13-46-79-101-22-34-55-67-88-910-1111-639147102581112h外結(jié)點外結(jié)點內(nèi)結(jié)點內(nèi)結(jié)點data.key進行比較：進行比較： 若若key等于等于T-data.key，則查找成功，返回根結(jié)點地，則查找成功，返回根結(jié)點地

12、址；址； 若若key小于小于T-data.key，則進一步查找左子樹；，則進一步查找左子樹； 若若key大于大于T-data.key，則進一步查找右子樹。，則進一步查找右子樹?！舅惴ㄋ枷胨惴ㄋ枷搿?2022年3月17日 BSTree SearchBST(BSTree T,KeyType key) if(!T) | key=T-data.key) return T; else if (keydata.key) return SearchBST(T-lchild,key);/在左子樹中繼續(xù)查找在左子樹中繼續(xù)查找 else return SearchBST(T-rchild,key); /在右子樹中

13、繼續(xù)查找在右子樹中繼續(xù)查找 / SearchBST【算法描述算法描述】 2022年3月17日 二叉排序樹的操作插入二叉排序樹的操作插入插入的元素插入的元素一定在一定在葉結(jié)點上葉結(jié)點上若二叉排序樹為空，則插入結(jié)點應(yīng)為若二叉排序樹為空，則插入結(jié)點應(yīng)為根結(jié)點根結(jié)點否則，繼續(xù)在其左、右子樹上查找否則，繼續(xù)在其左、右子樹上查找樹中已有，不再插入樹中已有，不再插入樹中沒有，樹中沒有，查找查找直至某個葉子結(jié)點的左子樹直至某個葉子結(jié)點的左子樹或右子樹為空為止，則插入結(jié)點應(yīng)為該或右子樹為空為止，則插入結(jié)點應(yīng)為該葉子結(jié)葉子結(jié)點點的左孩子或右孩子的左孩子或右孩子 2022年3月17日 451253337241006

14、1907820插入結(jié)點插入結(jié)點2020二叉排序樹的操作插入二叉排序樹的操作插入 2022年3月17日 10， 18， 3， 8， 12， 2， 710101810183101838101838 12101838 122101838 1227從空樹出發(fā)，經(jīng)過一系列的查找、插入操作之后，從空樹出發(fā)，經(jīng)過一系列的查找、插入操作之后，可生成一棵二叉排序樹可生成一棵二叉排序樹二叉排序樹的操作生成二叉排序樹的操作生成 2022年3月17日 不同插入次序的序列生成不同形態(tài)的二叉排序樹不同插入次序的序列生成不同形態(tài)的二叉排序樹4024551237122437405540，24，12，37，5512，24，37

15、，40，55二叉排序樹的操作生成二叉排序樹的操作生成 2022年3月17日 二叉排序樹的操作刪除二叉排序樹的操作刪除 2022年3月17日 2022年3月17日 2022年3月17日 第第i i層結(jié)點需比較層結(jié)點需比較i i次。在等概率的前提下，上述次。在等概率的前提下，上述兩圖的兩圖的平均查找長度平均查找長度為：為：)(35/ )54321 ()(2 . 25/ )23221 (11右圖左圖niiiniiicpcp40245512371224374055查找的性能分析查找的性能分析 2022年3月17日 平均查找長度和二叉樹的形態(tài)有關(guān)，即，平均查找長度和二叉樹的形態(tài)有關(guān)，即，最好：最好：lo

16、glog2 2n n（形態(tài)勻稱，與二分查找的判定樹相似）（形態(tài)勻稱，與二分查找的判定樹相似）最壞最壞: : （n n+1)/2+1)/2（單支樹）（單支樹）查找的性能分析查找的性能分析40245512371224374055)( 35/ ) 54321 ()( 2 . 25/ ) 23221 (11右圖左圖niiiniiicpcp 2022年3月17日 問題：如何提高二叉排序樹的查找效率？問題：如何提高二叉排序樹的查找效率？盡量讓二叉樹的形狀均衡盡量讓二叉樹的形狀均衡左、右子樹是平衡二叉樹；左、右子樹是平衡二叉樹；所有結(jié)點的左、右子樹深度之差的絕對值所有結(jié)點的左、右子樹深度之差的絕對值 1 1

17、平衡因子平衡因子: :該結(jié)點左子樹與右子樹的高度差該結(jié)點左子樹與右子樹的高度差 2022年3月17日 v任一結(jié)點的平衡因子只能?。喝我唤Y(jié)點的平衡因子只能?。?1-1、0 0 或或 1 1；如果；如果樹中任意一個結(jié)點的平衡因子的絕對值大于樹中任意一個結(jié)點的平衡因子的絕對值大于1 1，則這棵二叉樹就失去平衡，不再是則這棵二叉樹就失去平衡，不再是AVLAVL樹；樹；v對于一棵有對于一棵有n n個結(jié)點的個結(jié)點的AVLAVL樹，其樹，其高度保持在高度保持在O(logO(log2 2n n) )數(shù)量級，數(shù)量級，ASLASL也保持在也保持在O(logO(log2 2n n) )量級。量級。 2022年3月1

18、7日 (a) (a) 平衡樹平衡樹 (b) (b) 不平衡樹不平衡樹練習(xí)：判斷下列二叉樹是否練習(xí)：判斷下列二叉樹是否AVLAVL樹？樹？0 00 00 01 11 1-1-1-1-10 00 00 01 1-1-1 2022年3月17日 如果在一棵如果在一棵AVLAVL樹中插入一個新結(jié)點，就有可能造樹中插入一個新結(jié)點，就有可能造成失衡，此時必須成失衡，此時必須重新調(diào)整樹的結(jié)構(gòu)重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)，使之恢復(fù)平衡。我們稱調(diào)整平衡過程為平衡。我們稱調(diào)整平衡過程為平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)。LLLL平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)RRRR平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)LRLR平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)RLRL平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)保證二叉排序樹保證二

19、叉排序樹的次序不變的次序不變 2022年3月17日 若在若在A A的的左子樹的左子樹上插入左子樹的左子樹上插入結(jié)點，使結(jié)點，使A A的平衡因子從的平衡因子從1 1增加至增加至2 2，需要進行一次，需要進行一次順時針旋轉(zhuǎn)順時針旋轉(zhuǎn)。( (以以B B為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸）若在若在A A的的右子樹的右子樹上插入右子樹的右子樹上插入結(jié)點，使結(jié)點，使A A的平衡因子從的平衡因子從-1-1增加增加至至-2-2，需要進行一次，需要進行一次逆時針旋轉(zhuǎn)逆時針旋轉(zhuǎn)。( (以以B B為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） 2022年3月17日 若在若在A的的右右子樹的子樹的左左子樹上插入子樹上插入結(jié)結(jié)點，使點，使A的平衡因子從的平衡因

20、子從-1增加至增加至-2，需要需要先進行先進行順順時針旋轉(zhuǎn)，再時針旋轉(zhuǎn)，再逆逆時時針旋轉(zhuǎn)針旋轉(zhuǎn)。(以插入的結(jié)點以插入的結(jié)點C為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸）若在若在A的的左左子樹的子樹的右右子樹上插入子樹上插入結(jié)點，使結(jié)點，使A的平衡因子從的平衡因子從1增加至增加至2，需要，需要先進行先進行逆逆時針旋轉(zhuǎn)，再時針旋轉(zhuǎn)，再順順時針旋轉(zhuǎn)。時針旋轉(zhuǎn)。(以插入的結(jié)點以插入的結(jié)點C為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） 2022年3月17日 0 013130 037370 024240 013130 03737-1-113130 02424-1-124241313需要需要RR平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)(繞繞B逆轉(zhuǎn)逆轉(zhuǎn),B為根）為根）0 0909

21、0-1-12424-1-137370 053531 190903737需要需要RL平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)(繞繞C先順后逆）先順后逆）0 037370 090900 053530 037370 090900 05353 2022年3月17日 變種的變種的AVLAVL樹樹紅紅黑樹黑樹 2022年3月17日 I see a brand new nodeI want to paint it black. We need a balanced tree,weve got to paint it black. I want to find my key in log n time - thats all,Rot

22、ating sub-trees round sure can be a ball. I see a brand new nodeI want to paint it black. Cant have a lot of red nodes,We must paint them black. Unfortunately, coding them can be a bitch.紅紅黑樹之歌黑樹之歌The Red-Black Tree SongIf we had half a brain to splay trees we would switch. I see a brand new nodeI w

23、ant to paint it black. No time for AVL treeswe must paint it BLACK. And if theyre still confusing, you should have no fear.Because outside this class, of them youll never hear. I wanna paint em BLACK. Paint nodes black. Again and again. 2022年3月17日 7.3 7.3 哈希表的查找哈希表的查找 基本思想：基本思想：記錄的存儲位置與關(guān)鍵字之間存在記錄的存儲位

24、置與關(guān)鍵字之間存在對應(yīng)關(guān)系，對應(yīng)關(guān)系，Loc(i)=H(keyi)Loc(i)=H(keyi) 優(yōu)點：優(yōu)點：查找速度極快查找速度極快O(1),查找效率與元素個數(shù)查找效率與元素個數(shù)n無關(guān)無關(guān)哈希函數(shù)哈希函數(shù)關(guān)鍵字關(guān)鍵字集合集合存儲地址存儲地址集合集合hash 2022年3月17日 若將學(xué)生信息按如下方式存入計算機，如：若將學(xué)生信息按如下方式存入計算機，如：將將20010118102200101181020101的所有信息存入的所有信息存入VV0101 單元；單元；將將20010118102200101181020202的所有信息存入的所有信息存入VV0202 單元；單元；將將2001011810

25、2200101181023131的所有信息存入的所有信息存入V31V31單元。單元。查找查找20010118102200101181021616的信息，可直接訪問的信息，可直接訪問V16V16！例例1 1 2022年3月17日 數(shù)據(jù)元素序列數(shù)據(jù)元素序列(14(14，2323，3939，9 9，2525，11)11)，若規(guī)定每個，若規(guī)定每個元素元素k k的存儲地址的存儲地址H H（k k）k k，請畫出存儲結(jié)構(gòu)圖。，請畫出存儲結(jié)構(gòu)圖。141411119 9內(nèi)容內(nèi)容地址地址3939252524242323141411119 9232325253939例例2 2 2022年3月17日 根據(jù)哈希函數(shù)根

26、據(jù)哈希函數(shù)H（k）k 查找查找key=9,key=9,則訪問則訪問H(9)=9H(9)=9號地址，若內(nèi)容為號地址，若內(nèi)容為9 9則成功；則成功；若查不到，則返回一個特殊值，如空指針或空記錄。若查不到，則返回一個特殊值，如空指針或空記錄。 如何查找如何查找141411119 9內(nèi)容內(nèi)容地址地址3939252524242323141411119 9232325253939 2022年3月17日 哈希方法哈希方法( (雜湊法雜湊法) )選取某個選取某個函數(shù)函數(shù)，依該函數(shù)按關(guān)鍵字計算元素的存儲位置，依該函數(shù)按關(guān)鍵字計算元素的存儲位置，并按此存放；并按此存放；查找時，由同一個函數(shù)對給定值查找時，由同一個

27、函數(shù)對給定值k k計算地址，計算地址，將將k k與地址與地址單元中元素關(guān)鍵碼進行比單元中元素關(guān)鍵碼進行比，確定查找是否成功。，確定查找是否成功。哈希函數(shù)哈希函數(shù)( (雜湊函數(shù)雜湊函數(shù)) )：哈希方法中使用的哈希方法中使用的轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)有關(guān)術(shù)語有關(guān)術(shù)語 2022年3月17日 沖沖 突：突：不同的關(guān)鍵碼映射到同一個哈希地址不同的關(guān)鍵碼映射到同一個哈希地址哈希表哈希表( (雜湊表雜湊表) )：按上述思想構(gòu)造的表按上述思想構(gòu)造的表有關(guān)術(shù)語有關(guān)術(shù)語141411119 9內(nèi)容內(nèi)容地址地址3939252524242323141411119 9232325253939同義詞：同義詞：具有具有相同函數(shù)值相同

28、函數(shù)值的兩個關(guān)鍵字的兩個關(guān)鍵字key1 key2，但但H(key1)=H(key2) 2022年3月17日 （14，23，39，9，25，11）哈希函數(shù)：哈希函數(shù)：H(k)=k mod 72539239146個元素用個元素用7個個地址應(yīng)該足夠地址應(yīng)該足夠!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4同義詞同義詞 0 1 2 3 4 5 6沖突現(xiàn)象舉例沖突現(xiàn)象舉例 2022年3月17日 哈希函數(shù)在信息安全領(lǐng)域中的應(yīng)用哈希函數(shù)在信息安全領(lǐng)域中的應(yīng)用 2022年3月17日 wmic全稱全稱Windows Management Instrumentation Comma

29、nd-line（Windows管理規(guī)范命令行），它提管理規(guī)范命令行），它提供了從命令行接口和批命令腳本執(zhí)行系統(tǒng)管理的支供了從命令行接口和批命令腳本執(zhí)行系統(tǒng)管理的支持。通過它我們可以執(zhí)行一些復(fù)雜的命令，從而更持。通過它我們可以執(zhí)行一些復(fù)雜的命令，從而更為有效地管理系統(tǒng)。為有效地管理系統(tǒng)。 點擊點擊“開始開始”菜單菜單“運行運行”，輸入，輸入“cmd”運行運行“命令提示符命令提示符”，在其中輸入如下命令，在其中輸入如下命令“wmic process get”。第一次使用。第一次使用wmic時，它會提示你安裝，時，它會提示你安裝，安裝過程只需幾秒鐘。安裝過程只需幾秒鐘。MD5破解破解QQ密碼密碼 2

30、022年3月17日 點擊點擊QQ主界面下方的主界面下方的“QQ游戲游戲”，游戲自動登錄。，游戲自動登錄。在在 “ 命 令 提 示 符命 令 提 示 符 ” 中 輸 入中 輸 入 “ w m i c p ro c e s s getc:123.txt”并回車。這條命令的作用是執(zhí)行并回車。這條命令的作用是執(zhí)行“wmic process get”命令并將結(jié)果保存在命令并將結(jié)果保存在c盤的盤的123.txt文件中。文件中。打開此文件，按下打開此文件，按下“Ctrl”+“F” ，以，以“QQgame”為為關(guān)鍵字進行搜索，在進程的末尾處會看見類似的語句：關(guān)鍵字進行搜索，在進程的末尾處會看見類似的語句：ST

31、ART QQUIN:12345678 PWDHASH: sjTC1t9/B5zJKZWg9u236g= INCOG:1。將將“PWDHASH”和和“INCOG”之間的內(nèi)容復(fù)制下之間的內(nèi)容復(fù)制下來。這個就是來。這個就是QQ密碼在經(jīng)過密碼在經(jīng)過MD5加密后再進行加密后再進行BASE64編碼所得的結(jié)果。編碼所得的結(jié)果。 2022年3月17日 打開打開MD5在線破解網(wǎng)站：在線破解網(wǎng)站：，在其，在其中的文本框中輸入剛才得到的密文，點擊中的文本框中輸入剛才得到的密文，點擊“MD5”碰撞就可以對密文進行解密了。碰撞就可以對密文進行解密了。 2022年3月17日 沖突是不可能避免的沖突是不可能避免的如何減少沖

32、突如何減少沖突構(gòu)造好的哈希函數(shù)構(gòu)造好的哈希函數(shù)制定一個好的解決沖突方案制定一個好的解決沖突方案 2022年3月17日 哈希函數(shù)的構(gòu)造方法哈希函數(shù)的構(gòu)造方法根據(jù)元素集合的特性構(gòu)造根據(jù)元素集合的特性構(gòu)造地址空間盡量小地址空間盡量小均勻均勻直接定址法直接定址法 數(shù)字分析法數(shù)字分析法平方取中法平方取中法折疊法折疊法除留余數(shù)法除留余數(shù)法隨機數(shù)法隨機數(shù)法 2022年3月17日 Hash(key) = akey + b ( (a、b為常數(shù)為常數(shù)) )優(yōu)點：優(yōu)點：以關(guān)鍵碼以關(guān)鍵碼keykey的某個線性函數(shù)值為哈希的某個線性函數(shù)值為哈希地址，不會產(chǎn)生沖突。地址，不會產(chǎn)生沖突。缺點：缺點：要占用連續(xù)地址空間，空間

33、效率低。要占用連續(xù)地址空間，空間效率低。 直接定址法直接定址法 2022年3月17日 例：例： 100，300，500，700，800，900， 哈希函數(shù)哈希函數(shù)Hash(key)=key/1000 1 2 3 4 5 6 7 8 9900800700500300100直接定址法直接定址法 2022年3月17日 Hash(key)=key mod p (p是一個整數(shù)是一個整數(shù))關(guān)鍵：關(guān)鍵：如何選取合適的如何選取合適的p？技巧：技巧：設(shè)表長為設(shè)表長為m，取，取pm且為且為質(zhì)數(shù)質(zhì)數(shù) 除留余數(shù)法除留余數(shù)法 （最常用重點掌握）（最常用重點掌握） 2022年3月17日 執(zhí)行速度（即計算哈希函數(shù)所需時間）

34、；執(zhí)行速度（即計算哈希函數(shù)所需時間）； 關(guān)鍵字的長度；關(guān)鍵字的長度； 哈希表的大小；哈希表的大?。?關(guān)鍵字的分布情況；關(guān)鍵字的分布情況； 查找頻率。查找頻率。構(gòu)造哈希函數(shù)考慮的因素構(gòu)造哈希函數(shù)考慮的因素 2022年3月17日 1.開放開放定址法定址法處理沖突的方法處理沖突的方法2.鏈地址法鏈地址法 2022年3月17日 基本思想：基本思想：有沖突時就去有沖突時就去尋找下一個空尋找下一個空的哈希地的哈希地址，只要哈希表足夠大，空的哈希地址總址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。能找到，并將數(shù)據(jù)元素存入。 1.1.開放定址法（開地址法）開放定址法（開地址法）線性探測法線性探

35、測法二次探測法二次探測法偽隨機探測法偽隨機探測法 2022年3月17日 Hi=(Hash(key)+di) mod m ( 1i m ) 其中：其中：m為哈希表長度為哈希表長度 di 為增量序列為增量序列 1，2，m-1，且，且di=i一旦沖突，就找下一個空地址存入一旦沖突，就找下一個空地址存入線性探測法線性探測法 2022年3月17日 關(guān)鍵碼集為關(guān)鍵碼集為 47，7，29，11，16，92，22，8，3，設(shè)：設(shè)：哈希表表長為哈希表表長為m=m=11； 哈希函數(shù)為哈希函數(shù)為Hash(key)=key mod 11 0 1 2 3 4 5 6 7 8 9 10477 291116922283 4

36、7、7、11、16、92沒有沖突沒有沖突 Hash(29)=7，有沖突，由，有沖突，由H1=(Hash(29)+1) mod 11=8，哈希地址哈希地址8為空，因此將為空，因此將29存入存入 線性探測法線性探測法 2022年3月17日 線性探測法的特點線性探測法的特點優(yōu)點：優(yōu)點：只要哈希表未被填滿，只要哈希表未被填滿，保證能找到保證能找到一個空一個空地址單元存放有沖突的元素。地址單元存放有沖突的元素。缺點：缺點：可能使第可能使第i個哈希地址的同義詞存入第個哈希地址的同義詞存入第i+1個個地址，這樣本應(yīng)存入第地址，這樣本應(yīng)存入第i+1個哈希地址的元素個哈希地址的元素變成了第變成了第i+2個哈希地

37、址的同義詞，個哈希地址的同義詞，產(chǎn)，產(chǎn)生生“聚集聚集”現(xiàn)象，降低查找效率?，F(xiàn)象，降低查找效率。解決方案：解決方案：二次探測法二次探測法 2022年3月17日 二次探測法二次探測法關(guān)鍵碼集為關(guān)鍵碼集為 47，7，29，11，16，92，22，8，3，設(shè)：設(shè)： 哈希函數(shù)為哈希函數(shù)為Hash(key)=key mod 11 Hi=(Hash(key)di) mod m其中：其中：m為哈希表長度，為哈希表長度，m要求是某個要求是某個4k+3的質(zhì)數(shù)的質(zhì)數(shù)； di為增量序列為增量序列 12，-12，22，-22，q2 0 1 2 3 4 5 6 7 8 9 10829716924732211 Hash(3

38、)=3，哈希地址沖突，由，哈希地址沖突，由H1=(Hash(3)+12) mod 11=4，仍然沖突；，仍然沖突；H2=(Hash(3)-12) mod 11=2，找到空的哈希地址，存入。找到空的哈希地址，存入。 2022年3月17日 偽隨機探測法偽隨機探測法Hi=(Hash(key)+di) mod m ( 1i m ) 其中：其中：m為哈希表長度為哈希表長度 di 為隨機數(shù)為隨機數(shù) 2022年3月17日 2.2.鏈地址法鏈地址法( (拉鏈法）拉鏈法）基本思想：基本思想：相同哈希地址的記錄鏈成一單鏈表，相同哈希地址的記錄鏈成一單鏈表，m個哈個哈希地址就設(shè)希地址就設(shè)m個單鏈表個單鏈表，然后用用

39、一個數(shù)組將，然后用用一個數(shù)組將m個單個單鏈表的表頭指針存儲起來，形成一個動態(tài)的結(jié)構(gòu)鏈表的表頭指針存儲起來，形成一個動態(tài)的結(jié)構(gòu)0 1 2 3 4 5 6 7 8 9 10 11 12 14127796855198420231011 2022年3月17日 鏈地址法的優(yōu)點：鏈地址法的優(yōu)點： 非同義詞不會沖突，無非同義詞不會沖突，無“聚集聚集”現(xiàn)象現(xiàn)象 鏈表上結(jié)點空間動態(tài)申請，更適合于表長不確鏈表上結(jié)點空間動態(tài)申請，更適合于表長不確定的情況定的情況 2022年3月17日 哈希表的查找哈希表的查找給定給定k k值值計算計算H(k)H(k)此地址為空此地址為空關(guān)鍵字關(guān)鍵字=k=k查找失敗查找失敗查找成功查

40、找成功按處理沖突按處理沖突方法計算方法計算HiHiY YN NY YN N給定值與關(guān)鍵字比較給定值與關(guān)鍵字比較 2022年3月17日 已知一組關(guān)鍵字已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函數(shù)為：哈希函數(shù)為：H(key)=key MOD 13, H(key)=key MOD 13, 哈希表長為哈希表長為m=16m=16， 設(shè)每個記錄的查找概率相等設(shè)每個記錄的查找概率相等(1) (1) 用線性探測再散列處理沖突，即用線性探測再散列處理沖突，即Hi=(H(key)+di) M

41、OD mHi=(H(key)+di) MOD m0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1514 1 68 27 55 19 20 84 79 23 11 101 2 1 4 3 1 1 3 9 1 1 3 H(19)=6H(14)=1H(23)=10H(1)=1 沖突，沖突，H1=(1+1) MOD16=2H(68)=3H(20)=7H(27)=1 沖突，沖突，H1=(1+1)MOD16=2 沖突，沖突，H2=(1+2)MOD16=3 沖突，沖突，H3=(1+3)MOD16=4ASL=(1*6+2+3*3+4+9)/12=2.5哈希表的查找哈希表的查找 2022

42、年3月17日 (2) (2) 用鏈地址法處理沖突用鏈地址法處理沖突0 1 2 3 4 5 6 7 8 9 10 11 12 14127796855198420231011ASL=(1*6+2*4+3+4)/12=1.75關(guān)鍵字關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)哈希表的查找哈希表的查找 2022年3月17日 無序表查找無序表查找ASL?ASL?關(guān)鍵字關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)有序表折半查找有序表折半查找ASL?ASL?思考思考 2022年3月17日 使用平均查找長度使用平均查找長度ASLASL來衡量查找算法，來衡量查找算法，ASLASL取決于取決于哈希函數(shù)哈希函數(shù)處理沖突的方法處理沖突的方法哈希表的裝填因子哈希表的裝填因子哈希表的長度哈希表的長度表中填入