重念一次早該補起來的「資料結構與演算法」。這篇筆記下 Hash Table (雜湊表)。
課程相關資訊
[連結]：https://hiskio.com/courses/572/lectures/29850
本篇範圍：Chapter 8
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
1. 若使用傳統的 array 儲存資料，由於資料連續的關係，你要找某一筆特定資料就會非常慢 O(n)
2. 若你使用 direct-addressed array 來儲存雖然可快速找到，但你得佔據大量的記憶體以確保 array 的連續性
3. Hashtable 的時間複雜度為 O(1)。
4. Hash Function 本質上就是把一個值，經由轉換而得到另外一個值。因此，若你將原始的 id 經由 hash function 變得小一些，那儲存的長度就可以變小，也不會佔用太多記憶體
Hash Function
Division Method
1. Index 為 Key mod m, m 為 hashtable size, n 為 # of elements into hashtable
2. 不免俗的，你會有機會得到衝突 collision
3. n/m 的值越大，越不容易發生衝突，這個比值稱為 load factor。因此這個值多半是會在 0 ~ 1 之間
4. m 一定要大於 n。這個值請記得要遠離 2^P (因為 10^P 可以被 2^P 整除)
5. 另外，你也要注意物件本身的名稱衝突
