List <T>和ArrayList默认容量

Question

我一直在用Reflector查看.NET的List和ArrayList实现.

当看到Add(T项目)时,我碰到了这个.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;
    }
}

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

Answer 1

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

默认容量是浪费很少的内存(并且从小时开始没有什么害处,因为从我们刚刚看到的时间/空间角度看,双倍调整大小的策略是好的).

Answer 2

4是一个很好的默认值,因为大多数集合中只有几个项目.增量完成是为了确保每次添加项目时都不进行内存分配.

请参阅Joel关于内存使用情况的这篇好文章以及为什么分配双倍所需内容是一个好主意.

http://www.joelonsoftware.com/printerFriendly/articles/fog0000000319.html

这是相关的引用:

假设您编写了一个智能strcat函数,可以自动重新分配目标缓冲区.它应该始终将其重新分配到所需的确切大小吗？我的老师和导师Stan Eisenstat建议,当你调用realloc时,你应该总是将以前分配的内存大小加倍.这意味着你永远不必再调用realloc超过lg n次,即使对于巨大的字符串也具有良好的性能特征,并且你永远不会浪费超过50%的内存.

顺便说一句,列表<>和字典<>现在默认为10,但我敢打赌它们具有相同的递增逻辑.