.NET有很多复杂的数据结构.不幸的是,它们中的一些非常相似,我不总是确定何时使用一个以及何时使用另一个.我的大多数C#和Visual Basic书籍都在一定程度上谈论它们,但它们从未真正涉及任何真实的细节.
Array,ArrayList,List,Hashtable,Dictionary,SortedList和SortedDictionary之间有什么区别？
哪些是可枚举的(IList - 可以做'foreach'循环)？哪些使用键/值对(IDict)？
内存占用情况如何？插入速度？检索速度？
还有其他值得一提的数据结构吗？
我还在寻找有关内存使用和速度的更多细节(Big-O表示法).
脱离我的头顶:
Array* - 表示一个老式的内存数组 - 有点像普通type[]数组的别名.可以列举.无法自动增长.我会假设非常快的插入和回复速度.
ArrayList - 自动增长阵列.增加更多开销.可以枚举.,可能比正常数组慢,但仍然相当快.这些在.NET中使用很多
List- 我最喜欢的一个 - 可以与泛型一起使用,所以你可以有一个强类型数组,例如List.除此之外,行为非常像ArrayList
Hashtable - 普通的旧哈希表.O(1)到O(n)最坏的情况.可以枚举值和键属性,并执行键/值对
Dictionary - 与上述相同,仅通过泛型强类型,例如 Dictionary
SortedList - 已排序的通用列表.插入速度慢,因为它必须弄清楚放置的位置.可以枚举.可能在检索上是相同的,因为它不必求助,但删除将比普通的旧列表慢.
我倾向于使用List和Dictionary所有的时间 - 一旦你开始使用强类型泛型,它很难回到标准的非泛型.
还有很多其他的数据结构 - KeyValuePair你可以使用它来做一些有趣的事情,也有一些SortedDictionary也很有用.
如果可能的话,使用泛型. 这包括:
列表而不是ArrayList
字典而不是HashTable
首先,.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是一个用于更快检索的数组列表).
一本好的备忘单,提到数据结构,算法等的复杂性.
以下是一些适合您的一般提示:
您可以使用foreach实现的类型IEnumerable.IList本质上是一个IEnumberablewith Count和Item(使用从零开始的索引访问项目)属性.IDictionary另一方面,这意味着您可以通过任何可以删除的索引访问项目.
Array,ArrayList并List全部实施IList.
Dictionary,SortedDictionary和Hashtable实施IDictionary.
如果您使用的是.NET 2.0或更高版本,建议您使用上述类型的通用副本.
有关这些类型的各种操作的时间和空间复杂性,您应该查阅他们的文档.
.NET数据结构位于System.Collections命名空间中.有一些类型库,如PowerCollections,它们提供了额外的数据结构.
要全面了解数据结构,请参考CLRS等资源.
正如一个用户所说,Arrays是"旧学校"集合(是的,数组被认为是一个集合,虽然不是其中的一部分System.Collections).但是,与其他集合相比,数组中的"老派"是什么,即你在标题中列出的那些(这里是ArrayList和List(Of T))？让我们从查看Arrays开始.
首先,Microsoft .NET中的数组是"允许您将多个[逻辑相关]项目视为单个集合的机制"(参见链接文章).那是什么意思？数组按顺序存储各个成员(元素),在内存中一个接一个地存储起始地址.通过使用数组,我们可以轻松访问从该地址开始的顺序存储的元素.
除此之外,与编程101个常见概念相反,数组实际上可能非常复杂:
数组可以是单维,多维或jadded(锯齿状数组值得一读).数组本身不是动态的:一旦初始化,n大小的数组保留足够的空间来容纳n个对象.数组中的元素数量不能增长或缩小.Dim _array As Int32() = New Int32(100)在内存块上保留足够的空间,以使数组包含100个Int32基本类型对象(在这种情况下,数组初始化为包含0).返回此块的地址_array.
根据该文章,公共语言规范(CLS)要求所有阵列都是从零开始的..NET中的数组支持非零数组; 然而,这不太常见.由于零基数组的"共性",微软花了很多时间来优化其性能 ; 因此,单维,零基(SZs)数组是"特殊的" - 并且实际上是数组的最佳实现(与多维等相反) - 因为SZ具有用于操纵它们的特定中间语言指令.
数组总是通过引用传递(作为内存地址) - 要知道的数组难题的一个重要部分.虽然它们进行边界检查(将抛出错误),但也可以在数组上禁用边界检查.
同样,数组的最大障碍是它们不具有可重复性.他们有"固定"的能力.向我们的历史介绍ArrayList和List(Of T):
该ArrayList的(连同List(Of T)-虽然有一些重要的区别,在这里,稍后解释) -也许是为未来除了集合(广义上的)最好的思想.ArrayList继承自IList('ICollection'的后代)接口.ArrayLists本身比Lists 更笨重 - 需要更多开销.
IList确实使实现能够将ArrayLists视为固定大小的列表(如数组); 但是,除了ArrayLists添加的附加功能之外,使用固定大小的ArrayLists没有什么真正的优势,因为在这种情况下,ArrayLists(在Arrays上)明显更慢.
从我的阅读来看,ArrayLists不能被锯齿:"不支持使用多维数组作为元素......".再次,ArrayLists的棺材中的另一个钉子.ArrayLists也不是"类型化"的 - 这意味着,在所有内容下,ArrayList只是一个动态的对象数组:Object[].在实现ArrayLists时,这需要大量的装箱(隐式)和取消装箱(显式),再次增加了它们的开销.
毫无根据的想法:我想我记得要么是读过,要么听过我的一位教授的说法,ArrayLists就像是试图从阵列转移到List-type Collections的混蛋概念孩子,即曾经对阵列有了很大的改进,它们不再是最好的选择,因为在收集方面已经进行了进一步的开发
内存使用的差异非常大,以至于List(Of Int32)比包含相同原始类型的ArrayList消耗的内存少56%(在上面的绅士链接演示中,8 MB与19 MB相比:此处再次链接) - 尽管这是由64位机器复合的结果.这种差异实际上证明了两件事:第一(1),盒装Int32型"对象"(ArrayList)比纯Int32基元类型(List)大得多; 第二个(2),由于64位机器的内部工作,差异是指数的.
那么,有什么区别,什么是List(Of T)？MSDN定义了一个List(Of T)as,"......一个可以通过索引访问的强类型对象列表." 这里的重要性是"强类型"位:List(Of T)'识别'类型并将对象存储为其类型.因此,a Int32存储为Int32而不是Object类型.这消除了装箱和拆箱引起的问题.
MSDN指定这种差异仅在存储基元类型而非存储类型时发挥作用.太多,差异确实大规模发生:超过500个元素.更有趣的是,MSDN文档中写道:"使用List(Of T)类的特定于类型的实现而不是使用ArrayList类对你有利."
本质上,List(Of T)是ArrayList,但更好.它是ArrayList的"通用等价物".与ArrayList一样,不保证在排序之前对其进行排序(如图所示).List(Of T)也有一些附加功能.
我同情这个问题 - 我也发现(找到？)选择令人困惑,所以我科学地设定了哪个数据结构最快(我用VB做了测试,但我想C#会是相同的,因为两种语言在CLR级别做同样的事情).你可以看到我在这里进行的一些基准测试结果(还讨论了哪种数据类型最适合在哪种情况下使用).
京公网安备 11010802040832号 | 京ICP备19059560号-6 