logo标签列表

SortedList<>, SortedDictionary<> and Dictionary<>

c#genericsdictionarysortedlistsorteddictionary
128

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

  1. 什么时候我们应该选择使用 SortedList 和 SortedDictionary 而不是 Dictionary？
  2. 在应用程序方面，SortedList 和 SortedDictionary 有什么区别？
请参见https://dev59.com/b3NA5IYBdhLWcg3wgeEd。 - nawfal
6个回答
120

  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)更快。

25
另一个实际的区别是，在SortedList中，您可以通过索引检索（与按键值检索相反），而在SortedDictionary中则不行。 - Andrew Savinykh
78
3
很好的概述。虽然不在原问题中，但需要注意的是，如果您在这些字典之间选择“不可变”的版本，那么“已排序”的版本通常比非排序版本快约40-50％（仍为“O(log(n))”每个操作明显更快）。计时可能因输入的排序程度而异。请参阅 https://dev59.com/dV0b5IYBdhLWcg3wLOg2#30638592 - Abel
28

为了总结性能测试 - 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>
2
当检查这些测试结果时，人们可以质疑SortedDictionary的存在意义。 - MÇT
2
如果您的“Collection”需要进行“排序”，那么您可以忘记“Hashtable”和“Dictionary”：如果您一次性填充了Collection->请使用SortedList，但是如果您预计经常需要添加和删除项->请使用SortedDictionary。 - Ama
1
也许有必要澄清 sorted 的含义：当你使用 For Each MyItem in Collection 而不是按照你最初 .Add 添加这些项的顺序进行处理时，一个经过 sorted 的 Collection 将根据 Key 值上的标准（由 IComparer 定义）对它们进行排序。例如，如果你的 Keys 是字符串，则默认情况下，你的 Collection 将按照你的 Keys 的字母顺序进行处理，但你始终可以定义自定义排序规则。 - Ama
20
我看到提出的答案都注重性能。下面提供的文章并没有关于性能方面的新内容，但它解释了底层机制。还需要注意的是，它不仅关注问题中提到的三种{{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<>

SortedDictionary在用法上与Dictionary类似，但实现方式非常不同。 SortedDictionary在内部使用二叉树来按键维护项目的顺序。由于排序的结果，用于键的类型必须正确实现IComparable以便正确排序键。排序字典为了能够按键维护集合的顺序，牺牲了一点查找时间，因此排序字典中的插入/删除/查找时间是对数级别 - O(log n)。通常情况下，使用对数时间，你可以将集合的大小翻倍，并且只需要执行一个额外的比较即可找到该项。当您想要快速查找但又想按键维护集合顺序时，请使用SortedDictionary。

SortedList<>

SortedList是通用容器中的另一种排序关联容器类。与SortedDictionary一样，SortedList使用一个键来对键值对进行排序。但与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 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. 对于 i = 0 to n，找到 i 其中 HashArray(i) = Key.GetHash # O(log n) (有序数组)
  2. 返回 ItemArray(i)

循环遍历

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

SortedDictionary

内存

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

添加

  1. 添加KeyArray(n) = PointerToKey # O(1)
  2. 添加ItemArray(n) = PointerToItem # O(1)
  3. For i = 0 to n，使用ICompare查找i，其中KeyArray(i-1) < Key < KeyArray(i) # 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(n)
  3. 移除ItemArray(SortArray(i)) # O(n)
  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) = 排序后的指针数组<pointer>
ItemArray(n) = 排序后的指针数组<pointer>

添加

  1. 对于 i = 0 到 n，使用 ICompare 找到满足条件的 i，其中 KeyArray(i-1) < Key < KeyArray(i) # 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 # O(log n)
  2. 返回 ItemArray(i)

循环遍历

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

  1. 当您在迭代集合时希望按键排序时，请使用SortedDictionary。如果您不需要数据排序，则更适合使用普通字典(Dictionary)，它的性能更好。

  2. SortedList和SortedDictionary基本上执行相同的操作，但是它们的实现方式不同，因此具有不同的优点和缺点，详见这里。

0

尝试为@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

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

2
作为经验法则，O(log n)的权重将是log(n)/log(2)（每次n加倍+1），而O(n)的权重将是n。因此，对于大小不超过4的情况，您的权重计算是正确的。任何超过这个范围的大小都会迅速增加您的2:1比率。例如，如果n=100，则应该有O(log n)=15。按照类似的思路，您的O(1)将权重为100。结论：O(n)很快就会输掉这场战斗。如果没有输，那么意味着您的数组很小，那么效率就不是问题了。 - Ama
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接