該如何學好「寫程式」#2：為什麼 programmer 該學資料結構？

問題與答案 (FAQ)

Q&A 類別 A: 概念理解類

A-Q1: 什麼是資料結構？

• A簡: 資料結構是組織與存取資料的方式，決定操作效率，如搜尋、插入、排序等。
• A詳: 資料結構是為了高效地儲存、組織與存取資料而設計的抽象與具體資料組織方式，如陣列、連結串列、堆疊、佇列、樹、雜湊表與排序容器。不同結構對操作（搜尋、插入、刪除、排序）提供不同的時間複雜度與記憶體成本。選擇合適資料結構是將語言與函式庫工具轉化為高品質程式的關鍵。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: A-Q3, A-Q8, B-Q2

A-Q2: 為什麼 programmer 該學資料結構？

• A簡: 因為選對資料結構，性能可數十到數千倍差異，決定程式可擴展性與穩定性。
• A詳: 學會資料結構讓你能根據需求與資料規模挑選正確容器與演算法，避免線性掃描等低效操作。文中示例顯示：搜尋百萬筆資料，List 的 O(n) 與 SortedList 的 O(log n) 差異約 80 倍；放大到一億筆時更近 6000 倍。這種級距的效能差，任何局部微調都補不回來，關鍵在於資料結構與演算法的正確選擇。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: A-Q4, A-Q8, B-Q6

A-Q3: 什麼是時間複雜度（Big-O）？

• A簡: Big-O 描述演算法耗時隨資料量成長的階趨，如 O(1)、O(log n)、O(n)。
• A詳: 時間複雜度以漸進上界描述當輸入規模 n 變大時的執行時間趨勢。常見有 O(1) 常數時間、O(log n) 對數時間（二分搜尋）、O(n) 線性時間（全掃描）、O(n log n)（排序）與 O(n^2)（巢狀迴圈）。它是比較不同資料結構與演算法可擴展性的共同語言，能預估從百萬提升到億級的性能變化。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: A-Q4, B-Q6, B-Q7

A-Q4: O(1)、O(n)、O(log n) 有何差異？

• A簡: O(1)與資料量無關；O(n)隨資料線性變慢；O(log n)成長慢，擴展性最佳。
• A詳: O(1) 意味操作時間幾乎固定（如雜湊表查找）；O(n) 表示需掃描全部或大部分元素（如 List.Find）；O(log n) 對數級增長（如二分搜尋）。當資料量從 10^6 到 10^8，O(n) 慢 100 倍，O(log n) 只增加常數倍，差異可達數千倍。設計時應優先追求 O(1) 或 O(log n) 的關鍵路徑。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: B-Q1, B-Q2, B-Q3

A-Q5: 為什麼工具不是主角，觀念才是？

• A簡: 語言與函式庫是工具；效能與正確性取決於如何選擇與運用資料結構。
• A詳: 會用語言與 API 並不等於會寫高品質程式。相同 C#/.NET，若以 List 做線性搜尋，與選擇 SortedList/Dictionary 的結構化索引，性能可天壤之別。關鍵在理解資料結構、時間複雜度與需求型態（精確查詢、排序、範圍查詢），而非堆砌「先進」語法糖。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: A-Q8, B-Q7, B-Q10

A-Q6: 什麼是線性搜尋與二分搜尋？

• A簡: 線性搜尋逐一比對；二分搜尋在排序集合中對半縮小範圍。
• A詳: 線性搜尋從頭掃到尾，平均需比較 n/2 次，屬 O(n)。二分搜尋要求資料已排序，每步將搜尋區間減半，用比較器確認方向，最多約 log2(n) 次，屬 O(log n)。在需頻繁查找時，預先排序換得二分搜尋常大幅提升效率，尤其資料規模巨大時差異更明顯。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: B-Q1, B-Q3, B-Q5

A-Q7: 什麼是雜湊表（Hash Table）？

• A簡: 以雜湊函數將鍵映射到桶位，平均可 O(1) 存取的結構。
• A詳: 雜湊表利用 hash 函數將 key 映射為索引，透過開放位址或鍊結處理碰撞，達到近似常數時間的查找與插入。C# 的 Dictionary<TKey,TValue> 即為雜湊表實作，適合精確鍵查找，但不保序，亦不支援範圍或前綴查詢。選用場景與限制需搭配需求評估。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: B-Q2, A-Q11, B-Q10

A-Q8: List、Dictionary、SortedList 有何差異？

• A簡: List 適合順序存放與掃描；Dictionary 精確查找快；SortedList 有序且查找快。
• A詳: List 提供動態陣列，新增均攤 O(1)，Find 為 O(n)。Dictionary<TKey,TValue> 基於雜湊，新增與存取近 O(1)，但無排序與範圍查詢。SortedList<TKey,TValue> 維持鍵有序，查找 O(log n)，插入 O(n)（需位移）。依需求在掃描、精確查找、排序/範圍查找間權衡。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: B-Q1, B-Q2, B-Q3

A-Q9: SortedList 與 SortedDictionary 差異？

• A簡: SortedList 以陣列儲存有序鍵，插入 O(n)；SortedDictionary 為平衡樹，插入 O(log n)。
• A詳: SortedList<TKey,TValue> 內部為兩條平行陣列（鍵/值），查找以二分搜尋 O(log n)，插入需搬移元素 O(n)，記憶體較省。SortedDictionary<TKey,TValue> 為紅黑樹，查找/插入/刪除皆 O(log n)，適合大量動態插入，記憶體略多。兩者皆保序，可用於範圍與排序需求。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: B-Q3, B-Q9, B-Q10

A-Q10: 什麼是索引（Index）？與資料庫的關係？

• A簡: 索引是為特定欄位建立加速結構，讓查找與排序更快，類似資料庫 B-Tree/Hash 索引。
• A詳: 在記憶體中，為姓名、電話等欄位建立索引，可用 Dictionary 做精確查找，用 SortedList/SortedDictionary 做排序與範圍查詢。概念對應到資料庫的索引：Hash 索引加速精確鍵；B-Tree 類結構加速排序與範圍。多索引可並存，但要維護一致性與記憶體成本。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: B-Q4, B-Q5, D-Q10

A-Q11: 為何 Dictionary 不適合排序與前綴查詢？

• A簡: Dictionary 不保序且僅支援精確鍵，無法直接進行排序與前綴範圍切片。
• A詳: Dictionary 基於雜湊並將元素分散到桶位，不提供有序遍歷，因此無法以「大於等於/小於」等比較運算找連續範圍，更無法對字首前綴進行下/上界界定。需要排序或前綴時，應改用維持順序的結構（SortedList、SortedDictionary）並搭配二分搜尋求邊界。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: B-Q2, B-Q5, D-Q2

A-Q12: 為什麼前綴查詢要用「排序＋二分界點」？

• A簡: 先排序，利用二分搜尋找到前綴起迄位置，取得連續範圍切片。
• A詳: 對字串前綴如「0928-1234*」，可在有序鍵集合上用比較器尋找下界（>= “0928-1234”）與上界（< “0928-1235”）索引，再於此區間遍歷。此法時間為 O(log n + k)，k 為結果數，對大量資料比全掃描 O(n) 高效許多，亦便於分頁。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: B-Q5, C-Q5, D-Q5

A-Q13: 為什麼要看 MSDN 的時間複雜度註記？

• A簡: 官方文件標示各操作的 Big-O，可用以預估擴展性並正確選型。
• A詳: .NET 集合類別文件包含 Add、Find、索引器等操作的時間複雜度說明。閱讀這些註記可預判資料成長 100 倍時的表現，避免事後重構。文中以此比較 List.Find 的 O(n) 與 SortedList 查找 O(log n)，做出符合需求的選擇並解釋性能差異來源。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: B-Q7, B-Q6, A-Q4

A-Q14: 當資料從百萬變億，為何演算法勝過微調？

• A簡: Big-O 決定成長趨勢；O(n) 變慢百倍，O(log n) 只增少量，差距被放大。
• A詳: 微調如減少建立物件、小幅最佳化迴圈，只能帶來常數倍改善；但演算法選擇影響複雜度階別。百萬到億級，O(n) 放大 100 倍，O(log n) 僅增加約數十%。因此用對資料結構與演算法（如排序＋二分）遠比事後微調更具決定性。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: B-Q6, D-Q1, D-Q3

A-Q15: Bubble Sort 與 Quick Sort 差在哪？

• A簡: 泡沫排序 O(n^2) 慢；快速排序平均 O(n log n) 快，適合大多數排序任務。
• A詳: 泡沫排序透過相鄰交換，需多次掃描，對大資料極慢。快速排序以分治選樞紐分割，平均 O(n log n)，最壞 O(n^2)。實務常用庫內建排序（通常為 O(n log n)），對需排序後再二分搜尋的情境，選擇高效排序法是基礎。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: A-Q6, B-Q3, C-Q4

A-Q16: 什麼是程式「基本功與邏輯觀念」？

• A簡: 能把想法轉成正確程式，掌握迴圈、條件、資料結構與演算法。
• A詳: 基本功包含：清楚的問題拆解、正確運用控制流程、選用合適資料結構、理解複雜度、能以程式驗證與量測。邏輯觀念不好常見於不當迴圈、重複計算、錯誤結構選型，導致效能瓶頸與錯誤。此為稱職 programmer 的內功。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: D-Q1, B-Q7, C-Q6

A-Q17: 為何多索引能同時滿足不同查詢？

• A簡: 針對不同欄位建立相應結構，如姓名精確、電話前綴，各用最適索引。
• A詳: 單一容器難同時兼顧精確查找與範圍查詢。以通訊錄為例：建立 Dictionary 作姓名精確匹配，建立 SortedList 作電話前綴與排序輸出。兩索引指向同一資料本體，查詢時走相應路徑，兼顧速度與功能，代價是維護一致性與額外記憶體。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: B-Q4, D-Q10, C-Q4

A-Q18: 為何 SortedList 插入較慢？

• A簡: 內部為有序陣列，插入需搬移元素，故平均 O(n)。
• A詳: SortedList<TKey,TValue> 維持鍵陣列有序。插入時先二分找到位置 O(log n)，再將該位置之後的元素整體右移以空出位置，導致 O(n) 位移成本。若載入期大量新增，總成本高；但查找期的 O(log n) 高性能彌補讀多寫少的場景。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: B-Q3, B-Q9, D-Q3

A-Q19: 何時用 List 仍然合理？

• A簡: 當以追加與順序遍歷為主、少隨機查找時，List 輕量且快。
• A詳: List 動態陣列追加均攤 O(1)，序列化輸出、批次處理、少數次搜尋或小規模資料，使用 List 簡潔高效。當需求轉向頻繁查找、排序、前綴或範圍查詢時，才應考慮替換或補建索引以平衡功能與成本。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: B-Q1, A-Q8, D-Q1

A-Q20: 為何本文示例最終選 SortedList？

• A簡: 因需求含排序與前綴查詢，查找期望快，讀多寫少，SortedList最貼合。
• A詳: 需求包括：姓名/電話排序輸出、精確姓名查找、電話前綴過濾、規模可擴展。Dictionary 雖精確快但不保序；List 查找 O(n) 不可擴展。SortedList 查找 O(log n)，天然有序，配合自寫二分邊界即可前綴查詢，符合讀多寫少的通訊錄情境。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: B-Q3, B-Q5, C-Q4

Q&A 類別 B: 技術原理類

B-Q1: List.Find 如何運作？為何是 O(n)？

• A簡: 以委派逐一比對元素，最壞需掃描全表，線性時間。
• A詳: 原理: List.Find 會從索引 0 起逐個元素呼叫 Predicate，直到找到或掃完。流程: 1) 迭代器遍歷；2) 呼叫條件；3) 命中即回傳。組件: List、Predicate、enumerator。由於每次查找都需枚舉，時間與元素數量線性成長。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: A-Q6, A-Q8, D-Q1

B-Q2: Dictionary<TKey,TValue> 為何能近 O(1) 存取？

• A簡: 透過雜湊函數將鍵映射到桶位，平均常數時間存取，碰撞時處理鏈結。
• A詳: 原理: 使用 GetHashCode 將 key 轉為雜湊碼定位桶。流程: 1) 計算 hash；2) 定位桶；3) 比對相等（Equals）；4) 插入或回傳值。組件: 雜湊函數、桶陣列、碰撞解法。擴容時重雜湊 O(n)。平均查找/設定接近 O(1)，但不保序，不支援範圍與前綴。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: A-Q7, A-Q11, D-Q2

B-Q3: SortedList<TKey,TValue> 如何維持排序與查找？

• A簡: 以有序鍵陣列保存，查找二分 O(log n)，插入需搬移元素 O(n)。
• A詳: 原理: 兩條平行陣列存鍵值並保持有序。流程: 1) 以 Comparer 二分定位鍵；2) 查找直接回傳位置；3) 插入時搬移尾段元素空出位置；4) 可用索引區間遍歷。組件: Keys、Values、Comparer。適用讀多寫少、需排序/範圍查詢場景。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: A-Q9, B-Q5, D-Q3

B-Q4: 如何用雙索引同時支援姓名與電話查詢？

• A簡: 建立兩個索引，各自依欄位鍵入，查詢走相對應索引。
• A詳: 原理: 資料本體與多個視角（索引）分離。流程: 1) 定義 ContactData；2) 建 SortedList<string, ContactData> 依 Name；3) 建 SortedList 依 Phone；4) 查詢選對索引；5) 同步更新兩索引。組件: 兩個 SortedList、Comparer、資料本體參考。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: A-Q10, C-Q4, D-Q10

B-Q5: 前綴查詢如何以二分搜尋求邊界？

• A簡: 以前綴作下界與下一前綴作上界，二分找到起訖索引後切片遍歷。
• A詳: 原理: 使用排序鍵的字典序。流程: 1) 下界 key = “0928-1234”；2) 上界 key = “0928-1235”；3) 二分求 lower_bound 與 lower_bound(上界)；4) 區間 [l, r) 逐一取值。組件: SortedList.Keys、Comparer、BinarySearch 輔助函式。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: A-Q12, C-Q5, D-Q5

B-Q6: 如何以 Big-O 推估從百萬到億的效能？

• A簡: 用複雜度乘上規模比或對數比，估算延遲成長與倍數差異。
• A詳: 原理: 將已量測的時間作為基準，以複雜度外推。流程: 1) 取得 N=10^6 測得 t；2) O(n) 估 t100；3) O(log n) 估 t(log 10^8/log 10^6)；4) 比較倍數。組件: Stopwatch 測量、Big-O 概念、對數計算。可輔助產品規劃與風險預判。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: A-Q3, A-Q4, C-Q6

B-Q7: 如何閱讀 MSDN 集合文件做技術選型？

• A簡: 聚焦操作複雜度、排序特性、擴容行為，對齊需求型態選擇。
• A詳: 原理: 以需求導向對照能力。流程: 1) 鎖定關鍵操作（查找、插入、遍歷）；2) 查文件的時間複雜度；3) 檢視排序與唯一性；4) 檢查擴容與記憶體成本；5) 以使用情境（讀多寫少）決策。組件: MSDN、複雜度表、需求清單。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: A-Q13, A-Q20, D-Q3

B-Q8: 為何加 Dictionary 索引提升查找卻增加建置時間與記憶體？

• A簡: 多維護一份鍵到物件映射，需額外雜湊與桶陣列，成本上升。
• A詳: 原理: 建索引需為每筆資料計算雜湊並存入桶，擴容時重雜湊。流程: 1) 插入本體；2) 插入索引計算 hash；3) 桶位設定或鏈結；4) 可能觸發擴容。組件: 主集合、Dictionary、桶陣列。好處是精確查找近 O(1)，代價是初始化時間與記憶體上升。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: A-Q8, D-Q7, C-Q3

B-Q9: SortedList 插入為何 O(n)？內部搬移如何進行？

• A簡: 插入點後方元素需整段右移，造成線性位移成本。
• A詳: 原理: 以陣列保存有序鍵，插入需空出插入位。流程: 1) 二分定位索引；2) 檢查容量與擴容；3) Array.Copy 搬移尾段；4) 寫入鍵與值。組件: Keys/Values 陣列、Comparer、Array.Copy。對寫密集工作負載不利，但查找高效。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: A-Q18, D-Q3, C-Q7

B-Q10: SortedDictionary 的機制與適用情境？

• A簡: 以紅黑樹保序，查找與插入皆 O(log n)，適合頻繁插入與刪除。
• A詳: 原理: 平衡二元搜尋樹保證高度 O(log n)。流程: 1) 依 Comparer 走樹；2) 插入與刪除重平衡；3) 中序遍歷保序輸出。組件: 紅黑樹節點、Comparer、迭代器。適用持續插入/刪除、亦需排序或範圍查詢的場景，內存略高於 SortedList。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: A-Q9, D-Q3, C-Q4

B-Q11: Comparer 如何影響排序與查找正確性？

• A簡: 比較器定義鍵順序與等價，影響二分搜尋與字首邊界。
• A詳: 原理: 排序與查找皆依 Comparer.Compare 的結果決策方向與一致性。流程: 1) 選用適當 StringComparer（Ordinal/InvariantCulture）；2) 確保 Compare 與 Equals 一致；3) 前綴邊界用同一比較規則。組件: IComparer、StringComparer、BinarySearch。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: D-Q8, C-Q8, C-Q5

B-Q12: 在 SortedList 上實作二分搜尋應注意什麼？

• A簡: 邊界條件、比較方向、遞迴/迭代實作與空集合處理。
• A詳: 原理: 透過 mid 比較決定左右區間。流程: 1) start/end 初值；2) mid=(s+e)/2；3) 比較器決定縮小範圍；4) 終止條件與回傳策略（lower/upper bound）；5) 空與越界檢查。組件: Comparer、Keys、邏輯嚴謹的邊界處理。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: A-Q12, C-Q9, D-Q5

B-Q13: 如何設計資料本體與索引分離的架構？

• A簡: 本體存資料，索引存鍵到本體的參考，查詢不複製本體。
• A詳: 原理: 去重複與一致性。流程: 1) 定義 ContactData 本體集合；2) 各欄位建立索引容器；3) 插入/更新同時更新所有索引；4) 查詢回傳本體引用；5) 刪除同步移除。組件: 本體集合、索引容器、更新協定。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: A-Q10, D-Q10, C-Q4

B-Q14: 如何正確量測效能與記憶體？

• A簡: 用 Stopwatch 記 ticks/msec，暖機 JIT，多次取平均，觀察 WorkingSet。
• A詳: 原理: 測量需穩定與可重現。流程: 1) 預熱執行一次；2) 用 Stopwatch.Start/Stop；3) 重複 N 次取平均；4) 觀察 Environment.WorkingSet 近似常駐集；5) 記錄輸入規模。組件: Stopwatch、GC 控制（必要時）、統計方法。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: C-Q6, D-Q4, B-Q6

Q&A 類別 C: 實作應用類（10題）

C-Q1: 如何定義 ContactData 類別？

• A簡: 建立含 Name、Email、Phone 欄位與輸出方法的簡單類別。
• A詳: 步驟: 1) 宣告 class ContactData；2) 欄位 Name/EmailAddress/PhoneNumber；3) OutputData 輸出屬性。程式碼: public class ContactData { public string Name; public string EmailAddress; public string PhoneNumber; public void OutputData(TextWriter w){…} } 注意: 欄位可改屬性，必要時加驗證。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: A-Q1, C-Q4, B-Q13

C-Q2: 如何用 List 產生百萬測試資料並線性搜尋？

• A簡: 建 List 迴圈加入，再以 Find/FindAll 線性比對。
• A詳: 步驟: 1) var contacts=new List(1_000_000); 2) 迴圈生成測試資料；3) contacts.Find(x=>x.Name=="A123456"); 4) contacts.FindAll(x=>x.PhoneNumber.StartsWith("0928-1234")); 注意: 線性搜尋 O(n)；大量資料時延遲高。最佳實踐: 預設容量減少擴容。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: B-Q1, D-Q1, C-Q6

C-Q3: 如何用 Dictionary 建姓名索引進行精確查詢？

• A簡: 以姓名作鍵，將物件加入 Dictionary，查找時 O(1) 取值。
• A詳: 步驟: 1) var nameIdx=new Dictionary<string,ContactData>(1_000_000); 2) 生成資料時 nameIdx.Add(cd.Name,cd); 3) var data=nameIdx[“A123456”]; 程式碼片段: nameIdx.TryGetValue(key,out var v); 注意: 增加記憶體；鍵須唯一，重複需改為 Dictionary<string,List>。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: B-Q2, D-Q4, D-Q6

C-Q4: 如何用 SortedList 為姓名與電話建立雙索引？

• A簡: 各建一個 SortedList，鍵為姓名與電話，值為本體引用。
• A詳: 步驟: 1) var nameIdx=new SortedList<string,ContactData>(1_000_000,StringComparer.Ordinal); 2) var phoneIdx=new SortedList<string,ContactData>(1_000_000,StringComparer.Ordinal); 3) 載入時同時 Add；4) 查找 nameIdx[“A123456”]; 注意: 插入 O(n)；讀多寫少適用；Comparer 建議用 Ordinal。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: B-Q3, B-Q4, C-Q5

C-Q5: 如何在 SortedList 上實作電話前綴查詢？

• A簡: 用二分搜尋找 “0928-1234” 與 “0928-1235” 的下界索引，遍歷該區間。
• A詳: 步驟: 1) 定 lower=”0928-1234”; upper=”0928-1235”; 2) int l=LowerBound(phoneIdx,lower); 3) int r=LowerBound(phoneIdx,upper); 4) for(i=l;i<r;i++) yield phoneIdx.Values[i]; 程式碼: 利用 Comparer.Compare 與 Keys 陣列。注意: 邊界與空集合處理，Comparer 一致性。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: B-Q5, B-Q12, D-Q5

C-Q6: 如何量測建置、搜尋時間與記憶體？

• A簡: 使用 Stopwatch 記錄 msec/ticks，並讀取 Environment.WorkingSet。
• A詳: 步驟: 1) var sw=new Stopwatch(); sw.Start(); 載入資料；sw.Stop(); 2) 重置後測量查找；3) Console.WriteLine(sw.ElapsedTicks,sw.ElapsedMilliseconds); 4) Console.WriteLine(Environment.WorkingSet/1_000_000+”MB”); 注意: 先暖機，重複多次平均；避免 I/O 影響測量。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: B-Q14, D-Q4, B-Q6

C-Q7: 如何預先配置容量減少擴容成本？

• A簡: 使用帶容量建構子，減少重配置與拷貝，縮短初始化時間。
• A詳: 步驟: 1) new List(1_000_000); 2) new Dictionary<string,ContactData>(1_000_000); 3) new SortedList<string,ContactData>(1_000_000); 注意: 容量預估過小會多次擴容，過大浪費記憶體。SortedList.Capacity 可調整，但插入仍 O(n)。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: B-Q9, D-Q3, C-Q2

C-Q8: 如何自訂字串比較器確保排序一致？

• A簡: 使用 StringComparer.Ordinal 或自訂 IComparer，避免文化差異影響順序。
• A詳: 步驟: 1) 建索引時傳入 StringComparer.Ordinal；2) 或實作 IComparer 比較；3) 前綴邊界產生與 Comparer 一致。程式碼: new SortedList<string,ContactData>(..., StringComparer.Ordinal); 注意: 等價與排序一致性，避免排序/查找不一致錯誤。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: B-Q11, D-Q8, C-Q5

C-Q9: 如何實作 BinarySearch 輔助方法？

• A簡: 以 Comparer 比較 Keys，遞迴或迭代尋找 lower/upper bound。
• A詳: 步驟: 1) 寫 int LowerBound(SortedList<K,V> idx,K key); 2) while(l<r){ mid=(l+r)/2; if(cmp(key,keys[mid])<=0) r=mid; else l=mid+1; } 3) 依需求返回。注意: 處理空集合、全小於或全大於情況，避免越界。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: B-Q12, A-Q12, D-Q5

C-Q10: 如何以小實驗推估 10^6 與 10^8 的效能？

• A簡: 量測基準 n=10^6，再用 O(n)、O(log n) 外推估算億級延遲。
• A詳: 步驟: 1) 實測 List.Find 與 SortedList 查找時間；2) 計算 List：t100；3) 計算 SortedList：t(log 10^8/log 10^6)；4) 輸出比較報表。注意: 外推僅估趨勢；實務會受快取/記憶體限制影響，但仍可做規劃參考。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: B-Q6, C-Q6, A-Q14

Q&A 類別 D: 問題解決類（10題）

D-Q1: 用 List 搜尋很慢怎麼辦？

• A簡: 線性搜尋 O(n) 導致瓶頸；改用索引：Dictionary 精確、SortedList 範圍/排序。
• A詳: 症狀: 百萬筆查找需數十至數百毫秒。原因: List.Find 線性掃描。解決: 1) 精確鍵用 Dictionary；2) 需排序/前綴用 SortedList/SortedDictionary＋二分；3) 預先配置容量。預防: 設計時以需求選型，避免以 List 橫用所有情境。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: A-Q8, B-Q1, C-Q4

D-Q2: Dictionary 無法做排序或前綴查詢怎麼辦？

• A簡: 加入有序索引（SortedList/SortedDictionary），以二分取得範圍。
• A詳: 症狀: 需按姓名/電話排序與前綴過濾。原因: Dictionary 不保序、無範圍操作。解決: 1) 建立有序索引；2) 用二分找下/上界；3) 範圍遍歷。預防: 需求含排序/範圍時，初始架構即納入有序索引。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: A-Q11, B-Q5, C-Q5

D-Q3: 載入百萬筆 SortedList 太慢怎麼辦？

• A簡: 插入 O(n) 成本高；可改批次建陣列後排序，或用 SortedDictionary。
• A詳: 症狀: 初始化時間長。原因: 每筆插入需搬移元素。解決: 1) 先收集鍵值對至陣列，排序後一次建立；2) 或改用 SortedDictionary（插入 O(log n)）；3) 預設容量減少擴容。預防: 讀多寫多選 SortedDictionary，讀多寫少選 SortedList。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: B-Q9, B-Q10, C-Q7

D-Q4: 量測結果常出現 0ms 或波動大怎麼辦？

• A簡: 受計時解析度與 JIT 影響；先暖機，多次平均，改看 ticks。
• A詳: 症狀: 顯示 0ms、每次數值差異大。原因: 計時粒度不足、JIT 首次開銷、GC 干擾。解決: 1) 預熱執行；2) 重複 30 次以上取平均/中位數；3) 觀察 ElapsedTicks；4) 隔離 I/O。預防: 固定測試環境，關閉非必要背景工作。
• 難度: 初級
• 學習階段: 基礎
• 關聯概念: B-Q14, C-Q6, B-Q6

D-Q5: 前綴查詢結果多抓/漏抓怎麼辦？

• A簡: 邊界計算錯誤；用下一前綴作上界，檢查 lower/upper bound 邏輯。
• A詳: 症狀: 多出不屬於該前綴或漏資料。原因: 上界選擇錯、比較器不一致、越界。解決: 1) 以「0928-1234」與「0928-1235」作 [l,r)；2) 用同一 Comparer；3) 嚴格測試空/邊界。預防: 封裝並重用經驗證的 BinarySearch 輔助方法。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: B-Q5, B-Q12, C-Q5

D-Q6: 鍵重複（如同名、同電話）怎麼處理？

• A簡: 單值索引無法容納重複，改為多值索引 Dictionary<string,List>。
• A詳: 症狀: Add 時拋重複鍵例外或資料覆寫。原因: Dictionary/SortedList 鍵唯一。解決: 1) 索引值改為 List；2) Add 前 TryGetValue 建立清單；3) 查詢回傳清單遍歷。預防: 需求分析時評估唯一性，選擇正確索引形態。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: C-Q3, A-Q10, B-Q13

D-Q7: 記憶體使用飆升怎麼辦？

• A簡: 多索引與字串物件多造成壓力；減少重複、調整表示與容量。
• A詳: 症狀: WorkingSet 高、分配頻繁。原因: 每筆資料及每索引都存鍵/參考；字串分配多。解決: 1) 預估容量避免多次擴容；2) 以共享/Intern 常見字串（謹慎）；3) 適度壓縮鍵表示（如電話轉數值）。預防: 量測並平衡索引數量與必要欄位。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: C-Q7, B-Q8, B-Q14

D-Q8: 排序與查找行為在不同文化設定下不一致怎麼辦？

• A簡: 明確指定 StringComparer（Ordinal/InvariantCulture）保持一致。
• A詳: 症狀: 不同機器排序不同、查找失敗。原因: 預設文化比較導致順序差異。解決: 1) 索引統一使用 StringComparer.Ordinal（或 InvariantCulture）；2) 前綴與二分用同比較器；3) 設計時避免文化敏感欄位當鍵。預防: 於初始化統一比較設定。
• 難度: 中級
• 學習階段: 核心
• 關聯概念: B-Q11, C-Q8, C-Q5

D-Q9: 併發更新索引導致例外或髒讀怎麼辦？

• A簡: 索引非執行緒安全；用鎖或序列化更新，或採用並行容器。
• A詳: 症狀: KeyNotFound、ArgumentException、讀到不一致。原因: 競態條件。解決: 1) 以 ReaderWriterLockSlim 保護索引；2) 將多索引更新封裝為原子操作；3) 精確查找可用 ConcurrentDictionary。預防: 設計期定義一致性與鎖策略。
• 難度: 高級
• 學習階段: 進階
• 關聯概念: B-Q13, D-Q10, C-Q4

D-Q10: 多索引與本體資料如何保持一致？

• A簡: 封裝插入/更新/刪除為單一事務，成功才提交至所有索引。
• A詳: 症狀: 某索引找得到，另索引找不到。原因: 更新步驟分裂中斷。解決: 1) 設計 Repository 封裝操作；2) 先更新本體，再更新所有索引；3) 任一步驟失敗回滾；4) 單元測試覆蓋。預防: API 僅暴露原子化方法，避免外部繞過。
• 難度: 高級
• 學習階段: 進階
• 關聯概念: B-Q13, C-Q4, D-Q9

學習路徑索引

• 初學者：建議先學習哪 15 題
  • A-Q1: 什麼是資料結構？
  • A-Q2: 為什麼 programmer 該學資料結構？
  • A-Q3: 什麼是時間複雜度（Big-O）？
  • A-Q4: O(1)、O(n)、O(log n) 有何差異？
  • A-Q5: 為什麼工具不是主角，觀念才是？
  • A-Q6: 什麼是線性搜尋與二分搜尋？
  • A-Q7: 什麼是雜湊表（Hash Table）？
  • A-Q8: List、Dictionary、SortedList 有何差異？
  • A-Q11: 為何 Dictionary 不適合排序與前綴查詢？
  • A-Q19: 何時用 List 仍然合理？
  • C-Q1: 如何定義 ContactData 類別？
  • C-Q2: 如何用 List 產生百萬測試資料並線性搜尋？
  • C-Q3: 如何用 Dictionary 建姓名索引進行精確查詢？
  • C-Q6: 如何量測建置、搜尋時間與記憶體？
  • D-Q1: 用 List 搜尋很慢怎麼辦？
• 中級者：建議學習哪 20 題
  • A-Q9: SortedList 與 SortedDictionary 差異？
  • A-Q10: 什麼是索引（Index）？與資料庫的關係？
  • A-Q12: 為什麼前綴查詢要用「排序＋二分界點」？
  • A-Q13: 為什麼要看 MSDN 的時間複雜度註記？
  • A-Q14: 演算法為何勝過微調？
  • A-Q20: 為何本文示例最終選 SortedList？
  • B-Q1: List.Find 如何運作？
  • B-Q2: Dictionary 近 O(1) 的原理？
  • B-Q3: SortedList 如何維持排序與查找？
  • B-Q4: 如何用雙索引支援多鍵查詢？
  • B-Q5: 前綴查詢如何以二分求邊界？
  • B-Q6: 如何以 Big-O 推估效能？
  • B-Q7: 如何閱讀 MSDN 文件選型？
  • B-Q11: Comparer 如何影響正確性？
  • B-Q14: 如何正確量測效能與記憶體？
  • C-Q4: 如何用 SortedList 建立雙索引？
  • C-Q5: 如何在 SortedList 上實作電話前綴查詢？
  • C-Q7: 如何預先配置容量減少擴容成本？
  • C-Q8: 如何自訂字串比較器確保排序一致？
  • C-Q9: 如何實作 BinarySearch 輔助方法？
• 高級者：建議關注哪 15 題
  • A-Q17: 為何多索引能同時滿足不同查詢？
  • A-Q18: 為何 SortedList 插入較慢？
  • B-Q8: 為何加索引會增時耗與記憶體？
  • B-Q9: SortedList 插入 O(n) 的搬移機制？
  • B-Q10: SortedDictionary 的機制與適用情境？
  • B-Q13: 如何設計本體與索引分離架構？
  • C-Q4: 用 SortedList 建雙索引（權衡）
  • C-Q8: 自訂比較器（文化/語意）
  • D-Q2: Dictionary 無法排序/前綴的解法
  • D-Q3: 百萬筆 SortedList 載入太慢怎辦
  • D-Q5: 前綴查詢邊界錯誤的診斷
  • D-Q6: 鍵重複的處理策略
  • D-Q7: 記憶體飆升的原因與對策
  • D-Q9: 併發更新索引的風險與處理
  • D-Q10: 多索引一致性的事務化封裝