Building a sorted dictionary using ToDictionary
c#, dictionary, hashtable
Solution
`Dictionary` maintains two data structures: a flat array that's kept in insertion order for enumeration, and the hash table for retrieval by key.
If you use `ToDictionary()` on a sorted set, it will be in order when enumerated, but it won't be maintained in order. Any newly inserted items will be added to the back when enumerating.
Edit: If you want to rely on this behaviour, I would recommend looking at the MSDN docs to see if this is guaranteed, or just incidental.
Problem
I'm not an expert in C# and LINQ. I have a `Dictionary`, which I understand a hash table, that is, keys are not sorted. ``` dataBase = new Dictionary<string, Record>() ``` `Record` is a user-defined class that holds a number of data for a given key string. I found an interesting example that converts this `Dictionary` into a sorted dictionary by LINQ: ``` var sortedDict = (from entry in dataBase orderby entry.Key ascending select entry) .ToDictionary(pair => pair.Key, pair => pair.Value); ``` This code works correctly. The resulting `sortedDict` is sorted by keys. Question: I found that `sortedDict` is still a hash table, a type of: ``` System.Collections.Generic.Dictionary<string, Record> ``` I expected the resulting dictionary should be a sort of `map` 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. How `sortedDict` can maintain the ordering? A hash table can't hold the ordering of the keys. Is the implementation of C#'s `Generic.Dictionary` other than a typical hash table?