SortedList <>,SortedDictionary <>和Dictionary <>

Question

我发现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是字典中元素的数量.在这方面,它类似于SortedList(TKey,TValue)泛型类.这两个类具有相似的对象模型,并且都具有O(log n)检索.两个类别的不同之处在于内存使用和插入和移除速度:

SortedList(TKey,TValue)比SortedDictionary(TKey,TValue)使用更少的内存.

SortedDictionary(TKey,TValue)对未排序数据具有更快的插入和删除操作:O(log n),而不是SortedList(TKey,TValue)的O(n).

如果列表是从排序数据中一次性填充的,则SortedList(TKey,TValue)比SortedDictionary(TKey,TValue)快.

Answer 2

我会提到词典之间的区别.

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

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

Answer 3

总结性能测试的结果- SortedList vs. SortedDictionary vs. Dictionary vs. 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

1. 当您希望在迭代时按键对集合进行排序时.如果您不需要对数据进行排序,那么只需使用字典就可以获得更好的效果,它会有更好的性能.

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

Answer 5

我可以看到建议的答案集中在性能上。下面提供的文章未提供有关性能的任何新信息，但说明了其基本机制。还要注意，它不关注Collection问题中提到的三种类型，而是处理System.Collections.Generic名称空间的所有类型。

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

提取物：

字典<>

字典可能是最常用的关联容器类。字典是关联查找/插入/删除最快的类，因为它在底下使用哈希表。因为键是散列的，所以键类型应该正确地正确实现GetHashCode（）和Equals（），或者在构造时应为字典提供外部IEqualityComparer。字典中项目的插入/删除/查找时间是摊销的恒定时间-O（1）-这意味着，不管字典有多大，查找某物所花费的时间都保持相对恒定。这对于高速查找是非常理想的。唯一的缺点是，根据使用哈希表的性质，字典是无序的，因此您无法轻松地依次遍历字典中的项目。

SortedDictionary <>

SortedDictionary在用法上类似于Dictionary，但在实现上有很大不同。该SortedDictionary底层使用二叉树通过钥匙来维持秩序中的项目。排序的结果是，用于键的类型必须正确实现IComparable，以便可以正确地对键进行排序。排序后的字典需要一些查找时间，以维护项目的顺序，因此排序字典中的插入/删除/查找时间是对数-O（log n）。一般而言，使用对数时间，您可以将集合的大小加倍，并且只需要执行一次额外的比较即可找到该项目。当您想要快速查找但又希望能够通过键来维护集合时，请使用SortedDictionary。

SortedList <>

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（1）。

词典

记忆

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)

分类词典

记忆

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))

SortedList

记忆

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，找到＃O（log n）i在哪里KeyArray(i).GetHash = Key.GetHash
2. 删除KeyArray(i)＃O（n）
3. 删除ItemArray(i)＃O（n）

获取物品

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

依次通过

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