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

雜湊表 (Hash Table)

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

雜湊表的定義與特性

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

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

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

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

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

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

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

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

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

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

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

這種方式在查找資料的時候很簡單，若已知道要找尋的資料 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

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