.NET有很多复杂的数据结构。不幸的是，它们中的一些非常相似，我并不总是确定何时使用一个以及何时使用另一个。我的大多数C＃和Visual Basic书籍都在一定程度上谈论它们，但它们从未真正涉及任何真实的细节。
Array，ArrayList，List，Hashtable，Dictionary，SortedList和SortedDictionary之间有什么区别？
哪些是可枚举的（IList - 可以做'foreach'循环）？哪些使用键/值对（IDict）？
内存占用情况如何？插入速度？检索速度？
还有其他值得一提的数据结构吗？
我还在寻找有关内存使用和速度的更多细节（Big-O表示法）。
脱离我的头顶：
Array * - 代表一个老式的记忆数组 - 有点像普通的type[]数组的别名。可以列举。无法自动增长。我会假设非常快的插入和回复速度。ArrayList - 自动增长阵列。增加更多开销。可以枚举。，可能比正常数组慢，但仍然相当快。这些在.NET中使用很多List - 我最喜欢的一个 - 可以用于泛型，所以你可以有一个强类型数组，例如List<string>。除此之外，行为非常像ArrayListHashtable - 普通的旧哈希表。 O（1）到O（n）最坏的情况。可以枚举值和键属性，并执行键/值对Dictionary - 与上面相同，仅通过泛型强类型，例如Dictionary<string, string>SortedList - 一个有序的通用列表。插入速度慢，因为它必须弄清楚放置的位置。可以枚举。可能在检索上是相同的，因为它不必求助，但删除将比普通的旧列表慢。我倾向于一直使用List和Dictionary - 一旦你开始使用强类型泛型，它很难回到标准的非泛型。
还有很多其他的数据结构 - 你可以使用KeyValuePair来做一些有趣的事情，还有一个SortedDictionary也很有用。
通用集合的性能优于非泛型集合，尤其是在迭代许多项目时。这是因为不再发生装箱和拆箱。
关于高频系统交易工程的Hashtable vs Dictionary的一个重要说明：线程安全问题
Hashtable是线程安全的，可供多个线程使用。字典公共静态成员是线程安全的，但不保证任何实例成员都是如此。
因此，Hashtable仍然是这方面的“标准”选择。
泛型和非泛型集合之间存在微妙且不那么细微的差异。它们仅使用不同的底层数据结构。例如，Hashtable保证一个作者多读者没有同步。字典没有。
实际上，我认为MSDN有助于为所有这些问题提供相当好的答案。只需查看.NET集合。
最流行的C＃数据结构和集合
C＃.NET有许多不同的数据结构，例如，最常见的一种是数组。但是，C＃带有更多基本数据结构。选择正确的数据结构是编写结构良好且高效的程序的一部分。
在本文中，我将介绍内置的C＃数据结构，包括C＃.NET 3.5中引入的新结构。请注意，其中许多数据结构适用于其他编程语言。
排列
最简单和最常见的数据结构是数组。 C＃数组基本上是一个对象列表。它的定义特征是所有对象都是相同类型（在大多数情况下），并且具有特定数量的对象。数组的性质允许基于它们在列表中的位置（也称为索引）非常快速地访问元素。 C＃数组的定义如下：
[object type][] myArray = new [object type][number of elements]
一些例子：
int[] myIntArray = new int[5];
int[] myIntArray2 = { 0, 1, 2, 3, 4 };
从上面的示例中可以看出，数组可以初始化，不包含任何元素或来自一组现有值。只要值合适，将值插入数组就很简单。当元素的数量超过数组的大小时，操作会变得昂贵，此时需要扩展数组。这需要更长的时间，因为必须将所有现有元素复制到新的更大的数组。
数组列表
C＃数据结构ArrayList是一个动态数组。这意味着ArrayList可以包含任意数量的对象和任何类型的对象。此数据结构旨在简化将新元素添加到数组中的过程。在引擎盖下，ArrayList是一个数组，每当空间不足时，其大小加倍。将内部阵列的大小加倍是一种非常有效的策略，可以长期减少元素复制的数量。我们不会在此证明这一点。数据结构使用非常简单：
ArrayList myArrayList = new ArrayList();
myArrayList.Add(56);
myArrayList.Add("String");
myArrayList.Add(new Form());
ArrayList数据结构的缺点是必须将检索到的值转换回原始类型：
int arrayListValue = (int)myArrayList[0]
您可以在此处找到来源和更多信息：
如果可能的话，使用泛型。这包括：
首先，.NET中的所有集合都实现了IEnumerable。
其次，很多集合都是重复的，因为在框架的2.0版本中添加了泛型。
因此，尽管通用集合可能会添加功能，但大多数情况下：
数组是固定大小的集合，您可以更改存储在给定索引处的值。
SortedDictionary是一个基于键排序的IDictionary。 SortedList是一个IDictionary，它根据所需的IComparer进行排序。
因此，IDictionary实现（支持KeyValuePairs的实现）是：* Hashtable * Dictionary * SortedList * SortedDictionary
.NET 3.5中添加的另一个集合是Hashset。它是一个支持集合操作的集合。
此外，LinkedList是标准的链表实现（List是一个用于更快检索的数组列表）。
A good cheat sheet提到数据结构，算法等的复杂性。
以下是一些适合您的一般提示：
foreach的类型上使用IEnumerable。 IList本质上是IEnumberable与Count和Item（使用零基索引访问项目）属性。另一方面，IDictionary意味着您可以通过任何可清除的索引访问项目。Array，ArrayList和List都实施了IList。 Dictionary，SortedDictionary和Hashtable实施IDictionary。System.Collections命名空间中。有类型库，如PowerCollections，提供额外的数据结构。正如一位用户所说，阵列是“老派”集合（是的，阵列被认为是一个集合，虽然不是System.Collections的一部分）。但是，与其他集合相比，数组中的“老派”是什么，即你在标题中列出的那些（这里是ArrayList和List（Of T））？让我们从查看Arrays开始。
首先，Microsoft .NET中的Arrays是“允许您将多个[逻辑相关]项目视为单个集合的机制”（参见链接文章）。那是什么意思？数组按顺序存储各个成员（元素），在内存中一个接一个地存储起始地址。通过使用数组，我们可以轻松访问从该地址开始的顺序存储的元素。
除此之外，与编程101个常见概念相反，数组实际上可能非常复杂：
数组可以是单维，多维或jadded（锯齿状数组值得一读）。数组本身不是动态的：一旦初始化，n大小的数组保留足够的空间来容纳n个对象。数组中的元素数量不能增长或缩小。 Dim _array As Int32() = New Int32(100)在内存块上保留足够的空间，以便数组包含100个Int32基本类型对象（在这种情况下，数组初始化为包含0）。该块的地址返回给_array。
根据该文章，Common Language Specification（CLS）要求所有数组都是从零开始的。 .NET中的数组支持非零数组;然而，这不太常见。由于零基数组的“共性”，微软花了很多时间来优化其性能;因此，单维，零基（SZs）数组是“特殊的” - 并且实际上是数组的最佳实现（与多维等相反） - 因为SZ具有用于操纵它们的特定中间语言指令。
数组总是通过引用传递（作为内存地址） - 要知道的数组难题的一个重要部分。虽然它们进行边界检查（将抛出错误），但也可以在数组上禁用边界检查。
同样，数组的最大障碍是它们不具有可重复性。他们有“固定”的能力。向我们的历史介绍ArrayList和List（Of T）：
ArrayList（以及List(Of T) - 尽管存在一些重要的差异，这里稍后会解释） - 也许最好被认为是收藏的下一个补充（广义上）。 ArrayList继承自IList（'ICollection'的后代）接口。 ArrayLists本身就是bulkier - 需要更多的overhead - 而不是列表。
IList确实允许实现将ArrayLists视为固定大小的列表（如Arrays）;但是，除了ArrayLists添加的附加功能之外，使用固定大小的ArrayLists没有什么真正的优势，因为在这种情况下，ArrayLists（在Arrays上）明显更慢。
从我的阅读来看，ArrayLists不能被锯齿：“不支持使用多维数组作为元素......”。再次，ArrayLists的棺材中的另一个钉子。 ArrayLists也不是“类型化” - 意味着，在所有内容下，ArrayList只是一个动态的对象数组：Object[]。在实现ArrayLists时，这需要大量的装箱（隐式）和取消装箱（显式），再次增加了它们的开销。
毫无根据的想法：我想我记得要么是读过，要么听过我的一位教授的说法，ArrayLists就像是试图从阵列转移到List-type Collections的混蛋概念孩子，即曾经对阵列有了很大的改进，它们不再是最好的选择，因为在收集方面已经进行了进一步的开发
内存使用的差异非常大，以至于List（Of Int32）比包含相同原始类型的ArrayList消耗的内存少56％（在上面的绅士链接演示中，8 MB与19 MB相比：再次，链接here） - 尽管这是由64位机器复合的结果。这种差异实际上证明了两件事：第一（1），盒装Int32型“对象”（ArrayList）比纯Int32原型（List）大得多;第二个（2），由于64位机器的内部工作，差异是指数的。
那么，有什么不同，什么是List(Of T)？ MSDN将List(Of T)定义为“......可以通过索引访问的强类型对象列表。”这里的重要性是“强类型”位：List（Of T）'识别'类型并将对象存储为其类型。因此，Int32存储为Int32而不是Object类型。这消除了装箱和拆箱引起的问题。
MSDN指定这种差异仅在存储基元类型而非存储类型时发挥作用。太多，差异确实大规模发生：超过500个元素。更有趣的是，MSDN文档中写道：“使用List（Of T）类的特定于类型的实现而不是使用ArrayList类对你有利。”
本质上，List（Of T）是ArrayList，但更好。它是ArrayList的“通用等价物”。与ArrayList一样，不保证在排序之前对其进行排序（如图所示）。 List（Of T）也有一些附加功能。
我同情这个问题 - 我也发现（找到？）选择令人困惑，所以我科学地设定了哪个数据结构最快（我用VB做了测试，但我想C＃会是相同的，因为两种语言在CLR级别做同样的事情）。您可以看到some benchmarking results conducted by me here（还有一些关于哪种数据类型最适合在哪种情况下使用的讨论）。
他们在intellisense中拼写得非常好。只需键入System.Collections。或System.Collections.Generics（首选），您将获得可用内容的列表和简短描述。
Hashtables / Dictionaries是O（1）性能，这意味着性能不是大小的函数。知道这一点很重要。
编辑：实际上，Hashtable / Dictionary <>查找的平均时间复杂度为O（1）。