重念一次早該補起來的「資料結構與演算法」。這篇筆記下 Hash Table (雜湊表) 的 Multiplication Method 並處理碰撞問題。
課程相關資訊
[連結]：https://hiskio.com/courses/572/lectures/29853
本篇範圍：Chapter 8
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
Hash Function
Multiplication Method
1. Index 為 Key mod m, m 為 hashtable size, n 為 # of elements into hashtable
2. Index = [m ( keyA % 1 )]
3. A 為 (√5 – 1 ) /2，這為黃金比例的分數表現形式，值約為 0.618
4. Mod 1 代表留下「小數部分」
縱使用了如此複雜的方式，還是會出現 Collision。不過用 Division Method，可以有效的避免出現 Collision 的問題，因為此值的 Index 更為隨機
Handling Collisions
當遇到衝突時，就將其放進一個 array 來儲存。因此，你的 Hashtable 會變成是 array of arrays
