【正文】 字分布近乎隨機所以：取 ????任意兩位或兩位 與另兩位的疊加作哈希地址? 平方取中法–構(gòu)造：取關(guān)鍵字平方后中間幾位作哈希地址–適于不知道全部關(guān)鍵字情況? 折疊法– 構(gòu)造：將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進位）做哈希地址– 種類? 移位疊加：將分割后的幾部分低位對齊相加? 間界疊加：從一端沿分割界來回折送，然后對齊相加– 適于關(guān)鍵字位數(shù)很多，且每一位上數(shù)字分布大致均勻情況例 關(guān)鍵字為 ： 0442205864，哈希地址位數(shù)為 45 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位疊加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092間界疊加? 除留余數(shù)法– 構(gòu)造：取關(guān)鍵字被某個不大于哈希表表長 m的數(shù) p除后所得余數(shù)作哈希地址，即 H(key)=key MOD p， p?m– 特點? 簡單、常用，可與上述幾種方法結(jié)合使用? p的選取很重要； p選的不好，容易產(chǎn)生同義詞? 隨機數(shù)法– 構(gòu)造：取關(guān)鍵字的隨機函數(shù)值作哈希地址，即H(key)=random(key)– 適于關(guān)鍵字長度不等的情況? 選取哈希函數(shù)，考慮以下因素：– 計算哈希函數(shù)所需時間– 關(guān)鍵字長度– 哈希表長度（哈希地址范圍）– 關(guān)鍵字分布情況– 記錄的查找頻率 處理沖突的方法? 開放定址法– 方法：當(dāng)沖突發(fā)生時，形成一個探查序列；沿此序列逐個地址探查，直到找到一個空位置（開放的地址），將發(fā)生沖突的記錄放到該地址中，即 Hi=(H(key)+di)MOD m，i=1,2,……k(k ?m1)其中： H(key)—— 哈希函數(shù) m—— 哈希表表長 di—— 增量序列? di—— 增量序列 (有三種取法 )–線性探測再散列： di=1,2,3,……m1–二次探測再散列： di=1178。,1178。,2178。,2178。,3178。,……177。k178。(k ?m/2)–偽隨機探測再散列： di=偽隨機數(shù)序列例 表長為 11的哈希表中已填有關(guān)鍵字為 17， 60， 29的記錄， H(key)=key MOD 11,現(xiàn)有第 4個記錄，其關(guān)鍵字為 38， 按三種處理沖突的方法，將它填入表中(1) H(38)=38 MOD 11=5 沖突 H1=(5+1) MOD 11=6 沖突 H2=(5+2) MOD 11=7 沖突 H3=(5+3) MOD 11=8 不沖突 (2) H(38)=38 MOD 11=5 沖突 H1=(5+1178。) MOD 11=6 沖突 H2=(5 1178。) MOD 11=4 不沖突(3) H(38)=38 MOD 11=5 沖突 設(shè)偽隨機數(shù)序列為 9，則： H1=(5+9) MOD 11=3 不沖突0 1 2 3 4 5 6 7 8 9 1060 17 29 383838? 再哈希法–方法：構(gòu)造若干個哈希函數(shù)，當(dāng)發(fā)生沖突時，計算下一個哈希地址，即：Hi=Rhi(key) i=1,2,……k其中： Rhi—— 不同的哈希函數(shù)–特點：計算時間增加? 鏈地址法–方法：將所有關(guān)鍵字為同義詞的記錄存儲在一個單鏈表中，并用一維數(shù)組存放頭指針例 已知一組關(guān)鍵字(19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79) 哈希函數(shù)為： H(key)=key MOD 13, 用鏈地址法處理沖突^0 1 2 3 4 5 6 7 8 9 10 11 12 14^6819202311^^^^^1 27 79558410^^^^^^– 哈希查找過程及分析? 哈希查找過程給定 k值計算 H(k)此地址為空關(guān)鍵字 ==k查找失敗查找成功按處理沖突方法計算 HiYNYN? 哈希查找分析–哈希查找過程仍是一個給定值與關(guān)鍵字進行比較的過程–評價哈希查找效率仍要用 ASL–哈希查找過程與給定值進行比較的關(guān)鍵字的個數(shù)取決于：? 哈希函數(shù)? 處理沖突的方法? 哈希表的填滿因子 ?=表中填入的記錄數(shù) /哈希表長度例 已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函數(shù)為： H(key)=key MOD 13, 哈希表長為 m=16， 設(shè)每個記錄的查找概率相等 (1) 用線性探測再散列處理沖突，即Hi=(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 10H(55)=3 沖突， H1=(3+1)MOD16=4 沖突， H2=(3+2)MOD16=5H(79)=1 沖突， H1=(1+1)MOD16=2 沖突， H2=(1+2)MOD16=3 沖突， H3=(1+3)MOD16=4 沖突， H4=(1+4)MOD16=5 沖突， H5=(1+5)MOD16=6 沖突， H6=(1+6)MOD16=7 沖突， H7=(1+7)MOD16=8 沖突， H8=(1+8)MOD16=9ASL=(1*6+2+3*3+4+9)/12=H(19)=6H(14)=1H(23)=10H(1)=1 沖突， H1=(1+1) MOD16=2H(68)=3H(20)=7H(84)=6 沖突， H1=(6+1)MOD16=7 沖突， H2=(6+2)MOD16=8H(27)=1 沖突， H1=(1+1)MOD16=2 沖突， H2=(1+2)MOD16=3 沖突， H3=(1+3)MOD16=4H(11)=11H(10)=10 沖突， H1=(10+1)MOD16=11 沖突， H2=(10+2)MOD16=12(19,14,23,1,68,20,84,27,55,11,10,79)H(key)=key MOD 13 Hi=(H(key)+di) MOD m(2) 用鏈地址法處理沖突0 1 2 3 4 5 6 7 8 9 10 11 12 14^1 27 7968 5519 842023 1011^^^^^^^^^^^^ASL=(1*6+2*4+3+4)/12=關(guān)鍵字 (19,14,23,1,68,20,84,27,55,11,10,79)? 哈希查找算法實現(xiàn) – 用線性探測再散列法處理沖突? 實現(xiàn)–查找過程：同前–刪除：只能作標記，不能真正刪除–插入：遇到空位置或有刪除標記的位置就可以插入? 算法描述：– 用鏈表處理沖突算法? define M 100? int h(int k)? { return(k%97)。? }? int slbxxcz(int t[],int k)? { int i,j=0。? i=h(k)。? while((jM)amp。amp。(t[(i+j)%M]!=k)amp。amp。(t[(i+j}%M]!=0))? j++。? i=(i+j)%M。? if(t[i]==k) return(i)。? else return(1)。? }int slbxxcr(int t[],int k){ int i,j=0。 i=h(k)。 while((jM)amp。amp。(t[(i+j)%M]!=k)amp。amp。(t[(i+j}%M]0)) j++。 if(j==M) return(0)。 i=(i+j)%M。 if(t[i]=0) { t[i]=k。 return(1)。 } if(t[i]==k) return(1)。}int slbxxsc(int t[],int k){ int i,j=0。 i=h(k)。 while((jM)amp。amp。(t[(i+j)%M]!=k)amp。amp。(t[(i+j}%M]!=0)) j++。 i=(i+j)%M。 if(t[i]==k) { t[i]=1。 return(1)。 } return(0)。}? 哈希（ HSAE） 查找 散列查找– 基本思想：在記錄的存儲地址和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系；這樣，不經(jīng)過比較，一次存取就能得到所查元素的查找方法– 定義? 哈希函數(shù) —— 在記錄的關(guān)鍵字與記錄的存儲地址之間建立的一種對應(yīng)關(guān)系叫 ~ 根據(jù)關(guān)鍵字的值，利用某個函數(shù)直接計算出元素所在的位置。這函數(shù)稱為 “哈希函數(shù) ”，能用散列技術(shù)進行查找的表稱為散列表（ 哈希表）。? 哈希表技術(shù)的主要目標是提高查找效率，即縮短查表和填表的時間。例 30個地區(qū)的各民族人口統(tǒng)計表編號 地區(qū)別 總?cè)丝? 漢族 回族 …...1 北京2 上?！?.. …...以編號作關(guān)鍵字，構(gòu)造 哈希函數(shù)： H(key)=keyH(1)=1H(2)=2以地區(qū)別作關(guān)鍵字，取地區(qū)名稱第一個拼音字母的序號作哈希函數(shù)： H(Beijing)=2 H(Shanghai)=18 H(Shenyang)=18從例子可見：– 哈希函數(shù)只是一種映象，所以哈希函數(shù)的設(shè)定很靈活，只要使任何關(guān)鍵字的哈希函數(shù)值都落在表長允許的范圍之內(nèi)即可– 沖突： key1?key2， 但 H(key1)=H(key2)的現(xiàn)象叫 ~– 同義詞：具有相同函數(shù)值的兩個關(guān)鍵字，叫該哈希函數(shù)的 ~– 哈希函數(shù)通常是一種壓縮映象，所以沖突不可避免 ，只能盡量減少；同時，沖突發(fā)生后，應(yīng)該有處理沖突的方法– 哈希函數(shù)的構(gòu)造方法? 直接定址法– 構(gòu)造：取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)作哈希地址，即H(key)=key 或 H(key)=akey+b– 特點187。 直接定址法所得地址集合與關(guān)鍵字集合大小相等，不會發(fā)生沖突187。 實際中能用這種哈希函數(shù)的情況很少? 數(shù)字分析法– 構(gòu)造：對關(guān)鍵字進行分析，取關(guān)鍵字的若干位或其組合作哈希地址– 適于關(guān)鍵字位數(shù)比哈希地址位數(shù)大，且可能出現(xiàn)的關(guān)鍵字事先知道的情況例 有 80個記錄，關(guān)鍵字為 8位十進制數(shù)，哈希地址為 2位十進制數(shù)8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 8 6 78 1 3 6 8 5 3 78 1 4 1 8