hashing(雜湊法)

1、雜湊法,Hashing,學(xué)習(xí)目標(biāo),1.Hashing(雜湊)的定義。2.雜湊/赫序函數(shù)的選擇原則及方法。3.Hashing(雜湊)搜尋可能發(fā)生的問題。4.如何處理Hashing(雜湊)搜尋的碰撞及溢位問題。5.Dynamic Hashing(動(dòng)態(tài)雜湊)函數(shù)的各種理論。,何謂Hashing,,雜湊法定義,雜湊搜尋法是透過一個(gè)數(shù)學(xué)函數(shù)來計(jì)算或轉(zhuǎn)換一個(gè)鍵值所對(duì)應(yīng)的位址，這種搜尋可以直接且快速的找到鍵值所放的位址；任何透過雜湊搜尋的檔案

2、皆不須經(jīng)過事先的排序，也就是可以直接以：鍵值－－－＞雜湊函數(shù)－－－＞位址,雜湊(赫序)表格,雜湊(赫序)表格通常用來達(dá)成像字典般功能之資料結(jié)構(gòu)。例如拼字檢查，百科字典載入器之地址連結(jié)，編譯器裡的符號(hào)表,保留字表等查尋。定義雜湊(赫序)表格的函數(shù)稱為雜湊函數(shù),表格的一個(gè)位置稱為一個(gè)bucket每個(gè)bucket可以存放記錄個(gè)數(shù)為5，稱為slot(槽)通常s=1時(shí)，如果不同的鍵值對(duì)應(yīng)至同一位置時(shí)，則發(fā)生碰撞如果一個(gè)鍵值被對(duì)

3、應(yīng)到一個(gè)沒有空位的bucket時(shí)，則發(fā)生溢位因此當(dāng)s=1時(shí)，溢位與碰撞同時(shí)發(fā)生。,雜湊的相關(guān)名詞,Bucket(桶)： 雜湊表中儲(chǔ)存資料的立置，每一個(gè)位置對(duì)應(yīng)到唯一的位址，稱為bucket address。一個(gè)bucket(桶)就好比是一筆記錄。 s lot(槽)：每一個(gè)bucket有好幾個(gè)儲(chǔ)存區(qū)，此儲(chǔ)存區(qū)就是ｓlot(槽)。每一個(gè)ｓlot(槽) 即代表記錄中的某個(gè)欄位。 Collision(碰撞)： 當(dāng)兩筆不同的資料，經(jīng)過

4、雜湊函數(shù)運(yùn)算後對(duì)應(yīng)到相同的bucket address，稱為Collision(碰撞)。 Overflow(溢位)： 如果資料經(jīng)雜溱函數(shù)運(yùn)算後，所對(duì)應(yīng)的bucket已經(jīng)滿了，則稱為Overflow(溢位)。 Synonym(同義字)： 當(dāng)兩個(gè)識(shí)別字I及J的雜湊函數(shù)值經(jīng)過運(yùn)算後是相同的，則稱I及J為同義字。 Loading Factor(載入密度)： 雜湊空間的載入密度是指識(shí)別字的使用數(shù)目除以雜湊表內(nèi)槽的總數(shù)。,雜湊函數(shù),Ha

5、shing Functions,定義,雜湊(赫序)函數(shù)f將識(shí)別字轉(zhuǎn)換到雜湊表的Bucket位址上。理想狀況下的雜湊函數(shù) f 要能符合幾個(gè)設(shè)計(jì)的特點(diǎn)：,設(shè)計(jì)重點(diǎn),運(yùn)算容易且計(jì)算速度要快；碰撞頻率儘量小；文字儘量轉(zhuǎn)換成數(shù)字。若關(guān)鍵值是字串，必須將字串根據(jù)ASCII碼轉(zhuǎn)換成數(shù)字；函數(shù)選取通常是考慮能否將關(guān)鍵值轉(zhuǎn)換索引地址時(shí)均勻地散開；儘量充分利用所有的Bucket位置，不要有所偏差(Bias)，亦儘可能達(dá)到均勻分佈。,雜湊(赫序)函數(shù)

6、取得方式,除法(Division) 平方取中法(Mid-Square)折疊法(Folding)抽取法(Extraction)乘法(Mutiplication)基數(shù)法(Radix Method)位數(shù)分析法(Digit Analysis),除法(Division),利用餘數(shù)運(yùn)算(﹪或mod)，將鍵值K除以某一個(gè)數(shù)值M，餘數(shù)即是K的位址。此位址介於0~(M-1)之間。h(k)=k mod m其中k代表關(guān)鍵值，m表示索引位址的空

7、間大小。?以某數(shù)M除關(guān)鍵值k，所得餘數(shù)便是k的雜湊位址h(k)? h(k)之值可能為0，1，2....M-1，表格有M個(gè)buckets。?通常m都採(cǎi)用質(zhì)數(shù)，以減少碰撞。關(guān)於m 的選擇，根據(jù)經(jīng)驗(yàn)，m為偶數(shù)時(shí)較易發(fā)生碰撞。因此m的選擇最好是質(zhì)數(shù)或是奇數(shù)而這奇數(shù)必須符合沒有小於20的質(zhì)因數(shù)存在。,【範(fàn)例】鍵值k={34,59,72,95}，令m=7，＝＞h(k)＝(k mod 7)，可得雜湊位址：6,3,2,5＝＞即可將鍵值3

8、4放入第6號(hào)的位址，59放入第3號(hào)，以此類推。,平方取中法(Mid-Square)：,將識(shí)別字先轉(zhuǎn)換成一個(gè)數(shù)值，再將此值平方，然後取中間的幾個(gè)位數(shù)當(dāng)作Bucket位址。Bucket位址必須對(duì)映至真實(shí)的位址內(nèi)，因此若其範(fàn)圍超過實(shí)際空間範(fàn)圍，則必須再予以壓縮。k2＝關(guān)鍵值k的平方若m的位數(shù)為P，則只取k2中間的P位數(shù)值當(dāng)作索引位址；其中k代表關(guān)鍵值，m表示索引位址的空間大小。,【範(fàn)例】m值是從0~9999共四位數(shù)，且k=35625

9、，＝＞k2=1269140625，＝＞取正中四位數(shù)為9140為索引地址。,折疊法(Folding),將資料均分成幾個(gè)部分，再將這些小部分結(jié)合或摺疊起來，產(chǎn)生資料儲(chǔ)存的位置。,?將k值切割成若干相等長(zhǎng)度的區(qū)塊，將區(qū)塊值累加起來，再取Mod m以得索引位址。 【範(fàn)例】k=643,180,321分成643,180，321三區(qū)塊＝＞643+180+321=1144＝＞mod 1001h(k)1144 mod 1001=143。,?

10、將一個(gè)鍵值分割數(shù)部分，再予以相加或相減組合?！竟?fàn)例】k=97,250,483,217＝＞972+504+832+17=2325＝＞最後再取3位---->325,抽取法(Extraction),此法是在資料中抽取出最具雜湊效果的一部分來作函數(shù)運(yùn)算。省略一個(gè)鍵值的某部份，再以剩餘的作為雜湊位址。【範(fàn)例】k=70,192,387選擇鍵值的右邊第1，3及4個(gè)數(shù)字，使70192387-->237。,乘法(Mutipli

11、cation),除法的效果取決於m值的選取，若選的不好，碰撞問題將很嚴(yán)重。採(cǎi)用乘法，m值可不須要講究。令k為關(guān)鍵值，A是一個(gè)實(shí)常數(shù)，且0<A<1，雜湊函數(shù)為：h(k)=m(kA mod 1)+1，其中kA mod 1為此數(shù)的小數(shù)部分。,【範(fàn)例】令A(yù)= 0.618034，m=1024，k=1849970，則 h(k)=1024(1849970*A mod 1)=348。,基數(shù)法(Radix Method),將鍵值視為

12、某一基數(shù)數(shù)系中的數(shù)值，再將該數(shù)值轉(zhuǎn)換回原鍵值所有的基數(shù)數(shù)系，接著取出該數(shù)的某些位數(shù)值當(dāng)作雜湊函數(shù)的對(duì)應(yīng)值。鍵值：(kp)p，表示鍵值kp為p基數(shù)中的數(shù)值，其中p為一個(gè)基數(shù)。轉(zhuǎn)換基數(shù)：另選擇q為基數(shù)，其中q＞p，且q與p互質(zhì)，並視鍵值kp為基數(shù)q的數(shù)值(kp)q取得h(k)：轉(zhuǎn)回原基數(shù)並使其( kp)q＝(k)p，並從k中取出一部分k’，使(k’) p當(dāng)作h(k)之值。,【範(fàn)例】鍵值k=(530476)10，其中基數(shù)p=

13、10。另選擇基數(shù)q=11，將鍵值k看成(530476)11。?將(530476)11轉(zhuǎn)換回原基數(shù)系10的數(shù)值：(530476)11＝5*115＋3*114+7*111+6*110＝(849745)10?取後三位數(shù)當(dāng)作雜湊函數(shù)值，亦即h(k)＝745。,位數(shù)分析法(Digit Analysis),位數(shù)分析法主要用於十進(jìn)位制的各個(gè)鍵值之位數(shù)比較，採(cǎi)用分佈較均勻的若干個(gè)位數(shù)值做為每一個(gè)鍵值的雜湊函數(shù)值。此法適合靜態(tài)檔案，

14、且表中所有的識(shí)別字均事先已知時(shí)，特別有用。逐一檢查識(shí)別字的所有數(shù)位，並分析每一數(shù)位的分佈情形，盡量取平均分配的數(shù)位，刪除分配特殊的數(shù)位，並且刪除足夠的數(shù)位，使得剩餘的數(shù)位少到能夠?qū)τ持岭s湊表的位置上。,【範(fàn)例】設(shè)有五位學(xué)生的學(xué)號(hào)是由６個(gè)字元D６,D５,D4,D3,D2,D1所構(gòu)成的，分別是：ST1 = 682203ST2= 682171ST3 = 693214ST4 = 695252ST5 = 691340,令位址空間大小m

15、=100，那麼只能挑選兩位數(shù)當(dāng)做每一個(gè)學(xué)號(hào)的雜湊函數(shù)值。觀察上面各個(gè)學(xué)號(hào)的位數(shù)，不難發(fā)現(xiàn)從右邊算來第1,2位數(shù)分佈得最均勻，因此我們選擇每一個(gè)鍵值的(D2,D1)當(dāng)作湊雜函數(shù)值h(ST1)＝03h(ST2)＝71h(ST3)＝14h(ST4)＝52h(ST5)＝40,綜觀而論，雜湊函數(shù)除了具有快速資料存取的好處外，它還兼具保密的優(yōu)良效果；亦即當(dāng)別人沒有你的雜湊函數(shù)時(shí)，就很難去拿到他所想要的資料了；相反的，若遺失或遺忘雜湊函

16、數(shù)，則所有的資料即等於全部遺失了。雜湊函數(shù)還有另外一個(gè)問題，那就是一個(gè)位址可能同時(shí)被兩個(gè)或兩個(gè)以上的鍵值所對(duì)應(yīng)時(shí)，我們稱此現(xiàn)象為碰撞(Collision)。,碰撞問題及溢位處理,,定義,在雜湊法中，當(dāng)識(shí)別字要放入某個(gè)Bucket時(shí)，若該Bucket已經(jīng)滿了，則發(fā)生溢位(Overflow)；另一方面雜湊法的理想狀況是所有資料經(jīng)過雜湊函數(shù)運(yùn)算後都得到不同的值，但現(xiàn)實(shí)情況是即使所有關(guān)鍵欄位的值都不相同，還是可能得到相同的位址，於是就發(fā)生了

17、碰撞(Collision)問題。,解決碰撞問題的方法,,線性探測(cè)(Linear Probing),線性探測(cè)又稱為開放循序定址法(Linear Open Addressing) 此法是將表格的空間加大以環(huán)狀方式使用。當(dāng)發(fā)生溢位或碰撞時(shí)，則以線性方式從下一個(gè)位址繼續(xù)探測(cè)，若還有空位則將關(guān)鍵值存入，否則繼續(xù)往下搜尋；若搜尋完一個(gè)循環(huán)仍未找到空餘的儲(chǔ)存區(qū)，則表示所有位址皆被填滿。,插入時(shí)若碰撞發(fā)生，立即循序往下找一個(gè)空位，將此關(guān)鍵值之記錄存放

18、在該空位。若沒有空位可存放，可以把表格加長(zhǎng)再存放該記錄。若是刪除，可把該記錄的位置註記為空的。把該資料放在下一位置，若這位置也被佔(zhàn)用，再放在下一個(gè)位置直到有一空位置。搜尋時(shí)遇到碰撞，可循序往下尋找，直到找到所要的記錄為止。如果用數(shù)學(xué)描述法來表示，循序定址法可以寫成：(h(k) + i) mod m , 0 ≦ i ≦m-1i 最好跟空間位址的大小m互質(zhì)，否則容易造成永遠(yuǎn)找不到一個(gè)空的位置，卻循環(huán)不已地在某些固定的位址上不斷地搜

19、尋。,【範(fàn)例】,406 ─> 3　　727 ─> 12　　537 ─> 4　　425 ─> 9　　626 ─> 2　　508 ─> 1　　594 ─> 9 但位置 9 以被佔(zhàn)所以移至位置10　　603 ─> 5　　641 ─> 4 但位置 4,5 都被佔(zhàn)所以移至位置6　　347 ─> 9 ─> 10 ─> 11　　112 ─> 8,二次方探

20、測(cè)(Quadratic Probing),當(dāng)有碰撞發(fā)生時(shí)，利用非線性的跳躍去找下一個(gè)可能的空位置。例如對(duì)某一雜湊函數(shù)h，碰撞時(shí)所採(cǎi)用的雜湊函數(shù)為：(h(k)＋i 2) mod m或( h(k)－i 2 ) mod m，i表示第i次碰撞。其中1≦ i ≦(m-1)/2；m是4i +3型式的質(zhì)數(shù)。使用一個(gè)數(shù)i的二次方函數(shù)當(dāng)作下一次搜尋的相對(duì)位址，當(dāng)鍵值k的雜湊函數(shù)值h(k)和其他的鍵值撞在一起時(shí)，則下一次探測(cè)的位址是(h(k)＋i

21、 2) mod m與 (h(k)－i 2) mod m。線性探測(cè)很容易造成相近的識(shí)別字串連在一起而形成叢聚(Cluster)，然後再繼續(xù)串連成更大的叢聚(Cluster)，因此二次方探測(cè)可以加以改善這種情形。,重雜湊(Rehasing),以該位置函數(shù)變數(shù)在雜湊運(yùn)算一次，若該位置也被佔(zhàn)用，再以雜湊函數(shù)運(yùn)算一次，直到有空位置。設(shè)置一系列的雜湊函數(shù)f1，f2，f3，…，fm；當(dāng)使用f1產(chǎn)生溢位碰撞時(shí)，則改用f2，若又發(fā)生溢位時(shí)，則改用f3

22、…，直到?jīng)]有溢位或碰撞發(fā)生。,【範(fàn)例】,406 727 537 425 626 508 594 603 641 347 112雜湊函數(shù) h (value)= value MOD 13重覆雜湊函數(shù)：　　rh (i) = (i+2) MOD 13對(duì) 　　594 ─> rh(r(594))= rh(9)=11　　603 ─> 5　　640 ─> 4被佔(zhàn)用所以 rh(r(641))=rh(4)=6　　347 ─&

23、gt; 9，rh(r347))=r(9) =11亦被佔(zhàn)用　　　　─> rh(rh(r(347)))=rh(11)=0　　112 ─> 8,鏈結(jié)串列(Linked List),此法最為簡(jiǎn)單，鏈結(jié)法就是利用鏈結(jié)串列的方式來解決碰撞問題，也就是將碰撞的記錄利用串列連接一起，如圖所示,鏈結(jié)串列的雜湊函數(shù),【範(fàn)例】,試將識(shí)別字GA,D,A,G,L,A2,A1,A3,A4,Z,ZA及E，以鏈結(jié)串列法存放於雜湊表中。,利用串利法將資料

24、存放於雜湊表中,表格溢位,(Table Overflow),表格溢位的問題,主要是出現(xiàn)開放定址方法(Open Addressing hashing)。解決方式有兩種，此兩種皆不是等到表格滿了，才來擴(kuò)充記憶空間，通常是定一個(gè)負(fù)載因素a=(表格內(nèi)儲(chǔ)存記錄數(shù))/(表格的全體空間)。當(dāng)a大於某一設(shè)定值 at<1，立即擴(kuò)充表格空間，以減少碰撞的頻率。,解決方式,第一種解決方法是當(dāng)插入動(dòng)作，使得a> at，立即產(chǎn)生一個(gè)較大且新的表格，

25、將舊表格內(nèi)的記錄重新映射到新表格。第二種方法是當(dāng)插入動(dòng)作，使得某一表格的 ai> at，立即產(chǎn)生一個(gè)同大小的表格，再根據(jù)關(guān)鍵值的低位值決定選用那一個(gè)表格儲(chǔ)存，再根據(jù)赫序函數(shù)將舊表格內(nèi)的記錄分別存放到兩個(gè)表格內(nèi) 。,雜湊函數(shù)的選擇及效益分析,資料是靜態(tài)或是動(dòng)態(tài)的定址所需的時(shí)間鍵值長(zhǎng)度鍵值基數(shù)位址空間大小資料存取的頻率對(duì)於不成功的存取，能否很快地確定所要尋找的鍵值根本不存在檔案中。,資料是靜態(tài)或是動(dòng)態(tài)的,在電腦的應(yīng)用上，

26、不論是在設(shè)計(jì)一個(gè)資料庫管理系統(tǒng)(Data Base Management System; DBMS)、作業(yè)系統(tǒng)(Operating System)、高階語言的釋譯程式(Interpreter)、編譯程式(Complier)及一般的應(yīng)用程式等，均常須利用雜湊函數(shù)來存取資料。  其中有些內(nèi)容是一成不變的靜態(tài)資料如編譯程式中的保留字表及作業(yè)系統(tǒng)中的公用程式名稱表；有些則會(huì)隨著不同的原始程式而變化，如編譯程式中的識(shí)別字符號(hào)表，因?yàn)槠?/p>

27、鍵值內(nèi)容是多變化的動(dòng)態(tài)資料，故無法事先選擇一個(gè)較佳的雜湊函數(shù)。上述所介紹的雜湊函數(shù)，皆較適合靜態(tài)資料的建立及搜尋。,定址所需的時(shí)間,對(duì)於大量的資料而言，由於所有的資料均存放在磁碟中，故計(jì)算鍵值的位址，應(yīng)儘可能精確到該鍵值資料所存在的磁碟區(qū)段(Bucket或Block)位址。,鍵值長(zhǎng)度,若鍵值長(zhǎng)度較長(zhǎng)，則利用疊合法較除法省時(shí)省事。,鍵值基數(shù),若鍵值基數(shù)為二進(jìn)位，則除法、疊合法、乘法、平方取中法等較適用。若鍵值為十進(jìn)位，則可選用除法、位數(shù)分

28、析法、基數(shù)法及疊合法等。,位址空間大小,理論上位址空間愈大，愈不容易發(fā)生碰撞現(xiàn)象；反之在有限的位址空間且?guī)缀醴艥M所有鍵值的情況下，則容易發(fā)生碰撞。因此，如何選擇位址空間及預(yù)留多少空間，則是由程式設(shè)計(jì)師的經(jīng)驗(yàn)和所選用的函數(shù)來決定。,資料存取的頻率,若是某些資料特別常用經(jīng)常被查詢，則所選用的雜湊函數(shù)和解決碰撞的方法，對(duì)於整體查詢的效益會(huì)有很顯著的影響。,選擇了雜湊函數(shù)的取得方法之後，評(píng)估所設(shè)計(jì)的雜湊函數(shù)是否有效率：存取資料的速度資料新增