2.2 List底层源码剖析
部分编程多年的程序员在看到C#基础知识时总想跳过，因为看了太多次，次次都是一样的语法，都是由继承展开的特性，再加上一些高级属性，确实有点枯燥。但这里还是要强调基础的重要性，没有扎实的基础，所有编写的程序很有可能会随着软件规模和使用规模的扩大，或者使用途径的扩大而遇到越来越多的问题，这些程序最后大部分会被遗弃，或者需要重新进行编写。
也是深知基础的重要性，很多资深的程序员从这里出发，最终又回到了这里，他们一遍又一遍地看着这部分内容，希望从中得到新的启发或者纠正自己以前的错误观念。
我一方面想把基础的知识告知大家，另一方面又不想让大家觉得枯燥，所以想写些不一样的内容。在我看来，能读本书的，基本上都能做到基础语法部分已经滚瓜烂熟，所以本章在基础语法之上讲些进阶的内容会更有趣，如算法设计、常用组件的底层代码分析、设计模式、程序逻辑优化等。
首先讲解我们在日常工作中常会用到的C#组件底层的原理，从本章的知识中，我们可以充分了解到日常编程代码中这些组件在底层是如何运作的，当我们再次编写代码时，能有意识地理解背后的执行步骤，从而能更好地提升代码的质量。
1. List底层代码剖析
List是C#中一个最常见的可伸缩数组组件，我们常用它来替代数组。因为它是可伸缩的，所以我们在编写程序的时候不用手动去分配数组的大小，甚至有时会拿它当链表使用。那么到底它的底层是怎么编写的呢？每次增加和减少以及赋值，内部是如何执行和运作的呢？接下来进行详细讲解。
我们先来看看List的构造部分，源码如下：
public class List<T>: IList<T>, System.Collections.IList, IReadOnlyList<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];
// 构建一个列表，该列表最初是空的，容量为零
// 将第一个元素添加到列表后，容量将增加到16，然后根据需要以2的倍数增加
public List() {
_items = _emptyArray;
}
// 构造具有给定初始容量的List。该列表最初是空的。但是在需要重新分配之前，会为给定数量的元素留出空间。
//
public List(int capacity) {
if (capacity<0) ThrowHelper.ThrowArgumentOutOfRangeException(
ExceptionArgument.capacity,
ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
Contract.EndContractBlock();
if (capacity == 0)
_items = _emptyArray;
else
_items = new T[capacity];
}
// ...
// 其他内容
}
从以上源码可以知道，List继承于IList、IReadOnlyList。IList提供主要接口，IRead-OnlyList提供迭代接口。
IList源码网址为：https://referencesource.microsoft.com/#mscorlib/system/collections/ilist.cs,5d74f6adfeaf6c7d。
IReadOnlyList源码网址为：https://referencesource.microsoft.com/#mscorlib/system/collections/generic/ireadonlylist.cs,b040fb780bdd59f4。
看构造部分，我们明确了List内部是用数组实现的，而不是链表，并且当没有给予指定容量时，初始的容量为0。
也就是说，我们可以大概率推测，List组件在被Add()、Remove()两个函数调用时，都是采用“在数组上对元素进行转移的操作，或者从原数组复制生成到新数组”的方式工作的。
下面看看我们的猜测是否正确。
2. Add接口剖析
Add接口源码如下：
// 将给定对象添加到此列表的末尾。列表的大小增加1
// 如果需要，在添加新元素之前，列表的容量会增加1倍
//
public void Add(T item) {
if (_size == _items.Length) EnsureCapacity(_size + 1);
_items[_size++] = item;
_version++;
}
// 如果列表的当前容量小于min，则容量将增加到当前容量的两倍或min，以较大者为准
private void EnsureCapacity(int min) {
if (_items.Length<min) {
int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;
// 在遇到溢出之前，允许列表增长到最大可能的容量（约2GB元素）
// 请注意，即使_items.Length由于（uint）强制转换而溢出，此检查仍然有效
if ((uint)newCapacity>Array.MaxArrayLength) newCapacity =
Array.MaxArrayLength;
if (newCapacity<min) newCapacity = min;
Capacity = newCapacity;
}
}
上述List源码中的Add()函数，每次增加一个元素的数据，Add接口都会首先检查容量是够还是不够，如果不够，则调用EnsureCapacity()函数来增加容量。
在EnsureCapacity()函数中，有这样一行代码：
int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;
每次容量不够的时候，整个数组的容量都会扩充一倍，_defaultCapacity表示容量的默认值为4。因此，整个扩充的路线为4、8、16、32、64、128、256、512、1024……以此类推。
List使用数组形式作为底层数据结构，优点是使用索引方式提取元素很快。缺点是在扩容时会很糟糕，每次针对数组进行new操作都会造成内存垃圾，这给垃圾回收（GC）带来了很大负担。
这里按2的指数扩容的方式，可以为GC减轻负担。但是，如果数组被连续申请扩容，还是会造成GC的不小负担，特别是代码中的List频繁使用Add时，数组会不断被扩容。此外，如果数量使用不当，也会浪费大量内存空间，例如，当元素的数量为520时，List就会扩容到1024个元素，如果不使用剩余的504个空间单位，就会造成大部分内存空间的浪费。具体该怎么做才是最佳的策略，我们将在后面讨论。
3. Remove接口剖析
下面再来看Remove接口部分的源码：
// 删除给定索引处的元素。列表的大小减1
//
public bool Remove(T item) {
int index = IndexOf(item);
if (index>= 0) {
RemoveAt(index);
return true;
}
return false;
}
// 返回此列表范围内给定值首次出现的索引
// 该列表从头到尾向前搜索
// 使用Object.Equals方法将列表中的元素与给定值进行比较
//
// 此方法使用Array.IndexOf方法执行搜索
//
public int IndexOf(T item) {
Contract.Ensures(Contract.Result<int>()>= -1);
Contract.Ensures(Contract.Result<int>()<Count);
return Array.IndexOf(_items, item, 0, _size);
}
// 删除给定索引处的元素。列表的大小减1
//
public void RemoveAt(int index) {
if ((uint)index>= (uint)_size) {
ThrowHelper.ThrowArgumentOutOfRangeException();
}
Contract.EndContractBlock();
_size--;
if (index<_size) {
Array.Copy(_items, index + 1, _items, index, _size - index);
}
_items[_size] = default(T);
_version++;
}
Remove()函数中包含IndexOf()和RemoveAt()函数，其中使用IndexOf()函数是为了找到元素的索引位置，使用RemoveAt()可以删除指定位置的元素。
从源码中可以看到，元素删除的原理就是使用Array.Copy对数组进行覆盖。IndexOf()是用Array.IndexOf接口来查找元素的索引位置，这个接口本身的内部实现就是按索引顺序从0到n对每个位置进行比较，复杂度为线性迭代O(n)。
4. Insert接口剖析
先别急着总结，下面再看Insert接口源码：
// 在给定索引处将元素插入此列表，列表的大小增加1
// 如果需要，在插入新元素之前，列表的容量会增加一倍
//
public void Insert(int index, T item) {
// 请注意，结尾处的插入是合法的
if ((uint) index>(uint)_size) {
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index,
ExceptionResource.ArgumentOutOfRange_ListInsert);
}
Contract.EndContractBlock();
if (_size == _items.Length) EnsureCapacity(_size + 1);
if (index<_size) {
Array.Copy(_items, index, _items, index + 1, _size - index);
}
_items[index] = item;
_size++;
_version++;
}
与Add接口一样，先检查容量是否足够，不足则扩容。从以上源码中获悉，Insert()函数插入元素时，使用的是复制数组的形式，将数组里指定元素后面的所有元素向后移动一个位置。
看到这里，我们就明白了List的Add、Insert、IndexOf、Remove接口都是没有做过任何形式优化的，使用的都是顺序迭代的方式，如果过于频繁使用，效率就会降低，也会造成不少内存的冗余，使得垃圾回收（GC）时要承担更多的压力。
其他相关接口，比如AddRange、RemoveRange的原理和Add与Remove的一样，区别只是多了几个元素，把单个元素变成以容器为单位的形式进行操作，其操作对象是数组对数组。它们都是先检查容量是否合适，不合适则扩容，或者当进行Remove操作时先得到索引位置，再整体覆盖掉后面的元素，容器本身大小不会变化，只是执行了数组覆盖的操作。
5.其他接口剖析
其他接口也同样基于数组，并使用了类似的方式来对数据执行操作。下面来快速看看其他常用接口的源码是如何实现的。
（1）[]接口
示例代码如下：
// 设置或获取给定索引处的元素
//
public T this[int index] {
get {
// 跟随技巧可以将范围检查减少一半
if ((uint) index>= (uint)_size) {
ThrowHelper.ThrowArgumentOutOfRangeException();
}
Contract.EndContractBlock();
return _items[index];
}
set {
if ((uint) index>= (uint)_size) {
ThrowHelper.ThrowArgumentOutOfRangeException();
}
Contract.EndContractBlock();
_items[index] = value;
_version++;
}
}
[]接口的实现是直接使用数组的索引方式获取元素。
（2）Clear接口
示例代码如下：
// 清除列表的内容
public void Clear() {
if (_size>0)
{
Array.Clear(_items, 0, _size); // 无须对此进行记录，我们清除了元素，以便gc可以回收引用
_size = 0;
}
_version++;
}
Clear接口是清除数组的接口，在调用时并不会删除数组，而只是将数组中的元素设置为0或NULL，并设置_size为0而已，用于虚拟地表明当前容量为0。有时候你会认为对数组执行清零操作也是多余的，因为我们并不关心不使用的数组元素中的对象，但是，如果不清零，对象的引用会依然被标记，那么垃圾回收器会认为该元素依然是被引用的，这么看来对数组执行清零操作也是必要的。
（3）Contains接口
Contains接口用于确定某元素是否存在于List中，示例代码如下：
// 如果指定的元素在List中，则Contains返回true
// 它执行线性O（n）搜索。平等是通过调用item.Equals()来确定的
//
public bool Contains(T item) {
if ((Object) item == null) {
for(int i=0; i<_size; i++)
if ((Object) _items[i] == null)
return true;
return false;
}
else {
EqualityComparer<T>c = EqualityComparer<T>.Default;
for(int i=0; i<_size; i++) {
if (c.Equals(_items[i], item)) return true;
}
return false;
}
}
从以上源码中可以看到，Contains接口是使用线性查找方式比较元素，对数组执行循环操作，比较每个元素与参数实例是否一致，如果一致则返回true，全部比较结束后还没有找到，则认为查找失败。
（4）ToArray接口
示例代码如下：
// ToArray返回一个新的Object数组，其中包含List的内容
// 这需要复制列表，这是一个O（n）操作
public T[] ToArray() {
Contract.Ensures(Contract.Result<T[]>() != null);
Contract.Ensures(Contract.Result<T[]>().Length == Count);
T[] array = new T[_size];
Array.Copy(_items, 0, array, 0, _size);
return array;
}
ToArray接口是转化数组的接口，它重新创建了一个指定大小的数组，将本身数组上的内容复制到新数组上再返回，如果使用过多，就会造成大量内存的分配，在内存上留下很多无用的垃圾。
（5）Find接口
示例代码如下：
public T Find(Predicate<T>match) {
if( match == null) {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
Contract.EndContractBlock();
for(int i = 0 ; i<_size; i++) {
if(match(_items[i])) {
return _items[i];
}
}
return default(T);
}
Find接口是查找接口，它使用的同样是线性查找方式，对每个元素进行循环比较，复杂度为O(n)。
（6）Enumerator接口
示例代码如下：
// 返回具有给定删除元素权限的此列表的枚举数
// 如果在进行枚举时对列表进行了修改，
// 则枚举器的MoveNext和GetObject方法将引发异常
//
public Enumerator GetEnumerator() {
return new Enumerator(this);
}
/// 仅供内部使用
IEnumerator<T>IEnumerable<T>.GetEnumerator() {
return new Enumerator(this);
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
return new Enumerator(this);
}
[Serializable]
public struct Enumerator : IEnumerator<T>, System.Collections.IEnumerator
{
private List<T>list;
private int index;
private int version;
private T current;
internal Enumerator(List<T>list) {
this.list = list;
index = 0;
version = list._version;
current = default(T);
}
public void Dispose() {
}
public bool MoveNext() {
List<T>localList = list;
if (version == localList._version && ((uint)index<(uint)localList._size))
{
current = localList._items[index];
index++;
return true;
}
return MoveNextRare();
}
private bool MoveNextRare()
{
if (version != list._version) {
ThrowHelper.ThrowInvalidOperationException(
ExceptionResource.InvalidOperation_EnumFailedVersion);
}
index = list._size + 1;
current = default(T);
return false;
}
public T Current {
get {
return current;
}
}
Object System.Collections.IEnumerator.Current {
get {
if( index == 0 || index == list._size + 1) {
ThrowHelper.ThrowInvalidOperationException(
ExceptionResource.InvalidOperation_EnumOpCantHappen);
}
return Current;
}
}
void System.Collections.IEnumerator.Reset() {
if (version != list._version) {
ThrowHelper.ThrowInvalidOperationException(
ExceptionResource.InvalidOperation_EnumFailedVersion);
}
index = 0;
current = default(T);
}
}
Enumerator接口是枚举迭代部分细节的接口，其中要注意Enumerator这个结构，每次获取迭代器时，Enumerator都会被创建出来，如果大量使用迭代器，比如foreach，就会产生大量的垃圾对象，这也是为什么我们常常告诫程序员尽量不要使用foreach，因为List的foreach会增加新的Enumerator实例，最后由GC单元将垃圾回收掉。虽然.NET在4.0后已经修复了此问题，但仍然不建议大量使用foreach。
（7）Sort接口
示例代码如下：
// 对列表中一部分元素进行排序
// 排序使用给定的IComparer接口对元素进行比较
// 如果comparer为null，则使用IComparable接口对元素进行比较
// 在这种情况下，该接口必须由列表中的所有元素实现
//
// 此方法使用Array.Sort方法对元素进行排序
//
public void Sort(int index, int count, IComparer<T>comparer) {
if (index<0) {
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index,
ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
}
if (count<0) {
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count,
ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
}
if (_size - index<count)
ThrowHelper.ThrowArgumentException(
ExceptionResource.Argument_InvalidOffLen);
Contract.EndContractBlock();
Array.Sort<T>(_items, index, count, comparer);
_version++;
}
Sort接口是排序接口，它使用了Array.Sort接口进行排序，其中Array.Sort的源码我们也把它找出来。以下为Array.Sort使用的算法源码：
internal static void DepthLimitedQuickSort(T[] keys, int left, int right,
IComparer<T>comparer, int depthLimit)
{
do
{
if (depthLimit == 0)
{
Heapsort(keys, left, right, comparer);
return;
}
int i = left;
int j = right;
// 先对低、中（枢轴）和高三种值进行预排序
// 面对已经排序的数据或由多个排序后的行程组成的数据，
// 这可以提高性能
int middle = i + ((j - i)>>1);
SwapIfGreater(keys, comparer, i, middle); // 用中间点与低点交换
SwapIfGreater(keys, comparer, i, j); // 用高点与低点交换
SwapIfGreater(keys, comparer, middle, j); // 用中间点与高点交换
T x = keys[middle];
do
{
while (comparer.Compare(keys[i], x)<0) i++;
while (comparer.Compare(x, keys[j])<0) j--;
Contract.Assert(i>= left && j<= right, "(i>=left && j<=right)
Sort failed - Is your IComparer bogus?");
if (i>j) break;
if (i<j)
{
T key = keys[i];
keys[i] = keys[j];
keys[j] = key;
}
i++;
j--;
} while (i<= j);
// while循环的下一个迭代是“递归”对数组的较大部分进行排序，
// 随后的调用将会对较小的部分进行递归排序
// 因此，我们在此处对depthLimit自减一，以便两种排序都能看到新值
depthLimit--;
if (j - left<= right - i)
{
if (left<j) DepthLimitedQuickSort(keys, left, j, comparer, depthLimit);
left = i;
}
else
{
if (i<right) DepthLimitedQuickSort(keys, i, right, comparer, depthLimit);
right = j;
}
} while (left<right);
}
Array.Sort接口使用快速排序方式进行排序，从而使我们明白了List的Sort排序的效率为O(nlgn)。
前面把大部分接口都列举出来了，差不多把所有源码都分析了一遍，可以看到，List的效率并不高，只是通用性强而已，大部分算法使用的是线性复杂度的算法，当遇到规模比较大的计算量级时，这种线性算法会导致CPU的内存大量损耗。
我们可以自己改进它，比如不再使用有线性算法的接口，自己重写一套，但凡要优化List中线性算法的地方，都使用我们自己制作的容器类。
List的内存分配方式也极为不合理，当List里的元素不断增加时，会多次重新分配数组，导致原来的数组被抛弃，最后当GC被调用时就会造成回收的压力。我们可以在创建List实例时提前告知List对象最多会有多少元素在里面，这样List就不会因为空间不够而抛弃原有的数组去重新申请数组了。
List源码网址为：https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs。
另外也可以从源码中看出，代码是线程不安全的，它并没有对多线程做任何加锁或其他同步操作。由于并发情况下无法判断_size++的执行顺序，因此当我们在多线程间使用List时应加上安全机制。
最后，List并不是高效的组件，真实情况是，它比数组的效率还要差，它只是一个兼容性比较强的组件而已，好用但效率并不高。