Building a sorted dictionary using ToDictionary

Question

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?

Answer 1

SortedDictionary takes an existing Dictionary in the constructor so making a SortedDictionary is very easy.

But you can make it an extension method if you want then you can use dataBase.ToSortedDictionary()

public static SortedDictionary<K, V> ToSortedDictionary<K,V>(this Dictionary<K, V> existing)
{
    return new SortedDictionary<K, V>(existing);
}

Answer 2

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.

Answer 3

the linq code looks building a sorted dictionary, but the sorting is done by the linq, not the dictionary itself, whereas a SortedDictionary should maintain the sorting by itself.

to get a sorted dictionary, use new SortedDictionary<string, Record>(yourNormalDictionary);

if you want to make it more accessible, then you may write an extension to the ienumerable:

public static class Extensions
{
    public static SortedDictionary<T1, T2> ToSortedDictionary<T1, T2>(this IEnumerable<T2> source, Func<T2, T1> keySelector)
    {
        return new SortedDictionary<T1, T2>(source.ToDictionary(keySelector));
    }
}