Hash tables

進階數據結構：雜湊表 (3.10.3)

你好！歡迎來到計算機科學中最強大的數據結構之一：雜湊表 (Hash Table)。如果你想以近乎即時的速度儲存和檢索數據，這就是你的解決方案！我們將會深入剖析它的運作原理，重點探討讓它如此快速的巧妙數學邏輯，以及當出現問題（即「碰撞」）時該如何處理。

1. 雜湊表的概念及其用途

想像一下你在經營一間巨大的郵局。當信件送達時，你肯定不想翻遍每一條街道（就像「線性搜尋」那樣）。你想要根據郵遞區號（Key，鍵值）立刻知道應該把信件放進哪個信箱（儲存位置）。這正是雜湊表的功能！

雜湊表（有時稱為雜湊映射，Hash Map）是一種旨在實現極速插入、刪除和檢索數據的數據結構。

它透過在鍵 (Key) 與儲存對應值 (Value) 的實體位置（索引，Index）之間建立直接映射來達成此目標。

關鍵術語

• 鍵 (Key)：用於查找數據的唯一識別碼（例如：學生編號、使用者名稱）。
• 值 (Value)：實際儲存的數據（例如：學生的紀錄或個人資料）。
• 鍵值對 (Key-Value Pair)：鍵與其對應的值組合在一起儲存。
• 雜湊表（或陣列）：承載數據的底層結構（通常是陣列或列表）。

雜湊表的典型用途

每當需要極快速的查找時，雜湊表都是不可或缺的：

• 字典：將單詞（鍵）映射到其定義（值）。
• 數據庫索引：利用主鍵在大型數據庫中快速尋找紀錄。
• 編譯器/直譯器：在符號表中管理變數和函式。

2. 雜湊函式 (Hash Function)

雜湊表速度背後的魔法源於雜湊函式。

什麼是雜湊函式？

雜湊函式是一種演算法，它接收紀錄的鍵（可以是數字、字串，甚至是複雜的物件）並計算出一個數值。這個數值代表了該紀錄在雜湊表中應該儲存的位置（索引）。

此計算必須快速且具確定性（即相同的鍵永遠會產生相同的索引）。

應用簡單的雜湊函式（MOD 運算子）

由於鍵可能會非常大（例如 16 位的信用卡號），但雜湊表的大小是有限的（假設只有 100 個槽位），因此雜湊函式必須將鍵縮減為一個有效的索引。

一種非常普遍且簡單的限制輸出技巧是使用 MOD（模除）運算子。

MOD 運算子會返回除法的餘數。如果你的雜湊表大小為 \(N\)，使用 \( \text{Key} \bmod N \) 將永遠返回介於 0 到 \(N - 1\) 之間的索引。

分步範例：
假設我們有一個大小為 10 的雜湊表（索引 0 到 9）。

1. 我們想要儲存與 Key = 453 相關的數據。
2. 我們簡單的雜湊函式為：\( \text{Index} = \text{Key} \bmod 10 \)。
3. 計算：\( 453 \bmod 10 = 3 \)。
4. 數據將儲存於索引 3。

如果我們使用鍵 990，則索引會是 0 (\( 990 \bmod 10 = 0 \))。

優質雜湊函式的特性

雜湊函式不僅僅是簡單的算術；它需要經過精心設計，以確保雜湊表有效運作。

一個優質的雜湊函式應具備兩個關鍵特性：

1. 計算迅速：計算本身必須非常快。如果雜湊過程比線性搜尋還要慢，那麼這個數據結構就毫無意義了！
2. 平均分佈：它必須在表中產生紀錄的平均分佈。這意味著它應該將鍵分散到所有可用的索引中，以最大程度地減少堆疊。

如果你所有的鍵都雜湊到索引 5，那你就徹底違背了使用雜湊表的初衷！

3. 碰撞與碰撞處理 (Collisions and Collision Handling)

即便使用了最完美的雜湊函式，有時兩個不同的鍵產生完全相同的索引也是不可避免的。這稱為碰撞 (Collision)。

什麼是碰撞？

當兩個或多個不同的鍵值被雜湊函式映射到雜湊表中的同一個位置（索引）時，就會發生碰撞。

比喻：你有 10 個儲物櫃卻有 12 個學生。即便你聰明地分配鑰匙，至少會有兩名學生必須共用或尋找替代的儲物櫃。

使用再雜湊（線性探測）處理碰撞

當碰撞發生時，我們不能覆寫現有的數據。我們需要一種方法來找到下一個可用的空間。課程大綱中指定的方法稱為再雜湊 (Rehashing)，具體而言是指線性探測 (Linear Probing)。

再雜湊（線性探測）分步過程：

1. 一個鍵，Key A，被雜湊到索引 H。數據 A 儲存在 H。
2. 一個新的鍵，Key B，進行雜湊。其雜湊值也是 H（發生了碰撞）。
3. 系統檢查索引 H。由於已被數據 A 佔用，系統尋找下一個可用位置。
4. 系統檢查 \(H + 1\)。如果為空，數據 B 就儲存在那裡。
5. 如果 \(H + 1\) 也被佔用，它會檢查 \(H + 2\)，依此類推。（如果到達表尾，則會繞回到索引 0）。

給同學的重要提示：如果你稍後需要搜尋 Key B，電腦會先將 Key B 雜湊到索引 H。它看到那裡是數據 A，便知道數據 B 不是數據 A。接著它必須繼續檢查 \(H + 1\)、\(H + 2\) 等，直到找到目標鍵，或者遇到一個空槽（這告訴它該鍵並不存在）。

4. 雜湊表與陣列的比較

課程要求你理解將雜湊表作為標準陣列的替代方案時的優缺點。

陣列（列表）複習

陣列是靜態數據結構（大小固定，儘管存在動態列表/陣列）。按索引存取項目是即時的 (O(1))。搜尋特定的「值」通常涉及線性搜尋 (O(n))，除非陣列已排序，允許進行二分搜尋 (O(log n))。

雜湊表 vs. 陣列

特點	雜湊表的優點	雜湊表的缺點
查找速度（效率）	平均時間極快（接近常數時間，O(1)），因為位置是直接計算出來的。	在最壞情況下（大量碰撞），查找時間會顯著惡化，有時會變得與 O(n) 一樣慢。
儲存效率	與陣列本身的儲存無關。	如果表中的數據稀疏（存在大量空槽），可能會浪費記憶體空間。
插入/刪除	非常快，因為位置是直接計算的（平均時間 O(1)）。	處理碰撞增加了程式碼的複雜性。
排序	不適用	儲存在雜湊表中的數據通常是無序的；以順序排列的方式檢索數據非常困難甚至不可能。陣列則根據索引維持固有的順序。