C#如何为列表动态分配内存？ [英] How does C# dynamically allocate memory for a List<T>?

问题描述

发件人LukeH's答复what is the max limit of data into list<string> in c#?

List的当前实现中可以存储的最大元素数理论上是Int32.MaxValue，略高于20亿。

我们看到一个列表可以包含大量的项目。我假设编译器不只是为List<T>的每个新实现释放20亿倍于T的空间，那么列表如何动态增长呢？它是否有指向内存中非连续空格的指针？

推荐答案

List<T>类实现为在幕后使用内部T[]数组。如果使用List<T>(int)构造函数对其进行初始化，则它将分配指定大小的数组。如果使用默认构造函数，它将使用默认容量4，但在本例中，数组将仅在第一次相加时分配。

每次向列表添加元素时，都会首先检查是否已达到容量(即现有的Count是否等于Capacity)。如果是这样，它将创建一个大小是前一个数组两倍的新数组，将所有现有元素复制到其中，然后继续写入新元素。这将在后续元素添加时无限期地发生，直到达到您引用的硬限制(Int32.MaxValue)。

性能方面，这意味着元素的添加要么是O(1)操作，要么是O(N)操作，具体取决于容量是否需要增加(如Add中所讨论的)。但是，由于容量在需要增加时会翻一番，因此随着列表的增大，这种重新分配的频率会呈指数级下降。例如，从4开始，容量增加将发生在4、8、16、32、64、128、…元素。因此，当调用Addn次时，重新分配的总成本将大约为4 + 8 + 16 + … + n/8 + n/4 + n/2，仍对应于O(N)。

下面的示例显示了一系列加法操作中内部数组的状态：

                               //   ┌┐
var list = new List<char>();   //   ││   Count:    0
                               //   └┘   Capacity: 0
                               //   ┌───┬───┬───┬───┐
list.Add('h');                 //   │ h │ ░ │ ░ │ ░ │   Count:    1
                               //   └───┴───┴───┴───┘   Capacity: 4
                               //   ┌───┬───┬───┬───┐
list.Add('e');                 //   │ h │ e │ ░ │ ░ │   Count:    2
                               //   └───┴───┴───┴───┘   Capacity: 4
                               //   ┌───┬───┬───┬───┐
list.Add('l');                 //   │ h │ e │ l │ ░ │   Count:    3
                               //   └───┴───┴───┴───┘   Capacity: 4
                               //   ┌───┬───┬───┬───┐
list.Add('l');                 //   │ h │ e │ l │ l │   Count:    4
                               //   └───┴───┴───┴───┘   Capacity: 4
                               //   ┌───┬───┬───┬───┬───┬───┬───┬───┐
list.Add('o');                 //   │ h │ e │ l │ l │ o │ ░ │ ░ │ ░ │   Count:    5
                               //   └───┴───┴───┴───┴───┴───┴───┴───┘   Capacity: 8
                               //   ┌───┬───┬───┬───┬───┬───┬───┬───┐
list.Add(' ');                 //   │ h │ e │ l │ l │ o │   │ ░ │ ░ │   Count:    6
                               //   └───┴───┴───┴───┴───┴───┴───┴───┘   Capacity: 8
                               //   ┌───┬───┬───┬───┬───┬───┬───┬───┐
list.Add('w');                 //   │ h │ e │ l │ l │ o │   │ w │ ░ │   Count:    7
                               //   └───┴───┴───┴───┴───┴───┴───┴───┘   Capacity: 8
                               //   ┌───┬───┬───┬───┬───┬───┬───┬───┐
list.Add('o');                 //   │ h │ e │ l │ l │ o │   │ w │ o │   Count:    8
                               //   └───┴───┴───┴───┴───┴───┴───┴───┘   Capacity: 8
                               //   ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
list.Add('r');                 //   │ h │ e │ l │ l │ o │   │ w │ o │ r │ ░ │ ░ │ ░ │ ░ │ ░ │ ░ │ ░ │   Count:    9
                               //   └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘   Capacity: 16
                               //   ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
list.Add('l');                 //   │ h │ e │ l │ l │ o │   │ w │ o │ r │ ░ │ ░ │ ░ │ ░ │ ░ │ ░ │ ░ │   Count:    10
                               //   └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘   Capacity: 16
                               //   ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
list.Add('d');                 //   │ h │ e │ l │ l │ o │   │ w │ o │ r │ l │ d │ ░ │ ░ │ ░ │ ░ │ ░ │   Count:    11
                               //   └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘   Capacity: 16

<2-7]>符号表示仍未使用的已分配空间。这些数组位置将包含T的default value。对于char，这将是空字符。但是，消费者永远看不到这些值。

通过AddRange添加多个元素时，最多只重新分配一次。如果将以前的容量增加一倍不足以容纳所有新元素，则内部数组将立即增加到新计数。

与添加不同，删除元素不会自动缩小列表。但是，您可以通过调用TrimExcess手动执行此操作。

如comments中所述，上述内容的某些方面(如默认初始容量4)是从.NET框架4.7.2的实现细节派生的。然而，核心原则是根深蒂固的，不太可能在其他/未来框架中改变。

这篇关于C#如何为列表动态分配内存？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！