Dictionary vs. List Lookup Time - C#

Problem

You want to see how the lookup times for List and Dictionary compare. At what point does Dictionary become more efficient for lookups than List? Review some fundamentals and benchmark.

Solution: C# collection lookups

Whenever you look up a value in a Dictionary, the runtime must compute a hash code from the key. This is usually implemented by some low-level bit shifting or modulo divisions, which is very fast.

However, computing the hash value has some overhead. More importantly, though, there is substantial overhead in constructing Dictionaries in the first place.

Whenever you add items to the Dictionary, the hash keys must be computed and the values must be stored in the Dictionary's internal structure. This is slower than appending to a List.

Information: what I compared between the two

My experiment didn't include how long it takes for the Dictionary to be constructed. I exclusively focused on how long it takes to look up an item in the collection.

Some limitations of my experiment were that the keys were all strings, the lookup always succeeded, and the keys were all 12 characters long.

Dictionary test	List test
// 1. Get random number. int n = r.Next(m); // 2. Get random string. string k = l[n]; // 3. See if it exists. bool hit = false; if (d.ContainsKey(k)) { hit = true; }	// 1. Get random number. int n = r.Next(m); // 2. Get random string. string k = l[n]; // Loop through strings to see if it exists. bool hit = false; foreach (string s2 in l2) { if (s2 == k) { hit = true; break; } }
• String key always exists in Dictionary. • ContainsKey is used.	• String key always exists in List. • Foreach loop is used.

My test used random path names generated by Path.GetRandomFileName, which is an easy way to get random strings. You will see paths like "dliu3ms0.idt".

Information: benchmark results

I tested collection sizes of 1 to 12 elements. The index of the string item matched was random, which should average to about the middle index. My test showed that when you exceed 3 items, the Dictionary lookup is faster.

#   Dictionary ms   List ms
1   655	            453
2   702	            577
3   702	            670
4   655	            749
5   686	            811
6   702	            874
7   687             936
8   702	            1014
9   702	            1077
10  702	            1108
11  687             1170
12  718             1232

Note: this has many limitations

As I said before, this test uses only 12 character long strings. It uses only generic collections, and doesn't examine Hashtable, HybridDictionary, or SortedDictionary. However, it has some use.

Opinion: when to use List and Dictionary

I suggest using Dictionary when the number of lookups greatly exceeds the number of insertions. It is fine to use List when you will have less than 4 items always.

Perhaps most important, though, are the edge cases in your programs. If there is any possibility that there will be 1000's of elements, always use Dictionary. This will make the app usable in edge cases.

When uniqueness is important, Dictionary or Hashtable can check for duplicates automatically. This can lead to simpler code.

Summary: when to use Dictionary

For lookups, Dictionary is usually a much better choice. As you can see, the time required is flat, which is an O(1) constant time complexity. The List has an O(N) linear time complexity.

3 elements can be looped over faster than looked up in a Dictionary in this experiment. As a result, I use three elements as the threshold when I will switch to Dictionary lookups from List loops.