線性結構與雜湊：依操作需求選容器
本頁為依教材與考古題整理的原創摘要；考古題答案經技術覆核，但不是官方答案。
第一次接觸也沒關係
這堂先懂這些詞
先記住白話意思，不必急著背英文。看到正文時，再把正式名稱接回來。
大 O 複雜度
也會看到：Big O、time complexity、O(n)、時間複雜度描述輸入變大時，演算法所需時間或空間的成長速度。
- 生活例子：
- 排 10 人與排 1 萬人時，工作量增加多快比小規模快幾秒更重要。
- 別搞混：
- Big O 不是精確秒數，也不能忽略資料規模與常數成本。
雜湊碰撞
也會看到：hash collision、collision、雜湊衝突不同輸入經雜湊後落到同一位置，需要額外規則分開保存。
- 生活例子：
- 兩位同姓客人被分到同一取餐代號，櫃台還要用其他資訊辨認。
- 別搞混：
- 碰撞是有限位置下的正常可能，不等於雜湊函式壞掉或被攻擊。
Stack、Queue 與 Linked List
也會看到：stack、queue、linked list、LIFO、FIFOStack 後進先出，queue 先進先出，linked list 則用節點連結保存順序。
- 生活例子：
- 疊盤子像 stack，排隊買票像 queue，尋寶線索逐張指向下一張像 linked list。
- 別搞混：
- 資料結構的選擇要看操作需求；linked list 也不是所有插入都一定 O(1)。
負載因子
也會看到：load factor、bucket、chaining、open addressing雜湊表中資料筆數相對於儲存槽數量的比例，會影響碰撞與操作成本。
- 生活例子：
- 像停車場越接近停滿，找到空位通常越困難。
- 別搞混：
- 平均 O(1) 需要合理雜湊與負載控制，不是任何情況的最壞保證。
以 stack、queue、array、linked list 與 hash table 的操作契約為核心，從存取順序、更新成本、碰撞處理與 load factor 判斷資料結構；不把平均 O(1) 誤寫成最壞保證。
先抓住這幾件事
- 依 LIFO、FIFO、索引存取與中間插刪需求選擇線性結構
- 用 stack trace 判斷巢狀括號是否合法
- 說明 hash function、bucket、collision 與 load factor 的關係
- 比較 chaining 與 open addressing，並區分平均與最壞複雜度
先想像這個場景
園遊會寄物與取餐系統
園遊會同時要處理寄物、取餐叫號、姓名查找與巢狀置物箱。若所有需求都硬塞進同一種容器，尖峰時段就會順序錯亂或找不到物品。
先別急著往下看，花十秒想一想：
最新放入的置物盒必須先取出，但餐點必須依到單順序交付；兩處該用同一結構嗎？姓名查找又該沿用哪一個？
把故事換成電腦語言
| 生活中的角色 | 對應到 | 技術概念 |
|---|---|---|
| 最後放上推車的箱子最先拿下 | Stack 與 LIFO | |
| 取餐單依到達順序叫號 | Queue 與 FIFO | |
| 依姓名算出寄物櫃區號 | Hash function 與 bucket | |
| 兩個姓名算到同一櫃區後改掛清單或找下一格 | Chaining 與 open addressing | |
| 櫃位越接近滿載，找空位越容易繞路 | Load factor、collision 與 rehash |
題目出現這些字，先想到
- 看到 balanced parentheses：找 LIFO、push 左括號、右括號配 top。
- 看到 first-come-first-served：優先考慮 queue；最近加入先處理則是 stack。
- 看到 associative array 或 key-to-value：辨識 hash function 與 bucket。
- 看到 average O(1)：同時檢查 collision、load factor 與最壞退化，別寫成絕對保證。
1.先看操作契約，不看名稱猜答案
Array 支援 O(1) 索引定位，但中間插刪常需搬移元素；linked list 已知節點位置時能以指標改接完成插刪，但搜尋與第 k 個元素通常要走訪。Stack 只在同一端 push/pop，遵守 LIFO；queue 從尾端 enqueue、前端 dequeue，遵守 FIFO。題目應先辨識需要保留的順序與主要操作。
- LIFO 對應最近加入者先取出
- FIFO 對應最早加入者先服務
- ADT 描述行為，不限定唯一底層實作
- 複雜度要說明是否已知位置與採用何種實作
2.Stack 讓最近尚未配對的符號先被檢查
掃描括號時，左括號 push；右括號必須和 stack top 的左括號種類相符後 pop。若右括號到來時 stack 已空、種類不符，或掃描結束後 stack 非空，都代表不平衡。這正利用巢狀結構的最後開啟、最先關閉。
- 不能只比較左右括號總數
- 中途 pop 空 stack 立即失敗
- 不同括號種類也要配對
- 掃描完成仍有元素表示尚未關閉
3.Hash table 用函數把 key 導向 bucket
Hash function 把 key 映射到有限 bucket；不同 key 可能碰撞。好的分布可讓搜尋、插入、刪除平均接近 O(1)，但碰撞集中或惡意輸入時可能退化。Load factor α=n/m 描述 n 個項目相對於 m 個 bucket 的壓力，通常越高碰撞越頻繁。
- Hash table 實作 associative array 的 key-to-value mapping
- O(1) 是合理假設下的平均成本
- Rehash 會擴大表並重新映射既有 key
- Hash function 必須對相同 key 穩定產生相同位置
4.碰撞策略決定後續搜尋路徑
Chaining 在每個 bucket 掛一個串列或其他容器，碰撞項目留在同一 bucket；open addressing 則把所有項目留在表內，依 probing sequence 找空格。Linear probing 容易 primary clustering；double hashing 用第二個 hash 決定步長，步長需能走遍整張表。
- Chaining 可容許項目數超過 bucket 數
- Open addressing 的刪除常需要 tombstone
- Double hashing 仍不能消除所有碰撞
- 表大小與 probe step 互質有助覆蓋全部 slots
一起拆題目
範例 1：判斷字串 `([a+b]*c)` 是否括號平衡。
- 讀到 `(` push
- 讀到 `[` push
- 讀到 `]` 與 top `[` 配對後 pop
- 讀到 `)` 與 top `(` 配對後 pop
- 掃描結束 stack 為空
所以答案是：括號平衡；配對次序符合 LIFO。
範例 2：8 個 buckets 已存 6 個 keys，求 load factor；若大量 key 落在同一 bucket，能否仍保證 O(1)？
- α=n/m=6/8=0.75
- 平均效能仍取決於 hash 分布與碰撞策略
- 若全落同一 bucket，搜尋可能需檢查多個項目
所以答案是：Load factor 為 0.75；不能由此保證最壞 O(1)，極端碰撞可退化到 O(n)。
這裡最容易選錯
- 把 queue 誤當成 LIFO
- 只數括號數量、不檢查巢狀順序
- 把 hash table 的平均 O(1) 寫成無條件最壞 O(1)
- 認為 collision 表示 hash function 失效
- open addressing 刪除後直接清空 slot，破壞 probe chain
換你快速判斷
先在心中作答，再展開答案。答不出來時，回頭找本課的對照關係。
1為什麼 balanced parentheses 適合用 stack？
巢狀括號遵守最後開啟、最先關閉；stack 的 LIFO 讓每個右括號先和最近尚未配對的左括號比較。
遇左括號 push，遇右括號檢查 top 後 pop；中途 stack 空、種類不符或結束後非空都表示不平衡。
2選 stack、queue、array 或 linked list 時，第一個問題是什麼？
先問需要保留什麼存取順序，以及主要操作是索引、頭尾操作、搜尋或中間插刪。
ADT 描述行為；array/linked structure 是實作選擇。沒有脫離操作前提、永遠最快的結構。
3Hash table 的搜尋為何只能說平均 O(1)，不能說最壞 O(1)？
平均 O(1) 依賴 hash 分布、容量與碰撞控制；大量 keys 碰撞時，搜尋可能要檢查 O(n) 個項目。
Hash function 將 key 映射到 bucket，但有限 buckets 必然可能 collision。
4Chaining 與 open addressing 如何處理 collision？
Chaining 把同 bucket 的項目放入附屬容器；open addressing 依 probing sequence 在表內找其他 slot。
Linear probing 可能 primary clustering；double hashing 用第二個 hash 決定步長。
最後用考古題驗證
本課連結的題目都已通過可重現的技術覆核，可逐題練習與判分。
開始本課考古題練習參考來源
- Introduction to Algorithms (6.006) — Erik Demaine and Srini Devadas