名单＆LT; T＆GT;和ArrayList默认容量

问题描述：

我一直在寻找.NET的列表和的ArrayList 的实施与的反光。

I have been looking at .NET's List and ArrayList implementations with Reflector.

当在添加（T项目）看我跑过这个 EnsureCapacity （this._size + 1）：

When looking at the Add(T item) I ran across this.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看起来是这样的：

So EnsureCapacity looks like this:

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;
    }
}

为什么内部容量默认为4，然后递增2的倍数（如：双）？

Why does the internal Capacity default to 4 and then increment in multiples of 2(ie: double)?

答

关于调整需要的是由于以下原因时增加一倍。比方说，你要插入 N 项放入列表。我们将调整名单不超过为log N 倍以上。因此，插入 N 项放入列表将最坏情况下的 O（N）时间，以便插入恒定在摊销时间。此外，浪费的空间量由上界ñ。恒定比例增长的任何策略，将导致不断的摊余插入时间和线性空间浪费。增长速度超过一定比例的增长，可能会导致更快的插入，但在浪费更多的空间为代价。成长超过一定的比例增长放缓可能会导致更少的浪费空间，但在速度较慢的插入为代价的。

Regarding doubling when resizing is needed it is for the following reason. Let's say that you want to insert n items into a List. We will resize the list no more than log n times. Therefore, inserting n items into a List will take worst-case O(n) time so insertions are constant in amortized time. Further, the amount of wasted space is bounded above by n. Any strategy of constant proportional growth will result in constant amortized insertion time and linear wasted space. Growing faster than constant proportional growth could result in faster inserts but at the expense of more wasted space. Growing slower than constant proportional growth could result in less wasted space but at the expense of slower inserts.

默认容量为让小浪费内存（并且在开始小了一倍，调整策略是善者而从时间/空间的角度来看，因为我们刚才看到的任何伤害）。

The default capacity is so that little memory is wasted (and there is no harm in starting small as the doubling-resizing strategy is good from a time/space perspective as we just saw).

名单＆LT; T＆GT;和ArrayList默认容量

相关推荐