为什么 List<string> 比 Dictionary 快？

Question

考虑这段代码：

var str1 = "1234567890qwertyuiop[asdfghjkl;zxcvbnm1,.";

Dictionary<string, Object> objects = new Dictionary<string, object> {{str1, new object()}};

Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();

for (int i = 0; i < 100000000; i++)
{
    object result;
    objects.TryGetValue(str1, out result);
}

stopwatch.Stop();
Console.WriteLine(stopwatch.ElapsedMilliseconds);

stopwatch.Reset();
//////////////////////////////////////////////////////////////
var list = new List<string>();
list.Add(str1);

stopwatch.Start();

for (int i = 0; i < 100000000; i++)
{
    foreach (var item in list)
    {
        var result = "";

        if (item == str1)
        {
            result = item;
        }
    }
}

stopwatch.Stop();
Console.WriteLine(stopwatch.ElapsedMilliseconds);

当你运行这段代码会看到这样的结果：

5157      // Dictionary
3881      // List

所以列表比字典快。

我想知道为什么。字符串和长度有关系吗？

Answer 1

因为你只有一个元素，所以你的列表代码只是跳过哈希检查，没有做额外的工作。
因为你有这么长的键，字典会做更多的工作来计算键的散列，而列表实现会跳过所有这些，因为字符串是引用相等的（它根本不需要比较内容）。

添加更多项目，性能将发生巨大变化。

简而言之，如果 n 为 1，O(1) 并不比 O(n) 快。

为什么 List<string> 比 Dictionary 快？

Why is List<string> faster than Dictionary?

c#

performance

dictionary

list