iT邦幫忙

2021 iThome 鐵人賽

DAY 13
0
自我挑戰組

30天不怕演算法:白話文版系列 第 13

Day 13:雜湊表(hash table)

在通訊錄或朋友列表裡,我們可以搜尋一個名字,就找到電話或頁面,只需要O(1)。如果想要實現這樣的操作,可以想像一種融合上一回陣列和鏈結串列的資料結構。

雜湊函式(hash function)

雜湊表是可以儲存鍵(key)和值(value)的資料結構,但它並不是像試算表一樣,只是單純地把「John Smith」和他的電話「521-1234」存在一起。它做的事情比較像是,當我們輸入John Smith,可以找到他的電話的儲存位址。而雜湊表就是透過雜湊函式的運算,來做到這種比較複雜的結構。

雜湊函式可以輸入資料,並回傳一個值。以下圖為例,雜湊函式將John Smith這個字串轉為一個雜湊值(02),並以這個值作為陣列的索引,將John Smith的電話儲存在這個位址。換句話說,透過雜湊函式,我們可以得到一個資料存放的位址。

圖片來源:維基百科

雜湊函式的特性是:

  • 具有一致性,也就是每次輸入John Smith都會輸出同樣的值。
  • 不同的輸入可能會得到一樣的值(同樣的儲存位址),也就是所謂的雜湊衝突(hash collision,也譯作碰撞) 。

雜湊衝突

理想的情況下,我們希望每個資料都有一個獨一無二的陣列位址,這樣存取所有的資料都可以實現O(1),可是當資料量很大時,必須考慮陣列的儲存空間,而且很難實現雜湊函式回傳的值都不重複,所以必須想辦法解決雜湊衝突的問題。

舉例來說,如果有一個英文名單,我們用雜湊函式將所有人名的第一個字母轉為0-25的其中一個數字,存在長度為26的陣列中。

那很快就會出現衝突的情況,因為名字開頭字母很容易重複。衝突的一個解決方法是使用鏈結串列(linked list),我們可以使用鏈結串列儲存索引位置相同的資料(如下圖)。這種情況的雜湊表基本上就是每個元素都是一個鏈結串列的陣列。

圖片來源:https://itnext.io/data-structures-in-js-hash-tables-app-with-react-b28b02a9e6b5

但這時候可能又有另一個問題,假設名單裡S開頭的人名特別多,那就會變成陣列中S的索引位置是一個超長的鏈結串列,而其他位址是空的,那麼其實跟直接把名單存在一個鏈結串列中沒有兩樣,存取也會變得非常沒有效率。

所以由此可知,一個好的雜湊函式要能減少衝突的發生、讓資料平均分布在雜湊表中,提升資料結構的效率。要從零開始設計出一個時間空間效率俱佳的雜湊函式不是非常容易,不過好消息是在開發時基本上不會需要自己撰寫雜湊函式,各種語言的函式庫裡都有效能不錯的雜湊函式可以直接使用。


上一篇
Day 12 :陣列(array)與鏈結串列(linked list)
下一篇
Day 14:安全雜湊演算法(SHA)
系列文
30天不怕演算法:白話文版30

尚未有邦友留言

立即登入留言