为什么删除项目后堆栈，队列和列表不缩小内部数组？

Question

在.NET中Stack，Queue和和List（以及它们的通用实现）在内部使用数组保存项目。

添加新元素时，内部数组的大小将增加一倍Push()，Enqueue()或者Add()如果已满。

问题是，为什么在删除项目时这些数据结构不将内部数组减半？最好将上的阵列大小减半，或者如果阵列的大小小于四分之一，以防止浪费内存。Pop()Dequeue()Remove()

我使用以下代码检查此行为：

var s = new Stack<int>();
for (int i = 0; i <= 512; i++) s.Push(i); // Increases the array capacity to 1024.
for (int i = 0; i <= 512; i++) s.Pop();   // Doesn't decrease array capacity.

// Stack is empty, but internal array capacity is still 1024:
var fieldInfo = typeof(Stack<int>).GetField("_array", BindingFlags.NonPublic | BindingFlags.Instance);
Console.WriteLine((fieldInfo.GetValue(s) as int[]).Length);

Answer 1

最有可能的效率。

缩小和增长阵列涉及到在内存中复制阵列。您不能简单地将少量的新内存标记到现有分配上，然后再将其从分配中删除：分配在操作系统中的大小是固定的，因此，如果您要增加数组的大小，实际上要分配新的内存块，请将所有内容从源复制到目标，然后删除旧的分配。这也是收缩的类似操作。这可能很耗时。

现在，鉴于数组已经增长到给定的大小，对于.NET（或任何其他框架）而言，它是该数组的最佳大小的一个很好的指标。即使从其中删除了项目，数组也有可能再次增长到相同的大小：.NET不是Mystic Meg，因此不会知道您永远不会再使用该数组的块。因此，与不断分配和取消分配内存块相比，增大分配直到不再需要再次增长才更有效，然后只担心在变量超出范围并成为该变量的目标时清理它GC。