歡迎來到雜湊表 (Hash Table) 的世界！
你有沒有想過，電腦是如何在千萬個數據中，於瞬間找到某一個特定使用者的資料？它絕對不會逐一搜尋列表——那樣太慢了！相反地，它使用一種稱為雜湊表 (Hash Table) 的精妙數據結構。
在本章中，我們將學習這些數據世界的「速度惡魔」是如何運作的。如果起初聽起來有點像數學，別擔心；一旦你掌握了當中的規律，它就像在編號的掛鉤上找自己的外套一樣簡單！
1. 什麼是雜湊表？
雜湊表是一種數據結構，它能在鍵 (Key)（例如用戶名或 ID 編號）與值 (Value)（例如用戶的個人資料）之間建立映射 (Mapping)。
你可以把它想像成健身房裡的一大排置物櫃。每個置物櫃都有一個編號（稱為索引 (Index) 或地址 (Address)）。你不需要搜尋每個櫃子來找你的包包，你有一個「神奇公式」，能根據你的名字直接告訴你屬於你的櫃子編號。
為什麼要使用它？
我們使用雜湊表的主要原因是速度。無論儲存了多少數據，它們都能讓我們幾乎瞬間完成資料的尋找、新增或刪除。
你知道嗎？ 雜湊表是資料庫索引、快取 (Cache)，甚至某些程式語言儲存變數背後的秘密武器！
重點總結：
雜湊表將鍵映射到記憶體中的特定位置，讓我們可以瞬間找到它。
2. 神奇公式：雜湊演算法
我們如何決定一筆資料該放在哪裡？我們使用雜湊演算法 (Hashing Algorithm)（或稱雜湊函數 (Hash Function)）。
雜湊函數接收一個鍵作為輸入，並將其轉換為一個數字。這個數字會被用作儲存資料的地址（陣列中的索引）。
簡單範例：模數法 (Modulo Method)
一種非常普遍且「簡單」的雜湊演算法是模數 (Modulo) 法。
假設我們有一個包含 10 個槽位的雜湊表（索引為 0 到 9）。我們的公式是：
\( \text{address} = \text{key} \pmod{\text{table\_size}} \)
如果我們的鍵是 124：
\( 124 \pmod{10} = 4 \)
所以，鍵 124 的資料會被儲存在索引 4。
逐步解析：儲存一個鍵
1. 取得鍵（例如 57）。
2. 運行雜湊函數（例如 \( 57 \pmod{10} = 7 \)）。
3. 將資料儲存在該索引（地址 7）。
如果覺得數學有點枯燥，別擔心——只要記住函數只是一組規則，用來為資料挑選座位而已！
快速回顧：
雜湊函數：將鍵轉換為索引地址的計算過程。
3. 當空間擁擠時：碰撞 (Collisions)
想像你在參加派對，主辦人說：「每個人都坐在與你電話號碼最後一位數字對應的椅子上。」如果你的號碼尾數是 5，你就去 5 號椅。但如果別人的號碼尾數也是 5 呢？
在計算機科學中，這稱為碰撞 (Collision)。
定義：當兩個不同的鍵產生相同的雜湊值（地址）時，就會發生碰撞。
範例：使用我們的 \( \text{key} \pmod{10} \) 規則：
鍵 25 雜湊後對應到索引 5。
鍵 85 雜湊後也對應到索引 5。
糟糕！我們不能把兩份資料放進同一個槽位。
重點總結：
在現實世界中，碰撞是不可避免的，因為我們的可用鍵通常比表中的槽位多得多。
4. 解決問題：處理碰撞
當碰撞發生時，我們需要一個「備用方案」來為資料尋找新家。這通常稱為再雜湊 (Rehashing)。
線性探測 (Linear Probing)（「隔壁」法）
處理碰撞最簡單的方法就是尋找表中下一個可用的空槽位。
運作方式：
1. 計算地址（例如索引 5）。
2. 索引 5 滿了嗎？是的。
3. 查看索引 6。它是空的嗎？如果是，把資料放進去！
4. 如果索引 6 也滿了，就繼續往 7、8 等後續位置移動。
搜尋碰撞資料
如果之後我們要尋找鍵 85，電腦會：
1. 將 85 進行雜湊得到索引 5。
2. 檢查索引 5。發現裡面存的是鍵 25！（它知道這不是正確的資料）。
3. 它會接著檢查後續的槽位（使用相同的碰撞規則），直到找到 85 或一個空位為止。
要避免的常見錯誤：學生常認為雜湊是「隨機」的。其實不然！雜湊函數必須是確定性 (Deterministic) 的——這意味著如果你輸入相同的鍵，每次都必須得到相同的地址。
記憶小撇步：BUS 檢查法
思考碰撞時，想像一輛 BUS：
B (Busy) - 槽位是否忙碌 (Busy)？
U (Use) - 使用 (Use) 下一個槽位。
S (Search) - 搜尋 (Search) 直到找到它為止！
快速回顧盒：
碰撞：兩個鍵，同一個地址。
再雜湊：碰撞發生時尋找新位置的過程（例如移至下一個空槽）。
章節總結
- 雜湊表是將鍵映射到值的高速數據結構。
- 雜湊函數計算儲存資料的地址（索引）。
- 當兩個鍵雜湊到同一個地址時，會發生碰撞。
- 再雜湊（如線性探測）用於在碰撞發生時找到替代的槽位。