与Dictionary相比,SortedDictionary的性能出乎意料

Question

我不明白为什么SortedDictionary的性能比Dictionary设置和检索值慢约5倍.我希望插入和删除更慢但不更新或检索.我测试了.Net 3.5和.Net 4.0发布的编译代码.预先计算了一组随机密钥,以确保随机变化不对随机访问的差异负责.

以下是测试的以下场景.

1. 使用[key]访问器顺序更新每个值
2. 使用[key]访问器对每个值进行顺序访问
3. 使用TryGetValue对每个值进行顺序访问
4. 使用[key]访问器随机访问每个值
5. 使用TryGetValue随机访问每个值

谁知道为什么性能差异？

如果我做错了什么或愚蠢,请指出.

示例代码:只需使用SortedDictionary切换Dictionary以测试差异.

    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();
        }

Answer 1

SortedDictionary使用二进制搜索查找,即O(log n).
Dictionary使用哈希表,即O(1).

因此,Dictionary提供更快的查找.

字符串键的差异会更大,比较成本很高.
A Dictionary只会迭代字符串两次(如果存在哈希冲突则会更多) - 一次计算哈希码,一次确保它完全匹配.A SortedDictionary将为每次比较迭代字符串.