雜湊 ( hashing )

雜湊 ( hashing )
　
　　雜湊法 ( hashing ) 的搜尋與一般的搜尋法 ( saerching ) 不同。在 Hashing 中，鍵值 ( key value
　　) 或識別字 ( identifier ) 在記憶體的位址是經由函數 ( function ) 轉換而得。此種函數，一般稱之
　　為雜湊函數 ( hashing function ) 或鍵值對應位址轉換 ( key to address transformation ) 。
　
　　　　　　　　　　　　
　
　　雜湊法具有以下四項優點：
　　(１) 使用雜湊法搜尋，檔案不須事先排序 ( sorting ) 。
　　(２) 在沒有碰撞 ( collision ) 及溢位 ( overflow ) 的情形下，只需一次讀取即可，且搜尋的速度與
　　　　資料量的多寡無關。
　　(３) 保密性高，若不知雜湊函數，無法擷取到資料。
　　(４) 可做資料的壓縮 ( data compression ) ，利用適當的散置函數，可將資料壓縮到一個較小的
　　　　範圍內，以節省空間。
　
雜湊函數 ( hashing function )
　
　　一般常見的雜湊函數有下列幾種方法：
　
　　(１) 平方後取中間位數 ( mid - square )
　
　　　　此法是將鍵值平方後，然後視儲存空間的大小來決定取幾位。
　　　　
　　　　【範例】
　　　　　　　　鍵值 k = 113586 。令 m = 9999 ，故 m 為 4 位數的正整數。
　　　　　　　　則 h( k ) = k2 取中間四位數
　　　　　　　　　　　 = 12901779369 取中間 4 位數
　　　　　　　　　　　　= 1779
　
　　　　　　　　m 為儲存空間的大小。
　
　　(２) 折疊法 ( folding )
　
　　　　此法是將鍵值分為數段，除了最後一段外，其餘各段皆須等長，然後將每一段相加，即可
　　　　得到其所對應的位址。在相加的時後，有兩種方式：
　
　　　　(ａ) 位移折疊 ( shift folding )
　　　　　　將各段向左邊靠齊後相加。
　　　　(ｂ) 邊界折疊 ( folding at the boundaries )
　　　　　　將奇數位段或偶數位段反轉後相加。
　
　　　　【範例】
　　　　　　　　如有一個鍵值為 12320324111220 ，其儲存位址為何？
　
　　　　　　　　假設將其分為 5 段，如下所示：
　

　
　　(３) 除法 ( Division )
　
　　　　此法利用模數運算，將識別字 X 除以某一個數值 M ，取其餘數當做 X 的位址。這個位址
　　　　介於 0 ~ M-1 之間。
　
　　　　即 fD ( X ) = X mod M
　
　　(４) 數位分析法 ( digit analysis )
　
　　　　此法適用於大量的靜態資料，亦即所有的鍵值均事先知道，然後檢查所有的數位，分析每
　　　　一數位是否均勻分佈，將不均勻的數位刪除，然後根據儲存空間的大小來決定數位的數目
　　　　。
　
　　　　【範例】
　　　　　　有五位學生的學號分別是：
　　　　　　ST1 = 682203
　　　　　　ST2 = 682171
　　　　　　ST3 = 693214
　　　　　　ST4 = 695252
　　　　　　ST5 = 691340
　
　　　　　　令 m = 100 ，那我們只能挑選兩位數當做每一個學號的 Hashing Function 數值。可利
　　　　　　用統計的方法，分析各數位的分佈情形，方法如下：
　


　　　　　　　SKi 之值越小者，表示 Di 分佈越均勻，因此，我們選擇 D1 和 D2 當做 Hashing
　　　　　　　Function 的數值，故 h(ST1) = 03 ，h(ST2) = 71，h(ST3) = 14，h(ST4)=52，h
　　　　　　　(ST5) = 40
　
解決溢位的方法 ( overflow handing )
　
(１) 線性探測 ( linear probing )

　　又稱為線性開放定址 ( linear open addressing )。其做法是將雜湊位址視為環狀的空間，當溢位
　　發生時，以線性方式從下一號桶開始探測，找尋一個空的儲存位址將資料存入。如下圖所示：
　

　
(２) 鏈結串列 ( chaining )
　
　　是將雜湊空間建立成 b 個串列，起初只有 b 個串列首，只放起始位址，並不放資料，相同位址
　　的鍵值，將形成一個鏈結串列。如下圖所示：
　

　
　　平均探測次數 = 每個節點探測次數之總合 / 節點數
　
　　如上圖， 49 , 23 , 53 , 41 探測數為 1 次，30 , 60 為 2 次，67 為 3 次，節點數為 49 , 23 , 53
　　, 41 , 30 , 60 , 67 等 7 個。
　　故平均比較(探測)數 = ( 1+1+1+1+2+2+3 ) / 7 = 11 / 7
　
(３) 平方探測 ( quadratic probing )
　
　　此法是改善線性探測的缺失，避免相近的鍵值聚在一起。當 f(x) 的位址發生溢位時，下一次是
　　探測 ( f(x) + i2 ) mod b 與 ( f(x) - i2 ) mod b ，其中 1<= i <= ( b-1 ) / 2 ，b 是具有 4j+3 型式的
　　質數。
　
(４) 再雜湊 ( rehashing )
　
　　設置一系列的雜湊函數 g1 , g2 , g3 , .... , gm 。當使用 g1 產生溢位時，則改用 g2 ，若 g2 又
　　發生溢位時，則改用 g3 ，直到沒有溢位發生為止。
　
相關名詞
　
完美雜湊 ( Perfect Hashing )
　
　　完美雜湊 ( Perfect Hashing ) 係指沒有碰撞 ( collision )，亦沒有溢位 ( overflow ) 的雜湊法。一
　　般用於靜態表 ( static table ) 中，由於所有的鍵值均已事先得知，因此可設計出一完美雜湊法
　　來處理。
　
桶 ( bucket )
　
　　雜湊表中儲存資料的位置，每個位置被給定一個唯一的位址，稱之為 bucket address 。
　
槽 ( slot )
　
　　每一個桶可能有好幾個儲存區，此儲存區便稱之為槽 ( slot ) 。每一個槽可以容納一個記錄。

碰撞 ( collision )
　
　　當兩個不同的識別字經過雜湊函數運算後，落在相同的 bucket address ，稱之為碰撞。
　
溢位 ( overflow )
　
　　如果一個識別字經過雜湊函數運算後，所對應的 bucket 已經滿了，就稱之為溢位。
　
同義字 ( Synonym )