.NET 有很多复杂的数据结构。不幸的是，其中一些非常相似，我并不总是确定什么时候使用一个，什么时候使用另一个。我的大部分 C# 和 VB 书籍都在一定程度上谈到了它们，但它们从未真正深入任何真正的细节。
Array、ArrayList、List、Hashtable、Dictionary、SortedList 和 SortedDictionary 有什么区别？
哪些是可枚举的（IList -- 可以执行“foreach”循环）？哪些使用键/值对（IDict）？
内存占用呢？插入速度？检索速度？
还有其他值得一提的数据结构吗？
我仍在寻找有关内存使用和速度的更多详细信息（Big-O 表示法）
在我的头顶上：
Array* - 代表一个老式的内存数组 - 有点像普通type[]数组的别名。可以列举。不能自动生长。我会假设非常快的插入和检索速度。
ArrayList- 自动增长的数组。增加更多开销。可以枚举，可能比普通数组慢，但仍然相当快。这些在 .NET 中被大量使用
List- 我的最爱之一 - 可以与泛型一起使用，因此您可以拥有一个强类型数组，例如List<string>. 除此之外，行为非常像ArrayList
Hashtable- 普通的旧哈希表。O(1) 到 O(n) 最坏的情况。可以枚举 value 和 keys 属性，并做 key/val 对
Dictionary- 与上述相同，仅通过泛型进行强类型化，例如Dictionary<string, string>
SortedList- 排序的通用列表。插入速度变慢，因为它必须弄清楚把东西放在哪里。可以枚举，在检索时可能相同，因为它不必求助，但删除会比普通的旧列表慢。
我倾向于一直使用List-Dictionary一旦你开始使用泛型强类型的它们，就很难回到标准的非泛型。
还有很多其他的数据结构——KeyValuePair你可以用它来做一些有趣的事情，还有一个SortedDictionary也很有用。
如果可能，请使用泛型。 这包括：
首先，.NET 中的所有集合都实现了 IEnumerable。
其次，很多集合都是重复的，因为泛型是在 2.0 版框架中添加的。
因此，尽管通用集合可能会添加功能，但在大多数情况下：
数组是一个固定大小的集合，您可以更改存储在给定索引处的值。
SortedDictionary 是一个基于键排序的 IDictionary<T,K>。SortedList 是一个 IDictionary<T,K>，它根据所需的 IComparer 进行排序。
因此，IDictionary 实现（那些支持 KeyValuePairs）是：
.NET 3.5 中添加的另一个集合是 Hashset。它是一个支持集合操作的集合。
此外，LinkedList 是一个标准的链表实现（List 是一个用于更快检索的数组列表）。
这里有一些一般性的提示给你：
您可以foreach在实现IEnumerable. IList本质上是一个IEnumberablewith Countand Item（使用从零开始的索引访问项目）属性。IDictionary另一方面意味着您可以通过任何哈希索引访问项目。
Array，ArrayList并List全部实施IList。
Dictionary, SortedDictionary, 和Hashtable实施IDictionary。
如果您使用的是 .NET 2.0 或更高版本，建议您使用上述类型的通用对应项。
对于这些类型的各种操作的时间和空间复杂性，您应该查阅他们的文档。
.NET 数据结构位于System.Collections命名空间中。有一些类型库，例如PowerCollections，它们提供了额外的数据结构。
要全面了解数据结构，请查阅CLRS等资源。
正如一位用户所说，数组是“老派”集合（是的，数组被认为是一个集合，尽管不是 的一部分System.Collections）。但是，与其他集合相比，数组的“老派”是什么，即您在标题中列出的那些（这里是 ArrayList 和 List(Of T)）？让我们从数组的基础开始。
首先， Microsoft .NET 中的数组是“允许您将多个 [逻辑相关] 项视为单个集合的机制”（请参阅链接文章）。这意味着什么？数组按顺序存储各个成员（元素），一个接一个地存储在内存中，并具有起始地址。通过使用数组，我们可以轻松地访问从该地址开始的顺序存储的元素。
除此之外，与编程 101 个常见概念相反，数组确实可以非常复杂：
数组可以是单维的、多维的或加法的（交错的数组值得一读）。数组本身不是动态的：一旦初始化，一个n大小的数组就会保留足够的空间来容纳n个对象。数组中的元素数量不能增加或减少。Dim _array As Int32() = New Int32(100)在内存块上为数组保留足够的空间以包含 100 个 Int32 原始类型对象（在这种情况下，数组被初始化为包含 0）。该块的地址返回到_array。
根据这篇文章，公共语言规范(CLS) 要求所有数组都是从零开始的。.NET 中的数组支持非从零开始的数组；但是，这种情况不太常见。由于零基数组的“共性”，微软花了很多时间优化它们的性能；因此，单维、从零开始的 (SZ) 数组是“特殊的”——并且实际上是数组的最佳实现（与多维等相反）——因为 SZ 具有用于操作它们的特定中间语言指令。
数组总是通过引用传递（作为内存地址）——这是数组难题的一个重要部分。虽然他们进行边界检查（会抛出错误），但也可以在数组上禁用边界检查。
同样，数组的最大障碍是它们无法重新调整大小。它们具有“固定”容量。在我们的历史中介绍 ArrayList 和 List(Of T)：
ArrayList（连同——尽管这里List(Of T)有一些关键的区别，稍后解释）——也许最好被认为是集合的下一个补充（在广义上）。ArrayList 继承自IList（'ICollection' 的后代）接口。ArrayLists 本身比 Lists更庞大- 需要更多开销。
IList确实使实现能够将 ArrayLists 视为固定大小的列表（如 Arrays）；然而，除了 ArrayLists 添加的额外功能之外，使用固定大小的 ArrayLists 并没有真正的优势，因为在这种情况下 ArrayLists（相对于 Arrays）明显更慢。
根据我的阅读，ArrayLists 不能是锯齿状的：“不支持使用多维数组作为元素......”。再一次，ArrayLists 棺材上的另一个钉子。ArrayLists 也不是“类型化的”——这意味着，在一切之下，ArrayList 只是一个动态的对象数组：Object[]. 这在实现 ArrayList 时需要大量装箱（隐式）和拆箱（显式），再次增加了它们的开销。
未经证实的想法：我想我记得我读过或听过我的一位教授说 ArrayList 是试图从 Arrays 转移到 List 类型 Collections 的混蛋概念孩子，即曾经对 Arrays 进行了很大改进，它们不再是最好的选择，因为已经对收藏进行了进一步的开发
内存使用量的差异足以让 List(Of Int32) 消耗的内存比包含相同原始类型的 ArrayList 少 56%（在上述绅士的链接演示中为 8 MB 对 19 MB：再次，链接在这里） - 虽然这是 64 位机器的复杂结果。这种差异确实表明了两件事：第一（1），装箱的 Int32 类型“对象”（ArrayList）比纯 Int32 原始类型（List）大得多；第二 (2)，由于 64 位机器的内部工作，差异是指数级的。
那么，有什么区别，什么是List(Of T)？MSDN将 a 定义List(Of T)为“……一个可以通过索引访问的强类型对象列表”。这里的重要性是“强类型”位： List(Of T) '识别'类型并将对象存储为它们的类型。因此， anInt32存储为 anInt32而不是Object类型。这消除了装箱和拆箱引起的问题。
MSDN 指定这种差异仅在存储原始类型而不是引用类型时发挥作用。同样，差异确实发生在大规模上：超过 500 个元素。更有趣的是，MSDN 文档中写道：“使用 List(Of T) 类的特定于类型的实现而不是使用 ArrayList 类对您有利......”
本质上，List(Of T) 是 ArrayList，但更好。它是 ArrayList 的“通用等价物”。像 ArrayList 一样，在排序之前不能保证排序（见图）。List(Of T) 还具有一些附加功能。
我对这个问题表示同情 - 我也发现（发现？）这个选择令人困惑，所以我开始科学地查看哪种数据结构最快（我使用 VB 进行了测试，但我想 C# 会是一样的，因为两种语言在 CLR 级别做同样的事情）。你可以在这里看到我进行的一些基准测试结果（还有一些关于哪种数据类型最适合在哪种情况下使用的讨论）。
我发现 Microsoft Docs on Collection and Data Structure 页面上的“Choose a Collection”部分非常有用
还有下面的矩阵来比较一些其他的特性
它们在智能感知中的拼写很好。只需键入System.Collections。或System.Collections.Generics（首选），您将获得可用内容的列表和简短描述。
哈希表/字典是 O(1) 性能，这意味着性能不是大小的函数。知道这一点很重要。
编辑：实际上，Hashtable/Dictionary<> 查找的平均时间复杂度为 O(1)。
泛型集合将比它们的非泛型集合表现更好，尤其是在迭代许多项目时。这是因为不再发生装箱和拆箱。
关于高频系统交易工程的哈希表与字典的重要说明：线程安全问题
Hashtable 是线程安全的，可供多个线程使用。字典公共静态成员是线程安全的，但不保证任何实例成员都是如此。
因此 Hashtable 在这方面仍然是“标准”选择。
最流行的 C# 数据结构和集合
C#.NET有很多不同的数据结构，例如，最常见的一种是数组。然而，C# 带有更多基本的数据结构。选择要使用的正确数据结构是编写结构良好且高效的程序的一部分。
在本文中，我将介绍内置的 C# 数据结构，包括 C#.NET 3.5 中引入的新数据结构。请注意，其中许多数据结构适用于其他编程语言。
大批
也许最简单和最常见的数据结构是数组。AC# 数组基本上是一个对象列表。它的定义特征是所有对象都是相同的类型（在大多数情况下）并且它们的数量是特定的。数组的性质允许根据元素在列表中的位置（也称为索引）快速访问元素。AC# 数组定义如下：
[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]
您可以在此处找到来源和更多信息：
泛型和非泛型集合之间存在微妙和不那么微妙的差异。它们只是使用不同的底层数据结构。例如，Hashtable 保证一个写者多读者不同步。字典没有。