hashing(雜湊法)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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