我不明白为什么SortedDictionary的性能比字典约5倍的速度较慢设置和检索值。我期待插入和删除要慢一些，但不能更新或检索。我已经测试的.Net 3.5和.Net 4.0版本编译的code。随机密钥的数组是pre计算的，以确保随机变化是不负责的随机访问的区别。

下面是测试了以下场景。

在每个值的使用顺序更新[关键]访问 在每个值的使用顺序存取[关键]访问 在每个值的使用TryGetValue顺序存取 在每个值的使用随机存取[关键]访问 在使用TryGetValue每个值的随机访问

任何人都知道为什么性能差异？

请，如果我做错了什么，或愚蠢的，请指出来。

样品code：简单地切换出来字典与SortedDictionary测试的区别

。

  const int的numLoops = 100;
    const int的numProperties = 30;
    const int的numInstances = 1000;

    静态无效DictionaryBench（INT numLoops，诠释numValues​​，诠释numInstances，字符串[] keyArray）
    {
        秒表SW =新的秒表（）;
        双总= 0.0D;

        对于（INT J = 0; J＆LT; numLoops; J ++）
        {
            //sw.Start（）;
            字典＆LT;字符串，对象＆gt;原=新字典＆LT;字符串，对象＆gt;（numValues​​）;
            的for（int i = 0; I＆LT; numValues​​;我++）
            {
                original.Add（的String.Format（键+ i.ToString（）），Value0：+ i.ToString（））;
            }
            名单＆LT;字典＆LT;字符串，对象＆gt;＆GT; collectionList =新的名单，其中，字典＆LT;字符串，对象＆gt;＆GT;（numInstances）;
            的for（int i = 0; I＆LT; numInstances;我++）
            {
                collectionList.Add（新字典＆LT;字符串，对象＆gt;（原件））;
            }
            sw.Start（）;
            使用相同的密钥对每个克隆的实例潮头值//设定值
            对于（INT K = 0; K＆LT; numInstances; k ++）
            {
                的for（int i = 0; I＆LT; numValues​​;我++）
                {
                    collectionList [k]的[键+ i.ToString（）] =值+ k.ToString（）+：+ i.ToString（）;
                }
            }

            //访问的每个唯一值
            对象温度;
            对于（INT K = 0; K＆LT; numInstances; k ++）
            {
                的for（int i = 0; I＆LT; numValues​​;我++）
                {
                    TEMP = collectionList [k]的[键+ i.ToString（）];
                }
            }
            //随机访问
            //sw.Start（）;
            对于（INT K = 0; K＆LT; numInstances; k ++）
            {
                的for（int i = 0; I＆LT; numValues​​;我++）
                {
                    collectionList [k]的.TryGetValue（keyArray [I]中，出温度）;
                }
            }
            sw.Stop（）;
            共有+ = sw.ElapsedMilliseconds;
            sw.Reset（）;
        }
 

解决方案

SortedDictionary 使用二进制搜索查找，这是O（日志名词）。照片 词典使用哈希表，这是O（1）。

因此​​，词典提供更快的查找。

的差异会更大一些具有字符串键，这是昂贵的比较。 A 词典将只遍历字符串两次（或者，如果有哈希冲突更多） - 一旦计算哈希值code和一次，以确保它的精确匹配。 A SortedDictionary 将遍历字符串的每次的比较。

I don't understand why the performance of SortedDictionary is approximately 5x slower than Dictionary for setting and retrieving values. I expected inserts and deletes to be slower but not updates or retrieves. I have tested .Net 3.5 and .Net 4.0 release compiled code. An array of random keys was pre-computed to ensure random variations weren't responsible for the differences on random access.

Here are the following scenarios tested.

Sequential update of each value using [key] accessor Sequential access of each value using [key] accessor Sequential access of each value using TryGetValue Random access of each value using [key] accessor Random access of each value using TryGetValue

Anyone know why the performance difference?

Please if I am doing something wrong or stupid please point it out.

Sample Code: Simply switch out Dictionary with SortedDictionary to test the difference.

    const int numLoops = 100;
    const int numProperties = 30;
    const int numInstances = 1000;

    static void DictionaryBench(int numLoops, int numValues, int numInstances, string[] keyArray)
    {
        Stopwatch sw = new Stopwatch();
        double total = 0.0d;

        for (int j = 0; j < numLoops; j++)
        {
            //sw.Start();
            Dictionary<string, object> original = new Dictionary<string, object>(numValues);
            for (int i = 0; i < numValues; i++)
            {
                original.Add(String.Format("Key" + i.ToString()), "Value0:" + i.ToString());
            }
            List<Dictionary<string, object>> collectionList = new List<Dictionary<string, object>>(numInstances);
            for (int i = 0; i < numInstances; i++)
            {
                collectionList.Add(new Dictionary<string, object>(original));
            }
            sw.Start();
            //Set values on each cloned instance to uniqe values using the same keys
            for (int k = 0; k < numInstances; k++)
            {
                for (int i = 0; i < numValues; i++)
                {
                    collectionList[k]["Key" + i.ToString()] = "Value" + k.ToString() + ":" + i.ToString();
                }
            }

            //Access each unique value
            object temp;
            for (int k = 0; k < numInstances; k++)
            {
                for (int i = 0; i < numValues; i++)
                {
                    temp = collectionList[k]["Key" + i.ToString()];
                }
            }
            //Random access
            //sw.Start();
            for (int k = 0; k < numInstances; k++)
            {
                for (int i = 0; i < numValues; i++)
                {
                    collectionList[k].TryGetValue(keyArray[i],out temp);
                }
            }
            sw.Stop();
            total += sw.ElapsedMilliseconds;
            sw.Reset();
        }

解决方案

SortedDictionary uses a binary search lookup, which is O(log n). Dictionary uses a hashtable, which is O(1).

Therefore, Dictionary gives faster lookups.

The difference will be even greater with string keys, which are costly to compare. A Dictionary will only iterate the string twice (or more if there are hash collisions) - once to compute the hashcode, and once to ensure that it's an exact match. A SortedDictionary will iterate the string for every comparison.