Why is List faster than Dictionary?

Question

Consider this code:

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

When you run this code will see this result:

5157      // Dictionary
3881      // List

So the list is faster than a dictionary.

I want to know why. Is there any relation between string and length?

there are constraint checks in dictionary keys.. this topic has plenty of information covering it. — Brett Caswell, Jan 21 '15 at 16:48
No data structure is *ever* "faster" than another data structure. Different data structures have different operations, an each one has different performance characteristics for each operation. This one operation on these two specific structures of a particular size can be compared, but that's *radically* different. — Servy, Jan 21 '15 at 16:48
I'm not convinced your benchmark test is correctly constructed to measure what you're trying to discover. The way you've written the code, there are opportunities for the optimizer to optimize away much of what you are trying to benchmark, unless you are running a Debug build, or have optimizations turned off, neither of which are proper benchmarks either. — hatchet - done with SOverflow, Jan 21 '15 at 16:55
Notice that you are searching for interned string - so there is no need to actually do complete equals on it (O(string_length)) but just reference equality (O(1)) is enough. Construct the same string with string builder and difference will be different (visible in case of for more than one item in the list and your item you looking for not the first one). — Alexei Levenkov, Jan 21 '15 at 17:03
Also, if you're going to compare the two.. you should be using a foreach on the dictionary to make it appliciable to your foreach enumeration on the list. as state here: https://msdn.microsoft.com/en-us/library/yt2fy5zk(v=vs.110).aspx .. you would enumerate over the dictionary as a `KeyValuePair`.. also, your list should be a `List>` to make it applicable as well.. — Brett Caswell, Jan 21 '15 at 17:04

SLaks · Accepted Answer · 2015-01-21T16:55:15.263

14

Because you only have one element, your list code simply skips a hash check and does no extra work.
Because you have such a long key, the dictionary is doing even more work to compute the key's hash, whereas the list implementation skips all of that because the strings are reference-equal (it doesn't need to compare the content at all).

Add more items and the performance will change dramatically.

In short, O(1) is not faster than O(n) if n is 1.

edited Jan 21 '15 at 16:55

answered Jan 21 '15 at 16:47

SLaks

868,454
176
1,908
1,964

In fact, you will probably be able to place quite a few items (maybe hundreds) in your List before you notice a performance impact vs using a Dictionary. – Ralph Caraveo Jan 21 '15 at 16:50
@RalphCaraveo theoretically any limitation on `n` would make it O(1)... In practice I think it is about 16 - there was SO question about it - http://stackoverflow.com/questions/150750/hashset-vs-list-performance – Alexei Levenkov Jan 21 '15 at 16:53
2

@AlexeiLevenkov: It actually primarily depends on the performance of your hash. – SLaks Jan 21 '15 at 16:54
@SLaks and in case of OP - strings - position of string in the list... and whether strings of interest are interned... – Alexei Levenkov Jan 21 '15 at 16:59
@RalphCaraveo If you have a quality hash algorithm that number is likely to be around 2 or 3 items, not hundreds. It it takes hundreds of items to make the dictionary faster, it'd mean having one pretty terrible hashing function. – Servy Jan 21 '15 at 18:21
@Servy - that's true, but in terms of operation counting a single computed hash can easily add up...this is really besides the point. – Ralph Caraveo Jan 21 '15 at 18:54

Why is List faster than Dictionary?

1 Answers1