C# 集合類型效能大比拚：Hashtable vs Dictionary vs SortedDictionary vs SortedList 單值查找實測

測試背景

在開發分詞元件時，需高頻率查找字串鍵值。網路上常見建議「Dictionary 優於 Hashtable 因避免裝箱拆箱」，但實測發現並非絕對。本文以 10 萬筆資料，三種字串長度 (16/128/1024)，排序/未排序兩種插入順序，實測四大集合類型的插入與查找效能。

測試環境與方法

• 資料筆數：100,000 筆唯一字串
• 字串長度：16、128、1024 字元
• 插入順序：隨機順序 vs 已排序
• 測試項目：插入耗時、查找耗時 (單位：毫秒)
• 集合初始容量：預設 100,000 避免擴容干擾

插入效能測試結果 (ms)

查找效能測試結果 (ms)

深度分析

Hashtable 為何最快？

• **底層相同**：Dictionary 內部實際包裝 Hashtable，多一層泛型封裝開銷。
• **無裝箱誤區**：字串為參考型別，Hashtable 存儲 `object` 參考，不涉及值型別的裝箱拆箱。
• **字串比較優化**：.NET 字串駐留機制使相同內容字串指向同一記憶體，雜湊碼計算與相等比較極快 (僅比較參考位址)。

Dictionary 稍慢原因

• 泛型介面呼叫、型別安全檢查增加微小開銷。
• 長字串 (1024) 時差距明顯擴大 (查找 130ms vs 202ms)，推測與泛型比較器呼叫有關。

樹狀結構 (SortedDictionary) 與陣列結構 (SortedList)

• **插入**：SortedDictionary 維護紅黑樹，O(log n)；SortedList 隨機插入需大量陣列搬移，O(n)，效能極差。
• **查找**：兩者皆 O(log n)，但字串比較需逐字元比對大小 (非單純相等)，開銷遠大於雜湊表的相等比較。
• **已排序優勢**：SortedList 依序插入時無需搬移，插入效能反超 SortedDictionary。

結論與選型建議

完整測試程式碼

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;

namespace CollectionBenchmark
{
    class Program
    {
        static Random _rnd = new Random();
        static Hashtable _ht;
        static Dictionary _dict;
        static SortedDictionary _sdict;
        static SortedList _slist;

        static string GetRandomString(int len)
        {
            var sb = new StringBuilder(len);
            for (int i = 0; i < len; i++)
                sb.Append((char)_rnd.Next(32, 128));
            return sb.ToString();
        }

        static List GetTestData(int len, int count)
        {
            var list = new List(count);
            for (int i = 0; i < count; i++) list.Add(GetRandomString(len));
            return list;
        }

        static void TestInsert(List data, bool sorted)
        {
            if (sorted) data.Sort();
            Console.WriteLine($"=== Insert: Len={data[0].Length}, Count={data.Count}, Sorted={sorted} ===");

            var sw = Stopwatch.StartNew();
            _ht = new Hashtable(data.Count);
            foreach (var s in data) if (!_ht.ContainsKey(s)) _ht.Add(s, 0);
            Console.WriteLine($"Hashtable: {sw.ElapsedMilliseconds} ms");

            sw.Restart();
            _dict = new Dictionary(data.Count);
            foreach (var s in data) if (!_dict.ContainsKey(s)) _dict.Add(s, 0);
            Console.WriteLine($"Dictionary: {sw.ElapsedMilliseconds} ms");

            sw.Restart();
            _sdict = new SortedDictionary();
            foreach (var s in data) if (!_sdict.ContainsKey(s)) _sdict.Add(s, 0);
            Console.WriteLine($"SortedDictionary: {sw.ElapsedMilliseconds} ms");

            sw.Restart();
            _slist = new SortedList(data.Count);
            foreach (var s in data) if (!_slist.ContainsKey(s)) _slist.Add(s, 0);
            Console.WriteLine($"SortedList: {sw.ElapsedMilliseconds} ms");
        }

        static void TestFind(List data, bool sorted)
        {
            Console.WriteLine($"=== Find: Len={data[0].Length}, Count={data.Count}, Sorted={sorted} ===");
            var sw = Stopwatch.StartNew();
            foreach (var s in data) if (_ht[s] == null) Console.WriteLine("Error!");
            Console.WriteLine($"Hashtable: {sw.ElapsedMilliseconds} ms");

            sw.Restart();
            foreach (var s in data) if (!_dict.ContainsKey(s)) Console.WriteLine("Error!");
            Console.WriteLine($"Dictionary: {sw.ElapsedMilliseconds} ms");

            sw.Restart();
            foreach (var s in data) if (!_sdict.ContainsKey(s)) Console.WriteLine("Error!");
            Console.WriteLine($"SortedDictionary: {sw.ElapsedMilliseconds} ms");

            sw.Restart();
            foreach (var s in data) if (!_slist.ContainsKey(s)) Console.WriteLine("Error!");
            Console.WriteLine($"SortedList: {sw.ElapsedMilliseconds} ms");
        }

        static void Main()
        {
            foreach (int len in new[] { 16, 128, 1024 })
            {
                var data = GetTestData(len, 100000);
                TestInsert(data, false); TestFind(data, false);
                TestInsert(data, true);  TestFind(data, true);
            }
            Console.ReadKey();
        }
    }
}