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.`510px`390px`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 `gethashcode`Modulo `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. `This test used random path names ("dliu3ms0.idt") generated by Path.GetRandomFileName, an easy way to get random strings.`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.`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 `hashtable`HybridDictionary `hybriddictionary`SortedDictionary `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. `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 `dictionary`List `list

ETAOIDT- code that was benchmarked: C#IAAITO key always existsTpDT-; CT:Key is used.IAAT{1. Tkrandom TE.AITinTyr.Next(m);IAAT{2. Tkrandom TP.AITP kTyl[n];IAAT{3. See if it exists.AIbool hitTyfalse;ATmd.CT:Key(k))A{AEhitTytrue;A}AAITo code that was benchmarked: C#IAAITO key always existsTpTo; T@-loop is used.IAAT{1. Tkrandom TE.AITinTyr.Next(m);IAAT{2. Tkrandom TP.AITP kTyl[n];IAAT{TWthrough TPsTjsee if it exists.AIbool hitTyfalse;AT@ (TP s2Tpl2)A{AETms2Txk)AE{AEEhitTytrue;AEETGAE}A}INumber, DT- ms, To msIAA1 655EEE 453A2 702EEE 577A3 702EEE 670A4 655EEE 749A5 686EEE 811A6 702EEE 874A7 687EEE 936A8 702EEE 1014A9 702EEE 1077A10 702EEE 1108A11 687EEE 1170A12 718EEE 1232I