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

I've been doing some reading on the generic Dictionary class and the general advice is to use Dictionary if you need really fast access to an item matching a specific key. This is because a dictionary is using a type-safe Hashtable under the hood. When accessing items the search complexity is O(1) in dictionaries whereas in a List we would need to loop through EVERY SINGLE item until we find a match making the complexity O(n).

I wrote a little console app to see just how significant the difference between the two would be. The app stores 10 million items in each collection and attempts to access the second last item. The time difference between the List and Dictionary<TKey,TValue> is only one second, making the dictionary a winner but only just.

Question - can you provide an example(verbal is fine) where using a Dictionary vs a List would yield significant performance improvements?

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

CodePudding user response：

Your own example is fine to show where using a Dictionary yields significant performance improvements. The problem is you're not looking at the right thing. Your code spends a lot of time creating the dictionary or list and then does just one access of it. You need to separate out the collection creation and time multiple accesses of the item.

The code below does this. I get multiple accesses of the dictionary take 0.001s, whereas of the list the same number of accesses takes 2 minutes 32 seconds. Assuming I've done that right I think it shows dictionaries are faster for access.

    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];
    }
}