首页 文章

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

提问于
浏览 次
195

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

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

哪些是可枚举的（IList - 可以做'foreach'循环）？哪些使用键/值对（IDict）？

内存占用情况如何？插入速度？检索速度？

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

我还在寻找有关内存使用和速度的更多细节（Big-O表示法） .

c# .net vb.net arrays data-structures

14 回答

  • 21

    脱离我的头顶：

    • Array * - 表示旧式内存数组 - 有点像普通 type[] 数组的别名 . 可以列举 . 无法自动增长 . 我会假设非常快的插入和回复速度 .

    • ArrayList - 自动增长数组 . 增加更多开销 . 可以枚举 . ，可能比正常数组慢，但仍然相当快 . 这些在.NET中使用很多

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

    • Hashtable - 普通旧哈希表 . O（1）到O（n）最坏的情况 . 可以枚举值和键属性，并执行键/值对

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

    • SortedList - 已排序的通用列表 . 插入速度慢，因为它必须弄清楚放置的位置 . 可以枚举 . 可能在检索上是相同的，因为它不必求助，但删除将比普通的旧列表慢 .

    我倾向于一直使用 List 和 Dictionary - 一旦你开始使用强类型泛型，它很难回到标准的非泛型 .

    还有很多其他的数据结构 - 你可以使用_1134007来做一些有趣的事情，有一个 SortedDictionary 也可以用 .

    回复于
  • 1

    If at all possible, use generics. 这包括：

    • 列表而不是ArrayList

    • Dictionary而不是HashTable

    回复于
  • 5

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

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

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

    • List是ArrayList的通用实现 .

    • Dictionary是Hashtable的通用实现

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

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

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

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

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

    回复于
  • 138

    以下是一些适合您的一般提示：

    • 您可以在实现 IEnumerable 的类型上使用 foreach . IList 本质上是 IEnumberable ，其中包含 Count 和 Item （使用从零开始的索引访问项目）属性 . 另一方面， IDictionary 表示您可以通过任何可哈希的索引访问项目 .

    • Array ， ArrayList 和 List 全部实施 IList . Dictionary ， SortedDictionary 和 Hashtable 实现 IDictionary .

    • 如果您使用的是.NET 2.0或更高版本，建议您使用上述类型的通用副本 .

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

    • .NET数据结构位于 System.Collections 名称空间中 . 有一些类型库，如PowerCollections，它们提供了额外的数据结构 .

    • 要全面了解数据结构，请参阅CLRS等资源 .

    回复于
  • 3

    A good cheat sheet提到数据结构，算法等的复杂性

    回复于
  • 3

    我同情这个问题 - 我也发现（找到？）选择令人困惑，所以我科学地设定了哪个数据结构最快（我做了使用VB测试，但我想C＃会是相同的，因为两种语言在CLR级别都做同样的事情） . 你可以看到some benchmarking results conducted by me here（还讨论了哪种数据类型最适合在哪种情况下使用） .

    回复于
  • 25

    .NET数据结构：

    更多关于为什么ArrayList和List实际上不同的对话

    数组

    正如一个用户所说，Arrays是"old school"集合（是的，数组被认为是一个集合，虽然不是 System.Collections 的一部分） . 但是，与其他集合相比，"old school"关于数组是什么，即你在 Headers 中列出的那些（这里是ArrayList和List（Of T））？让我们从查看Arrays开始 .

    首先，Microsoft .NET中的Arrays是"mechanisms that allow you to treat several [logically-related] items as a single collection,"（参见链接文章） . 那是什么意思？数组按顺序存储各个成员（元素），在内存中一个接一个地存储起始地址 . 通过使用数组，我们可以轻松访问从该地址开始的顺序存储的元素 .

    除此之外，与编程101个常见概念相反，数组实际上可能非常复杂：

    数组可以是单维，多维或jadded（锯齿状数组值得一读） . 数组本身不是动态的：一旦初始化，n大小的数组保留足够的空间来容纳n个对象 . 数组中的元素数量不能增长或缩小 . Dim _array As Int32() = New Int32(100) 在内存块上保留足够的空间，以使数组包含100个Int32基本类型对象（在这种情况下，数组初始化为包含0） . 该块的地址返回 _array .

    根据该文章，Common Language Specification（CLS）要求所有数组都是从零开始的 . .NET中的数组支持非零数组;然而，这不太常见 . 由于"common-ness"基于零的数组，微软花了 a lot of time optimizing their performance ;因此，单维，零基（SZs）数组是"special" - 并且实际上是数组的最佳实现（与多维等相反） - 因为SZ具有用于操纵它们的特定中间语言指令 .

    数组总是通过引用传递（作为内存地址） - 要知道的数组难题的一个重要部分 . 虽然它们进行边界检查（将抛出错误），但也可以在数组上禁用边界检查 .

    同样，数组的最大障碍是它们不具有可重复性 . 他们有“固定”的能力 . 向我们的历史介绍ArrayList和List（Of T）：

    ArrayList - 非通用列表

    ArrayList（以及 List(Of T) - 尽管存在一些重要的差异，这里稍后会解释） - 也许最好被认为是集合的下一个补充（广义上） . ArrayList继承自IList（'ICollection'的后代）接口 . ArrayLists本身是bulkier - 需要更多overhead - 而不是列表 .

    IList 确实使实现能够将ArrayLists视为固定大小的列表（如Arrays）;但是，除了ArrayLists添加的附加功能之外，使用固定大小的ArrayLists没有什么真正的优势，因为在这种情况下，ArrayLists（在Arrays上）明显更慢 .

    从我的阅读来看，ArrayLists不能是锯齿状的："Using multidimensional arrays as elements... is not supported" . 再次，ArrayLists的棺材中的另一个钉子 . ArrayLists也不是"typed" - 这意味着，在所有内容下，ArrayList只是一个动态的对象数组： Object[] . 在实现ArrayLists时，这需要大量的装箱（隐式）和取消装箱（显式），再次增加了它们的开销 .

    毫无根据的想法：我想我记得要么是读过，要么听过我的一位教授的说法，ArrayLists就像是试图从阵列转移到List-type Collections的混蛋概念孩子，即曾经对阵列有了很大的改进，它们不再是最好的选择，因为在收集方面已经进行了进一步的开发

    List（Of T）：ArrayList成为（并希望是）

    内存使用的差异非常大，以至于List（Of Int32）比包含相同原始类型的ArrayList消耗的内存少56％（在上述绅士的链接演示中，8 MB与19 MB相比：再次，链接here） - 尽管这是由64位机器复合的结果 . 这种差异确实证明了两件事：第一（1），盒装Int32型"object"（ArrayList）比纯Int32原型（List）大得多;第二（2），差异是指数为a64位机器内部工作的结果 .

    那么，有什么区别，什么是List(Of T)？ MSDN定义 List(Of T) as，"... a strongly typed list of objects that can be accessed by index."这里的重要性是"strongly typed"位：List（Of T）'recognizes'类型并将对象存储为其类型 . 因此， Int32 存储为 Int32 而不是 Object 类型 . 这消除了装箱和拆箱引起的问题 .

    MSDN specifies this difference only comes into play when storing primitive types and not reference types. 太多，差异确实大规模发生：超过500个元素 . 更有趣的是MSDN文档读取，"It is to your advantage to use the type-specific implementation of the List(Of T) class instead of using the ArrayList class...."

    本质上，List（Of T）是ArrayList，但更好 . 它是ArrayList的“通用等价物” . 与ArrayList一样，不保证在排序之前对其进行排序（如图所示） . List（Of T）也有一些附加功能 .

    回复于
  • 5

    他们在intellisense中拼写得非常好 . 只需键入System.Collections . 或System.Collections.Generics（首选），你'll get a list and short description of what'可用 .

    回复于
  • 16

    Hashtables / Dictionaries是O（1）性能，这意味着性能不是大小的函数 . 知道这一点很重要 .

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

    回复于
  • 2

    通用集合的性能优于非泛型集合，尤其是在迭代许多项目时 . 这是因为不再发生装箱和拆箱 .

    回复于
  • 1

    关于高频系统交易工程的Hashtable vs Dictionary的一个重要说明：线程安全问题

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

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

    回复于
  • 3

    实际上，我认为MSDN有助于为所有这些问题提供相当好的答案 . 只需查看.NET集合 .

    回复于
  • 17

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

    回复于
  • 2

    Most popular C# Data Structures and Collections

    • Array

    • ArrayList

    • List

    • LinkedList

    • Dictionary

    • HashSet

    • Stack

    • Queue

    • SortedList

    C#.NET 有许多不同的数据结构，例如，最常见的一种是数组 . 但是，C＃带有更多基本数据结构 . 选择正确的数据结构是编写结构良好且高效的程序的一部分 .

    在本文中，我将介绍内置的C＃数据结构，包括C＃.NET 3.5中引入的新结构 . 请注意，其中许多数据结构适用于其他编程语言 .

    Array

    最简单和最常见的数据结构是数组 . C＃数组基本上是一个对象列表 . 它的定义特征是所有对象都是相同类型（在大多数情况下），并且具有特定数量的对象 . 数组的性质允许基于它们在列表中的位置（也称为索引）非常快速地访问元素 . C＃数组的定义如下：

    [object type][] myArray = new [object type][number of elements]

    一些例子：

    int[] myIntArray = new int[5];
 int[] myIntArray2 = { 0, 1, 2, 3, 4 };

    从上面的示例中可以看出，数组可以初始化，不包含任何元素或来自一组现有值 . 只要值合适，将值插入数组就很简单 . 当元素的数量超过数组的大小时，操作会变得昂贵，此时需要扩展数组 . 这需要更长的时间，因为必须将所有现有元素复制到新的更大的数组 .

    ArrayList

    C＃数据结构ArrayList是一个动态数组 . 这意味着ArrayList可以包含任意数量的对象和任何类型的对象 . 此数据结构旨在简化将新元素添加到数组中的过程 . 在引擎盖下，ArrayList是一个数组，每当空间不足时，其大小加倍 . 将内部阵列的大小加倍是一种非常有效的策略，可以长期减少元素复制的数量 . 我们不会在此证明这一点 . 数据结构使用非常简单：

    ArrayList myArrayList = new ArrayList();
    myArrayList.Add(56);
    myArrayList.Add("String");
    myArrayList.Add(new Form());

    ArrayList数据结构的缺点是必须将已检索的值转换回其原始类型：

    int arrayListValue = (int)myArrayList[0]

    Sources and more info you can find here ：

    回复于

相关问题