不同字符串字典的基准测试显示正常的更快，我不知道为什么

Question

我正在对几个字符串字典进行一些基准测试，因为我想了解不同配置的执行情况，但我惊讶地发现正常Dictionary<String,String>的速度更快。可能是因为我缺少一些概念或者我做错了什么，但这些是我得到的结果：

Collection:             2147482 items.
Random Keys:            1000 keys.

Normal dictionary
        Add 1000 items:         573ms.
        Get 1000 keys:          0ms.

Normal Dictionary with OrdinalIgnoreCase comparer
        Add 1000 items:         642ms.
        Get 1000 keys:          0ms.

Normal Dictionary with InvariantCultureIgnoreCase comparer
        Add 1000 items:         1661ms.
        Get 1000 keys:          0ms.

Sorted dictionary
        Add 1000 items:         11996ms.
        Get 1000 keys:          5ms.

Sorted dictionary with OrdinalIgnoreCase comparer
        Add 1000 items:         11097ms.
        Get 1000 keys:          5ms.

Sorted dictionary with InvariantCultureIgnoreCase comparer
        Add 1000 items:         9814ms.
        Get 1000 keys:          5ms.

这是我用来测试它的代码：

    static void Main(string[] args)
    {
        String[] col = GenerateCollectionUnsorted(Int32.MaxValue / 1000).ToArray();
        Int32 len = col.Length;
        Console.WriteLine("Collection:\t\t" + len.ToString() + " items.");

        String[] randomKeys = GetRandomKeys(col, 1000);
        Console.WriteLine("Random Keys:\t\t" + randomKeys.Length.ToString() + " keys.");

        GC.Collect();
        GC.WaitForPendingFinalizers();

        Console.WriteLine();
        Console.WriteLine("Normal dictionary");
        TestDic(col, randomKeys, new Dictionary<String, String>());
        GC.Collect();
        GC.WaitForPendingFinalizers();

        Console.WriteLine();
        Console.WriteLine("Normal Dictionary with OrdinalIgnoreCase comparer");
        TestDic(col, randomKeys, new Dictionary<String, String>(StringComparer.OrdinalIgnoreCase));
        GC.Collect();
        GC.WaitForPendingFinalizers();

        Console.WriteLine();
        Console.WriteLine("Normal Dictionary with InvariantCultureIgnoreCase comparer");
        TestDic(col, randomKeys, new Dictionary<String, String>(StringComparer.InvariantCultureIgnoreCase));
        GC.Collect();
        GC.WaitForPendingFinalizers();

        Console.WriteLine();
        Console.WriteLine("Sorted dictionary");
        TestDic(col,randomKeys, new SortedDictionary<String,String>());
        GC.Collect(); 
        GC.WaitForPendingFinalizers();
        
        Console.WriteLine();
        Console.WriteLine("Sorted dictionary with OrdinalIgnoreCase comparer");
        TestDic(col, randomKeys, new SortedDictionary<String, String>(StringComparer.OrdinalIgnoreCase));
        GC.Collect();
        GC.WaitForPendingFinalizers();

        Console.WriteLine();
        Console.WriteLine("Sorted dictionary with InvariantCultureIgnoreCase comparer");
        TestDic(col, randomKeys, new SortedDictionary<String, String>(StringComparer.InvariantCultureIgnoreCase));
        GC.Collect();
        GC.WaitForPendingFinalizers();

        Console.WriteLine("\nEnd");
        Console.ReadKey(true);
    }

    static void TestDic(String[] col, String[] randomKeys, IDictionary<String,String> dic)
    {
        Stopwatch crono = new Stopwatch();
        
        crono.Start();
        foreach (String s in col)
            dic.Add(s, s);
        crono.Stop();

        Console.WriteLine("\tAdd "+randomKeys.Length.ToString()+" items:\t\t" + crono.ElapsedMilliseconds.ToString() + "ms.");

        crono.Reset();
        crono.Start();
        String sv;
        foreach (var rk in randomKeys)
        {
            sv = dic[rk];
            sv.ToString();
        }
        crono.Stop();
        Console.WriteLine("\tGet " + randomKeys.Length.ToString() + " keys:\t\t" + crono.ElapsedMilliseconds.ToString() + "ms.");
    }

    static String[] GetRandomKeys(String[] col, Int32 count)
    {
        Random ran = new Random(DateTime.Now.Millisecond);

        List<Int32> indexSelection = new List<int>();
        List<String> selection = new List<string>();
        
        Int32 len = col.Length;
        
        while (indexSelection.Count < count)
        {
            Int32 value = ran.Next(0, len - 1);
            if (!indexSelection.Contains(value))
            {
                indexSelection.Add(value);
                selection.Add(col[value]);
            }
        }
        return selection.ToArray();
    }

    static IEnumerable<String> GenerateCollection(Int32 count)
    {
        for (int i = 0; i < count; i++)
        {
            yield return i.ToString("X").PadLeft(5, '0');
        }
    }

    static IEnumerable<String> GenerateCollectionUnsorted(Int32 amount)
    {
        for (int i = 0; i < amount / 2; i++)
        {
            yield return i.ToString("X").PadLeft(5, '0');
            yield return (amount-i).ToString("X").PadLeft(5, '0');
        }
    }

知道为什么会这样吗？

编辑 1：据我所知，排序字典添加项目会更慢，因为集合已排序，所以获取它们会更快。而且，将字符串与 OrdinalIgnoreCase 或 InvariantCultureIgnoreCase 进行比较应该比正常比较更快，因此查找应该更快。但也许我的理解是完全错误的：D

提前致谢。

编辑 2：出于好奇，我对字符串比较进行了一些测试：

Collection:             2147482 items.
Random Keys:            1000 keys.

CurrentCulture
        LookUp:         158209ms.

CurrentCultureIgnoreCase
        LookUp:         160710ms.

InvariantCulture
        LookUp:         132765ms.

InvariantCultureIgnoreCase
        LookUp:         133409ms.

Ordinal
        LookUp:         36115ms.

OrdinalIgnoreCase
        LookUp:         36329ms.

Answer 1

因为只有带有默认比较器的普通字典实际上是一个普通字典，所有其他的都是排序字典。

所以，结果是非常一致的。

编辑：

解决了这个问题，结果就不一样了。:)

排序字典在添加项目时速度较慢，因为它们需要排序，但在获取项目时不会更快。搜索二叉树很快，但搜索常规字典使用的哈希列表更快。当二叉树增长时，将有更多步骤来定位每个项目，而字典主要通过添加更多桶来增长，因此比较次数几乎不受影响。

比较字符串与Ordinal比常规 ( CurrentCulture) 比较OrdinalIgnoreCase快，并且比 快CurrentCultureIgnoreCase，但不确定OrdinalIgnoreCase是否比 快CurrentCulture。InvariantCulturecompare 并不比常规比较快，它只是使用不同的文化。序数比较快得多的原因是它根本不需要考虑文化设置。

顺便说一下，我注意到 GetRandomKeys 方法中有一个错误。它永远不会选择最后一项，因为您会得到一个介于 0 和 Length - 2 之间的随机数。

Answer 2

来自MSDN 文档SortedDictionary：

的SortedDictionary<TKey, TValue>通用类是O（log n）的检索，其中n是字典中的元件的数目的二进制搜索树。

从文档开始Dictionary：

使用键检索值非常快，接近 O(1)，因为Dictionary<TKey, TValue>该类是作为哈希表实现的。

因此，在许多情况下Dictionary能跑赢大盘也就不足为奇了SortedDictionary。