做分詞組件時，有網友提出采用Hashtable 數據結構查找字符串效率較低，建議改為Dictionary，其理由是采用Hashtable 時Key值是object 會觸發裝箱和拆箱動作，一直對這種說法表示懷疑，因為我理解只有值類型和引用類型通過object 互轉時才會發生裝箱和查詢，引用類型之間強制轉換不應發生裝箱和拆箱，而Dictionary 泛型實際上底層還是調用的Hashtable，所以效率怎麼會比Hashtable 要高呢？今天決定對比較常用的4種數據結構做一個測試，以便以後做系統性能優化時做一個參考。
這四種數據結構分別是 Hashtable, Dictionary, SortedDictionary,SortedList。它們所代表的數據結構分別是 哈希表、哈希表、二叉索引樹和二分查找。測試設計如下。以10萬條數據為一組，按照每條記錄的字符串長度不同分為3組，分別是16，128，1024，並且分別根據原數據是排序的還是不排序的兩種情況進行插入和單值查找的測試。測試時間單位為毫秒。下面看測試結果
插入的測試結果 (所有結果都是插入10萬次的總時間)
測試條件 HashTable Dictionary SortedDictionary SortedList 字符串長度 16,未排序 14 21 896 8009 字符串長度 16,已排序 25 35 990 671 字符串長度 128,未排序 30 52 868 8415 字符串長度 128,已排序 43 67 1053 666 字符串長度 1024,未排序 132 262 1269 8159 字符串長度 1024,已排序 158 277 1036 684
查詢的測試結果 (所有結果都是查詢10萬次的總時間)
測試條件 HashTable Dictionary SortedDictionary SortedList 字符串長度 16,未排序 13 15 412 366 字符串長度 16,已排序 25 29 349 315 字符串長度 128,未排序 31 40 492 438 字符串長度 128,已排序 42 54 408 371 字符串長度 1024,未排序 130 202 934 894 字符串長度 1024,已排序 160 219 801 757
從測試結果上看，無論是插入和查詢，Hashtable的效率是最高的 其次是Dictionary 這和我的預期基本是一致的。
采用哈希方式插入，時間主要消耗在對哈希沖突情況的處理上，但由於只是選擇空閒的桶而沒有另外進行內存分配，其消耗時間是有限的。這裡需要說明的是在我的測試設計中已經將每種數據結構的初始值設置為10萬。而Dictionary 由於在Hashtable基礎上封裝了一層，效率稍有下降。
采用二叉搜索樹插入，時間消耗在對樹的節點的維護以及查找上（因為每次插入前需要確定記錄是否有重復，重復記錄不插入）。
二分查找，由於底層是一個順序數組，當順序插入時，效率比二叉搜索樹稍高，當隨機插入時會要求不斷調整元素在數組中的位置，這導致大量的大塊內存的拷貝，所以這種情況下效率極低，而且隨著元素個數的增加會成指數上升。
哈希查找的時間消耗主要還是在沖突情況的匹配上，哈希函數的計算一般是很快的。但這裡有一點必須要注意到，就是.net string 類型的特殊性，由於相同的string 指向相同的地址，所以在string 進行兩兩比較時，只比較地址，而不是每個字符都去計算，這大大提高了比較的效率。
而其他兩種方式則需要比較字符串的大小，而不是僅僅比較相等，這帶來了非常大的開銷。
結論
對以字符串為主鍵的單值查找的優先選擇 Hashtable 或者 Dictionary. 個人覺得如果只注重效率的話， Hashtable 更好一些，特別是在字符串較長時其效率幾乎比Dictionary 快將近一倍。
測試代碼
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
namespace StringDictionaryPerformance
{
class Program
{
static Random _Rand = new Random();
static Hashtable _Hashtable;
static Dictionary<string, int> _Dictionary;
static SortedDictionary<string, int> _SortDictionary ;
static SortedList<string, int> _SortedList ;
static string GetRandString(int length)
{
StringBuilder str = new StringBuilder();
for (int i = 0; i < length; i++)
{
str.Append((char)_Rand.Next(32, 128));
}
return str.ToString();
}
static List<string> GetTestStrings(int length, int number)
{
List<string> retVal = new List<string>(number);
for (int i = 0; i < number; i++)
{
retVal.Add(GetRandString(length));
}
return retVal;
}
static void TestInsert(List<string> strings, bool sort)
{
if (sort)
{
strings.Sort();
}
Console.WriteLine(string.Format("TestInsert string length = {0} count of strings = {1} sort={2}",
strings[0].Length, strings.Count, sort));
Stopwatch stopWatch = new Stopwatch();
Console.WriteLine("Begin Hashtable");
_Hashtable = new Hashtable(strings.Count);
stopWatch.Reset();
stopWatch.Start();
for (int i = 0; i < strings.Count; i++)
{
if (_Hashtable[strings[i]] != null)
{
_Hashtable.Add(strings[i], i);
}
}
stopWatch.Stop();
Console.WriteLine(string.Format("ElapsedMilliseconds = {0} ms", stopWatch.ElapsedMilliseconds));
Console.WriteLine("Begin Dictoinary");
_Dictionary = new Dictionary<string,int>(strings.Count);
stopWatch.Reset();
stopWatch.Start();
for (int i = 0; i < strings.Count; i++)
{
if (!_Dictionary.ContainsKey(strings[i]))
{
_Dictionary.Add(strings[i], i);
}
}
stopWatch.Stop();
Console.WriteLine(string.Format("ElapsedMilliseconds = {0} ms", stopWatch.ElapsedMilliseconds));
Console.WriteLine("Begin SortDictionary");
_SortDictionary = new SortedDictionary<string, int>();
stopWatch.Reset();
stopWatch.Start();
for (int i = 0; i < strings.Count; i++)
{
if (!_SortDictionary.ContainsKey(strings[i]))
{
_SortDictionary.Add(strings[i], i);
}
}
stopWatch.Stop();
Console.WriteLine(string.Format("ElapsedMilliseconds = {0} ms", stopWatch.ElapsedMilliseconds));
Console.WriteLine("Begin SortedList");
_SortedList = new SortedList<string, int>(strings.Count);
stopWatch.Reset();
stopWatch.Start();
for (int i = 0; i < strings.Count; i++)
{
if (!_SortedList.ContainsKey(strings[i]))
{
_SortedList.Add(strings[i], i);
}
}
stopWatch.Stop();
Console.WriteLine(string.Format("ElapsedMilliseconds = {0} ms", stopWatch.ElapsedMilliseconds));
}
static void TestFind(List<string> strings, bool sort)
{
Console.WriteLine(string.Format("TestFind string length = {0} count of strings = {1} sort={2}",
strings[0].Length, strings.Count, sort));
Stopwatch stopWatch = new Stopwatch();
Console.WriteLine("Begin Hashtable");
_Hashtable = new Hashtable(strings.Count);
stopWatch.Reset();
stopWatch.Start();
for (int i = 0; i < strings.Count; i++)
{
if (_Hashtable[strings[i]] != null)
{
Console.WriteLine("Error!");
}
}
stopWatch.Stop();
Console.WriteLine(string.Format("ElapsedMilliseconds = {0} ms", stopWatch.ElapsedMilliseconds));
Console.WriteLine("Begin Dictoinary");
stopWatch.Reset();
stopWatch.Start();
for (int i = 0; i < strings.Count; i++)
{
if (!_Dictionary.ContainsKey(strings[i]))
{
Console.WriteLine("Error!");
}
}
stopWatch.Stop();
Console.WriteLine(string.Format("ElapsedMilliseconds = {0} ms", stopWatch.ElapsedMilliseconds));
Console.WriteLine("Begin SortDictionary");
stopWatch.Reset();
stopWatch.Start();
for (int i = 0; i < strings.Count; i++)
{
if (!_SortDictionary.ContainsKey(strings[i]))
{
Console.WriteLine("Error!");
}
}
stopWatch.Stop();
Console.WriteLine(string.Format("ElapsedMilliseconds = {0} ms", stopWatch.ElapsedMilliseconds));
Console.WriteLine("Begin SortedList");
stopWatch.Reset();
stopWatch.Start();
for (int i = 0; i < strings.Count; i++)
{
if (!_SortedList.ContainsKey(strings[i]))
{
Console.WriteLine("Error!");
}
}
stopWatch.Stop();
Console.WriteLine(string.Format("ElapsedMilliseconds = {0} ms", stopWatch.ElapsedMilliseconds));
}
static void Main(string[] args)
{
List<string> strings;
strings = GetTestStrings(16, 100000);
TestInsert(strings, false);
TestFind(strings, false);
TestInsert(strings, true);
TestFind(strings, true);
strings = GetTestStrings(128, 100000);
TestInsert(strings, false);
TestFind(strings, false);
TestInsert(strings, true);
TestFind(strings, true);
strings = GetTestStrings(1024, 100000);
TestInsert(strings, false);
TestFind(strings, false);
TestInsert(strings, true);
TestFind(strings, true);
}
}
}
