深入探讨List<>中的一个姿势。

距离上一篇博文，差不多两年了。终于憋出来了一篇。[手动滑稽]

List<>是c#中很常见的一种集合形式，近期在阅读c#源码时，发现了一个很有意思的定义：

[DebuggerTypeProxy(typeof(Mscorlib_CollectionDebugView<>))]
    [DebuggerDisplay("Count = {Count}")]
    [Serializable]
    public class List<T> : IList<T>, System.Collections.IList, IReadOnlyList<T>
    {
        private const int _defaultCapacity = 4;
 
        private T[] _items;
        [ContractPublicPropertyName("Count")]
        private int _size;
        private int _version;
        [NonSerialized]
        private Object _syncRoot;
        
        static readonly T[]  _emptyArray = new T[0];        
            
        // Constructs a List. The list is initially empty and has a capacity
        // of zero. Upon adding the first element to the list the capacity is
        // increased to 16, and then increased in multiples of two as required.
        public List() {
            _items = _emptyArray;
        }
    }
    ...
    ...
    ...
    private void EnsureCapacity(int min) {
        if (_items.Length < min) {
            int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;
            if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;
            if (newCapacity < min) newCapacity = min;
            Capacity = newCapacity;
        }
    }
           

咦，_defaultCapacity = 4， _items.Length * 2。抱着怀疑的态度，有了以下这一篇文章。

defaultCapacity=4？

带着怀疑的态度，我们新建一个Console程序，Debug一下。

var list = new List<int>();
Console.WriteLine(list.Capacity);
           

运行结果：

图片：

...怎么是0呢？一定是我打开的姿势不对，再看一下源码。发现：

static readonly T[]  _emptyArray = new T[0];
...
...
public List() {
     _items = _emptyArray;
}
           

哦，这就对了，初始化时候当然是0。那这个_defaultCapacity有何用？继续看源码。

if (_items.Length < min) {
    int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;
           

发现这个三元表达式，为什么要这样做呢？翻了一下google，发现了这样一段文字：

List实例化一个List对象时，Framework只是在内存中申请了一块内存存放List对象本身，系统此时并不知道List会有多少个item元素及元素本身大小。当List添加了第一个item时，List会申请能存储4个item元素的存储空间，此时Capacity是4，当我们添加第五个item时，此时的Capacity就会变成8。也就是当List发现元素的总数大于Capacity数量时，会主动申请且重新分配内存，每次申请的内存数量是之前item数量的两倍。然后将之前所有的item元素复制到新内存。

上面的测试，Capacity=0已经证明了上述这段话的

List实例化一个List对象时，Framework只是在内存中申请了一块内存存放List对象本身，系统此时并不知道List会有多少个item元素及元素本身大小。

接下来我们证明

当List添加了第一个item时，List会申请能存储4个item元素的存储空间，此时Capacity是4

RT，接下来，我们证明

我们添加第五个item时，此时的Capacity就会变成8。

RT，的确是这样。

那是否我们得出一个结论，因为不定长的List在Add的时候，频繁的重新申请、分配内存、复制到新内存，效率是否还可以再提升一下呢？

我们先试一下

for (int i = 0; i < count; i++)
{
    var listA = new List<int>(10);
    listA.Add(i);
}
           

循环次数	定长长度	运行时间
100	144
	5	23
	6	49
	7	45
	8	73
	9	21
	10	22

运行结果：注定长为0表示未设置List长度

10000	3741
		3934
		4258
		4013
		4830
		4159
		2370

好吃鲸...为啥9和10差距这么多。。。

我们加大循环次数。结果：

1000000	317590
		263378
		150444
		157317
		139041
		124714
		120547

随着循环次数、定长的增加，可以看出，频繁的重新申请、分配内存、复制到新内存，是很耗费时间和性能的。

在以后的工作中，如果有频繁的List.Add,特别是循环Add，不妨考虑一下给List设置一个定长。

鸟文名：YamatAmain

地 址:http://www.cnblogs.com/YamatAmain/

本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。