資結筆記｜雜湊表（Hash Table）

## 資結筆記｜雜湊表（Hash Table） ### 複習 &emsp;&emsp;先前有提到[堆積樹（heap tree）](https://hackmd.io/@fooox0864/r1PuXJsTyx)還沒看或是感興趣的讀者歡迎去看看唷！ ### 基本概念 &emsp;&emsp;Hash其實是一個人名，他發明了hash algorithm（雜湊演算法）其主要的目的是提高搜尋的效率，透過將物件相關訊息映射成一個唯一的數值，這個值就是雜湊值。在電腦中會透過雜湊函數來處理這件事，將輸入的訊息轉換成數值，一個好的雜湊函數須包含以下特性 1. 每個字串可以產生唯一的雜湊值 2. 相同字串在不同時間輸入，也要得到相同的雜湊值 3. 不論字串大小都可以產稱相同長度的雜湊值 ![雜湊函數-4](https://hackmd.io/_uploads/BJADyl1CJg.png) &emsp;&emsp;我們會用表單來表示"鍵（key）：值（value）"的配對關係，在python又稱為字典（dict）的資料格式，用以下的表格舉例，用動物對應到體重 | 鍵（key） |值（value） | 雜湊值| | ---------- | -------- | --------| | 狗 | 12000 |0023| | 貓 | 8000 |0024| | 豬 | 21000 |0025| | 雞 | 5000 |0026| | 兔 | 6500 |0027| &emsp;&emsp;上述資料結構只要當我們有key就可以得到value，我們又稱為雜湊表，透過key搜尋value的時間複雜度是O(1)。 ### 雜湊表轉換成陣列 &emsp;&emsp;本質上雜湊表也是一種陣列，所以我們可以將雜湊表轉成[陣列索引](https://hackmd.io/@fooox0864/S19qO-681x)，首先我們計算鍵（key）的雜湊值，以上面的表格為例輸入狗會得到雜湊值0023，以程式表達的方式如下 ``` hashcode = hashfunction(key) ``` 接著假設陣列的長度是ｎ可以使用求餘數（mod）的方式計算鍵的索引值。 ``` index = hashcode % n ``` #### 雜湊表寫入 &emsp;&emsp;假設有一個空的雜湊表，此陣列包含三個空間元素，如下圖 ![雜湊函數-3](https://hackmd.io/_uploads/Bk0QJlkC1g.png) 因為狗對應的值為0023，除以3的餘數為2，因此要存入index為2的的位置 ![41](https://hackmd.io/_uploads/HyulOx10yg.png) #### 雜湊碰撞與鏈結法 &emsp;&emsp;你會發現有時候求索引值是會出現相同的餘數，像是上面的雞 -> 0026 % 3 = 2，就跟狗的索引值相同，遇到這種情況我們就稱為雜湊碰撞，這時候我們可以使用[鏈結串列](https://hackmd.io/@fooox0864/BkTd014vyl)將資料接在前面的資料後，當所有的資料儲存至陣列，雜湊表就算完成了，見下圖 ![42](https://hackmd.io/_uploads/SJZl_xkC1x.png) 除了用鏈結串列的方式解決雜湊碰撞，還可以用開放定址的方式，我們有機會再來補充。 ### 搜尋雜湊表 &emsp;&emsp;假設我們要搜尋狗的體重，先計算雜湊值得到0023，除以3取餘數得2，因此我們知道狗的資料放在陣列中索引2的位置，接著可以找到12000，得知狗的體重是12000公克。而假設我們要搜尋雞的體重，因為雞的索引值一樣是2，但索引2的第一個資料不是雞，我們就在索引2進行線性搜尋，就可以找到雞了。 ### 雜湊表的規模與擴充 &emsp;&emsp;假設要存放的資料太多，雜湊表的空間太少，就會導致碰撞的機率過高，使搜尋效率下降；反之若資料的數量太少，但建立了超大的雜湊表就會浪費非常多空間，造成記憶體浪費。因此跟大家介紹一個新的名詞叫做負載系數（loadfactor），其計算方式如下 ``` 負載系數 = 雜湊表的項目數 / 雜湊表的陣列容量 ``` 一般來說當負載系數 > 0.75雜湊表就需要擴充了。 ### 雜湊表的效能分析 | 雜湊表動作 | 時間複雜度 | | ---------- | -------- | | 搜尋 | $O(1)$ | | 插入 | $O(1)$ | | 刪除 | $O(1)$ | 和其他資料結構做分析 | 時間複雜度比較 | 陣列 | 鏈結串列 |雜湊表| | ---------- | -------- | -------- | -------- | | 插入 | $O(n)$ | $O(1)$ | $O(1)$ | | 刪除 | $O(n)$ | $O(1)$ | $O(1)$ | | 搜尋 | $O(1)$ 有陣列索引 | $O(n)$ | $O(1)$ | 在做搜尋的時候，如果跟二元樹相比，二元樹的時間複雜度為O(log n)，但雜湊表的時間複雜度為O(1)，所以效能差異非常大。以上大家對雜湊表有沒有基本的概念拉，後續會再補充用python實作雜湊表，請各位筆者敬請期待。