title: Optimizing Lookups: Dictionary key lookups vs. Array index lookups
body: <p>I'm writing a 7 card poker hand evaluator as one of my pet projects. While trying to optimize its speed (I like the challenge), I was shocked to find that the performance of Dictionary key lookups was quite slow compared to array index lookups.</p>
  
  <p>For example, I ran this sample code that enumerates over all 52 choose 7 = 133,784,560 possible 7 card hands:</p>
  
  <pre><code>var intDict = new Dictionary&lt;int, int&gt;();
  var intList = new List&lt;int&gt;();
  for (int i = 0; i &lt; 100000; i ++)
  {
      intDict.Add(i, i);  
      intList.Add(i);
  }
  
  int result;
  
  var sw = new Stopwatch();
  sw.Start();
  for (int card1 = 0; card1 &lt; 46; card1++)
    for (int card2 = card1 + 1; card2 &lt; 47; card2++)
      for (int card3 = card2 + 1; card3 &lt; 48; card3++)
        for (int card4 = card3 + 1; card4 &lt; 49; card4++)
          for (int card5 = card4 + 1; card5 &lt; 50; card5++)
            for (int card6 = card5 + 1; card6 &lt; 51; card6++)
              for (int card7 = card6 + 1; card7 &lt; 52; card7++)
                result = intDict[32131]; // perform C(52,7) dictionary key lookups
  sw.Stop();
  Console.WriteLine("time for dictionary lookups: {0} ms", sw.ElapsedMilliseconds);
  
  sw.Reset();
  
  sw.Start();
  for (int card1 = 0; card1 &lt; 46; card1++)
    for (int card2 = card1 + 1; card2 &lt; 47; card2++)
      for (int card3 = card2 + 1; card3 &lt; 48; card3++)
        for (int card4 = card3 + 1; card4 &lt; 49; card4++)
          for (int card5 = card4 + 1; card5 &lt; 50; card5++)
            for (int card6 = card5 + 1; card6 &lt; 51; card6++)
              for (int card7 = card6 + 1; card7 &lt; 52; card7++)
                result = intList[32131]; // perform C(52,7) array index lookups
  sw.Stop();
  Console.WriteLine("time for array index lookups: {0} ms", sw.ElapsedMilliseconds);
  </code></pre>
  
  <p>which outputs:</p>
  
  <pre><code>time for dictionary lookups: 2532 ms
  time for array index lookups: 313 ms
  </code></pre>
  
  <p>Is this type of behavior expected (performance decrease by a factor of 8)? IIRC, a Dictionary has, on average, O(1) lookups, while an array has worst-case O(1) lookups, so I do expect the array lookups to be faster, but not by this much!</p>
  
  <p>I am currently storing poker hand rankings in a Dictionary. I suppose if this is as fast as the dictionary lookups can be, I have to rethink my approach and use arrays instead, although indexing the rankings will get a little tricky and I'll probably have to ask another question about it.</p>