第一部分：基礎路由

< 返回目錄 | 下一題：封包排隊 >

---

場景：週一早上九點，流量暴增

東京辦公室的員工同時上線。流量監控顯示：**每秒 120 萬個封包**湧入台北資料中心的路由器。

每個封包都帶著目的地 IP，路由器要查表決定「這個封包往哪送」。你看了一下現有的路由表實作——一個**線性陣列**，查詢是 \(O(n)\)。

路由表大小 \(n = 100,000\) 條規則。

「\(O(n)\) 查詢？120 萬 × 10 萬 = 災難」

你打開計算機：如果每次查詢要掃描 10 萬條規則，每秒 120 萬次查詢... 這台路由器根本撐不住。

你決定：重新設計路由表結構，查詢必須是 \(O(1)\)。

---

第 1 題：路由表設計 - Hash Table 與碰撞處理

這道題將帶你從「為什麼需要 \(O(1)\) 查詢」出發，逐步建立 Hash Table 的完整知識體系。每個小題解決一個具體問題，最後你會發現：這個看似簡單的資料結構，背後有豐富的數學原理。

---

(a) 為什麼需要 Hash Table？

3 分 ・ 大二

你的任務是：給定一個目的地 IP（key），快速找到對應的下一跳路由器（value）。這是典型的 **key-value 查詢**問題。

你需要知道：什麼資料結構能做到「給 key 查 value」是 \(O(1)\)？

題目：

1. 比較以下資料結構的**查詢時間複雜度**：

   資料結構	查詢時間	備註
   未排序陣列	?	線性搜尋
   已排序陣列	?	二分搜尋
   平衡 BST	?	如 AVL Tree
   Hash Table	?	平均情況

2. 說明 Hash Table 如何達到 \(O(1)\) 平均查詢時間

3. 設計一個簡單的 hash function，將 IPv4 地址（32-bit 整數）映射到大小為 \(m\) 的陣列

提示

• 查詢的本質是「從 n 個候選中找到目標」
• 不同資料結構用不同策略縮小搜尋範圍
• Hash Table 的核心想法：直接計算位置，不用搜尋

解答

1. 時間複雜度比較：

資料結構	查詢時間	原因
未排序陣列	\(O(n)\)	最壞要看完全部
已排序陣列	\(O(\log n)\)	每次砍半
平衡 BST	\(O(\log n)\)	樹高 = \(\log n\)
Hash Table	\(O(1)\) 平均	直接定位

2. Hash Table 如何達到 \(O(1)\)？

核心想法：把 key 「算」成一個位置，直接存取。

key → hash(key) → index → 直接存取 array[index]

不需要比較、不需要搜尋。就像圖書館的書架編號：你不用一本本找，直接走到 A-23-7 就拿到書。

3. IPv4 Hash Function：

IPv4 地址是 32-bit 整數（如 192.168.1.1 = 3232235777）。

最簡單的 hash function：除法取餘數

\[h(k) = k \mod m\]

其中 \(m\) 是 hash table 大小。

例如：\(m = 1000\)，\(h(3232235777) = 3232235777 \mod 1000 = 777\)

這個封包的路由規則就存在 table[777]。

這個概念有什麼用？

效能對比：假設路由表有 \(n = 100,000\) 條規則

資料結構	單次查詢	每秒 120 萬次
未排序陣列	100,000 次比較	無法負荷
已排序陣列	17 次比較	2000 萬次比較
Hash Table	1-2 次操作	200 萬次操作

Hash Table 讓路由器從「癱瘓」變成「游刃有餘」。

---

(b) 碰撞問題 - 兩個 IP 映射到同一位置

3 分 ・ 大二

你高興地用 \(h(k) = k \mod m\) 實作了路由表。但測試時發現問題：

h(1000) = 1000 mod 1000 = 0
h(2000) = 2000 mod 1000 = 0  // 撞了！

兩個不同的 IP 映射到同一個位置！這叫做**碰撞（collision）**。

你需要知道：碰撞無法避免，但可以處理。怎麼處理？

題目：

1. 解釋為什麼碰撞**必然發生**（鴿籠原理）

2. 說明 Chaining（鏈結法） 如何處理碰撞

3. 假設 hash table 大小 \(m = 1000\)，存了 \(n = 800\) 個元素（負載因子 \(\alpha = n/m = 0.8\)），使用 Chaining。在 Simple Uniform Hashing Assumption (SUHA) 下，計算：

   • 每條 chain 的平均長度
   • 成功搜尋的平均比較次數
   • 失敗搜尋的平均比較次數

提示

• SUHA：每個 key 等機率落在任一位置
• Chaining：同位置的元素串成 linked list
• 搜尋時要遍歷該位置的整條 chain

解答

1. 為什麼碰撞必然發生？

鴿籠原理（Pigeonhole Principle）：如果 \(n\) 隻鴿子要住進 \(m\) 個籠子，且 \(n > m\)，則至少有一個籠子住超過一隻鴿子。

IPv4 地址空間：\(2^{32} \approx 43\) 億個可能的 key

Hash table 大小：\(m\)（通常遠小於 43 億）

所以**不同的 key 必然會映射到相同位置**。

2. Chaining 處理碰撞：

Index 0: [1000] → [2000] → [3000] → null
Index 1: [1001] → null
Index 2: [empty]
...

每個位置維護一條 linked list，碰撞的元素串在一起。

• 插入：計算 \(h(k)\)，加到該位置的 list 頭部，\(O(1)\)
• 搜尋：計算 \(h(k)\)，遍歷該位置的 list
• 刪除：搜尋 + 刪除 list 節點

3. 複雜度分析：

負載因子 \(\alpha = n/m = 800/1000 = 0.8\)

在 SUHA 下，每個位置期望有 \(\alpha\) 個元素。

• 每條 chain 平均長度：\(\alpha = 0.8\)

• 失敗搜尋：要遍歷整條 chain 才能確認「不存在」 $\(\text{平均比較次數} = \alpha = 0.8\)$

• 成功搜尋：平均遍歷 chain 的一半 $\(\text{平均比較次數} = 1 + \frac{\alpha}{2} = 1 + 0.4 = 1.4\)$

（1 是「找到目標的那次比較」，\(\alpha/2\) 是「之前遍歷的平均長度」）

為什麼是 \(1 + \alpha/2\)？

假設 chain 長度為 \(L\)，目標等機率在位置 \(1, 2, ..., L\)。

平均比較次數 = \(\frac{1 + 2 + ... + L}{L} = \frac{L+1}{2}\)

由於 \(L\) 的期望值是 \(\alpha\)，所以平均比較次數約為 \(\frac{\alpha + 1}{2} \approx 1 + \frac{\alpha}{2}\)（當 \(\alpha\) 不大時）。

數學小結：Chaining 複雜度

操作	平均時間	最壞時間
插入	\(O(1)\)	\(O(1)\)
搜尋（成功）	\(O(1 + \alpha/2)\)	\(O(n)\)
搜尋（失敗）	\(O(1 + \alpha)\)	\(O(n)\)
刪除	\(O(1 + \alpha)\)	\(O(n)\)

關鍵洞察：只要 \(\alpha = O(1)\)（例如 \(\alpha < 1\)），所有操作都是 \(O(1)\)！

---

© Open Addressing - 不用額外空間的碰撞處理

4 分 ・ 大三

Chaining 很直覺，但有個缺點：每個節點需要額外的**指標空間**。在記憶體寸土寸金的路由器上，這很浪費。

你需要知道：有沒有不需要額外空間的碰撞處理方法？

答案是 Open Addressing：碰撞時，在 table 內部找另一個空位。

題目：

1. 說明以下三種 probing 策略的原理：

   • Linear Probing
   • Quadratic Probing
   • Double Hashing

2. 解釋 Primary Clustering 和 Secondary Clustering 現象

3. 分析 Open Addressing 中**刪除操作的困難**，並說明 tombstone（墓碑） 機制

提示

• Probe sequence：碰撞時依序嘗試的位置序列
• Clustering：多個元素「聚集」在一起，降低效能
• 刪除後留下的「洞」會影響後續搜尋

解答

1. 三種 Probing 策略：

設第 \(i\) 次探測的位置為 \(h(k, i)\)：

策略	公式	範例（\(m=10, h(k)=3\)）
Linear Probing	\(h(k,i) = (h(k) + i) \mod m\)	3, 4, 5, 6, 7, ...
Quadratic Probing	\(h(k,i) = (h(k) + c_1 i + c_2 i^2) \mod m\)	3, 4, 7, 12, ...
Double Hashing	\(h(k,i) = (h_1(k) + i \cdot h_2(k)) \mod m\)	取決於 \(h_2(k)\)

Linear Probing：最簡單，碰撞就往後一格。

Quadratic Probing：碰撞後跳的距離越來越大（1, 4, 9, 16...）。

Double Hashing：用第二個 hash function 決定步長，不同 key 有不同步長。

2. Clustering 現象：

Primary Clustering（一次聚集）：Linear Probing 的問題。

[X][X][X][X][ ][ ][ ][ ][ ][ ]
          ↑
          新元素落在這區塊後，會讓區塊更大

一旦形成連續的「已佔用區塊」，新元素落在區塊任一位置都會被推到區塊尾端，讓區塊**越長越快**。

Secondary Clustering（二次聚集）：Quadratic Probing 的問題。

不同 key 若 \(h(k)\) 相同，會走**完全相同的 probe sequence**。比 primary clustering 輕微，但仍有影響。

Double Hashing 解決兩種 clustering：不同 key 即使初始位置相同，步長 \(h_2(k)\) 也不同，所以 probe sequence 不同。

3. 刪除的困難與 Tombstone：

問題：假設 A、B 碰撞，A 先插入位置 5，B 被推到位置 6。

[5: A] [6: B]

如果刪除 A，位置 5 變空：

[5: 空] [6: B]

現在搜尋 B：\(h(B) = 5\)，看到空位，以為「B 不存在」—— 錯誤！

解法：Tombstone（墓碑）

刪除時不是真的清空，而是標記為「已刪除」：

[5: 墓碑] [6: B]

搜尋時：遇到墓碑**繼續找**，遇到空位才停。

插入時：墓碑位置**可以覆蓋使用**。

缺點：太多墓碑會降低效能，需要定期「重建」table。

數學小結：Open Addressing 複雜度

假設 \(\alpha = n/m < 1\)（Open Addressing 要求 \(\alpha < 1\)）

策略	成功搜尋	失敗搜尋
Linear Probing	\(\frac{1}{2}(1 + \frac{1}{1-\alpha})\)	\(\frac{1}{2}(1 + \frac{1}{(1-\alpha)^2})\)
Double Hashing	\(\frac{1}{\alpha} \ln \frac{1}{1-\alpha}\)	\(\frac{1}{1-\alpha}\)

結論：\(\alpha\) 接近 1 時，效能急劇下降。實務上保持 \(\alpha < 0.7\)。

---

(d) 動態擴容 - 當 Table 太滿時

4 分 ・ 大三

你的路由表越來越大，\(\alpha\) 從 0.5 漲到 0.7、0.8、0.9... 查詢越來越慢。

你需要知道：什麼時候該擴容？怎麼擴？成本是多少？

題目：

1. 解釋為什麼 \(\alpha\) 太高會導致效能下降

2. 設計一個 rehashing 策略：

   • 什麼時候觸發擴容？
   • 新 table 大小應該是多少？
   • 如何搬移舊元素？

3. 證明：採用「滿了就 double size」的策略，插入 \(n\) 個元素的總成本是 \(O(n)\)（攤銷分析）

提示

• 擴容需要重新計算所有元素的位置（因為 \(m\) 變了）
• 攤銷分析：把「偶爾的大成本」分攤到「多次的小操作」

解答

1. \(\alpha\) 太高的影響：

以 Open Addressing (Double Hashing) 為例，失敗搜尋期望探測次數：

\[\frac{1}{1-\alpha}\]

\(\alpha\)	期望探測次數
0.5	2
0.7	3.3
0.9	10
0.95	20
0.99	100

\(\alpha\) 越接近 1，效能指數級下降。

2. Rehashing 策略：

def insert(key, value):
    if load_factor() > THRESHOLD:  # 例如 0.75
        resize(2 * m)              # double size

    # 正常插入...

def resize(new_m):
    old_table = table
    table = new_table(new_m)

    for entry in old_table:
        if entry is not empty and not tombstone:
            # 重新 hash 並插入
            new_index = hash(entry.key) % new_m
            insert_at(new_index, entry)

觸發時機：\(\alpha > 0.75\)（Java HashMap 的預設值）

新大小：通常是 \(2m\)（或下一個質數）

搬移方式：必須重新計算每個元素的位置，因為 \(h(k) = k \mod m\)，\(m\) 變了位置就變了。

3. 攤銷分析：

設插入第 \(i\) 個元素的成本為 \(c_i\)：

• 普通插入：\(c_i = 1\)
• 觸發擴容：\(c_i = 1 + (\text{舊 table 大小})\)

採用 double size 策略，擴容發生在 \(n = 1, 2, 4, 8, 16, ...\)

插入 \(n\) 個元素的總成本：

\[\sum_{i=1}^{n} c_i \leq n + \sum_{j=0}^{\log n} 2^j = n + (2^{\log n + 1} - 1) < n + 2n = 3n\]

攤銷成本 = \(O(n) / n = O(1)\)

直覺理解：雖然偶爾要花 \(O(n)\) 搬家，但搬家頻率是指數遞減的（每搬一次，下次搬家要等翻倍的元素進來）。把成本攤到每次插入，平均還是 \(O(1)\)。

業界實務

語言/框架	預設 \(\alpha\) 閾值	擴容倍數
Java HashMap	0.75	2x
Python dict	⅔	2x（新版更複雜）
Go map	6.5（bucket 設計不同）	2x

為什麼是 0.75？

這是 時間 vs 空間的 trade-off： - \(\alpha\) 太小 → 浪費空間 - \(\alpha\) 太大 → 查詢變慢

0.75 是經驗上的甜蜜點。

---

(e) 期望搜尋時間的嚴謹證明

4 分 ・ 碩一

你向主管報告「Hash Table 平均 \(O(1)\)」。主管問：「證明給我看。」

你需要知道：在 SUHA 下，嚴謹證明 Chaining 的期望搜尋時間

題目：

假設 Simple Uniform Hashing Assumption (SUHA)：每個 key 獨立且等機率映射到 \(m\) 個位置中的任一個。

1. 證明**失敗搜尋**的期望比較次數是 \(\Theta(1 + \alpha)\)

2. 證明**成功搜尋**的期望比較次數是 \(\Theta(1 + \alpha)\)

3. 討論 SUHA 在實務中何時**不成立**

提示

• 失敗搜尋：要遍歷整條 chain
• 成功搜尋：目標可能在 chain 的任何位置
• 成功搜尋的分析需要考慮「插入順序」

解答

1. 失敗搜尋：

失敗搜尋必須遍歷整條 chain 才能確認「key 不存在」。

設 \(n_j\) = 第 \(j\) 個位置的 chain 長度。

在 SUHA 下，每個元素等機率落在位置 \(j\)，所以：

\[E[n_j] = \frac{n}{m} = \alpha\]

搜尋時，先計算 \(h(k)\)（\(O(1)\)），再遍歷該位置的 chain（期望長度 \(\alpha\)）。

期望比較次數 = \(\alpha = \Theta(1 + \alpha)\)（當 \(\alpha = O(1)\) 時）

2. 成功搜尋：

這個比較微妙。假設我們搜尋的是「已存在的某個 key \(k\)」。

關鍵觀察：\(k\) 在 chain 中的位置，取決於**插入時有多少元素已經在同一位置**。

假設 \(k\) 是第 \(i\) 個被插入的元素（\(i = 1, 2, ..., n\)）。

插入 \(k\) 時，已有 \(i-1\) 個元素。其中期望有 \(\frac{i-1}{m}\) 個在同一位置。

如果我們採用「插入到 chain 尾端」，搜尋 \(k\) 需要遍歷這些「更早插入的同位置元素」。

期望比較次數（對所有 \(n\) 個元素平均）：

\[\frac{1}{n} \sum_{i=1}^{n} \left(1 + \frac{i-1}{m}\right) = 1 + \frac{1}{nm} \sum_{i=1}^{n}(i-1) = 1 + \frac{1}{nm} \cdot \frac{n(n-1)}{2}\]

\[= 1 + \frac{n-1}{2m} = 1 + \frac{\alpha}{2} - \frac{1}{2m} = \Theta(1 + \alpha)\]

3. SUHA 何時不成立？

SUHA 假設 key 是「均勻隨機」的，但實際上：

• IP 地址不是隨機的：同一網段的 IP 可能有相似的 prefix
• 字串 key 有模式：例如 user_1, user_2, ... 差異很小
• 時間戳有序：連續插入的 key 可能很接近

如果 hash function 設計不好，這些「有模式的 key」會聚集在少數位置，導致嚴重的**不均勻分布**。

解法：使用更強的 hash function（如 Universal Hashing、MurmurHash、xxHash）。

---

進階挑戰：Universal Hashing - 防禦 Hash Collision Attack

3 分 ・ 碩一

有一天，你的路由器突然變得超慢。查看 log 發現：某個攻擊者送來大量封包，它們的目的地 IP 全部 hash 到**同一個位置**！

h(IP_1) = h(IP_2) = h(IP_3) = ... = h(IP_100000) = 42

位置 42 的 chain 長度爆炸，每次查詢都是 \(O(n)\)。這是 Hash Collision Attack（碰撞攻擊）。

攻擊者怎麼做到的？如果他知道你的 hash function \(h(k) = k \mod m\)，他可以預先計算出哪些 IP 會碰撞，然後專門發送這些封包。

你需要知道：如何設計「即使攻擊者知道演算法，也無法預測碰撞」的 hash function？

題目：

1. 定義 Universal Hash Family \(\mathcal{H}\)

2. 證明：從 Universal Hash Family 隨機選取 \(h\)，任兩個不同 key 碰撞的機率 \(\leq 1/m\)

3. 說明 Universal Hashing 如何**在攻擊者面前保持 \(O(1)\) 期望時間**

提示

• 關鍵：hash function 是**隨機選取**的，攻擊者不知道選了哪一個
• 這是「隨機化演算法」的思想：用隨機性對抗最壞情況

解答

1. Universal Hash Family 定義：

一個 hash function 集合 \(\mathcal{H} = \{h : U \to \{0, 1, ..., m-1\}\}\) 是 universal 的，若對任意兩個不同的 key \(k_1 \neq k_2\)：

\[\Pr_{h \sim \mathcal{H}}[h(k_1) = h(k_2)] \leq \frac{1}{m}\]

也就是說：隨機選一個 \(h\)，任兩個 key 碰撞的機率不超過 \(1/m\)。

經典例子（\(U = \{0, 1, ..., p-1\}\)，\(p\) 是質數，\(m < p\)）：

\[h_{a,b}(k) = ((ak + b) \mod p) \mod m\]

其中 \(a \in \{1, ..., p-1\}\), \(b \in \{0, ..., p-1\}\) 隨機選取。

2. 碰撞機率證明：

對於固定的 \(k_1 \neq k_2\)，我們要計算：

\[\Pr_{h \sim \mathcal{H}}[h(k_1) = h(k_2)]\]

由於 \(\mathcal{H}\) 是 universal 的，這個機率 \(\leq 1/m\)（這是定義）。

直覺理解：如果 hash function 是「完美隨機」的，\(h(k_1)\) 和 \(h(k_2)\) 各自獨立均勻分布在 \(\{0, ..., m-1\}\)，碰撞機率恰好是 \(1/m\)。Universal hash family 保證「至少不比完美隨機差」。

3. 對抗攻擊者：

攻擊者知道 \(\mathcal{H}\) 的定義，但**不知道我們選了哪個 \(h\)**（因為 \(a, b\) 是秘密的隨機數）。

攻擊者想製造碰撞，但對於他選的任意兩個 key，碰撞機率只有 \(1/m\)——跟隨機一樣。

期望分析：

假設攻擊者送來 \(n\) 個 key。對於我們搜尋的某個 key \(k\)，期望碰撞數：

\[E[\text{碰撞數}] = \sum_{k' \neq k} \Pr[h(k) = h(k')] \leq (n-1) \cdot \frac{1}{m} = \frac{n-1}{m} < \alpha\]

所以即使面對惡意輸入，期望搜尋時間仍是 \(O(1 + \alpha) = O(1)\)！

這就是隨機化的威力：攻擊者可以選擇輸入，但我們選擇隨機性，攻擊者無法同時優化對抗所有可能的 \(h\)。

---

第 1 題小結：你的路由表工具箱

「每秒百萬封包，查詢不能慢」
    │
    ├─► (a) 為什麼 Hash Table？
    │       → O(1) 平均查詢，直接計算位置
    │
    ├─► (b) 碰撞怎麼辦？→ Chaining
    │       → 同位置串成 linked list
    │       → 期望長度 = α = n/m
    │
    ├─► (c) 不想用額外空間？→ Open Addressing
    │       → Linear / Quadratic / Double Hashing
    │       → 注意 Clustering、Tombstone
    │
    ├─► (d) Table 太滿怎麼辦？→ Rehashing
    │       → α > 0.75 時擴容
    │       → 攤銷成本 O(1)
    │
    ├─► (e) 怎麼證明 O(1)？→ SUHA 分析
    │       → 成功搜尋：1 + α/2
    │       → 失敗搜尋：α
    │
    └─► 進階：攻擊者來了？→ Universal Hashing
            → 隨機選 hash function
            → 碰撞機率 ≤ 1/m，攻擊者無法預測

概念	重點
Hash Function	\(h(k) = k \mod m\)，將 key 映射到位置
碰撞處理	Chaining（額外空間）vs Open Addressing（內部探測）
負載因子	\(\alpha = n/m\)，控制在 0.75 以下
動態擴容	攤銷 \(O(1)\)，double size 策略
Universal Hashing	隨機化防禦碰撞攻擊

---

< 返回目錄 | 下一題：封包排隊 >