C#如何动态为List<T>分配内存？

Question

根据LukeH在C#中List<string>的最大数据限制是什么？中的回答，目前实现的List中可以存储的元素数量理论上为Int32.MaxValue，略大于20亿。

我们可以看到List可以容纳大量的项。我假设编译器并不会为每个新的List<T>实现释放2亿次T大小的空间，那么List如何动态增长呢？它是否有指向非连续内存空间的指针？

- 8protons

---

@CamiloTerevinto 谢谢你，Camilo。我不知道为什么我总是忘记去查看源代码。 - 8protons

这可能是一个基础问题，但它不是重复引用的问题。.NET中集合的内存分配讨论了堆栈与堆，并没有提到动态增长。 - Douglas

问题没有任何问题，你得到了很好的答案，但我仍然想指出原则上我们不知道，因为这是一个实现细节。它在各种平台和版本中可能会有所不同。 - Bent Tranberg

Answer 1

List<T>类使用内部的T[]数组实现。如果使用List<T>(int)构造函数进行初始化，它将分配指定大小的数组。如果使用默认构造函数，则会使用默认容量4，但在这种情况下，数组仅在第一次添加时分配。

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

就性能而言，这意味着添加元素是O(1)或O(n)操作，具体取决于是否需要增加容量（如Add中所讨论的）。但是，由于容量在需要增加时会加倍，因此随着列表变得越来越大，这种重新分配的频率呈指数级减少。例如，从4开始，容量增加会发生在4、8、16、32、64、128等元素处。因此，在调用Add n次时，重新分配的总成本大致为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

░符号表示已分配但尚未使用的空间。这些数组位置将包含T的默认值。对于char来说，这将是空字符\0。但是，这些值永远不会对消费者可见。

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

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

如评论中所述，上述某些方面（例如默认初始容量为4）是从.NET Framework 4.7.2的源代码中导出的实现细节。然而，核心原则深入人心，并且不太可能在其他/未来的框架中发生变化。

- Douglas

---

太好了。您能介绍一本关于这个的书或文献吗？ - Farhad Zamani

Answer 2

您的假设是正确的，编译器不会分配任何东西。 List<T> 类在内部使用数组来存储元素，并在每次调用 Add 时检查数组的大小是否足够，正如您可以在源代码中看到的那样。

public void Add(T item) {
    if (_size == _items.Length) EnsureCapacity(_size + 1);
    _items[_size++] = item;
    _version++;
}

private void EnsureCapacity(int min) {
    if (_items.Length < min) {
        int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;
        // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
        // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
        if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;
        if (newCapacity < min) newCapacity = min;
        Capacity = newCapacity;
    }
}

- Camilo Terevinto

Answer 3

源代码会非常明确地展示，就像@CamiloTerevinto的答案那样，如何具体实现，但文档也有所涉及。 List<>类的备注部分指出：

List类是ArrayList类的泛型等效类。它通过使用大小根据需要动态增加的数组来实现IList泛型接口。

Capacity属性的备注部分进行了详细说明：

容量是List在重新调整大小之前可以存储的元素数, 而Count是实际在List中的元素数。

容量总是大于或等于Count。如果在添加元素时Count超过了容量，则自动重新分配内部数组以便在复制旧元素并添加新元素之前进行扩充。

- Lance U. Matthews