#11 如何快速搜尋資料 - 利用 Hash function/Hash table

前面文章講了 binary search,這篇文章來介紹另一個好用而且非常常見的分類方法,它叫做 Hash.談到 Hash 時,通常包含兩個部份,一個是 Hash function,另一個是 Hash table.在業界的產品上,如 .Net/Java 等,都有提供業界標準的 hash function 以上一些 Hash table 的應用,如 .Net 的 HashSet, Dictionary 等就是 Hash table 的應用.首先,我們先談 Hash function.

Hash function 有一個很重要的特點是運算快速,那要多快呢? 最好是  O(1),也就是指運算的速度不應該與輸入量的大小有關.換言之,你可以想像成你有兩個字串要輸入 hash function,其中一個字串很長,另一個字串很短,當你同時輸入到 hash function 運算時,得到結果的時間是一樣的.若用數學來表示,它就是 output = H (intput) ,其中 H 就是 hash function.

實行 Hash 的方法有無數種,你可以寫一個很簡單的.Hash 的實作要怎麼寫,這必須取決於你用 hash function 的目的是什麼.例如,你只是希望把一大堆的資料做一個簡單的分類,那麼你的 hash function 就可以用簡單的 mod (數學的求餘數) 來達成.舉個例子,有一些整數,而你要把他們分類到三個籃子裡,最簡單的方法就是求 3 的餘數,餘數如果是 0,那就放在第一個籃子,如果是 1,那就放在第二個籃子,以此類推.所以,你的整數數字經過 hash function 運算後就會被分成三個群組.今天若有人要找這些整數數字中有沒有 77 這個數字,那麼他只要到第三個籃子 ( 77 mod 3 = 2),然後把第三個籃子裡面的數字全部找過一遍就知道有沒有 77了.以這例子來看,在尋找 77 的過程中,我們只需要尋找 1/3 的數字,另外有 2/3 的數字放在另外兩個籃子裡是不需要去找的,這等於加快了找資料的時間.所以,從這個例子來看,Hash 的分類法還蠻好用的,如果今天籃子夠多的話,這樣等於每個籃子裡面所儲存的數字越更少,因此找到數字的速度就會更快.


如果你的 hash function 的目的不像前面談的做分類這麼單純的話,則 hash function 的實作就得符合你的目的才行.在一般基本的加解密裡,多多少少會用到一點 hash function 的功能,如果此時 hash function 寫的太過簡單,這將造成加解密不夠 "強".什麼樣才叫做夠 "強" 的 hash function 呢? 前面說的,output = H(input),input 是你所定義的輸入範圍,可能是所有的字串,可能是所有的數字,也可能是所有的正整數.output 也是你定義的輸出範圍.通常來說一個夠強的 hash function 都會給出相同長度的 output.也就是說,H(1) = KI87CJDL , H(-100) = O9DI3KJ4 等等.Hash function 的目的並不是要加解密,output / input 的關係不用是一對一,所以一個 hash function 很有可能讓兩個或多個 input 得到相同的 output,例如 H(54839) = H(abcd),只要你 "很難" 能找到兩個 input 會得到相同的 output,我們就可以稱這個 hash function 夠強,其中 "很難" 的意思就是你得花很多時間才能找到.

當一個 hash function 夠強時,它就具有單向和不可逆的特性,也就是說因為 "很難" 找到兩個 output 會得到同一個 input,因此當你看到 hash function 的 output 時,你就 "很難" 知道 input 會是什麼,就算你找到了一個,也不代表它就是目標 input,因為多個 input 會得到相同 output."很難" 不代表不可能,只是很難而己.

你只要選到一個適合的 hash function,便能幫你處理很多的事情,適合不等於要夠強,主要符合你的需求即可,如前面說的資料分類功能.Java 和 .Net 平台都提供了業界裡常用的 Hash function,比如 MD5 或 SHA 演算法,提供了不同運算位元長度 .而 Hash table 就是讓 input 經過 hash function 計算之後,讓 output 值做為放到籃子的依據,就像 Java 的 Hashmap 或 .Net 的 HashSet 之類的資料結構.如前面所說的,籃子越多,資料就能分更多的群組,所以當一樣數量的資料量要分類時,籃子越多的,裡面放的資料就更少.

接下來,你認為把 input 透過 hash function 得到 output 放到一個籃子裡,它的 Big O 怎麼算呢 ? 如果籃子都是空的,那就是 O(1),因為此時只是一個簡單的數學運算,如前面提的求餘數 mod.這個運算跟資料數量大小沒有關係,如果你自己寫的 hash function 不是 O(1),那就問題大了,因為這失去了 hash table 的意義.如果籃子不是空的呢 ? 這就要看籃子是用什麼資料結構做的.一般來說都會用 List,所以有一個新的資料放到籃子時,如果籃子已經有資料了,那麼新的資料就會被加到 List 的最前面,這動作也是 O(1),所以使用 Hash table 時,平均來說,它的 Big O 就是 O(1),也就是說當你使用 Hash table 時,平均來說,你找到資料是 O(1),這個比用 Array 的 O(n) 來的快,也比用 Binary search (Olog(n)) 的方式要來的快.

Share: