iT邦幫忙

2021 iThome 鐵人賽

DAY 12
0
Software Development

少女人妻在廚房裡想不通的演算法系列 第 12

【在廚房想30天的演算法】Day 12 資料結構:雜湊表 Hash Table

Aloha!又是我少女人妻 Uerica!以前我爸開車在停紅綠燈的時候,總會趁著紅燈幾秒的空擋跟我玩遊戲,如果時間允許,就會刻意走不同的路回家看看,有時總能挖掘到一些很好吃的美食小吃,當然惡整我也是他日常的樂趣之一 QQ。總之 ”努力把一成不變的生活過得很有趣“ 是爸爸的人生觀。我想我應該也有遺傳到一些吧!我以前國文課本上的偉人都有化妝綁辮子呢!


雜湊表 (Hash Table)

雜湊表有點類似陣列 Array 與連結串列 Linked List 的結合,前面有提到陣列的特性為搜尋容易,但插入與刪除較無效率,連結串列卻剛好相反,屬於搜尋困難,但插入與刪除較為有效率的資料結構。而雜湊表即可解決這兩種資料結構的缺點。

雜湊表的定義與特性

雜湊表的所儲存的資料元素都有成對的鍵 (Key) 及值 (Value) ,將 Key 經過雜湊函數 (Hash Function) 後,計算出新的值並放入對應的陣列索引中。若發生雜湊碰撞 (collsion),則使用連結串列的方式儲存。此資料結構方法被廣泛運用在資料庫搜索、關鍵字搜尋、快取等。

好!先來喝杯果汁吧~
假設今天要儲存水果 (Key) 以及水果的數量 (Value),而果汁機是雜湊函數 (Hash Function)。

Db3XHz0

我想儲存蘋果有三顆這個資料,先將蘋果 (Key) 放進果汁機 (Hash Function) 打一打。

3TUMc7J

得到了雜湊值 (Hash Values) 111,因陣列的長度是 4 ,所以將雜湊值除以 4 值取餘數,放入對應的陣列索引值位置。(此部分的雜湊值只是舉例),在此得出蘋果的雜湊值是 111 ,取餘數後是 3。
UDeKstA

所以將蘋果及三顆的值 (Value),一起放在索引 3 的位置
Ncmbb1s

再來要處理五顆草莓,在此得出草莓的雜湊值是 112 ,取餘數後是 0。
OQYDEst

將草莓有五顆這個資料存在對應的索引值 0 。
ocHtWYi

只有一顆的桃太郎的桃子也是同樣的道理。
Qlpe0Vt

將桃子有一顆這個資料放入對應的索引值 2 。
c47QXRn

櫻桃來了~櫻桃得出的雜湊值取餘數後是 0,但索引值 0 的位置已經有草莓的資料了!這種狀況就稱為雜湊碰撞 collsion!
ZJHU9RB

這時就可以用我們之前提過的連結串列的方式來儲存資料!
IlSmMOU

這種方式在查找資料的時候很簡單,若已知道要找尋的資料 key 是什麼,只要將 key 經過雜湊函數的計算並取餘數後,根據求得的該索引值下去查找即可!

  • 雜湊表優點

    • 搜尋資料前無需事先排序
    • 無 collsion 的情況下搜尋某資料元素的時間複雜度為 O(1)。
    • 保密與安全性高
  • 雜湊碰撞 collsion :
    不同的資料元素放入雜湊函數中,雖然機率很小,還是可能會獲的同樣的結果。這時可以使用下列方式處理。

    • 鏈結法 chaining : 利用串列將資料元素依序存在陣列中已有資料元素的後面,如同上面的例子
    • 開放定址法 open addressing : 發生碰撞時,計算出下一個候補位置,若下一個位置也發生碰撞,就繼續計算到有空的位置為止。
  • 雜湊值 Hash Values :
    雜湊值是資料經由雜湊函數後得出的結果,但雜湊值並非加密,相同的資料值進入雜湊函數後會求得相同的結果,但也有很小的機率會發生不同的資料值會得到相同的結果。但因雜湊函數的計算與設計方式,雜湊值是幾乎無法回推到雜湊前的值,所以雜湊並非加密。

  • 雜湊函數 Hash Function :
    又稱雜湊演算法,可以想像成為資料元素建立指紋的方法,該函式會將資料打亂並混合,建立出該資料對應的雜湊值。雜湊函數的演算法有數種,有些程式語言或工具會有內建的 Hash Function,或 Hash Code 的函數可使用。代表性的演算法有 MD5、SHA系列等。

參考資料:

【資料結構】雜湊表

[資料結構] Hash Table

Data Structures 101: implement hash tables in JavaScript


好的今天就到這邊啦~希望大家也都能努力在生活中找樂趣,這樣不管做多無聊得事都有滿滿的力量堅持下去了~~明天見啦掰掰!


上一篇
【在廚房想30天的演算法】Day 11 資料結構:圖 Graph
下一篇
【在廚房想30天的演算法】Day 13 資料結構:堆積 Heap
系列文
少女人妻在廚房裡想不通的演算法30

1 則留言

0

用果汁機來解釋太可愛了!!! /images/emoticon/emoticon07.gif

啊哈~謝謝 Iris!/images/emoticon/emoticon35.gif

我要留言

立即登入留言