title: Building a sorted dictionary using ToDictionary
body: <p>I'm not an expert in C# and LINQ.</p>
  
  <p>I have a <code>Dictionary</code>, which I understand a hash table, that is, keys are not sorted.</p>
  
  <pre><code>dataBase = new Dictionary&lt;string, Record&gt;()
  </code></pre>
  
  <p><code>Record</code> is a user-defined class that holds a number of data for a given key string.</p>
  
  <p>I found an interesting example that converts this <code>Dictionary</code> into a <em>sorted</em> dictionary by LINQ:</p>
  
  <pre><code>var sortedDict = (from entry in dataBase orderby entry.Key ascending select entry)
  .ToDictionary(pair =&gt; pair.Key, pair =&gt; pair.Value);
  </code></pre>
  
  <p>This code works correctly. The resulting <code>sortedDict</code> is sorted by keys.</p>
  
  <p><strong>Question</strong>: I found that <code>sortedDict</code> is still a hash table, a type of:</p>
  
  <pre><code>System.Collections.Generic.Dictionary&lt;string, Record&gt;
  </code></pre>
  
  <p>I expected the resulting dictionary should be a sort of <code>map</code> as in C++ STL, which is generally implemented as a (balanced) binary tree to maintain the ordering of the keys. However, the resulting dictionary is still a hash table.</p>
  
  <p>How <code>sortedDict</code> can maintain the ordering? A hash table can't hold the ordering of the keys. Is the implementation of C#'s <code>Generic.Dictionary</code> other than a typical hash table?</p>