.net源码分析 – List<T>

旧城等待， 2021-06-26 16:06 385阅读 0赞

通过分析源码可以更好理解`List<T>`的工作方式，帮助我们写出更稳定的代码。

`List<T>`源码地址: [https://github.com/dotnet/corefx/blob/master/src/System.Collections/src/System/Collections/Generic/List.cs。][https_github.com_dotnet_corefx_blob_master_src_System.Collections_src_System_Collections_Generic_List.cs]

## 接口 ##

`List<T>`实现的接口：`IList<T>, IList, IReadOnlyList<T>`

其实`.net framework`经过多代发展，`List`的接口确实是有点多了，添加新功能时为了兼容老功能，一些旧的接口又不能丢掉，所以看上去有点复杂。先把这些接口捋一下：  
![在这里插入图片描述][20181128223903845.png]  
`IEnumerator`是枚举器接口，拥有枚举元素的功能，成员有`Current, MoveNext, Reset`，这三个函数可以使集合支持遍历。

`IEnumerable`是支持枚举接口，实现这接口表示支持遍历，成员就是上面的`IEnumerator`。

`ICollection`是集合接口，支持着集合的`Count`属性和`CopyTo`操作，另外还有同步的属性`IsSynchronized`（判断是否线程安全）和`SyncRoot`（`lock`的对象）。

`IList`是集合的操作接口，支持索引器，`Add, Remove, Insert, Contains`等操作。

泛型部分基本是上面这些接口的泛型实现，不过`IList<T>`的一些操作放到`ICollection<T>`里了，可能微软也觉得对于集合的一些操作放到`ICollection`更合理吧。

`IReadOnlyCollection<T>`[是.net][.net] 4.5加进来的，可以认为是`IList<T>`的只读版。

## 变量 ##

private const int _defaultCapacity = 4;
    
    private T[] _items;
    
    private int _size;
    
    private int _version;
    
    private Object _syncRoot;
    
    static readonly T[] _emptyArray = new T[0];

`_defaultCapacity`意思是`new List<T>`时默认大小是4。

`_items`就是存`List<T>`元素的数组了，`List<T>`也是基于数组实现的。

`_size`指元素个数。

`_version`看字面意思是版本，具体用处下面看，与遍历集合时经常碰到的集合被修改异常有关。

`_syncRoot`上面有说到，内置的用于`lock`的对象，如果在多线程时只是操作这个集合就可以`lock`这个来保证线程安全，当然一般来说这个是内部用的，虽然对`List<T>`本身来说没什么用，这个不取的话是不会把对象`new`出来的，对于锁我们更常用的是在外面`new`一个`readonly`的`object`。

`emptyArray`这是个静态只读的空数组，所有没有元素的`List<T>`都是用这个，所以两个`List<int>`的`_items`其实是一样的，都是这个`_emptyArray`。  
![在这里插入图片描述][20181128224345268.png]

## 构造函数 ##

有三个构造函数

public List()
    { 
       _items = _emptyArray;
    }

最常用的，`_items`直接指向静态空数组。

public List(int capacity)
    { 
        if (capacity < 0) throw new ArgumentOutOfRangeException(nameof(capacity), capacity, SR.ArgumentOutOfRange_NeedNonNegNum);
        Contract.EndContractBlock();
    
        if (capacity == 0)
            _items = _emptyArray;
        else
            _items = new T[capacity];
    }

可以通过`capacity`指定大小

public List(IEnumerable<T> collection)
    { 
        if (collection == null)
            throw new ArgumentNullException(nameof(collection));
        Contract.EndContractBlock();
    
        ICollection<T> c = collection as ICollection<T>;
        if (c != null)
        { 
            int count = c.Count;
            if (count == 0)
            { 
                _items = _emptyArray;
            }
            else
            { 
                _items = new T[count];
                c.CopyTo(_items, 0);
                _size = count;
            }
        }
        else
        { 
            _size = 0;
            _items = _emptyArray;
            // This enumerable could be empty. Let Add allocate a new array, if needed.
            // Note it will also go to _defaultCapacity first, not 1, then 2, etc.
    
            using (IEnumerator<T> en = collection.GetEnumerator())
            { 
                while (en.MoveNext())
                { 
                    Add(en.Current);
                }
            }
        }
    }

初始添加一个集合， 先看是否是`ICollection`，看上面知道这个接口有`Copy`的功能，`copy`到`_items`里。如果不是`ICollection`，不过由于是`IEnumerable`，所以可以遍历，一个一个加到`_items`里。

## 属性 ##

`Count` 返回的是`_size`，这个是元素的实际个数，不是数组大小。

`IsSynchronized`是`false`，表示并非用`SyncRoot` 来实现同步。`List<T>`不是线程安全，需要我们自己用锁搞定，

`IsReadOnly`也是`false`, 那为什么要继承`IReadOnlyList<T>`呢，是为了提供一个转换成只读`List`的机会，比如有的方法不希望传进来的`List`可以修改，就可以把参数设成`IReadOnlyList`。

Object System.Collections.ICollection.SyncRoot
    { 
        get
        { 
            if (_syncRoot == null)
            { 
                System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null);
            }
            return _syncRoot;
        }
    }

`SyncRoot`通过原子操作得到一个对象，对于`List<T>`来说并没有用，对于某些集合比较有用，比如`SyncHashtable`，就是通过`syncRoot`来实现线程安全。

比较重要的`Capacity`:

public int Capacity
    { 
        get
        { 
            Contract.Ensures(Contract.Result<int>() >= 0);
            return _items.Length;
        }
        set
        { 
            if (value < _size)
            { 
                throw new ArgumentOutOfRangeException(nameof(value), value, SR.ArgumentOutOfRange_SmallCapacity);
            }
            Contract.EndContractBlock();
    
            if (value != _items.Length)
            { 
                if (value > 0)
                { 
                    var items = new T[value];
                    Array.Copy(_items, 0, items, 0, _size);
                    _items = items;
                }
                else
                { 
                    _items = _emptyArray;
                }
            }
        }
    }

`Capacity`取的就是数组的长度，另外我们可以通过`Capacity`给`List`设置大小，即使这个`List`里面已经有元素，会先`new`一个目标大小的数组，然后通过`Array.Copy`把现有元素复制到新数组里。但一般情况下这些不用我们设置`Capacity`，添加新元素时发现长度不够会自动扩大数组。`Capacity`是int型，说明最大是`int.MaxValue`，大约2G个，如果我们直接给`List`设置`int.MaxValue`就要看你的内存够不够2G\*4也就是8G了，不够的话会报`OutofMemory Exception`。其实个人觉得这里`Capacity`用`uint`是不是更好。  
![在这里插入图片描述][2018112822513673.png]  
用100M个，内存占用400M多  
![在这里插入图片描述][20181128225203906.png]  
同样100M个，由于是`long`，内存占了800M多  
![在这里插入图片描述][20181128225328609.png]

## 方法 ##

看几个重要的方法：

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

当前数组大小和元素个数相等时表明再`Add`的话大小不够了，需要先通过`EnsureCapacity`扩容, `_size+1`指明了一个最小的扩容目标。

private void EnsureCapacity(int min)
    { 
        if (_items.Length < min)
        { 
            int newCapacity = _items.Length == 0 ? _defaultCapacity : _items.Length * 2;
            // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
            // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
            //if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;
            if (newCapacity < min) newCapacity = min;
            Capacity = newCapacity;
        }
    }

扩容方法，如果数组长度是0的话则用`_defaultCapacity`也就是4来做为数组长度，否则则以当前元素个数的2倍去扩大。如果新得到的长度比传进来的`min`小的话则就用`min`，也就是选大的，这种情况在`InsertRange`时有可能发生，因为`insert`的`list`很可能比当前`list`的元素个数多。

`Add`函数里还有个`_version++`，这个\_version可以在很多方法里看到，如`remove, insert, sort`等，但凡要修改集合都需要`_version++`。那这个`_version`有什么用呢？

public void ForEach(Action<T> action)
    { 
        if (action == null)
        { 
            throw new ArgumentNullException(nameof(action));
        }
    
        int version = _version;
    
        for (int i = 0; i < _size; i++)
        { 
            if (version != _version)
            { 
                break;
            }
            action(_items[i]);
        }
    
        if (version != _version)
            throw new InvalidOperationException(SR.InvalidOperation_EnumFailedVersion);
    }

在遍历时如果发现`_version`变了立即退出并抛出遍历过程集合被修改异常，比如在`foreach`里`remove`或`add`元素就会导致这个异常。更常见的是出现在多线程时一个线程遍历集合，另一个线程修改集合的时候，相信很多人吃过苦头。

如果一个线程时想在遍历时修改集合，比如删除，可以用原始的`for(int i=list.Count-1;i>=0;i--)`方式。

另外用到`version`还有枚举器`Enumerator`，`MoveNext`过程中同样会检测这个。

其他大部分方法都是通过`Array`的静态函数实现，不多说，需要注意的是`List<T>`继承自`IList`，所以可以转成`IList`，转之后泛型就没了，如果是`List<int>`，转成`IList`的话和`IList<object>`没什么两样，装拆箱带来的性能损失也值得注意。

## 总结 ##

`List<T>`初始大小是4，自动扩容是以当前数组元素的两倍或`InsertRange`目标`list`的元素个数来扩容（哪个大选哪个）。如果有比较确定的大小可以考虑提前设置，因为每次自动扩容需要重新分配数组和`copy`元素，性能损耗不小。

`List<T>`通过`version`来跟踪集合是否发生改变，如果在`foreach`遍历时发生改变则抛出异常。

`List<T>`并非线程安全，任何使用的时候都要考虑当前环境是否可能有多线程存在，是否需要用锁来保证集合线程安全。

[https_github.com_dotnet_corefx_blob_master_src_System.Collections_src_System_Collections_Generic_List.cs]: https://github.com/dotnet/corefx/blob/master/src/System.Collections/src/System/Collections/Generic/List.cs%E3%80%82
[20181128223903845.png]: /images/20210626/73cd1d0067814d10863b5cc1cc7d8149.png
[.net]: http://xn--0iv.net
[20181128224345268.png]: /images/20210626/3605a07031ad461597177896f7d744a1.png
[2018112822513673.png]: /images/20210626/bafbb05095c84b0995bed59d2b855a75.png
[20181128225203906.png]: /images/20210626/390101965fb34d61a7e1b3eca4dbb973.png
[20181128225328609.png]: /images/20210626/f1263265301b4bc38a522686b1424c3c.png