SortedDictionary <>或（Dictionary <> Manual Sort）

Question

当我使用SortedDictionary<>而不是Dictionary<>考虑到我需要一个有序的词典时，性能是否受到影响，所以如果我使用了词典，我将不得不手动排序它。哪个会更快？ SortedDictionary<>或（Dictionary<> +手动排序）。

Answer 1

插入到SortedDictionary是O（log（n）），所以插入n个项目是O（n log（n））。相反，插入到Dictionary中的是O（1），因此插入n个项目是O（n），但是您需要在使用之前对项目进行排序，即O（n log（n））。基于此，没有太大的区别，但Dictionary具有散列的开销，而SortedDictionary可能具有更差的内存局部性，因为它可能实现为链接结构。

SortedDictionary还对可以使用的键类型设置限制，因为它需要按键排序，而Dictionary不使用散列。

真的，哪个更好取决于你的访问模式，所以最好的做法是衡量你的用例的性能。

Answer 2

有一个性能问题。阅读http://msdn.microsoft.com/en-us/library/f7fta44c.aspx

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

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

Answer 3

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

• 你使用了很多物品还是不是很多物品。
• 与您需要排序时相比，您添加新项目的频率如何。
• 你做更多的查找或插入

做的最好的事情就是做真实上下的数据有两种方法一些性能测试，看看哪些适合你的情况更好。

Answer 4

这取决于您是否将数据添加到字典中，与获取排序结果分开，还是一次完成。

如果您在较长时间内添加数据，您将使用SortedDictionary<>获得每次添加的小性能打击，但是当您最终希望得到排序结果时，您可以立即得到它。例如，如果您等待用户输入添加项目，这是理想的，因为小的性能点击并不明显。

如果您创建一本词典，向其中添加数据并立即获取排序结果，则Dictionary<T>会更快，因为它使用更快的排序算法（因为它可以一次排序，而不是维护排序结果而物品被添加）。