1. 当迭代这两个元素中的任何一个元素时，元素将被排序。

2. MSDN 解决了 SortedList<T,V>和 SortedDictionary<T,V>之间的区别:

SortedDictionary (TKey，TValue)泛型类是一个 < a href = “ http://en.wikipedia.org/wiki/Binary _ search _ tree”rel = “ noReferrer”> 二进制搜索 带有 O (log n)检索的 tree ，其中 n 是 在这方面，它类似于 SortedList (TKey, 这两个类具有相似的对象模型，并且 都有 O (logn)检索。这两个类的不同之处在于 memory use and speed of insertion and removal:

SortedList (TKey，TValue)比 SortedDictionary (TKey, TValue).

SortedDictionary (TKey，TValue)插入和删除速度更快 对未排序数据的操作: O (log n) ，而对于 SortedList (TKey，TValue).

如果列表是从已排序的数据一次性全部填充的, SortedList (TKey，TValue)比 SortedDictionary (TKey, TValue).

1. 当迭代集合时，如果希望按键对集合进行排序。如果不需要对数据进行排序，最好使用 Dictionary，它的性能会更好。

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

我会提到字典之间的区别。

上面的图片显示，Dictionary<K,V>在每种情况下都等于或快于 Sorted模拟，但是如果需要元素的顺序，例如打印它们，则选择 Sorted模拟。

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

To summarize the results of a 性能测试-SortedList vs SortedDictionary vs Dictionary vs Hashtable, the results from best to worst for different scenarios:

内存使用情况:

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 循环操作 foreach 循环操作

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

试图为@Lev 提供的每个案例分配一个 表现得分，我使用了以下值:

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

结果是(越高 = 越好) :

Dictionary:       12.0
SortedDictionary:  9.0
SortedList:        6.5

当然，每个用例都会更加重视某些操作。

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

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

摘录:

字典 < >

Dictionary 可能是最常用的关联容器类。Dictionary 是关联查找/插入/删除最快的类，因为 它使用一个哈希表的掩护下。因为键是散列的，所以 键类型应该正确实现 GetHashCode ()和 Equals ()是适当的，或者您应该在构造时为字典提供一个外部的 IEqualityComparer。字典中条目的插入/删除/查找时间是分摊的常量时间 -O (1)-这意味着无论字典变得多大，找到某些条目所需的时间都保持相对恒定。这对于高速查找非常有用。唯一的 downside是字典，由于使用散列表的性质，它是无序的，所以是 you cannot easily traverse the items in a Dictionary in order。

SortedDictionary < >

The SortedDictionary is similar to the Dictionary in usage but very different in implementation. The SortedDictionary 使用隐藏的二叉树来维护按键顺序排列的项. As a consequence of sorting, 用于键的类型必须正确地实现 ICompable so that the keys can be correctly sorted. The sorted dictionary trades a little bit of lookup time for the ability to maintain the items in order, thus insert/delete/lookup times in a sorted dictionary are logarithmic - O(log n). Generally speaking, with logarithmic time, you can double the size of the collection and it only has to perform one extra comparison to find the item. Use the SortedDictionary when you want fast lookups but also want to be able to maintain the collection in order by the key.

SortedList < >

SortedList 是泛型容器中的另一个排序关联容器类。同样是 SortedList，就像 SortedDictionary，uses a key to sort key-value pairs。然而，与 SortedDictionary 不同的是，SortedList 中的项作为项的排序数组存储。这意味着插入和删除是线性的-O (n)-因为删除或添加一个项目可能涉及到在列表中向上或向下移动所有项目。但是，查找时间为 O (log n) ，因为 SortedList 可以使用二进制搜索根据其键查找列表中的任何项。你为什么要这么做？答案是，如果您打算预先加载 SortedList，那么插入会慢一些，但是由于数组索引比跟踪对象链接更快，所以查找比 SortedDictionary 稍快一些。在需要快速查找并按键顺序维护集合的情况下，以及很少插入和删除的情况下，我会再次使用这种方法。

Tentative Summary of underlying Procedures

Feedback is very welcome as I am sure I did not get everything right.

• 所有数组的大小都是 n。
• 非排序数组 = . Add/. delete 是 O (1) ，但. Item (i)是 O (n)。
• 排序数组 = . Add/. delete 是 O (n) ，但. Item (i)是 O (log n)。

字典

记忆

KeyArray(n) -> non-sorted array<pointer>
ItemArray(n) -> non-sorted array<pointer>
HashArray(n) -> sorted array<hashvalue>

加

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

拿开

1. For i = 0 to n，找到 i，其中 HashArray(i) = Key.GetHash # O (log n)(排序数组)
2. 删除 HashArray(i) # O (n)(排序数组)
3. 删除 KeyArray(i) # O (1)
4. 删除 ItemArray(i) # O (1)

去找伊曼

1. For i = 0 to n，找到 i，其中 HashArray(i) = Key.GetHash # O (log n)(排序数组)
2. 返回 ItemArray(i)

循环穿越

1. 返回 ItemArray(i)

分类字典

Memory

KeyArray(n) = non-sorted array<pointer>
ItemArray(n) = non-sorted array<pointer>
OrderArray(n) = sorted array<pointer>

加

1. 加入 KeyArray(n) = PointerToKey # O (1)
2. Add ItemArray(n) = PointerToItem # O(1)
3. For i = 0 to n, find i where KeyArray(i-1) < Key < KeyArray(i) (using ICompare) # O(n)
4. 添加 OrderArray(i) = n # O (n)(排序数组)

拿开

1. For i = 0 to n，在 KeyArray(i).GetHash = Key.GetHash # O (n)处找到 i
2. 删除 KeyArray(SortArray(i)) # O (n)
3. 删除 ItemArray(SortArray(i)) # O (n)
4. 删除 OrderArray(i) # O (n)(排序数组)

去找伊曼

1. For i = 0 to n，在 KeyArray(i).GetHash = Key.GetHash # O (n)处找到 i
2. 返回 ItemArray(i)

循环穿越

1. 返回 ItemArray(OrderArray(i))

分类列表

Memory

KeyArray(n) = sorted array<pointer>
ItemArray(n) = sorted array<pointer>

Add

1. For i = 0 to n，找到 i，其中 KeyArray(i-1) < Key < KeyArray(i)(使用 ICompare) # O (log n)
2. 加入 KeyArray(i) = PointerToKey # O (n)
3. 加入 ItemArray(i) = PointerToItem # O (n)

拿开

1. For i = 0 to n，在 KeyArray(i).GetHash = Key.GetHash # O (log n)处找到 i
2. 删除 KeyArray(i) # O (n)
3. 删除 ItemArray(i) # O (n)

去找伊曼

1. For i = 0 to n, find i where KeyArray(i).GetHash = Key.GetHash # O(log n)
2. Return ItemArray(i)

循环穿越

1. 返回 ItemArray(i)