排序列表<>，SortedDictionary <>和字典<>(

我发现， SortedList<TKey, TValue> SortedDictionary<TKey, TValue>和Dictionary<TKey, TValue>实现相同的接口。

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

Answer 1:

1. 当通过在任两个的元件进行迭代，该元素将被排序。 不是这样的Dictionary<T,V>

2. MSDN地址之间的差值SortedList<T,V>和SortedDictionary<T,V>

所述SortedDictionary（TKEY的，TValue）通用类是二叉搜索树以O（log n）的检索，其中n是字典中的元素的数量。 在这方面，它是类似于排序列表（TKEY的，TValue）通用类。 这两个类具有相似的对象模型，并且都具有O（log n）的检索。 其中两个类的区别是在内存使用和插入和移除的速度：

排序列表（TKEY的，TValue）使用比SortedDictionary（TKEY的，TValue）存储器更少。

SortedDictionary（TKEY的，TValue）具有用于未排序的数据更快地插入和移除操作：O（log n）的，而不是为O（n），用于排序列表（TKEY的，TValue）。

如果该列表是从排序的数据填充全部一次，排序列表（TKEY的，TValue）比SortedDictionary（TKEY的，TValue）更快。

Answer 2:

我想提的字典之间的区别。

上面的图片显示的是Dictionary<K,V>等于或在任何情况下的速度比Sorted的模拟，但是，如果需要的元素顺序，例如，以将它们打印， Sorted一个被选择。

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

Answer 3:

总结出的结果性能测试-排序列表与SortedDictionary与字典与哈希表 ，结果从最好到最差的不同的方案：

内存使用情况：

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:

1. 当你想收集到的关键，当你遍历它进行排序。 如果您不需要您的数据进行排序做，你只是一个字典更好，这将有更好的表现。

2. 排序列表和SortedDictionary几乎做同样的事情，但实现方式不同，因此具有不同的优势和劣势在这里解释 。

Answer 5:

我可以看到所提出的答案注重业绩。 下面提供的文章没有提供有关性能什么新的东西，但它说明了潜在的机制。 还要注意不集中在这三个Collection的问题mentionned类型，而是将不会忽略所有类型System.Collections.Generic命名空间。

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

摘录：

Dictionnary <>

该词典可能是最常用的关联容器类。 该字典是关联查找/插入速度最快的类/删除，因为它底层使用哈希表 。 因为密钥被散列， 密钥类型应该正确地适当地执行的GetHashCode（）和equals（）或你应该提供一个外部的IEqualityComparer对施工字典。 插入/删除字典中的项目/查找时间分期常量时间 - O（1） - 这意味着不管字典有多大得到，它需要找到一些时间保持相对恒定。 这对于高速查找高度期望的。 唯一的缺点是，字典，通过使用哈希表的本质，是无序的，所以你不能轻易穿越，才能在字典中的项目 。

SortedDictionary <>

该SortedDictionary是使用类似于字典，但实施非常不同。 该SortedDictionary底层使用二叉树通过钥匙来维持秩序中的项目 。 作为排序的结果， 用于密钥类型必须正确地实现IComparable，使得密钥可以正确排序。 该分类辞典行业的查找时间一点点，以保持项目有序，从而插入/删除/查询时间在有序字典的能力，是对数 - O（log n）的。 一般来说，具有对数时间，你可以双击该集合的大小，而且只需要执行一个额外的比较，找出该项目。 使用SortedDictionary当你想快速查找，也希望能够通过的关键，保持集合中的顺序。

排序列表<>

该排序列表是在通用容器中的其他排序关联容器类。 再次排序列表，像SortedDictionary， 使用一键键值对排序 。 不像SortedDictionary，然而， 在一个排序列表项被存储为项目的排序的阵列 。 这意味着，插入和缺失是线性 - O（N） - 因为删除或添加一个项目可以包括向上或向下移动列表中的所有项目。 查找时间，但为O（log n）的，因为排序列表可以使用二进制搜索它的键查找列表中的任何项目。 那么，为什么你想这样做吗？ 那么，答案是如果你要加载SortedList的上行方面，插入会比较慢，但是因为数组索引比下面的对象链接速度更快，查找是稍快比SortedDictionary。 再次我会在你想快速查找和想要的关键，维持为了收集，并在插入和缺失是罕见的情况下使用这个。

---

底层程序的暂定概要

反馈是非常欢迎的，因为我相信我没有得到的一切权利。

• 所有的数组大小的n 。
• 非排序后的数组=。新增/卸下摆臂是O（1），但.Item（ⅰ）为O（n）。
• 排序后的数组=。新增/卸下摆臂为O（n），但.Item（i）是O（1）。

Dictionnary

记忆

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. For i = 0 to n ，返回ItemArray(i)

SortedDictionary

记忆

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

加

1. 添加KeyArray(n) = PointerToKey ＃O（1）
2. 添加ItemArray(n) = PointerToItem ＃O（1）
3. For i = 0 to n ，找到i其中KeyArray(i-1) < Key < KeyArray(i)使用ICompare ）＃O（n）的
4. 添加OrderArray(i) = n ＃为O（n）（排序后的数组）

去掉

1. For i = 0 to n ，找到i其中KeyArray(i).GetHash = Key.GetHash ＃O（n）的
2. 除去KeyArray(SortArray(i)) ＃O（1）
3. 除去ItemArray(SortArray(i)) ＃O（1）
4. 除去OrderArray(i)为O（n）（排序后的数组）

找项目

1. For i = 0 to n ，找到i其中KeyArray(i).GetHash = Key.GetHash ＃O（n）的
2. 返回ItemArray(i)

依次通过

1. For i = 0 to n ，返回ItemArray(OrderArray(i))

排序列表

记忆

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

加

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 ，找到i其中KeyArray(i).GetHash = Key.GetHash ＃O（log n）的
2. 除去KeyArray(i) ＃O（n）的
3. 除去ItemArray(i) ＃O（n）的

找项目

1. For i = 0 to n ，找到i其中KeyArray(i).GetHash = Key.GetHash ＃O（log n）的
2. 返回ItemArray(i)

依次通过

1. For i = 0 to n ，返回ItemArray(i)

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

当然，每一个用例将给予更大权重，以某些操作。

文章来源: SortedList<>, SortedDictionary<> and Dictionary<>