Dictionary<TKey,TValue> 与 List<T> 的搜索复杂度

Question

我一直在阅读通用词典 class，如果您确实需要快速访问与特定键匹配的项目，一般建议使用词典。这是因为字典在底层使用类型安全的哈希表。访问项目时，字典中的搜索复杂度为 O(1)，而在列表中，我们需要遍历每个项目，直到找到匹配项，使得复杂度为 O(n)。

我编写了一个小控制台应用程序来查看两者之间的区别有多大。该应用程序在每个集合中存储 1000 万个项目，并尝试访问倒数第二个项目。 List 和 Dictionary 的时间差只有一秒，让字典胜出也只是刚刚.

问题 - 您能否提供一个示例（口头表达即可），说明使用字典与列表相比会产生显着的性能改进？

class Program
{
    static void Main(string[] args)
    {
        var iterations = 10000000;//10 million

        var sw = new Stopwatch();

        sw.Start();
        var value1 = GetSecondLastFromDictionary(iterations);
        sw.Stop();
        var t1 = sw.Elapsed.ToString();
        sw.Restart();

        var value2 = GetSecondLastFromList(iterations);

        sw.Stop();
        var t2 = sw.Elapsed.ToString(); 

        Console.WriteLine($"Dictionary - {t1}\nList - {t2}");
        Console.ReadKey();
    }

    private static string GetSecondLastFromList(int iterations)
    {
        var collection = new List<Test>();
        for (var i = 0; i < iterations; i++)
            collection.Add(new Test { Key = i, Value = $"#{i}" });
        return collection.Where(e => e.Key == iterations - 1).First().Value;
    }

    private static string GetSecondLastFromDictionary(int iterations)
    {
        var collection = new Dictionary<int, string>();
        for (var i = 0; i < iterations; i++)
            collection.Add(i, $"#{i}");
        return collection[iterations - 1];
    }
}
class Test
{
    public int Key { get; set; }
    public string Value { get; set; }
}

Answer 1

您自己的示例很好地展示了使用字典可以显着提高性能的地方。问题是你没有看到正确的东西。您的代码花费大量时间创建字典或列表，然后只对其进行一次访问。您需要将项目的集合创建和时间多次访问分开。

下面的代码就是这样做的。我对字典进行多次访问需要 0.001 秒，而对列表进行相同次数的访问需要 2 分 32 秒。假设我做对了，我认为它表明字典的访问速度更快。

    static void Main(string[] args)
    {
        var iterations = 100000;

        var sw = new Stopwatch();
        var dict = CreateDict(iterations);
        var list = CreateList(iterations);
        sw.Start();
        GetSecondLastFromDictionary(iterations, dict);
        sw.Stop();
        var t1 = sw.Elapsed.ToString();
        sw.Restart();
        GetSecondLastFromList(iterations, list);
        sw.Stop();
        var t2 = sw.Elapsed.ToString();

        Console.WriteLine($"Dictionary - {t1}\nList - {t2}");
        Console.ReadKey();
    }

    private static Dictionary<int, string> CreateDict(int iterations)
    {
        var collection = new Dictionary<int, string>();
        for (var i = 0; i < iterations; i++)
            collection.Add(i, $"#{i}");
        return collection;
    }

    private static List<Test> CreateList(int iterations)
    {
        var collection = new List<Test>();
        for (var i = 0; i < iterations; i++)
            collection.Add(new Test { Key = i, Value = $"#{i}" });
        return collection;
    }

    private static void GetSecondLastFromList(int iterations, List<Test> collection)
    {
        string test;
        for (var i = 0; i < iterations; i++)
            test = collection.Where(e => e.Key == iterations - 1).First().Value;
    }

    private static void GetSecondLastFromDictionary(int iterations, Dictionary<int, string> collection)
    {
        string test;
        for (var i = 0; i < iterations; i++)
            test = collection[iterations - 1];
    }
}

Dictionary<TKey,TValue> 与 List<T> 的搜索复杂度

Search complexity of Dictionary<TKey,TValue> vs List<T>

.net

c#