Hashing function (散列函式) 在網頁應用中被廣泛採用,從數碼簽署、錯誤檢測、登入驗證、到壓縮儲存空間,由於它的原理比較複雜,很多人把它跟加密函式混淆,對於如何運用 hash function,如何選擇合適的 hash function,和它的優點缺點都不清楚,本文嘗試解答這些問題。
Hashing 是甚麼?
簡單地說,Hashing 是一種數據影射 (mapping) 的算法 (algorithm),通常用來把一大串不定長度的數據影射到一個固定長度的、較短的數據,這個固定長度的數據稱為 hashing value (散列值)。
例如我們把一個由英文字母組成的任意長度的字串,把每一個字符的 ASCII 數值加起來,最後除以 256 得到的餘數作為 hash value,這裡輸入的字串長度沒有限制,輸出的數值則必定在 0 至 255 之間,所以是一個合法的 hashing function。
以上的 hash function 只有 256 個可能的 hash value,很明顯有很多字串都會得到相同的 hash value,這種情況我們稱為 hash collision (散列衝突),或者簡稱 collision,事實上從一個不定長度的數據影射到一個固定長度的數據,Collision 是無可避免的,我們並不要求完全沒有 collision,只需把 collision 的機會盡量降低便可以了,若果真的要完全沒有 collision 的話,Hash value 理論上必須與輸入的數據長度相同,這樣便違背了 hash function 的設計目的。 ......閱讀全文 >>>