C# SortedList<>、SortedDictionary<> 和 Dictionary<>

SortedList<>, SortedDictionary<> and Dictionary<>

提问by Sunder

I find that SortedList<TKey, TValue>SortedDictionary<TKey, TValue>and Dictionary<TKey, TValue>implement the same interfaces.

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

1. When should we opt for SortedListand SortedDictionaryover Dictionary?
2. What is the difference between SortedListand SortedDictionaryin terms of application?

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

采纳答案by Szymon Rozga

1. When iterating over the elements in either of the two, the elements will be sorted. Not so with Dictionary<T,V>.

2. MSDNaddresses the difference between SortedList<T,V>and SortedDictionary<T,V>:

1. 当迭代两者中的任何一个中的元素时，元素将被排序。不是这样的Dictionary<T,V>。

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

The SortedDictionary(TKey, TValue) generic class is a binary search treewith O(log n) retrieval, where n is the number of elements in the dictionary. In this respect, it is similar to the SortedList(TKey, TValue) generic class. The two classes have similar object models, and both have O(log n) retrieval. Where the two classes differ is in memory use and speed of insertion and removal:

SortedList(TKey, TValue) uses less memory than SortedDictionary(TKey, TValue).

SortedDictionary(TKey, TValue) has faster insertion and removal operations for unsorted data: O(log n) as opposed to O(n) for SortedList(TKey, TValue).

If the list is populated all at once from sorted data, SortedList(TKey, TValue) is faster than SortedDictionary(TKey, TValue).

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

回答by Meta-Knight

1. When you want the collection to be sorted by key when you iterate over it. If you don't need your data to be sorted, you're better off with just a Dictionary, it'll have better performance.

2. SortedList and SortedDictionary pretty much do the same thing, but are implemented differently, thus have different strengths and weaknesses explained here.

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

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

回答by Lev

I'd mention difference between dictionaries.

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

Above picture shows that Dictionary<K,V>is equal or faster in every case than Sortedanalog, but if order of elements is required, e.g. to print them, Sortedone is chosen.

上图显示Dictionary<K,V>在每种情况下都比Sorted模拟相同或更快，但如果需要元素的顺序，例如打印它们，Sorted则选择一个。

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

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

回答by NullReference

To summarize the results of a Performance Test - SortedList vs. SortedDictionary vs. Dictionary vs. Hashtable, the results from best to worst for different scenarios:

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

Memory Usage:

内存使用情况：

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

Insertions:

插入：

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

Search Operations:

搜索操作：

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

foreach loop operations

foreach 循环操作

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

回答by Jaime

Trying to assign a performance scoreto each case presented by @Lev, I used the following values:

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

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

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

The results are (higher = better):

结果是（更高=更好）：

Dictionary:       12.0 
SortedDictionary:  9.0 
SortedList:        6.5

Of course, every use-case will give more weight to certain operations.

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

回答by Ama

I can see the proposed answers focus on performance. The article provided below does not provide anything new regarding performance, but it explains the underlying mechanisms. Also note it does not focus on the three CollectionTypes mentioned in the question, but addresses all the Types of the System.Collections.Genericnamespace.

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

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

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

Extracts:

摘录：

Dictionary<>

字典<>

The Dictionary is probably the most used associative container class. The Dictionary is the fastest class for associative lookups/inserts/deletes because it uses a hash table under the covers. Because the keys are hashed, the key type should correctly implement GetHashCode() and Equals()appropriately or you should provide an external IEqualityComparer to the dictionary on construction. The insert/delete/lookup time of items in the dictionary is amortized constant time - O(1) - which means no matter how big the dictionary gets, the time it takes to find something remains relatively constant. This is highly desirable for high-speed lookups. The only downsideis that the dictionary, by nature of using a hash table, is unordered, so you cannot easily traverse the items in a Dictionary in order.

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

SortedDictionary<>

排序字典<>

The SortedDictionary is similar to the Dictionary in usage but very different in implementation. The SortedDictionary uses a binary tree under the covers to maintain the items in order by the key. As a consequence of sorting, the type used for the key must correctly implement IComparableso 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.

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

SortedList<>

排序列表<>

The SortedList is the other sorted associative container class in the generic containers. Once again SortedList, like SortedDictionary, uses a key to sort key-value pairs. Unlike SortedDictionary, however, items in a SortedList are stored as sorted array of items. This means that insertions and deletions are linear - O(n) - because deleting or adding an item may involve shifting all items up or down in the list. Lookup time, however is O(log n) because the SortedList can use a binary search to find any item in the list by its key. So why would you ever want to do this? Well, the answer is that if you are going to load the SortedList up-front, the insertions will be slower, but because array indexing is faster than following object links, lookups are marginally faster than a SortedDictionary. Once again I'd use this in situations where you want fast lookups and want to maintain the collection in order by the key, and where insertions and deletions are rare.

SortedList 是通用容器中的另一个排序关联容器类。SortedList 再次与 SortedDictionary 一样，使用键对键值对进行排序。然而，与 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.

非常欢迎反馈，因为我确信我没有做对。

• All arrays are of size n.
• Non-sorted array = .Add/.Remove is O(1), but .Item(i) is O(n).
• Sorted array = .Add/.Remove is O(n), but .Item(i) is O(log n).

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

Dictionary

字典

Memory

记忆

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

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

Add

添加

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

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

Remove

消除

1. For i = 0 to n, find iwhere HashArray(i) = Key.GetHash# O(log n) (sorted array)
2. Remove HashArray(i)# O(n) (sorted array)
3. Remove KeyArray(i)# O(1)
4. Remove ItemArray(i)# O(1)

1. For i = 0 to n, find iwhere HashArray(i) = Key.GetHash# O(log n) (排序数组)
2. 删除HashArray(i)# O(n)（排序数组）
3. 删除KeyArray(i)# O(1)
4. 删除ItemArray(i)# O(1)

Get Item

获取物品

1. For i = 0 to n, find iwhere HashArray(i) = Key.GetHash# O(log n) (sorted array)
2. Return ItemArray(i)

1. For i = 0 to n, find iwhere HashArray(i) = Key.GetHash# O(log n) (排序数组)
2. 返回 ItemArray(i)

Loop Through

依次通过

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

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

SortedDictionary

排序字典

Memory

记忆

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

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

Add

添加

1. Add KeyArray(n) = PointerToKey# O(1)
2. Add ItemArray(n) = PointerToItem# O(1)
3. For i = 0 to n, find iwhere KeyArray(i-1) < Key < KeyArray(i)(using ICompare) # O(n)
4. Add OrderArray(i) = n# O(n) (sorted array)

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

Remove

消除

1. For i = 0 to n, find iwhere KeyArray(i).GetHash = Key.GetHash# O(n)
2. Remove KeyArray(SortArray(i))# O(n)
3. Remove ItemArray(SortArray(i))# O(n)
4. Remove OrderArray(i)# O(n) (sorted array)

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)（排序数组）

Get Item

获取物品

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

1. For i = 0 to n, 找到i哪里KeyArray(i).GetHash = Key.GetHash# O(n)
2. 返回 ItemArray(i)

Loop Through

依次通过

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

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

SortedList

排序列表

Memory

记忆

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

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

Add

添加

1. For i = 0 to n, find iwhere KeyArray(i-1) < Key < KeyArray(i)(using ICompare) # O(log n)
2. Add KeyArray(i) = PointerToKey# O(n)
3. Add ItemArray(i) = PointerToItem# O(n)

1. For i = 0 to n, find iwhere KeyArray(i-1) < Key < KeyArray(i)(using ICompare) # O(log n)
2. 添加KeyArray(i) = PointerToKey#O(n)
3. 添加ItemArray(i) = PointerToItem#O(n)

Remove

消除

1. For i = 0 to n, find iwhere KeyArray(i).GetHash = Key.GetHash# O(log n)
2. Remove KeyArray(i)# O(n)
3. Remove ItemArray(i)# 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)

Get Item

获取物品

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

1. For i = 0 to n, 找到i哪里KeyArray(i).GetHash = Key.GetHash# O(log n)
2. 返回 ItemArray(i)

Loop Through

依次通过

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

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