使用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

SortedDictionaryDictionary在构造函数中使用一个现有的,因此制作一个SortedDictionary非常简单.

但是如果你想要,那么你可以使它成为一种扩展方法 dataBase.ToSortedDictionary()

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