C# .NET 数据结构：ArrayList、List、HashTable、Dictionary、SortedList、SortedDictionary——速度、内存以及何时使用？

.NET data structures: ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary -- Speed, memory, and when to use each?

提问by Pretzel

.NET has a lot of complex data structures. Unfortunately, some of them are quite similar, and I'm not always sure when to use one and when to use another. Most of my C# and Visual Basic books talk about them to a certain extent, but they never really go into any real detail.

.NET 有很多复杂的数据结构。不幸的是，其中一些非常相似，我并不总是确定何时使用一个，何时使用另一个。我的大部分 C# 和 Visual Basic 书籍都在一定程度上讨论了它们，但它们从未真正涉及任何实际细节。

What's the difference between Array, ArrayList, List, Hashtable, Dictionary, SortedList, and SortedDictionary?

Array、ArrayList、List、Hashtable、Dictionary、SortedList 和 SortedDictionary 有什么区别？

Which ones are enumerable (IList -- can do 'foreach' loops)? Which ones use key/value pairs (IDict)?

哪些是可枚举的（IList - 可以执行“foreach”循环）？哪些使用键/值对（IDict）？

What about memory footprint? Insertion speed? Retrieval speed?

内存占用呢？插入速度？检索速度？

Are there any other data structures worth mentioning?

还有其他值得一提的数据结构吗？

I'm still searching for more details on memory usage and speed (Big-O notation).

我仍在寻找有关内存使用和速度（Big-O 表示法）的更多详细信息。

采纳答案by Sam Schutte

Off the top of my head:

在我的头顶：

• Array* - represents an old-school memory array - kind of like a alias for a normal type[]array. Can enumerate. Can't grow automatically. I would assume very fast insert and retrival speed.

• ArrayList- automatically growing array. Adds more overhead. Can enum., probably slower than a normal array but still pretty fast. These are used a lot in .NET

• List- one of my favs - can be used with generics, so you can have a strongly typed array, e.g. List<string>. Other than that, acts very much like ArrayList

• Hashtable- plain old hashtable. O(1) to O(n) worst case. Can enumerate the value and keys properties, and do key/val pairs

• Dictionary- same as above only strongly typed via generics, such as Dictionary<string, string>

• SortedList- a sorted generic list. Slowed on insertion since it has to figure out where to put things. Can enum., probably the same on retrieval since it doesn't have to resort, but deletion will be slower than a plain old list.

• Array* - 代表一个老式的内存数组 - 有点像普通type[]数组的别名。可以列举。不能自动增长。我假设插入和检索速度非常快。

• ArrayList- 自动增长数组。增加了更多的开销。可以枚举，可能比普通数组慢，但仍然相当快。这些在 .NET 中被大量使用

• List- 我的最爱之一 - 可以与泛型一起使用，因此您可以拥有一个强类型数组，例如List<string>. 除此之外，行为非常像ArrayList

• Hashtable- 普通的旧哈希表。O(1) 到 O(n) 最坏情况。可以枚举值和键属性，并做键/值对

• Dictionary- 与上面相同，仅通过泛型进行强类型，例如 Dictionary<string, string>

• SortedList- 排序的通用列表。插入速度变慢，因为它必须弄清楚把东西放在哪里。可以枚举，在检索时可能相同，因为它不必求助，但删除将比普通的旧列表慢。

I tend to use Listand Dictionaryall the time - once you start using them strongly typed with generics, its really hard to go back to the standard non-generic ones.

我倾向于使用List和Dictionary所有的时间-一旦你开始使用它们泛型强类型，它真的很难回到标准的非通用的。

There are lots of other data structures too - there's KeyValuePairwhich you can use to do some interesting things, there's a SortedDictionarywhich can be useful as well.

还有很多其他的数据结构——KeyValuePair你可以用它来做一些有趣的事情，还有一个SortedDictionary也很有用。

回答by Adam Tegen

If at all possible, use generics.This includes:

如果可能，请使用泛型。这包括：

• List instead of ArrayList
• Dictionary instead of HashTable

• 列表而不是 ArrayList
• 字典代替哈希表

回答by Joel Coehoorn

They're spelled out pretty well in intellisense. Just type System.Collections.or System.Collections.Generics(preferred) and you'll get a list and short description of what's available.

它们在智能感知中被很好地阐明。只需键入System.Collections。或System.Collections.Generics（首选），您将获得可用内容的列表和简短描述。

回答by Abe Heidebrecht

First, all collections in .NET implement IEnumerable.

首先，.NET 中的所有集合都实现了 IEnumerable。

Second, a lot of the collections are duplicates because generics were added in version 2.0 of the framework.

其次，很多集合都是重复的，因为泛型是在框架的 2.0 版中添加的。

So, although the generic collections likely add features, for the most part:

因此，尽管通用集合可能会添加功能，但在大多数情况下：

• List is a generic implementation of ArrayList.
• Dictionary is a generic implementation of Hashtable

• List 是 ArrayList 的通用实现。
• Dictionary 是 Hashtable 的通用实现

Arrays are a fixed size collection that you can change the value stored at a given index.

数组是一个固定大小的集合，您可以更改存储在给定索引处的值。

SortedDictionary is an IDictionary that is sorted based on the keys. SortedList is an IDictionary that is sorted based on a required IComparer.

SortedDictionary 是一个基于键排序的 IDictionary。SortedList 是一个 IDictionary，它根据所需的 IComparer 进行排序。

So, the IDictionary implementations (those supporting KeyValuePairs) are: * Hashtable * Dictionary * SortedList * SortedDictionary

因此，IDictionary 实现（支持 KeyValuePairs 的实现）是：* Hashtable * Dictionary * SortedList * SortedDictionary

Another collection that was added in .NET 3.5 is the Hashset. It is a collection that supports set operations.

.NET 3.5 中添加的另一个集合是 Hashset。它是一个支持集合操作的集合。

Also, the LinkedList is a standard linked-list implementation (the List is an array-list for faster retrieval).

此外，LinkedList 是一个标准的链表实现（List 是一个用于更快检索的数组列表）。

回答by blackwing

Here are a few general tips for you:

以下是一些给您的一般提示：

• You can use foreachon types that implement IEnumerable. IListis essentially an IEnumberablewith Countand Item(accessing items using a zero-based index) properties. IDictionaryon the other hand means you can access items by any-hashable index.

• Array, ArrayListand Listall implement IList. Dictionary, SortedDictionary, and Hashtableimplement IDictionary.

• If you are using .NET 2.0 or higher, it is recommended that you use generic counterparts of mentioned types.

• For time and space complexity of various operations on these types, you should consult their documentation.

• .NET data structures are in System.Collectionsnamespace. There are type libraries such as PowerCollectionswhich offer additional data structures.

• To get a thorough understanding of data structures, consult resources such as CLRS.

• 您可以foreach在实现IEnumerable. IList本质上是一个IEnumberablewithCount和Item（使用从零开始的索引访问项目）属性。IDictionary另一方面意味着您可以通过任何可哈希索引访问项目。

• Array，ArrayList并且List都执行IList。 Dictionary, SortedDictionary, 并Hashtable实施IDictionary。

• 如果您使用 .NET 2.0 或更高版本，建议您使用上述类型的通用对应项。

• 对于这些类型的各种操作的时间和空间复杂性，您应该查阅它们的文档。

• .NET 数据结构位于System.Collections命名空间中。PowerCollections等类型库提供了额外的数据结构。

• 要彻底了解数据结构，请参阅CLRS等资源。

回答by Chris

Hashtables/Dictionaries are O(1) performance, meaning that performance is not a function of size. That's important to know.

哈希表/字典的性能是 O(1)，这意味着性能不是大小的函数。知道这一点很重要。

EDIT: In practice, the average time complexity for Hashtable/Dictionary<> lookups is O(1).

编辑：实际上，Hashtable/Dictionary<> 查找的平均时间复杂度为 O(1)。

回答by Ilya Ryzhenkov

There are subtle and not-so-subtle differences between generic and non-generic collections. They merely use different underlying data structures. For example, Hashtable guarantees one-writer-many-readers without sync. Dictionary does not.

泛型和非泛型集合之间存在细微的差异。它们只是使用不同的底层数据结构。例如，Hashtable 保证一个作者多读者没有同步。字典没有。

回答by Russ Cam

The generic collections will perform better than their non-generic counterparts, especially when iterating through many items. This is because boxing and unboxing no longer occurs.

泛型集合将比非泛型集合表现得更好，尤其是在迭代多个项目时。这是因为不再发生装箱和拆箱。

回答by Rob

An important note about Hashtable vs Dictionary for high frequency systematic trading engineering: Thread Safety Issue

关于高频系统交易工程的哈希表与字典的重要说明：线程安全问题

Hashtable is thread safe for use by multiple threads. Dictionary public static members are thread safe, but any instance members are not guaranteed to be so.

Hashtable 是线程安全的，可供多个线程使用。字典公共静态成员是线程安全的，但不保证任何实例成员都是线程安全的。

So Hashtable remains the 'standard' choice in this regard.

因此 Hashtable 仍然是这方面的“标准”选择。

回答by Andy Brown

I sympathise with the question - I too found (find?) the choice bewildering, so I set out scientifically to see which data structure is the fastest (I did the test using VB, but I imagine C# would be the same, since both languages do the same thing at the CLR level). You can see some benchmarking results conducted by me here(there's also some discussion of which data type is best to use in which circumstances).

我很同情这个问题——我也发现（找到？）这个选择令人困惑，所以我科学地着手查看哪种数据结构最快（我使用 VB 进行了测试，但我想 C# 会是一样的，因为这两种语言在 CLR 级别做同样的事情）。你可以在这里看到我进行的一些基准测试结果（还有一些关于在哪种情况下最好使用哪种数据类型的讨论）。