title: Why c# dictionary foreach loop USUALLY iterates in the same order as insertion
body: <p>According to the common truth and many upvoted answers the C# <code>Dictionary</code> is internally implemented as <code>Hashtable</code>, which if I have a correct understanding means that:</p>
  
  <ol>
  <li><p>the order in which <code>foreach</code> statement iterates over dictionary's items is unpredictable - because behind the scenes every key is being hashed and the index in underlying array is assigned according to this hash value.</p></li>
  <li><p>If want to add let's say keys equal to <code>1, 2, 3, 4, 5, 6, 7</code> it shouldn't matter in which order we will do that, since the only thing that matters regarding the internal representation is the hash value of the key.</p></li>
  </ol>
  
  <p>How is it then possible that if I add the same keys in different order the <code>foreach</code> loop executed after that addition iterates over the keys in the same order as they were added? </p>
  
  <p>What magic implementation stays behind this behavior?</p>
  
  <p>The code snippet I used for testing:</p>
  
  <pre><code>static int[] x =  { 3, 9, 5, 11, 12, 13, 2, 24, 137, 4, 1256, 67, 1, 125555 };
  
  static void Main(string[] args)
  {
      //to avoid any rehashing and collisions issues the capacity is manually set to a value &gt;&gt; than the number of stored items
      Dictionary&lt;int, string&gt; dict = new Dictionary&lt;int, string&gt;(10000);
  
      for (int i = 0; i &lt; x.Length; i++)
      {
          dict.Add(x[i], x[i].ToString());
      }
  
      Console.WriteLine("Foreaching element of dict after inserting from left to right\n");
  
      foreach (var kvp in dict)//this displays items in exactly same order as they were added
      {
          Console.WriteLine(kvp.Key);
      }
  
      dict.Clear();
  
      for (int i = x.Length - 1; i &gt;= 0; i--)
      {
          dict.Add(x[i], x[i].ToString());
      }
  
      Console.WriteLine("Foreaching element of dict after inserting from right to left\n");
  
      foreach (var kvp in dict)//this displays items in exactly same order as they were added
      {
          Console.WriteLine(kvp.Key);
      }
  }
  </code></pre>