Search

雜湊函數

雜湊函數之相關名詞說明：

【桶，bucket】雜湊表中儲存資料的位置，每一位置給定一個唯一的位址，此位址稱為bucket address。

【槽，slot】每一個位置(桶)有多個資料儲存區，每一儲存區稱為槽(slot)。每一槽可以容納一筆記錄。

【碰撞，collision】當不同之鍵值經雜湊函數計算後，落在相同的位置(bucket address)，稱之為碰撞。

【溢位，overflow】如有一鍵值經雜湊函數計算後，相對應之位置(桶,bucket)已裝滿，就稱為溢位。

中間平方法(mid-square)
此方法，鍵值平方後，取出中間某些位元當作資料儲存的位址。

【範例】假設有一鍵值k=510324。若儲存空間(桶數目)為104，也就是取四位數(0000~9999)。則雜湊函數h(k)

h(k)=k2取中間四位數=260430584976取中間四位數=3058

折疊法(folding)
此方法，是將鍵值分為數段，除最後一段外，其餘各段皆等長(等於儲存空間，桶數目)。然後，將各段相加，就可得所對應之位址。相加方式有兩種：

【位移折疊，shifting folding】將各段直接相加。

範例：鍵值123203241112205

à123,203,241,112,205à(+)à884 (hash address)

【邊界折疊，folding at the boundaries】將奇數段或偶數段反轉後相加。

範例：鍵值123203241112205

à123,203,241,112,205à(偶反轉)

à123,302,241,211,205à1082(hash address)

除法(Division)
此方法運用MOD運算，將鍵值X除以某一數值 M，取其餘數當作X的位址。這位址介於0~M-1間。一般M建議使用質數效果較佳(不會有因數消去之問題)。

h(X)= X mod M

【範例】假設有一鍵值數列{X}={15,29,52,100,200}。以除數M=13，則依h(X)= X mod M，建立之雜湊表為：



數字分析法(digital analysis)
此方法需先對資料鍵值之分佈情形詳細分析再設計雜湊函數，數字分析法有兩種：

【目視數字分析法】利用目視法，將鍵值各位數的分佈不均的數字刪除，其餘保留為雜湊位址(hash address)。

【統計數字分析法】運用統計方法分析鍵值各位數的分佈情形，求出雜湊位址(hash address)。