Dictionary<TKey,TValue> vs List<T>：遍歷效能、記憶體佈局與選型指南

面對大量資料集合遍歷，究竟選 Dictionary 還是 List？本文從底層儲存原理、執行緒安全性、實測效能三個維度深度剖析，並給出具體選型建議。

核心差異速覽

Dictionary 與 Hashtable 關鍵差異

// Dictionary 保持插入順序遍歷
var dic = new Dictionary();
dic.Add(1,5); dic.Add(10,3); dic.Add(2,5);
foreach(var k in dic.Keys) Console.WriteLine(k); // 1, 10, 2

// Hashtable 打亂順序
var ht = new Hashtable();
ht.Add(1,5); ht.Add(10,3); ht.Add(2,5);
foreach(var k in ht.Keys) Console.WriteLine(k); // 順序不定

Hashtable 內部使用 Thread.BeginCriticalRegion() 提供寫入鎖定，屬舊版相容產品；Dictionary 無同步機制，效能更高。

Dictionary 儲存原理：雜湊桶與 Entry 鏈

Key 經 GetHashCode() 計算雜湊碼，模桶數量決定桶索引。衝突時以 Entry 結構體形成單向鏈表（開放定址法）。查找流程：
1. 計算 Key 雜湊碼 → 桶索引
2. 遍歷該桶鏈表，EqualityComparer<TKey>.Default.Equals 比對 Key
3. 命中回傳 Value

此為 Key 必須唯一且不可變的根本原因。

實測：10 萬筆資料遍歷效能對比

var dic = new Dictionary();
var list = new List>();
var r = new Random();
for(int i=0; i<100000; i++) {
  string k = i.ToString(), v = r.Next(10).ToString();
  dic.Add(k, v);
  list.Add(new KeyValuePair(k, v));
}

// Dictionary 遍歷
var sw = Stopwatch.StartNew();
var sb = new StringBuilder();
foreach(var kv in dic) sb.Append(kv.Value);
sw.Stop();
Console.WriteLine($"Dictionary: {sw.ElapsedMilliseconds} ms");

// List 遍歷
sw.Restart(); sb.Clear();
foreach(var kv in list) sb.Append(kv.Value);
sw.Stop();
Console.WriteLine($"List: {sw.ElapsedMilliseconds} ms");

典型結果（Release 模式，x64）：
Dictionary: ~12 ms | List: ~8 ms

分析：
- List 連續記憶體，CPU 快取命中率極高，遍歷最快。
- Dictionary 需遍歷桶陣列 + Entry 鏈，指令較多，但差距在百萬級以下可忽略。
- 若需頻繁 Key 查找，Dictionary 綜合效能完勝。

選型決策樹

1. 需 Key 快速查找/去重 → Dictionary / HashSet
2. 純序列遍歷、記憶體敏感、資料量大 → List / 陣列
3. 多執行緒讀寫 → ConcurrentDictionary / ImmutableDictionary / 鎖保護
4. 需保持插入順序且頻繁插入刪除 → LinkedList / OrderedDictionary

進階提示

• Dictionary.TryGetValue 避免雙重查找。
• 預估資料量用 new Dictionary(capacity) 減少擴容。
• Value 為參考型別時，修改 Value 內容不影響雜湊表結構；修改 Key 會導致查找失效。