问答中心分类: VB.NET.Net 数据结构:ArrayList、List、HashTable、Dictionary、SortedList、SortedDictionary——速度、内存以及何时使用它们?
0
Abe Heidebrecht 提问 29分钟 前

关闭.这个问题需要多专注.它目前不接受答案。

想改进这个问题?更新问题,使其仅关注一个问题编辑这篇文章.

关闭去年.

改进这个问题

.NET 有很多复杂的数据结构。不幸的是,其中一些非常相似,我并不总是确定什么时候使用一个,什么时候使用另一个。我的大部分 C# 和 VB 书籍都在一定程度上谈到了它们,但它们从未真正深入任何真正的细节。
Array、ArrayList、List、Hashtable、Dictionary、SortedList 和 SortedDictionary 有什么区别?
哪些是可枚举的(IList — 可以执行“foreach”循环)?哪些使用键/值对(IDict)?
内存占用呢?插入速度?检索速度?
还有其他值得一提的数据结构吗?
我仍在寻找有关内存使用和速度的更多详细信息(Big-O 表示法)

user1228 回复 29分钟 前

你应该把这个问题分开。你问了二十个不同的问题,其中一半可以通过简单的谷歌搜索来回答。请更具体;当您的问题如此分散时,它很难提供帮助。

user1228 回复 29分钟 前

我想把它拆开,但意识到有人可能能够将所有这些答案整合到一个地方。事实上,如果有人能想出一个表格来分析所有内容,它可能会成为这个网站上的一个很好的资源。

user1228 回复 29分钟 前

这个问题可以变成维基吗?

user1228 回复 29分钟 前

瑞安,该链接上的文章已有 14 年历史(发帖时为 12 岁)。旁注我自己上周一直在阅读它们。但它们也不包括更新的技术,迫切需要更新。以及更多性能指标和示例。

user1228 回复 29分钟 前

LinkedList 在您的问题中有什么地方吗?只是问问而已。

user1228 回复 29分钟 前

@Dracolyte 我相信这个问题是你想问的,它被删除了。

11 Answers
0
Adam Tegen 回答 29分钟 前

如果可能,请使用泛型。这包括:

  • 列表而不是 ArrayList
  • 字典而不是 HashTable
0
Abe Heidebrecht 回答 29分钟 前

首先,.NET 中的所有集合都实现了 IEnumerable。
其次,很多集合都是重复的,因为泛型是在 2.0 版框架中添加的。
因此,尽管通用集合可能会添加功能,但在大多数情况下:

  • List 是 ArrayList 的通用实现。
  • 字典<T,K>是 Hashtable 的通用实现

数组是一个固定大小的集合,您可以更改存储在给定索引处的值。
SortedDictionary 是一个 IDictionary<T,K>这是根据键排序的。 SortedList 是一个字典<T,K>根据所需的 IComparer 进行排序。
因此,IDictionary 实现(那些支持 KeyValuePairs)是:

  • 哈希表
  • 字典<T,K>
  • 排序列表<T,K>
  • 排序字典<T,K>

.NET 3.5 中添加的另一个集合是 Hashset。它是一个支持集合操作的集合。
此外,LinkedList 是一个标准的链表实现(List 是一个用于更快检索的数组列表)。

0
blackwing 回答 29分钟 前

这里有一些一般性的提示给你:

  • 您可以使用foreach关于实现的类型IEnumerable.IList本质上是一个IEnumberableCountItem(使用从零开始的索引访问项目)属性。IDictionary另一方面意味着您可以通过任何哈希索引访问项目。
  • Array,ArrayListList全部实现IList.Dictionary,SortedDictionary, 和Hashtable实施IDictionary.
  • 如果您使用的是 .NET 2.0 或更高版本,建议您使用上述类型的通用对应项。
  • 对于这些类型的各种操作的时间和空间复杂性,您应该查阅他们的文档。
  • .NET 数据结构在System.Collections命名空间。有类型库,例如PowerCollections它提供了额外的数据结构。
  • 要彻底了解数据结构,请查阅资源,例如CLRS.
Haim Bendanan 回复 29分钟 前

微软,似乎 sortedList 实现了 IDictionnary – 而不是 IList

blackwing 回复 29分钟 前

固定的。感谢您的评论。似乎 SortedList 保留了键/值列表,因此它基本上代表字典的数据。不记得我第一次写答案时这个类是如何工作的……

0
Thomas 回答 29分钟 前

.NET 数据结构:
更多关于为什么 ArrayList 和 List 实际上不同的对话
Arrays
正如一位用户所说,数组是“老派”集合(是的,数组被认为是一个集合,但不是System.Collections)。但是,与其他集合相比,数组的“老派”是什么,即您在标题中列出的那些(这里是 ArrayList 和 List(Of T))?让我们从数组的基础开始。
开始,Arrays在 Microsoft .NET 中,“允许您将多个 [逻辑相关] 项目视为单个集合的机制”(参见链接文章)。这意味着什么?数组按顺序存储各个成员(元素),一个接一个地存储在内存中,并具有起始地址。通过使用数组,我们可以轻松地访问从该地址开始的顺序存储的元素。
除此之外,与编程 101 个常见概念相反,数组确实可以非常复杂:
数组可以是单维的、多维的或加法的(交错的数组值得一读)。数组本身不是动态的:一旦初始化,数组nsize 预留足够的空间来容纳n对象的数量。数组中的元素数量不能增加或减少。Dim _array As Int32() = New Int32(100)在内存块上为数组保留足够的空间以包含 100 个 Int32 原始类型对象(在这种情况下,数组被初始化为包含 0)。该块的地址返回到_array.
根据这篇文章,通用语言规范(CLS) 要求所有数组都是从零开始的。 .NET 中的数组支持非从零开始的数组;但是,这种情况不太常见。由于从零开始的数组的“共性”,微软花费了很多时间优化他们的表现;因此,单维、从零开始的 (SZ) 数组是“特殊的”——并且实际上是数组的最佳实现(与多维等相反)——因为 SZ 具有用于操作它们的特定中间语言指令。
数组总是通过引用传递(作为内存地址)——这是数组难题的一个重要部分。虽然他们进行边界检查(会抛出错误),但也可以在数组上禁用边界检查。
同样,数组的最大障碍是它们无法重新调整大小。它们具有“固定”容量。在我们的历史中介绍 ArrayList 和 List(Of T):
ArrayList – 非泛型列表
ArrayList(随着List(Of T)– 虽然有一些关键的区别,这里,稍后解释) – 最好将其视为集合的下一个添加(在广义上)。 ArrayList 继承自从伊利诺伊州(“ICollection”的后代)接口。 ArrayLists 本身是更笨重– 需要更多高架– 比列表。
IList确实使实现能够将 ArrayLists 视为固定大小的列表(如 Arrays);然而,除了 ArrayLists 添加的额外功能之外,使用固定大小的 ArrayLists 并没有真正的优势,因为在这种情况下 ArrayLists(相对于 Arrays)明显更慢。
根据我的阅读,ArrayLists 不能是锯齿状的:“不支持使用多维数组作为元素……”。再一次,ArrayLists 棺材上的另一个钉子。 ArrayLists 也不是“类型化的”——这意味着,在一切之下,ArrayList 只是一个动态的对象数组:Object[].这在实现 ArrayList 时需要大量装箱(隐式)和拆箱(显式),再次增加了它们的开销。
未经证实的想法:我想我记得我读过或听过我的一位教授说 ArrayLists 是尝试从 Arrays 转移到 List-type Collections 的混蛋概念孩子,即曾经对 Arrays 进行了很大改进,它们不再是最好的选择,因为已经对收藏进行了进一步的开发
List(Of T):ArrayList 变成了什么(并希望变成什么)
内存使用量的差异非常显着,以至于 List(Of Int32) 消耗的内存比包含相同原始类型的 ArrayList 少 56%(在上述绅士的链接演示中为 8 MB 对 19 MB:再次,链接这里) – 虽然这是由 64 位机器复合的结果。这种差异确实表明了两件事:第一(1),装箱的 Int32 类型“对象”(ArrayList)比纯 Int32 原始类型(List)大得多;第二 (2),由于 64 位机器的内部工作,差异是指数级的。
那么,有什么区别,什么是列表(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) 还具有一些附加功能。

0
pk_code 回答 29分钟 前

我发现 Microsoft Docs on Collection and Data Structure 页面上的“Choose a Collection”部分非常有用
C# 集合和数据结构:选择一个集合
在此处输入图像描述
还有下面的矩阵来比较一些其他的特性
在此处输入图像描述