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

結論

對以字串為主鍵的單值查找，優先選擇 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 Dictionary");
            _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 SortedDictionary");
            _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");
            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 Dictionary");
            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 SortedDictionary");
            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);
        }
    }
}