序言
在.NET开发中，List<T>是我们经常用到的类型。前段时间看到其他部门小伙伴讨论“两个List（10W个元素）集合求并集，list1.Where(p=>list2.Contains(p)).ToList()”，性能很差，有人说是ToList的问题，我当时第一直觉是关键在Contains方法，这个问题后面在来细说讨论。还有某大神说过，没反编译过框架源码的码农不是合格码农:)。下面我们就借助Reflector来读一读.NET4.0中List<T>的源码，在读到一些方法实现时候，会更清楚，oh，原来是这样，解开以前的疑惑，写更有效率的代码。
List<T>的数据成员
private const int _defaultCapacity = ;
private static readonly T[] _emptyArray;
private T[] _items;
private int _size;
[NonSerialized]
private object _syncRoot;
private int _version;
根据读整个类的代码，简单解释下：
_defaultCapacity：表示默认的初始容量，即内部容器数组的Length。但在ctrl+f搜索不到有该字段的使用，有点奇怪（代码中都是写死的4），于是查看IL后，发现是static literal string str="123".我们都知道const是在编译期必须初始化值。const字段的本质是static，那么它同样具备Type Dictionary，但我们无法通过像下面的验证，因为它在编译时必须初始化，值确定了。
class Test<T>
{
//public const string _defaultCapacity="123";
public static string Address;
static Test()
{
Address = typeof(T).ToString();
} }
class MyList
{
static void Main()
{
// Console.WriteLine("const :{0}",object.ReferenceEquals(Test<int>._defaultCapacity, Test<string>._defaultCapacity));
Console.WriteLine("static :{0}", object.ReferenceEquals(Test<int>.Address, Test<string>.Address));//false
//Console.WriteLine(Test<string>._defaultCapacity);
}
}
但是反编译的代码中没有对_defaultCapacity使用，代码中是写死4的，难道在编译时候对所以使用的地方都替换成了4？为什么要定义为const而不用static，大神您怎么看？
_emptyArray：默认为一个空数组，在静态构造函数中初始化。为什么不这样写public static readonly T[] _emptyArray=new T[0];效果是一样的。大神您怎么看？
_items：这个真正存储数据的内部数组。
_size：表示List中存储元素的个数。
_syncRoot：用于Thread Safe的。
_version：表示一个版本，当Add元素或者Remove元素等时候，会自增。我们在foreach list过程中如果list改变了，那么会抛出异常（好像是集合已修改，不能枚举），就是根据它来判断的。
List<T>的构造函数
static List()
{
List<T>._emptyArray = new T[];//每个T 都有一个对应的new T[0]
} [TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
public List()
{
this._items = List<T>._emptyArray;//比如：对于所有的new List<int>()对象都共享同一份空数组。设计的目的可能为了性能优化。
} [TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
public List(int capacity)
{
if (capacity < )
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
}
this._items = new T[capacity];//可以看出capacity就是内部数组的Length啦。
} public List(IEnumerable<T> collection)
{
if (collection == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
}
ICollection<T> is2 = collection as ICollection<T>;
if (is2 != null)
{
int count = is2.Count;
this._items = new T[count];
is2.CopyTo(this._items, );//这样的初始化直接数组对拷，性能很高。
this._size = count;
}
else
{
this._size = ;//您是否有疑问，为什么这个下面代码中没有该修改过该值呢？它可表示list元素的个数啊，其实秘密在Add方法中。
this._items = new T[];//看到伐，直接写死的4，不知道是反编译还是源代码就这样写的，大神您怎么看？
using (IEnumerator<T> enumerator = collection.GetEnumerator())
{
while (enumerator.MoveNext())
{
this.Add(enumerator.Current);
}
}
}
}
List<T>的常用方法成员
public void Add(T item)
{
if (this._size == this._items.Length)
{
this.EnsureCapacity(this._size + );
}
this._items[this._size++] = item;
this._version++;
}
当元素个数和内部数组（_items）Length相等时，那么就要确保_items的Length必须有this._size+1。顺便提一下，可以看到Add方法不是thread safe的，其实内部有一个
internal static IList<T> Synchronized(List<T> list)
{
return new SynchronizedList<T>(list);
}
private void EnsureCapacity(int min)
{
if (this._items.Length < min)
{
int num = (this._items.Length == ) ? : (this._items.Length * );//容量是以2倍于原容量来增长的，我们知道数组是定长的，一旦分配后，长度不可改变，那么List如何扩容的呢？看下面
if (num < min)
{
num = min;
}
this.Capacity = num;
}
}
public int Capacity//对于扩容这样一个高消耗操作，用一个属性的set来设置，是否合适，为啥不写成一个方法SetCapacity(int c)呢？大神您怎么看？
{
[TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
get
{
return this._items.Length;
}
set
{
if (value < this._size)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
}
if (value != this._items.Length)
{
if (value > )
{
T[] destinationArray = new T[value];//看到木，重写分配一个新数组，将原数组中元素copy到新数组中。所以如果一开始就知道或者可以预估List的容量，可以new List（x）
if (this._size > ) //来避免以后List的扩容，可能造成的性能影响（如GC回收原数组，copy大量元素等）。
{
Array.Copy(this._items, , destinationArray, , this._size);
}
this._items = destinationArray;
}
else
{
this._items = List<T>._emptyArray;
}
}
}
}
下面来看看AddRange
public void AddRange(IEnumerable<T> collection)
{
this.InsertRange(this._size, collection);
}
public void InsertRange(int index, IEnumerable<T> collection)
{
if (collection == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
}
if (index > this._size)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
}
ICollection<T> is2 = collection as ICollection<T>;
if (is2 != null)//如果实现了ICollection<T>，特殊对待，直接使用高性能的Array.Copy（是一个extern外部实现）
{
int count = is2.Count;
if (count > )
{
this.EnsureCapacity(this._size + count);
if (index < this._size)
{
Array.Copy(this._items, index, this._items, index + count, this._size - index);
}
if (this == is2)//特殊对待
{
Array.Copy(this._items, , this._items, index, index);
Array.Copy(this._items, (int) (index + count), this._items, (int) (index * ), (int) (this._size - index));
}
else
{
T[] array = new T[count];//创建新数组
is2.CopyTo(array, );//将待添加元素先copy到新数组
array.CopyTo(this._items, index);//把新数组copy到List后面。wait等等，各位看官有木有发现，为什么要创建临时数组啊，直接is2.CopyTo(this.items,。。)，且看下面测试结果。
}
this._size += count;
}
}
else
{
using (IEnumerator<T> enumerator = collection.GetEnumerator())
{
while (enumerator.MoveNext())
{
this.Insert(index++, enumerator.Current);
}
}
}
this._version++;
}
public T[] ToArray()
{
T[] destinationArray = new T[this._size];//创建新数组
Array.Copy(this._items, , destinationArray, , this._size);
return destinationArray;
}
//在内部的 public struct Enumerator : IEnumerator<T>, IDisposable, IEnumerator中，下面两个方法为什么不合并成一个啊？还有这个struct为什么没有这样Enumerator<T>呢？您看懂没，反正我看了半天懂了:)
public bool MoveNext()
{
List<T> list = this.list;
if ((this.version == list._version) && (this.index < list._size))
{
this.current = list._items[this.index];
this.index++;
return true;
}
return this.MoveNextRare();
} private bool MoveNextRare()
{
if (this.version != this.list._version)
{
ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
}
this.index = this.list._size + ;
this.current = default(T);
return false;
}
public bool Contains(T item)
{
if (item == null)
{
for (int j = ; j < this._size; j++)
{
if (this._items[j] == null)
{
return true;
}
}
return false;
}
EqualityComparer<T> comparer = EqualityComparer<T>.Default;
for (int i = ; i < this._size; i++)//顺序查找啊，在序言中那个问题，如果使用Dictionary查找，查找复杂度近似O(1)啊，以后在说这个问题。
{
if (comparer.Equals(this._items[i], item))//依赖于T是否实现接口
{
return true;
}
}
return false;
}
其他方法不解释了，有兴趣自己去看看啦。
其中，AddRange方法是否真的比Add方法性能高
测试代码：
static List<int> GetData(int length)
{
List<int> result = new List<int>(length);//潜移默化的影响，哈哈哈
for (int i = ; i < length; i++)
{
result.Add(i);
}
return result;
}
static void Main()
{
int itemLength = ;
List<int> itemList = GetData(itemLength); int iteration = ;
List<int> firstList = new List<int>(itemLength*iteration);
List<int> secondList = new List<int>(itemLength * iteration); CodeTimer.Initialize();
CodeTimer.Time("AddRange方法测试", iteration, () => {
firstList.AddRange(itemList);
});
CodeTimer.Time("Add方法测试", iteration, () =>
{
for (int i = ; i < itemList.Count; i++)
{
secondList.Add(itemList[i]);
}
});
Console.ReadKey();
}
通过故意执行多次AddRange，让其内部不断的创建临时数组，可以看到下面的结果，消耗的时间既然比Add多，而且Gen 0 有33的垃圾回收。AddRange中创建临时数组，到底算不算疏忽，写FCL的工程师应该技术水平不容质疑吧，难道故意的，大神您怎么看？:)
测试结果如下：
类型字典（Type Dictionary）
还是来看下Contains中，比较两个元素是否相等，其中：
public abstract class EqualityComparer<T> : IEqualityComparer, IEqualityComparer<T>
{
private static EqualityComparer<T> defaultComparer; protected EqualityComparer()
{
} [SecuritySafeCritical]
private static EqualityComparer<T> CreateComparer()
{
RuntimeType c = (RuntimeType) typeof(T);
if (c == typeof(byte))
{
return (EqualityComparer<T>) new ByteEqualityComparer();
}
if (typeof(IEquatable<T>).IsAssignableFrom(c))
{
return (EqualityComparer<T>) RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType) typeof(GenericEqualityComparer<int>), c);
}
if (c.IsGenericType && (c.GetGenericTypeDefinition() == typeof(Nullable<>)))
{
RuntimeType type2 = (RuntimeType) c.GetGenericArguments()[];
if (typeof(IEquatable<>).MakeGenericType(new Type[] { type2 }).IsAssignableFrom(type2))
{
return (EqualityComparer<T>) RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType) typeof(NullableEqualityComparer<int>), type2);
}
}
if (c.IsEnum && (Enum.GetUnderlyingType(c) == typeof(int)))
{
return (EqualityComparer<T>) RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType) typeof(EnumEqualityComparer<int>), c);
}
return new ObjectEqualityComparer<T>();
} public abstract bool Equals(T x, T y);
public abstract int GetHashCode(T obj);
internal virtual int IndexOf(T[] array, T value, int startIndex, int count)
{
int num = startIndex + count;
for (int i = startIndex; i < num; i++)
{
if (this.Equals(array[i], value))
{
return i;
}
}
return -;
} internal virtual int LastIndexOf(T[] array, T value, int startIndex, int count)
{
int num = (startIndex - count) + ;
for (int i = startIndex; i >= num; i--)
{
if (this.Equals(array[i], value))
{
return i;
}
}
return -;
} bool IEqualityComparer.Equals(object x, object y)
{
if (x == y)
{
return true;
}
if ((x != null) && (y != null))
{
if ((x is T) && (y is T))
{
return this.Equals((T) x, (T) y);
}
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArgumentForComparison);
}
return false;
} int IEqualityComparer.GetHashCode(object obj)
{
if (obj != null)
{
if (obj is T)
{
return this.GetHashCode((T) obj);
}
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArgumentForComparison);
}
return ;
} public static EqualityComparer<T> Default
{
[SecuritySafeCritical, TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
get
{
EqualityComparer<T> defaultComparer = EqualityComparer<T>.defaultComparer;
if (defaultComparer == null)
{
defaultComparer = EqualityComparer<T>.CreateComparer();
EqualityComparer<T>.defaultComparer = defaultComparer;
}
return defaultComparer;
}
}
}
泛型类中，静态字段private static EqualityComparer<T> defaultComparer;会为每个T类型都缓存一份该数据，是这样去初始化的：
public static EqualityComparer<T> Default
{
[SecuritySafeCritical, TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
get
{
EqualityComparer<T> defaultComparer = EqualityComparer<T>.defaultComparer;
if (defaultComparer == null)
{
defaultComparer = EqualityComparer<T>.CreateComparer();
EqualityComparer<T>.defaultComparer = defaultComparer;
}
return defaultComparer;
}
}
其实发现很多FCL中代码都是这样的模式，可学习使用在平时工作项目中。Type Dictionary真是一劳永逸的哦，貌似某大神说是必备技能啊，有兴趣的可以看我之前写的几篇文章。
总结
通过阅读分析FCL源码，可以更清楚知道实现细节，更高效的使用，可学习MS大神们的代码和设计，命名规范等等，总之，好处多多，其他好处等着你来补充:)。当我们看懂代码意思后，能否思考为什么要这样设计，这样设计的好处是什么，这将是更高一层次的武功了。
如有不正之处，还请斧正，谢谢大家。期待着大家的讨论~~