C# Dictionary Versus List Lookup Time

Compare the performance of Dictionary and List look up operations in a benchmark.

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.Optimization

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.GetHashCode Modulo

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.Hashtable HybridDictionary SortedDictionary

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.

Dictionary List

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

C# Dictionary Versus List Lookup Time

Related Links:

.Net

Java

Related Links