歡迎來到雜湊表（Hash Table）的世界！
在之前的章節中，我們探討了如何搜尋列表（List）和陣列（Array）。還記得嗎？二分搜尋法（Binary Search）雖然很快，但要求資料必須先排序；而線性搜尋（Linear Search）呢？如果列表很長，那簡直慢得讓人崩潰！
如果有一種方法可以讓你瞬間找到目標，而無需逐一搜尋每個項目，那該多好？這就是雜湊表（Hash Tables）的魔力所在。在本章中，我們將學習它的運作原理、如何處理「交通擁堵」（碰撞，Collisions），以及為什麼它是程式設計師工具箱中最強大的工具之一。別擔心，如果聽起來一開始有點複雜，我們會一步步拆解說明！
1. 什麼是雜湊表？
雜湊表（Hash Table）是一種以關聯式（associative）方式儲存資料的數據結構。這意味著資料的儲存方式能實現極其快速的檢索。試著想像一下健身房裡那一整面牆的儲物櫃。
比喻：
想像你有 100 個儲物櫃。與其逐一打開櫃子找你的包包（線性搜尋），系統會根據你的名字給你一個儲物櫃編號。每次你回來時，只需要看一眼你的名字，算出你的號碼，直接走向那個櫃子就行了。完全不需要搜尋！
關鍵組件：
1. 鍵值（Key）：這是你提供的唯一輸入資訊（例如使用者名稱或產品 ID）。
2. 雜湊函數（Hash Function）：一種特殊的公式，將你的鍵值轉換成特定的數字（索引/Index）。
3. 雜湊表（陣列）：實際存放資料的列表或「插槽」。
快速複習：雜湊表的主要目標是提供常數時間（constant time）的存取能力，這意味著無論你是搜尋 10 個項目還是 10,000 個項目，找到資料所需的時間幾乎是一樣的！
2. 雜湊如何運作（雜湊函數）
雜湊表的「秘方」在於雜湊函數（Hash Function）。這是一種數學演算法，它接收一個鍵值（Key）並將其對應到陣列中的特定索引。
考試中非常常見的一種方法是餘數法（Modulo Method）。其公式如下：
\( \text{index} = \text{key} \mod \text{table\_size} \)
範例：
假設我們的雜湊表有 10 個插槽（大小為 10）。我們想儲存 ID 147。
\( 147 \mod 10 = 7 \)
ID 147 將會儲存在索引 7 的位置。
什麼是「好的」雜湊函數？
為了保持高效，一個好的雜湊函數應該：
• 計算速度非常快。
• 將鍵值均勻分佈在表中（這樣才不會導致大家都在搶同一個儲物櫃！）。
• 盡量減少碰撞（我們接下來會討論這個）。
重點提示：雜湊函數會精確告訴電腦資料該放在哪裡，以便日後無需四處搜尋就能直接找到。
3. 處理碰撞（「交通擁堵」）
有時候，兩個不同的鍵值會得出相同的索引。這稱為碰撞（Collision）。
範例：
如果表的大小是 10：
ID 147 \( \mod 10 = 7 \)
ID 257 \( \mod 10 = 7 \)
糟糕！兩個 ID 都想擠進索引 7。我們不能直接刪除舊的資料，所以需要策略來處理這種情況。
牛津 AQA 課程大綱要求你掌握兩種主要的解決方法：
方法 A：線性探測（Linear Probing / 開放定址法）
這是一種「尋找下一個空位」的方法。如果索引 7 發生碰撞，電腦會檢查索引 8。如果索引 8 滿了，就檢查索引 9，以此類推，直到找到一個空插槽為止。
優點：非常容易實作。
缺點：可能導致「聚簇（clustering）」，即大量資料堆疊在一起，拖慢運作速度。
方法 B：鏈結法（Chaining / 封閉定址法）
這種方法中，雜湊表中的每個插槽不只是一個單獨的格子，它是一個指向鏈結串列（Linked List）的指標（pointer）。如果發生碰撞，新項目只需加到該索引處串列的末端即可。
優點：表永遠不會像線性探測那樣「填滿」；你可以一直往鏈結中添加資料。
缺點：如果鏈結變得太長，它就會變得像線性搜尋一樣，速度會變慢！
你知道嗎？大多數現代軟體會混合使用這些技術，以確保系統以極致速度運行！
4. 常見陷阱與小技巧
需避免的錯誤：別忘了，當你使用線性探測在表中搜尋某個項目時，你必須遵循相同的「下一個插槽」邏輯。如果你在計算出的索引位置找不到該項目，你必須繼續查看後續的插槽，直到找到該項目或遇到空白空間為止！
記憶小口訣：
• Linear Probing = Look for the next Location（尋找下一個位置）。
• Chaining = Connect a Chain（連接一個鏈結串列）。
5. 章節總結檢查清單
在繼續學習前，先檢查一下你的理解程度：
• 我能解釋雜湊函數的作用嗎？（它將鍵值轉換為索引）
• 我知道餘數法的公式嗎？（ \( \text{key} \mod \text{size} \) ）
• 我能定義什麼是碰撞嗎？（當兩個鍵值產生相同的索引時）
• 我能描述線性探測與鏈結法嗎？（尋找下一個空位 vs. 使用鏈結串列）
如果一開始覺得有點棘手，別擔心！試著在紙上畫一個有 5 個插槽的小陣列，並用 \( \mod 5 \) 把數字 5、11 和 15 「雜湊」進去。親自畫出碰撞發生的過程，是學習的最佳方法！