List <>元素是否按顺序位于堆中？

Question

我正在学习C#,基本上知道数组和Lists 之间的区别,最后一个是通用的,可以动态增长,但我想知道:

• 被List元件顺序地位于堆状阵列或位于"随机"在不同的位置的每个元素？
• 如果这是真的,那是否会影响从内存访问和数据检索的速度？
• 如果这是真的,这是什么使得数组比Lists 快一点？

Answer 1

让我们先看看第二个和第三个问题:

如果这样做会影响从内存访问和数据检索的速度吗？

如果这是真的是什么使得数组比列表快一点？

在.NET中只有一种类型的"本机"集合(使用.NET我的意思是CLR,所以运行时):数组(从技术上讲,如果你考虑一种string集合,那么有两种本地类型的集合:-))(从技术上讲,第2部分:并非所有你认为是数组的数组都是"本机"数组......只有基于单维0的数组是"本机"数组.类型的数组T[,]不是,而数组的第一个数组元素没有索引0不是).每个其他集合(除了LinkedList<>)都是在它上面构建的.如果你看看List<T>与IlSpy你会发现在它的基础是有T[]与添加int的Count(该T[].Length是Capacity).显然,一个数组比a快一点,List<T>因为要使用它,你只需要少一个间接(你可以直接访问数组,而不是访问访问列表的数组).

让我们看看第一个问题:

List元素顺序位于堆像数组中,还是每个元素随机位于不同的位置？

基于内部数组,显然会List<>像元素一样记忆它的元素,所以在一个连续的内存块中(但要注意,List<SomeObject>where SomeObject是一个引用类型,列表是引用列表,而不是对象列表,所以引用放在一个连续的内存块中(我们将忽略使用计算机的高级内存管理,"连续的内存块"这个词并不精确",最好说"一个连续的地址块") )

(是的,甚至Dictionary<>和HashSet<>内置阵列之上,相反树状集合可以在不使用数组来建,因为它更类似于一个LinkedList)

一些额外的细节:语言中有四组指令CIL(编译的.NET程序中使用的中间语言)与"本机"数组一起使用:

• Newarr

• Ldelem 和家人 Ldelem_*

• Stelem 和家人 Stelem_*

• ReadOnly (不要问我使用它,我不知道,文件不清楚)

如果你看一下,OpCodes.Newarr你会在XML文档中看到这个评论:

// Summary:
//     Pushes an object reference to a new zero-based, one-dimensional array whose
//     elements are of a specific type onto the evaluation stack.

Answer 2

是的，List 中的元素是连续存储的，就像数组一样。列表实际上在内部使用数组，但这是您实际上不需要关心的实现细节。

当然，为了从该陈述中获得正确的印象，您还必须了解一些有关 .NET 中的内存管理的知识。即值类型和引用类型之间的区别，以及这些类型的对象如何存储。值类型将存储在连续的内存中。对于引用类型，引用将存储在连续的内存中，而不是实例本身。

使用列表的优点是类内部的逻辑会为您处理分配和管理项目。您可以在任何地方添加元素、从任何地方删除元素以及增加集合的整个大小，而无需执行任何额外的工作。当然，这也是 List 比数组稍慢的原因。如果为了满足您的请求而必须进行任何重新分配，那么当分配一个更大的新数组并将元素复制到其中时，性能将会受到影响。但它不会比您编写代码来使用原始数组手动执行此操作慢。

如果您的长度要求是固定的（即，您永远不需要增加/扩展数组的总容量），您可以继续使用原始数组。它甚至可能比 List 稍微快一些，因为它避免了额外的开销和间接性（尽管这可能会被 JIT 编译器优化掉）。

如果您需要能够动态调整集合的大小，或者需要 List 类提供的任何其他功能，只需使用 List。性能差异几乎难以察觉。