幾種 C# 框架提供的資料結構對單值查找效率比較（一）

做分詞元件時，有網友提出用 Hashtable 查找字串效率較低，建議改 Dictionary，理由是 Hashtable 的 Key 是 object 會觸發裝箱拆箱。一直懷疑這說法，因為我理解只有實值型別與參考型別透過 object 互轉才會發生裝箱拆箱，參考型別間強制轉換不應發生。而 Dictionary 泛型底層仍調用 Hashtable，效率怎麼會更高？今天決定對比 4 種常用資料結構測試，供系統效能優化參考。

四種資料結構：Hashtable、Dictionary、SortedDictionary、SortedList，分別代表雜湊表、雜湊表、二元搜尋樹、二分搜尋。測試設計：10 萬筆資料一組，依字串長度分 3 組（16、128、1024），分別按原資料排序與未排序兩種情況測試插入與單值查找。時間單位毫秒。

插入測試結果（插入 10 萬次總時間）

查詢測試結果（查詢 10 萬次總時間）

從結果看，無論插入查詢，Hashtable 效率最高，其次 Dictionary，符合預期。

雜湊插入時間消耗在處理雜湊衝突，但只選擇空閒桶無額外記憶體配置，消耗有限。測試中已將各資料結構初始值設 10 萬。Dictionary 在 Hashtable 基礎上封裝一層，效率略降。

二元搜尋樹插入消耗在節點維護與查找（每次插入前確認是否重複）。

二分搜尋底層是順序陣列，順序插入效率比二元樹略高，隨機插入需不斷調整元素位置，導致大量大塊記憶體拷貝，效率極低且隨元素增加指數上升。

雜湊查找消耗主要在衝突匹配，雜湊函數計算很快。注意 .NET string 特殊性：相同字串指向相同位址，兩兩比較只比位址而非每字元，大幅提高比較效率。其他兩種方式需比較字串大小而非僅相等，帶來巨大開銷。