SortedDictionary<>或(Dictionary<>手动排序)

Question

当我使用SortedDictionary<>而不是Dictionary<>时，考虑到我需要一个排序字典，所以如果我使用一个字典，我将不得不手动对它进行排序，这是否会影响性能。哪个更快？SortedDictionary<>和(Dictionary<> +手动排序)。

Answer 1

插入一个对数是O( SortedDictionary (N))，所以插入n个项是O( into (N))。相反，插入到一个对数是O(1)，所以插入n个项是O(n)，但是在使用之前需要对这些项进行排序，这是O(n Dictionary (N))。基于这一点，没有太大的区别，但是Dictionary有散列的开销，而SortedDictionary可能有更差的内存局部性，因为它可能是作为链接结构实现的。

SortedDictionary还对您可以使用的键类型进行了限制，因为它需要按键排序，而字典没有限制，因为它使用散列。

实际上，哪一个更好取决于您的访问模式，所以最好的做法是针对您的用例来衡量两者的性能。

Answer 2

这对性能有影响。在http://msdn.microsoft.com/en-us/library/f7fta44c.aspx上阅读评论

基本上，SortedDictionary<T>是一个二进制搜索树，而Dictionary<T>是一个哈希表。

对于插入、删除和随机查找，Dictionary<T>会更快。如果你按顺序进行不频繁的修改和频繁的列表，SortedDictionary会更快。如果您频繁地进行修改和随机查找，并且很少需要排序然后输出，那么Dictionary的速度会更快。

Answer 3

这真的取决于你是如何使用字典的。

• 你使用了很多项目还是不是很多。
• 与需要排序时相比，添加新项的频率如何。
• 您是否对

执行更多的查找或插入操作

最好的做法是使用这两种方法在真实数据上进行一些性能测试，看看哪种方法更适合您的环境。