基本概念
Hash其實是一個人名，他發明了hash algorithm（雜湊演算法）其主要的目的是提高搜尋的效率，透過將物件相關訊息映射成一個唯一的數值，這個值就是雜湊值。在電腦中會透過雜湊函數來處理這件事，將輸入的訊息轉換成數值，一個好的雜湊函數須包含以下特性
- 每個字串可以產生唯一的雜湊值
- 相同字串在不同時間輸入，也要得到相同的雜湊值
- 不論字串大小都可以產稱相同長度的雜湊值
上述資料結構只要當我們有key就可以得到value，我們又稱為雜湊表，透過key搜尋value的時間複雜度是O(1)。
雜湊表轉換成陣列
本質上雜湊表也是一種陣列，所以我們可以將雜湊表轉成陣列索引，
首先我們計算鍵（key）的雜湊值，以上面的表格為例輸入狗會得到雜湊值0023，以程式表達的方式如下
hashcode = hashfunction(key)
接著假設陣列的長度是ｎ可以使用求餘數（mod）的方式計算鍵的索引值。
index = hashcode % n
雜湊表寫入
假設有一個空的雜湊表，此陣列包含三個空間元素，如下圖
因為狗對應的值為0023，除以3的餘數為2，因此要存入index為2的的位置
雜湊碰撞與鏈結法
你會發現有時候求索引值是會出現相同的餘數，像是上面的雞 -> 0026 % 3 = 2，就跟狗的索引值相同，遇到這種情況我們就稱為雜湊碰撞，這時候我們可以使用鏈結串列將資料接在前面的資料後，當所有的資料儲存至陣列，雜湊表就算完成了，見下圖
除了用鏈結串列的方式解決雜湊碰撞，還可以用開放定址的方式，我們有機會再來補充。
搜尋雜湊表
假設我們要搜尋狗的體重，先計算雜湊值得到0023，除以3取餘數得2，因此我們知道狗的資料放在陣列中索引2的位置，接著可以找到12000，得知狗的體重是12000公克。而假設我們要搜尋雞的體重，因為雞的索引值一樣是2，但索引2的第一個資料不是雞，我們就在索引2進行線性搜尋，就可以找到雞了。
雜湊表的規模與擴充
假設要存放的資料太多，雜湊表的空間太少，就會導致碰撞的機率過高，使搜尋效率下降；反之若資料的數量太少，但建立了超大的雜湊表就會浪費非常多空間，造成記憶體浪費。因此跟大家介紹一個新的名詞叫做負載系數（loadfactor），其計算方式如下
負載系數 = 雜湊表的項目數 / 雜湊表的陣列容量
一般來說當負載系數 > 0.75雜湊表就需要擴充了。
雜湊表的效能分析
和其他資料結構做分析
在做搜尋的時候，如果跟二元樹相比，二元樹的時間複雜度為O(log n)，但雜湊表的時間複雜度為O(1)，所以效能差異非常大。
以上大家對雜湊表有沒有基本的概念拉，後續會再補充用python實作雜湊表，請各位讀者敬請期待。
竹林裡的呢喃：
哇凌晨3點11分快累鼠拉，跟大家分享達文西的一句話
如果今天我很努力地學習 過得很充實 則我晚上將睡得很安穩
要不是因為睡前發現今天好像沒有讀新東西，晚上感覺會睡不安穩，所以就硬著頭皮坐在電腦桌前坑吃吭哧的啃書加上輸出成文章了，希望這些文章可以幫助到以後學資結的人～
