SortedList<>、SortedDictionary<>和字典<>

Question

我发现 SortedList SortedDictionary 和 Dictionary 实现相同的接口。

1. 我们什么时候应该选择 SortedList 和 SortedDictionary 而不是 Dictionary？
2. SortedList 和 SortedDictionary 在应用方面有什么区别？

Answer 1

1. 当迭代两者中的任何一个中的元素时，元素将被排序。 Dictionary 则不然。

2. MSDN 解决了 SortedList 和 SortedDictionary：

SortedDictionary(TKey, TValue) 泛型类是一个二分搜索
树，检索时间复杂度为 O(log n)，其中 n 是其中的元素数量
字典。在这方面，它类似于 SortedList(TKey,
TValue) 泛型类。这两个类具有相似的对象模型，并且
两者都有 O(log n) 检索。这两个类的不同之处在于
内存使用和插入和删除速度：

SortedList(TKey, TValue) 使用的内存比 SortedDictionary(TKey,
T值）。

SortedDictionary(TKey, TValue) 具有更快的插入和删除速度
未排序数据的操作：O(log n) 而不是 O(n)
排序列表（TKey，TValue）。

如果列表是从排序数据一次性填充的，
SortedList(TKey, TValue) 比 SortedDictionary(TKey,
T值）。

Answer 2

我会提到字典之间的差异。

上图显示 Dictionary 在每种情况下都等于或快于 Sorted 模拟，但如果需要元素的顺序（例如打印它们），已排序 选择其中之一。

源： http://people.cs .aau.dk/~normark/oop-csharp/html/notes/collections-note-time-complexity-dictionaries.html

Answer 3

总结性能测试的结果 - SortedList、SortedDictionary、Dictionary、Dictionary。 Hashtable，不同场景下从最好到最差的结果：

内存使用：

SortedList<T,T>
Hashtable
SortedDictionary<T,T>
Dictionary<T,T>

插入：

Dictionary<T,T>
Hashtable
SortedDictionary<T,T>
SortedList<T,T>

搜索操作：

Hashtable
Dictionary<T,T>
SortedList<T,T>
SortedDictionary<T,T>

foreach 循环运营

SortedList<T,T>
Dictionary<T,T>
Hashtable
SortedDictionary<T,T>

Answer 4

我可以看到建议的答案侧重于性能。下面提供的文章没有提供任何有关性能的新内容，但它解释了底层机制。另请注意，它并不关注问题中提到的三个 Collection 类型，而是解决 System.Collections.Generic 命名空间的所有类型。

http:// /geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx

摘录：

字典<>

字典可能是最常用的关联容器类。 Dictionary 是关联查找/插入/删除最快的类，因为它在幕后使用哈希表。由于键经过哈希处理，键类型应正确实现 GetHashCode() 和 Equals()，或者您应在构造时向字典提供外部 IEqualityComparer。字典中项目的插入/删除/查找时间是摊销常数时间 - O(1) - 这意味着无论字典有多大，查找某些内容所需的时间都保持相对恒定。这对于高速查找来说是非常理想的。唯一的缺点是，字典本质上使用哈希表，是无序的，因此您无法轻松地按顺序遍历字典中的项目。

排序字典<>

SortedDictionary 在用法上与 Dictionary 类似，但在实现上却截然不同。 SortedDictionary 在幕后使用二叉树来按键按顺序维护项目。作为排序的结果，用于键的类型必须正确实现 IComparable，以便可以正确对键进行排序。排序字典用一点查找时间来换取按顺序维护项目的能力，因此排序字典中的插入/删除/查找时间是对数的 - O(log n)。一般来说，使用对数时间，您可以将集合的大小加倍，并且只需执行一次额外的比较即可找到该项目。当您想要快速查找但又希望能够通过键按顺序维护集合时，请使用 SortedDictionary。

排序列表<>

SortedList 是通用容器中的另一个排序关联容器类。同样，SortedList 与 SortedDictionary 一样，使用键对键值对进行排序。然而，与 SortedDictionary 不同的是，SortedList 中的项目存储为已排序的项目数组。这意味着插入和删除是线性的 - O(n) - 因为删除或添加项目可能涉及在列表中向上或向下移动所有项目。然而，查找时间为 O(log n)，因为 SortedList 可以使用二分搜索通过其键查找列表中的任何项目。那么你为什么要这样做呢？好吧，答案是，如果您要预先加载 SortedList，则插入会更慢，但由于数组索引比遵循对象链接更快，因此查找比 SortedDictionary 稍快。在您想要快速查找并希望按键按顺序维护集合以及插入和删除很少见的情况下，我会再次使用它。

---

基本过程的初步总结

非常欢迎反馈，因为我确信我没有把所有事情都做对。

• 所有数组的大小都是n。
• 非排序数组 = .Add/.Remove 的复杂度为 O(1)，但 .Item(i) 的复杂度为 O(n)。
• 排序数组 = .Add/.Remove 的时间复杂度为 O(n)，但 .Item(i) 的时间复杂度为 O(log n)。

字典

内存

KeyArray(n) ->非排序数组<指针>
ItemArray(n) ->非排序数组<指针>
HashArray(n) ->排序数组

添加

1. 添加HashArray(n) = Key.GetHash # O(1)
2. 添加KeyArray(n) = PointerToKey # O(1)
3. 添加 ItemArray(n) = PointerToItem # O(1)

删除

1. 对于 i = 0 到 n，找到 < code>i where HashArray(i) = Key.GetHash # O(log n)（排序数组）
2. 删除 HashArray(i) # O(n) （排序数组）
3. 删除 KeyArray(i) # O(1)
4. 删除 ItemArray(i) # O(1)

获取项目

1. 对于 i = 0 到 n，找到 i，其中 HashArray(i) = Key.GetHash # O(log n)（排序数组）
2. Return ItemArray(i)

循环

1. 对于 i = 0 到 n，返回 ItemArray(i)

SortedDictionary

内存

KeyArray(n) = 非排序数组<指针>
ItemArray(n) = 非排序数组<指针>
OrderArray(n) = 排序数组

Add

1. Add KeyArray(n) = PointerToKey # O(1)
2. Add ItemArray( n) = PointerToItem # O(1)
3. 对于 i = 0 到 n，找到 i，其中 KeyArray(i-1) 键< KeyArray(i) （使用 ICompare） # O(n)
4. 添加 OrderArray(i) = n # O(n) （排序数组）

删除

1. 对于 i = 0 到 n，找到 i，其中 KeyArray(i).GetHash = Key.GetHash # O(n )
2. 删除KeyArray(SortArray(i)) # O(n)
3. 删除ItemArray(SortArray(i)) # O(n)
4. 删除OrderArray(i)< /code> # O(n)（排序数组）

获取项目

1. 对于 i = 0 到 n，找到 i 其中 KeyArray( i).GetHash = Key.GetHash # O(n)
2. 返回 ItemArray(i)

循环

1. For i = 0 到 n, return ItemArray(OrderArray(i))

SortedList

内存

KeyArray(n) = 排序数组<指针>
ItemArray(n) = 排序数组

添加

1. 对于 i = 0 到 n，找到 i 其中 <代码>KeyArray(i-1) <键< KeyArray(i) （使用 ICompare） # O(log n)
2. 添加 KeyArray(i) = PointerToKey # O(n)
3. 添加 ItemArray( i) = PointerToItem # O(n)

删除

1. 对于 i = 0 到 n，找到 i 其中 KeyArray( i).GetHash = Key.GetHash # O(log n)
2. 删除 KeyArray(i) # O(n)
3. 删除 ItemArray(i) # O( n)

获取项目

1. 对于 i = 0 到 n，找到 i，其中 KeyArray(i).GetHash = Key.GetHash code> # O(log n)
2. Return ItemArray(i)

循环

1. 对于 i = 0 到 n，返回 ItemArray(i ）

Answer 5

1. 当您希望在迭代集合时按键对集合进行排序时。如果您不需要对数据进行排序，那么最好只使用字典，它会具有更好的性能。

2. SortedList 和 SortedDictionary 几乎做同样的事情，但实现方式不同，因此具有不同的优点和缺点 在这里解释。

Answer 6

尝试为 @Lev 提出的每个案例分配性能分数，我使用了以下值：

• O(1) = 3
• O(log n) = 2
• O(n) = 1
• O(1)或 O(n) = 2
• O(log n) 或 O(n) = 1.5

结果是（越高=越好）：

Dictionary:       12.0 
SortedDictionary:  9.0 
SortedList:        6.5

当然，每个用例都会给某些操作更多的权重。