Hash Table（三）什麼是 Hash Table 雜湊表？
講解 Hash Table 的意思
-1 min read
- 當資料沒有數字可以當作索引，或是資料間當作索引的數字差距太大，導致 Array 過長，就可以透過某種 Hash function 把資料中某個 Key 雜湊為較小數字的索引，這樣就更容易儲存資料，也好存取。
- Hash Table 是一個陣列，陣列中每個元素都是一個 bucket。
- 選出每筆資料都有的一個值當作 key（如姓名、編號），經過
hash函式後可以得到索引，藉此知道資料要放在 Hash Table 中哪個 bucket 中。 - 若遍歷原始資料 hash 過後，得到重覆的索引，就稱作衝突，可以用 Array 或是 Linked List 的結構讓資料共存在 bucket 內。
- 公開的方法：set、get、delete
- 私有的方法：hash
時間複雜度
- set：O(1)
- Delete: O(1)
- get: O(1)：能夠透過 hash function 直接找出該 key 對應的 bucket