C# Dictionary Versus List Lookup TimeCompare the performance of Dictionary and List look up operations in a benchmark.
dot net perls

Lookup times are different in List and Dictionary. We compare them in the C# language targeting the .NET Framework. We determine the point at which Dictionary becomes more efficient for lookups than List.

Intro. First, 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 fast.



However Computing the hash value has some overhead. Also, there is substantial overhead in constructing Dictionaries in the first place.

Example Whenever you add items to the Dictionary, the hash keys must be computed and the values must be stored in the buckets.

Benchmark. My experiment didn't include Dictionary construction. I focused on how long it takes to look up an item. Some limitations were that the keys were all strings, the lookup always succeeded, and the keys were all 12 characters long.

Note This test used random path names ("dliu3ms0.idt") generated by Path.GetRandomFileName, an easy way to get random strings.

Dictionary code that was benchmarked: C#
// 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; }

List code that was benchmarked: C#
// 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; } }

Results. Here are the benchmark results for this article. 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.

Result My test showed that when you exceed three items, the Dictionary lookup is faster. You can see a graph above.

Number, 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

Discussion. This test uses only 12 character long strings. It uses only generic collections, and doesn't examine Hashtable, HybridDictionary or SortedDictionary. In my experience, collections like HybridDictionary are not often useful.




Here are guidelines for choosing between List or 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 always have fewer than four items.

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

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

Summary. For lookups, Dictionary is usually a better choice. The time required is flat, an O(1) constant time complexity. The List has an O(N) linear time complexity. Three elements can be looped over faster than looked up in a Dictionary.

Thus I use three elements as the threshold when I will switch to Dictionary lookups from List loops.



© 2007-2021 sam allen. send bug reports to info@dotnetperls.com.