c# - 用什么数据结构来实现arraylist

Question

在构建数组列表时使用什么数据结构，因为我们能够在其上动态添加/删除值。

我假设它使用链表，但在做了一些谷歌后，我发现它使用矢量..但没有关于它的更多细节。

Answer 1

在现代处理器上，内存缓存为王。有效地使用缓存会产生巨大的不同，当程序访问内容未被缓存的地址时，处理器很容易停滞数百个周期，等待非常慢的内存总线提供数据。

顺序访问内存时，访问内存的效率最高。一个字节在缓存中可用的几率是最大的，它很可能出现在同一个缓存行中。这使得数组成为迄今为止最有效的集合对象，假设您按顺序索引数组元素。

因此，除了 LinkedList 之外，所有 .NET 集合类都使用数组来存储数据。包括哈希集合(Hashtable、Dictionary、Hashset)，它们使用的是数组的数组。包括数组列表。 LinkedList 应该避免使用，因为它的缓存局部性非常差，除非在随机已知位置进行廉价的插入和删除是主要问题。

数组的一个问题是它们的大小是固定的，这使得难以实现自动调整大小的集合，例如 ArrayList。这是通过故意浪费地址空间来解决的。每当数组填满容量时，就会重新分配 数组并复制元素。重新分配的大小是以前的两倍，您可以从 Capacity 属性中观察到这一点。虽然这听起来很昂贵，但该算法的摊销时间为 O(1)，并且操作系统中的虚拟内存子系统可确保您实际上不会为不使用的内存付费。 p>

您可以通过预先猜测容量来避免不太便宜的复制。有关更多详细信息，请参阅 this answer .