什么时候我应该使用排序字典而不是字典
本文关键字：字典 排序 我应该 什么时候 | 更新日期: 2023-09-27 17:52:36
正如我在上一篇文章中所写的那样，我对c#世界仍然很陌生，所以我编写了一个小基准来比较字典，哈希表，排序列表和排序字典。测试运行8000次迭代，从50到100000个元素。我测试了添加新元素，搜索元素和循环通过一些随机元素。结果和我预期的一样，除了SortedDictionary的结果让我很困惑……它只是在所有结果中都很慢。我是不是漏掉了排序字典的概念。我已经问过谷歌了，但我发现其他人也得出了同样的测试结果。根据他们测试的实现略有不同。我的问题是:为什么sorteddictionary比其他的慢这么多?
SortedDictionary实现为二叉搜索树。因此，访问一个元素是O(lg(n))。字典是一个哈希表，其访问复杂度为0(1)。
SortedDictionary在需要对数据进行排序时非常有用(Dictionary没有定义的顺序)。
答案很简单，如果您需要一个排序的字典，您将使用SortedDictionary。
请记住，即使它在测试中最后是最慢的，但它仍然不慢。如果您确实需要SortedDictionary的功能，那么它是最佳解决方案。使用Dictionary或SortedList做同样的事情会慢得多。
又是我的问题:为什么sorteddictionary比其他的慢这么多?
Etienne之前已经给出了技术答案，但是要添加一个更"简单"的注释:我猜SortedDictionary的"排序"位部分在插入上增加了一些开销，甚至从Etienne的答案中检索项目。
然而，在一个真实的应用程序中，如果你需要一个"已经排序的字典"，SortedDictionary可能会提供相当大的性能或"感知性能"提升。
希望对你有帮助。