C# Dictionary Versus List Lookup Time

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.

GetHashCodeModulo

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#
    String key always exists in Dictionary; ContainsKey is used.

// 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#
    String key always exists in List; foreach-loop is used.

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

HashtableHybridDictionarySortedDictionary

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.

Related Links