.NET数据结构：ArrayList，List，HashTable，Dictionary，SortedList，SortedDictionary – 速度，内存，以及何时使用？
.NET有很多复杂的数据结构。 不幸的是，其中一些是非常相似的，我不知道什么时候使用一个，什么时候使用另一个。 我的C＃和Visual Basic书籍中的大部分都在某种程度上对它们进行了讨论，但是他们从来没有真正细读过。
Array，ArrayList，List，Hashtable，Dictionary，SortedList和SortedDictionary有什么区别？
哪些是可枚举的（IList – 可以做'foreach'循环）？ 哪些使用键/值对（IDict）？
内存占用情况如何？ 插入速度？ 检索速度？
还有其他的数据结构值得一提吗？
我仍然在寻找关于内存使用和速度的更多细节（Big-O符号）。
closures我的头顶上：
-
Array* – 表示一个老派的内存数组 – 有点像普通type[]数组的别名。 可以枚举。 不能自动增长。 我会假设非常快的插入和回归速度。 -
ArrayList– 自动增长的数组。 增加更多的开销。 可以枚举，可能比一个正常的数组慢，但仍然相当快。 这些在.NET中使用了很多 -
List– 我的最爱之一 – 可以用于generics，所以你可以有一个强types的数组，例如List<string>。 除此之外，非常像ArrayList -
Hashtable表 – 简单的旧哈希表。 O（1）到O（n）最坏的情况。 可以枚举值和键属性，并执行键/ VAL对 -
Dictionary– 与上述相同只能通过generics强types化，如Dictionary<string, string> -
SortedList– 一个有序的通用列表。 由于必须弄清楚放置的位置，所以插入速度变慢了。 可以枚举，可能是相同的检索，因为它不必诉诸，但删除将比一个普通的旧名单慢。
我倾向于一直使用List和Dictionary – 一旦你开始使用强types的generics，它真的很难回到标准的非generics。
还有很多其他的数据结构 – 有KeyValuePair ，你可以使用它来做一些有趣的事情，还有一个SortedDictionary也可以是有用的。
如果可能的话，使用generics。 这包括：
- 列表而不是ArrayList
- 字典而不是HashTable
首先，.NET中的所有集合实现IEnumerable。
其次，很多集合都是重复的，因为在框架的2.0版本中添加了generics。
所以，虽然通用的集合可能会增加function，大部分：
- List是ArrayList的通用实现。
- Dictionary是Hashtable的通用实现
数组是固定大小的集合，您可以更改存储在给定索引处的值。
SortedDictionary是一个基于密钥sorting的IDictionary。 SortedList是一个基于所需IComparersorting的IDictionary。
所以，IDictionary实现（支持KeyValuePairs的）是：* Hashtable * Dictionary * SortedList * SortedDictionary
在.NET 3.5中添加的另一个集合是Hashset。 它是一个支持集合操作的集合。
此外，LinkedList是一个标准的链表实现（List是一个快速检索的数组列表）。
以下是您的一些常规提示：
-
您可以在实现
IEnumerabletypes上使用foreach。IList本质上是一个IEnumberableCount和Item（访问项目使用零IEnumberable引）属性。 另一方面，IDictionary意味着你可以通过任意可哈希索引访问项目。 -
Array，ArrayList和List都实现了IList。Dictionary，SortedDictionary和Hashtable实现了IDictionary。 -
如果您使用的是.NET 2.0或更高版本，build议您使用上述types的通用对象。
-
对于这些types的各种操作的时间和空间复杂性，您应该查阅他们的文档。
-
.NET数据结构位于
System.Collections命名空间中。 有types库，如PowerCollections提供额外的数据结构。 -
要深入了解数据结构，请查阅CLRS等资源。
一个很好的备忘单提到了数据结构，algorithm等的复杂性
我同情这个问题 – 我也发现（find）select令人迷惑，所以我科学地设定了哪个数据结构是最快的（我用VB做了testing，但是我想C＃会是相同的，因为两种语言在CLR级别做同样的事情）。 您可以在这里看到我进行的一些基准testing结果 （还有一些讨论哪种数据types最适合在哪些情况下使用）。
.NET数据结构：
更多关于为什么ArrayList和List实际上是不同的对话
数组
正如一个用户所说，数组是“旧学校”集合（是的，数组被认为是一个集合，尽pipe不是System.Collections一部分）。 但是，与其他集合相比，数组的“老派”是什么，即您在标题中列出的集合（这里是ArrayList和List（Of T））？ 让我们从查看数组开始的基础知识。
首先，Microsoft .NET中的数组是“允许您将多个[逻辑相关]项目作为单个集合来处理的机制”（请参阅链接的文章）。 那是什么意思？ 数组依次存储单个成员（元素），一个接一个地存储起始地址。 通过使用该数组，我们可以轻松地访问从该地址开始的顺序存储的元素。
除此之外，与编程101常见概念相反，数组确实可能相当复杂：
数组可以是单维的，多维的，也可以是锯齿状的（参差不齐的数组值得一读）。 数组本身并不是dynamic的：一旦初始化，一个n大小的数组将保留足够的空间来容纳n个对象。 数组中元素的数量不能增长或缩小。 Dim _array As Int32() = New Int32(100)在内存块上保留足够的空间，以使数组包含100个Int32基元types对象（在这种情况下，数组初始化为包含0）。 该块的地址返回到_array 。
根据这篇文章， Common Language Specification （CLS）要求所有的数组都是基于零的。 .NET中的数组支持非零数组; 然而，这是不常见的。 由于零基arrays的“共同性”，微软花了很多时间优化其性能 ， 因此，单维，零基（SZ）数组是“特殊的” – 实际上是数组的最佳实现（而不是多维等） – 因为SZ具有特定的中介语言指令来操纵它们。
数组总是通过引用传递（作为内存地址），这是数组难题的重要组成部分。 虽然他们做边界检查（会抛出一个错误），边界检查也可以禁用数组。
再一次，数组的最大障碍是它们不是可重定义的。 他们有一个“固定”的能力。 介绍ArrayList和List（Of T）到我们的历史：
ArrayList – 非通用列表
ArrayList （连同List(Of T) – 尽pipe存在一些关键的区别，这里稍后解释）也许被认为是广义上的下一个集合。 ArrayListinheritance自IList （“ICollection”的后代）接口。 ArrayLists本身比List更笨重 – 需要更多的开销 。
IList确实能够将ArrayList视为固定大小的列表（如数组）。 然而，除了ArrayLists添加的额外的function性之外，使用固定大小的ArrayLists没有真正的好处，因为在这种情况下ArrayList（在数组上）明显较慢。
从我的阅读，ArrayLists不能锯齿状：“使用multidimensional array作为元素…不被支持”。 再一次，ArrayLists的棺材中的另一个钉子。 ArrayLists也不是“types的” – 意味着，在一切之下，一个ArrayList只是一个dynamic的Object： Object[]数组。 这在实现ArrayLists时需要大量的装箱（隐式）和拆箱（显式），再次增加开销。
无法证实的想法：我记得无论是从阅读还是从我的一位教授那里听说，ArrayLists是从数组转移到列表types集合的混蛋概念孩子，也就是说，虽然一旦对数组进行了很大的改进，它们不再是最好的select，因为在collections方面已经进一步发展
列表（T）：什么ArrayList成为（并希望是）
内存使用方面的差异足以使List（Int32）的内存消耗比包含相同基元types的ArrayListless56％（上述先生的关联演示中的8 MB vs. 19 MB），尽pipe如此这是由64位机器复合的结果。 这个区别确实说明了两点：首先（1），盒装Int32types的“对象”（ArrayList）比纯Int32原始types（List）大得多。 第二（2），由于64位机器的内部工作，差异是指数的。
那么，有什么区别？什么是T（T）列表 ？ MSDN将List(Of T)定义为“…可以通过索引访问的对象的强types列表”。 这里的重要性是“强types”位：List（Of T）'识别'types并将对象存储为它们的types。 所以，一个Int32存储为一个Int32而不是一个Objecttypes。 这消除了拳击和拆箱造成的问题。
MSDN指定这种差异仅在存储基元types而不是引用types时起作用。 而且，这种差异确实发生在一个大的范围内：超过500个元素。 更有意思的是，MSDN文档读到：“使用List（Of T）类的types特定实现而不是使用ArrayList类是有利的。
基本上，List（Of T）是ArrayList，但更好。 它是ArrayList的“通用等价物”。 像ArrayList，它不保证sorting，直到sorting（去图）。 List（Of T）也有一些额外的function。
散列表/字典是O（1）性能，这意味着性能不是大小的函数。 这很重要。
编辑：在实践中，Hashtable / Dictionary <>查找的平均时间复杂度是O（1）。
generics集合将比其非generics集合更好，特别是在遍历多个项目时。 这是因为装箱和拆箱不再发生。
他们在intellisense中拼写得非常好。 只需键入System.Collections。 或System.Collections.Generics （首选），你会得到一个列表和可用的简短说明。
实际上，我认为MSDN可以为所有这些问题提供很好的答案。 只要查看.NET集合。
generics集合与非generics集合之间存在细微的差别。 他们只是使用不同的基础数据结构。 例如，Hashtable保证没有同步的单写多读者。 字典不。
高频系统交易工程Hashtable和Dictionary的重要注意事项：线程安全问题
散列表是multithreading使用的线程安全的。 字典公共静态成员是线程安全的，但任何实例成员不能保证是这样的。
所以Hashtable依然是这方面的“标准”select。
线程安全可以通过使用ConcurrentDictionary来实现。 HashTable不是唯一的select。
