Creating a Sorted Dictionary Using ToDictionary

Question

I am not an expert in C # and LINQ.

I have a Dictionary , which I understand hash table, that is, keys are not sorted.

 dataBase = new Dictionary<string, Record>() 

Record is a custom class that contains a series 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 is working correctly. The resulting sortedDict sorted by key.

Question : I found that sortedDict is still a hash table, type:

 System.Collections.Generic.Dictionary<string, Record> 

I expected that the resulting dictionary should be a kind of map , as in C ++ STL, which is usually implemented as a (balanced) binary tree to maintain key order. However, the resulting dictionary is still a hash table.

How can sortedDict maintain order? A hash table cannot hold key order. Is the C # Generic.Dictionary different from a typical hash table?

Answer 1

Dictionary supports two data structures: a flat array, which is stored in insertion order for listing, and a hash table for searching by key.

If you use ToDictionary() in a sorted set, it will be fine if it is specified, but it will not be supported in order. Any newly inserted items will be added to the back when enumerated.

Edit: If you want to rely on this behavior, I would recommend looking at the MSDN docs to make sure it is guaranteed or just by accident.

Answer 2

SortedDictionary takes an existing Dictionary in the constructor, so making SortedDictionary very simple.

But you can do this with an extension method, if you want, 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 3

linq code is looking to build a sorted dictionary, but sorting is done using linq, not the dictionary itself, while SortedDictionary must support sorting by itself.

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

if you want to make it more accessible, you can write an extension for 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)); } }