c# - List<T> 和 ArrayList 默认容量

Question

我一直在研究 .NET 的 List 和 ArrayList 实现 Reflector .

在查看 Add(T item) 时，我遇到了这个。EnsureCapacity(this._size + 1):

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

所以 EnsureCapacity 看起来像这样:

private void EnsureCapacity(int min)
{
    if (this._items.Length < min)
    {
        int num = (this._items.Length == 0) ? 4 : (this._items.Length * 2);
        if (num < min)
        {
            num = min;
        }
        this.Capacity = num;
    }
}

为什么内部Capacity默认为4，然后以2的倍数递增(即:double)？

Answer 1

关于需要调整大小时加倍的原因如下。假设您要将 n 项插入到 List 中。我们将调整列表的大小不超过 log n 次。因此，将 n 项插入 List 将花费最坏情况下的 O(n) 时间，因此插入在 amortized time 中保持不变。 .此外，浪费的空间量受 n 限制。任何恒定比例增长的策略都会导致恒定的摊销插入时间和线性浪费的空间。比恒定比例增长更快的增长可能导致更快的插入，但代价是更多的空间浪费。增长速度慢于恒定比例增长可能会减少空间浪费，但代价是插入速度较慢。

默认容量使得很少有内存被浪费(并且从小开始没有坏处，因为正如我们刚刚看到的那样，从时间/空间的角度来看，双倍调整策略是好的)。