List 元素是否按顺序位于堆像数组中?

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

  • List元素是顺序位于堆像数组中还是每个元素“随机”位于不同的位置?
  • 如果这是真的,那会影响从内存访问和数据检索的速度吗?
  • 如果这是真的,这是什么使得数组比List s快一点?

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

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

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

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

让我们看看第一个问题:

List元素是按顺序位于堆类数组中还是每个元素随机位于不同的位置?

基于内部数组,显然List<>其元素记忆为数组,因此在连续的内存块中(但要注意使用List ,其中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. 

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

当然,为了从该声明中获得正确的印象,您还必须了解.NET中的内存管理。 即, 值类型和引用类型之间的差异 ,以及如何存储这些类型的对象。 值类型将存储在连续的内存中。 对于引用类型,引用将存储在连续的内存中,但不存储在实例本身中。

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

如果您的长度要求是固定的(即,您永远不需要增加/扩展arrays的总容量),您可以继续使用原始arrays。 它甚至可能比List略快,因为它避免了额外的开销和间接(尽管这可能会受到JIT编译器的优化)。

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