iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 24
7
Software Development

30天學演算法和資料結構系列 第 24

[資料結構] 雜湊 (Hash)

  • 分享至 

  • xImage
  •  

很多人以為雜湊就是加密,但雜湊不是加密! 雜湊不是加密! 雜湊不是加密! 雜湊是因為他的特性很適合來做加密的運算,但真的不等同於加密!

雜湊 (Hash)

雜湊(英語:Hashing)是電腦科學中一種對資料的處理方法,通過某種特定的函式/演算法(稱為雜湊函式/演算法)將要檢索的項與用來檢索的索引(稱為雜湊,或者雜湊值)關聯起來,生成一種便於搜尋的資料結構(稱為雜湊表)。舊譯哈希(誤以為是人名而採用了音譯)。它也常用作一種資訊安全的實作方法,由一串資料中經過雜湊演算法(Hashing algorithms)計算出來的資料指紋(data fingerprint),經常用來識別檔案與資料是否有被竄改,以保證檔案與資料確實是由原創者所提供。

如今,雜湊演算法也被用來加密存在資料庫中的密碼(password)字串,由於雜湊演算法所計算出來的雜湊值(Hash Value)具有不可逆(無法逆向演算回原本的數值)的性質,因此可有效的保護密碼。
---引自〈維基百科〉

這邊來統整一下。

雜湊函數 (Hash function)
主要是將不定長度訊息的輸入,演算成固定長度雜湊值的輸出,且所計算出來的雜湊值必須符合兩個主要條件:

  • 由雜湊值是無法反推出原來的訊息
  • 雜湊值必須隨明文改變而改變。

舉例來說,雜湊函數就像一台果汁機,我們把蘋果香蕉你個芭樂 (資料) 都丟進去打一打、攪一攪,全部變得爛爛的很噁心對吧?!這時候出來的產物 (經過雜湊函數後的值),是獨一無二的,沒有辦法反向組合成原來的水果 (資料)。倘若我們把蘋果改成紅龍果,出來的產物 (經過雜湊函數後的值) 就會跟著改變,變成桃紅色的,不再是原來的淡黃色。

承上述的例子,用紅龍果香蕉你個芭樂經過雜湊函數出來的顏色是桃紅色 (雜湊值),那有沒有可能我用其他的水果也可以打出相同的顏色呢?但因為雜湊值的特性是無法反推的,所以如果真的打出相同的顏色的話,我們稱為碰撞 (Collision)。這就代表說這個雜湊值已經不安全,不再是獨一無二的了,需要更改雜湊函數。

雜湊表 (Hash table)
在用雜湊函數運算出來的雜湊值,根據 鍵 (key) 來儲存在數據結構中。而存放這些記錄的數組就稱為 雜湊表

舉例來說,我們有一筆資料用字典的形式表示,每個名字都搭配性別:

{Joe:'M', Sue:'F', Dan:'M', Nell:'F', Ally:'F', Bob:'M'}

而我們將每個名字經過雜湊函數的運算。

(Key)                 (hash value)     (stored index)
Joe  → (Hash function) →   4928   mod 5   =   3
Sue  → (Hash function) →   7291   mod 5   =   1
Dan  → (Hash function) →   1539   mod 5   =   4
Nell → (Hash function) →   6276   mod 5   =   1
Ally → (Hash function) →   9143   mod 5   =   3
Bob  → (Hash function) →   5278   mod 5   =   3

hash value 是獨一無二的,用 mod 5 來得到餘數並儲存才記憶體中。

0: 
1: [ Sue, F ] → [ Nell, F ]
2: 
3: 
4: [ Joe, M ] → [ Ally, F ] → [ Bob, M ]
5: [ Dan, M ]

當我們要找資料的時候,例如 Ally 的性別,我們就把 Ally 丟到名為 Hash 的果汁機來得到 hash value,再用 mod 5 找到儲存在記憶體中的位置,但記憶體中的第一個位置並不是 Ally 是 Joe,我們根據 Joe 的鏈結找到下一個元素,直到找到答案。

另一個會讓人疑惑的點是為什麼用 mod 5?其實有很多種方式來選擇怎麼儲存在記憶體中,這邊只是範例。而會用 mod 5 是因為記憶體儲存空間假設為 5 。但儲存空間的大小也不是隨意設的,如果設得太大,資料沒那麼多,會造成空間浪費;若設得太小,會造成每一個空間的資料重疊,查找不易。所以設定空間大小也是一門學問。

總的來說,雜湊表其實很適合來存放不確定數量大小的資料,查找的時候也很快速、彈性。


上一篇
[資料結構] 圖的廣度優先走訪 (Breadth-first Search)
下一篇
[演算法] K-means 分群 (K-means Clustering)
系列文
30天學演算法和資料結構31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言