我什么时候应该使用排序字典而不是字典
正如我在上一篇文章中所写的那样，我对 C# 世界还很陌生，因此我编写了一个小基准来相互比较 Dictionary、Hashtable、SortedList 和 SortedDictionary。该测试运行 8000 次迭代和 50 到 100000 个元素。我测试了添加新元素、搜索元素以及随机循环某些元素。结果正如我所期望的那样，除了 SortedDictionary 的结果，这让我很困惑......所有结果都很慢。我是否遗漏了一些有关排序字典概念的内容。我已经问过谷歌，但我发现其他人也得出了相同的测试结果。根据测试的实施情况略有不同。我的问题又来了：为什么 SortedDicrionary 比其他所有的慢得多？
As I wrote in some of my last posts I am still quite new to the c# world so it comes that I wrote small benchmark to compare Dictionary, Hashtable, SortedList and SortedDictionary against each other. The test runs with 8000 iterations and from 50 to 100000 elements. I tested adding of new elements, search for elements and looping through some elements all random. The results was as I expected them to be except the result of the SortedDictionary which was much confusing for me... It was just slow in all results. So did I missing sometging about the concept of a sorted dictionary. I already asked google but All that I found out was that others had come to the same test result. Slightly different based on their implementation of the test. Again my question: why is the SortedDicrionary so much slower than all the others?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
SortedDictionary 被实现为二叉搜索树。因此，访问一个元素的时间复杂度为 O(lg(n))。 Dictionary 是一个哈希表，访问复杂度为 O(1)。
当您需要对数据进行排序（字典没有定义的顺序）时，SortedDictionary 非常有用。字典适用于大多数情况。
A SortedDictionary is implemented as a binary search tree. Therefore, accessing an element is O(lg(n)). A Dictionary is a hash table, and has a complexity of O(1) for access.
A SortedDictionary is quite useful when you need the data to be sorted (a Dictionary has no defined order). Dictionary is appropriate for most cases.
答案很简单，如果您需要已排序的字典，则可以使用
SortedDictionary。请记住，尽管它在测试中最终成为最慢的，但它仍然不慢。如果您需要的正是
SortedDictionary的功能，那么它是最好的解决方案。使用Dictionary或SortedList执行相同操作会慢得多。The answer is simply that you would use the
SortedDictionaryif you need a dictionary that is sorted.Remember that eventhough it ended up as slowest in your tests, it's still not slow. If you need exactly what the
SortedDictionarydoes, it's the best solution. To do the same using aDictionaryor aSortedListwould be very much slower.艾蒂安之前已经给出了技术答案，但要添加更“简单”的评论：我猜想 SortedDictionary 的“排序”位部分会在插入甚至检索项目上带来一些开销，正如艾蒂安的答案所示。
然而，在真实的应用程序中，如果您在应用程序中的某个时间需要“已排序的字典”，则 SortedDictionary 可能可以提供相当大的性能或“感知性能”提高。
希望有帮助。
Etienne already gave the technical answer before, but to add a more 'plain' remark: I'd guess that the "Sorted" bit part of a SortedDictionary puts some overhead on inserts and even retrieving items as it seems from Etienne's answer.
However, in a real app a SortedDictionary can probably provide considerable performance or 'perceived performance' increase if you need an "already sorted dictionary" at some time in your app.
Hope that helps.