SortedDictionary<比;或(Dictionary<比;手动排序)

本文关键字：排序 SortedDictionary Dictionary | 更新日期: 2023-09-27 18:01:49

考虑到我需要一个排序字典，当我使用SortedDictionary<>而不是Dictionary<>时，是否会有性能影响，所以如果我使用字典，我将不得不手动排序它。哪个更快?SortedDictionary<> or (Dictionary<> + Manual Sort).

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

SortedDictionary还限制了您可以使用的键类型，因为它需要按键排序，而Dictionary则没有，因为它使用哈希。

实际上，哪一个更好取决于您的访问模式，因此最好的方法是针对您的用例测量两者的性能。

这会影响性能。阅读http://msdn.microsoft.com/en-us/library/f7fta44c.aspx

上的注释

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

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

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

你是使用很多物品还是不是很多物品?
你添加新项目的频率与你需要它们排序的频率相比。
你是否做更多的查找或插入

最好的办法是用这两种方法在真实数据上做一些性能测试，看看哪一种更适合您的情况。

这取决于您是在获取排序结果的同时单独向字典中添加数据，还是一次性全部添加。

如果您在较长时间内添加数据，那么每次使用SortedDictionary<>添加数据都会受到较小的性能影响，但是当您最终想要排序结果时，您会立即得到它。例如，如果您等待用户输入添加项，这是理想的，因为小的性能影响是不明显的。

如果您创建一个字典，向其中添加数据，并立即获得排序结果，则Dictionary<T>将更快，因为它使用更快的排序算法(因为它可以一次对所有内容进行排序，而不是在添加项时维护排序结果)。