何时应该使用 SortedDictionary 而不是 Dictionary？

Question

正如我在先前的一些文章中所写的，我对C#编程还比较新，因此我编写了一个小型基准测试来比较Dictionary、Hashtable、SortedList和SortedDictionary。测试运行8000次，元素数量从50到100000个不等。我测试了添加新元素、查找元素和随机遍历一些元素的速度。结果符合我的预期，除了SortedDictionary的结果让我感到困惑......它在所有结果中都很慢。所以我是否忽略了有关已排序字典的概念。我已经问过谷歌，但我发现其他人也得出了相同的测试结果，尽管基于他们的测试实现略有不同。再次提问：为什么SortedDictionary比其他所有东西都要慢那么多？

- sra

Answer 1

SortedDictionary是一个二叉搜索树实现的数据结构，因此访问元素的时间复杂度为O(lg(n))。Dictionary是一个哈希表，访问元素的时间复杂度为O(1)。

当你需要数据排序时，SortedDictionary非常有用（Dictionary没有定义顺序）。大多数情况下，使用Dictionary就可以了。

- Etienne de Martel

---

作为对“为什么 SortedDictionary 比其他所有数据结构都要慢？”这个问题的直接回应：这是CPU使用率和内存使用率之间的权衡。字典（Dictionary）比SortedDictionary更快，因为它实现为哈希表，这是一种旨在利用过剩内存尽可能少地使用操作的算法。SortedDictionary是二叉搜索树，这是一种旨在使用尽可能少的RAM来执行尽可能多的操作的算法。 - M-Pixel

INB4：是的，那些对哈希表和二叉搜索树背后动机的描述过于简化了。 - M-Pixel

性能不仅仅是大O表示法。一个O(1)的操作可能比进行25次树搜索还要久。我并不认为这种情况会发生，但这个答案并没有告诉你在哪些情况下应该使用它们。 - Justin Meiners

对于大多数用例，当您不需要按键排序数据时，仍然适用于字典。当然，您应该始终进行分析，但是初始实现应该使用字典，除非需要排序或分析显示使用SortedDictionary更有效。 - Etienne de Martel

排序字典的一个例子是，如果您需要按键的排序顺序循环遍历所有元素，则会非常有用。标准字典不会按排序顺序循环遍历键。另一个好处是，如果您需要在调试时按排序顺序查看值，这对我个人来说非常有用，以查看哪些键丢失了，但您可能希望将其更改回字典以供生产代码使用。如果您只需要通过已知键查找值，则排序字典提供很少或没有额外的价值。 - user3308241

Answer 2

答案很简单，如果需要排序的字典，您应该使用 SortedDictionary。

请记住，即使它在您的测试中最终变得最慢，它仍然不慢。 如果您需要完全相同的功能，那么 SortedDictionary 是最佳解决方案。 使用 Dictionary 或 SortedList 实现相同的功能将会慢得多。

- Guffa

---

这个答案基本上回答了这个问题：“什么时候需要使用SortedDictionary？”说：“当你需要的时候！”这一点也不有帮助。请至少给出一个使用SortedDictionary的好处的例子。 - Jack Miller

@JackMiller：你为什么认为需要一个具体的例子？被接受的答案没有给出任何例子。 - Guffa

被接受的答案解决了性能问题（不需要示例）。这个答案涉及到标题中的问题：“何时应该使用SortedDictionary而不是Dictionary？”要回答这样的问题，可以定义（普遍适用的）规则（这将非常困难），或者给出一些具体的例子。 - Jack Miller

Answer 3

再次提问：为什么SortedDictionary比其他字典慢这么多？

Etienne之前已经给出了技术上的答案，但是我想补充一些更加通俗易懂的解释：我猜“Sorted”部分会在插入和获取项时增加一些开销，正如Etienne的回答所示。

然而，在实际应用中，如果您需要在某个时刻使用“已排序的字典”，则SortedDictionary可能会提供相当大的性能或“感知性能”增益。

希望这有所帮助。

- Jeroen

---

我认为使用SortedDictionary在大多数情况下可以更快地“检索项目”。 - Grantly

在大多数情况下，这取决于字典的大小。一个包含3个项的SortedDictionary可能比一个包含3个项的Dictionary更快读取，而一个包含15个项的SortedDictionary最终会变得更慢。 - M-Pixel