使用ToDictionary构建排序字典

Question

我不是C#和LINQ方面的专家。

我有一个Dictionary，我理解一个哈希表，也就是说，键没有排序。

dataBase = new Dictionary<string, Record>()

Record是一个用户定义的类，它包含给定键字符串的大量数据。

我发现了一个有趣的例子，它通过LINQ将这个Dictionary转换为一个排序字典：

var sortedDict = (from entry in dataBase orderby entry.Key ascending select entry)
.ToDictionary(pair => pair.Key, pair => pair.Value);

此代码工作正常。得到的sortedDict按键排序。

问题：我发现sortedDict仍然是一个哈希表，一种类型为：

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

我期望得到的字典应该是一种map，就像在C++ STL中一样，它通常作为一个(平衡的)二叉树来实现，以维护键的排序。但是，生成的字典仍然是一个哈希表。

sortedDict如何维护订单？哈希表无法保存键的顺序。C#的Generic.Dictionary的实现不是一个典型的哈希表吗？

Answer 1

Dictionary维护两个数据结构:一个按插入顺序排列的平面数组用于枚举，另一个哈希表用于按键检索。

如果在排序集上使用ToDictionary()，则枚举时它将是有序的，但不会按顺序进行维护。任何新插入的项目都将在枚举时添加到后面。

编辑:如果您想依赖这种行为，我建议您查看MSDN文档，看看这是否有保证，或者只是附带的。

Answer 2

SortedDictionary在构造函数中使用现有的Dictionary，因此创建SortedDictionary非常容易。

但是，如果需要，可以将其作为扩展方法，然后可以使用dataBase.ToSortedDictionary()。

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

Answer 3

linq代码看起来构建了一个排序字典，但是排序是由linq完成的，而不是字典本身，而SortedDictionary应该自己维护排序。

若要获得排序字典，请使用new SortedDictionary<string, Record>(yourNormalDictionary);

如果您想让它更容易访问，那么您可以为i枚举写一个扩展：

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));
    }
}