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

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

哪些是可枚举的(IList-可以执行" foreach"循环)吗？哪些使用键/值对(IDict)？

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

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

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

解决方案

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

• 用列表代替ArrayList
• 用字典代替HashTable

实际上，我认为MSDN可以为所有这些问题提供很好的答案。只需查找.NET集合。

他们在智能感知中的表现非常出色。只需键入System.Collections。或者System.Collections.Generics(首选)，我们将获得可用清单和简短描述。

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

其次，由于集合是在框架的2.0版中添加的，因此许多集合都是重复的。

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

• List是ArrayList的通用实现。
• 字典是Hashtable的通用实现

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

SortedDictionary是根据密钥排序的IDictionary。
SortedList是一个IDictionary，它根据所需的IComparer进行排序。

因此，IDictionary实现(那些支持KeyValuePair的实现)是：

• 哈希表
  *字典
• SortedList
• SortedDictionary

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

另外，LinkedList是标准的链接列表实现(该列表是一个数组列表，可加快检索速度)。

从我的头顶上：

• Array *-代表一种老式的内存数组，有点像普通的type []数组的别名。可以枚举。不能自动增长。我会假设插入和检索速度非常快。
• ArrayList-自动增长的数组。增加更多的开销。可以枚举，可能比普通数组慢，但仍然非常快。这些在.NET中使用很多
• List是我的最爱之一-可以与泛型一起使用，因此我们可以拥有一个强类型化的数组，例如List <string>。除此之外，它的行为非常类似于" ArrayList"
• Hashtable-普通的旧哈希表。 O(1)到O(n)最坏的情况。可以枚举值和键属性，并执行键/值对
• Dictionary-与上面相同，仅通过泛型强类型输入，例如`Dictionary <string，string>
• SortedList-排序的通用列表。插入速度很慢，因为它必须弄清楚放置在哪里。可以枚举。由于不必求助，因此在检索上可能相同，但是删除将比普通的旧列表慢。

一旦开始使用泛型强类型化它们，我倾向于一直使用List和Dictionary，这真的很难回到标准非泛型类型。

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

以下是一些适用于一般提示：

• 我们可以在实现" IEnumerable"的类型上使用" foreach"。 IList本质上是一个具有Count和Item(使用从零开始的索引访问项)属性的IEnumberable。另一方面，" IDictionary"表示我们可以通过任何可哈希索引访问项目。
• Array，ArrayList和List全部实现IList。 Dictionary，SortedDictionary和Hashtable实现IDictionary。
• 如果我们使用的是.NET 2.0或者更高版本，建议我们使用上述类型的通用副本。
• 有关这些类型的各种操作的时间和空间复杂性，应查阅其文档。
• .NET数据结构位于" System.Collections"命名空间中。有诸如PowerCollections之类的类型库，它们提供了其他数据结构。
• 要全面了解数据结构，请查阅诸如CLRS之类的资源。

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

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

通用和非通用集合之间存在细微和不太细微的差异。他们仅使用不同的基础数据结构。例如，Hashtable保证一个作者很多读者不同步。字典没有。

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