参考资料
[1] .netCore 源码 https://github.com/dotnet/corefx
[2] 《Unity 3D脚本编程 使用C#语言开发跨平台游戏》陈嘉栋著
[3] 《数据结构 第四版》 叶核亚编著
[4] @InCerry【浅析C# Dictionary实现原理】https://www.cnblogs.com/InCerry/p/10325290.html
基础知识
- 在C#中,List是最常用的可变长泛型列表,类似数组,用于存储一系列数据,使用下标进行索引。
- Dictionary(字典)是C#中最常用的键值对存储数据结构,通过键(须为不可变类型)来对其中的值进行索引。
疑难解答
List如何实现可变长机制?
List是C#中的可变长数组,它是ArrayList的泛型版本,由于ArrayList中所有对象都是Object,往其中加入值类型数据时会频繁触发装箱拆箱(关于装箱拆箱的详情,可以参考我上一篇博文【C#基础复习(2) 之 装箱拆箱】),导致效率问题,同时还有一些关于强制转换的安全问题,所以一般不使用ArrayList。
List底层是通过一个泛型数组进行实现,根据他的无参初始化方法可以知道,当我们使用new List<T>()的方式生成他时,他是将当前内部的数组指向了一个空数组。这段源码内容如下:
public class List<T> : IList<T>, IList, IReadOnlyList<T>
{
private const int DefaultCapacity = 4;
private T[] _items; // Do not rename (binary serialization)
private int _size; // Do not rename (binary serialization)
private int _version; // Do not rename (binary serialization)
private static readonly T[] s_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 DefaultCapacity, and then increased in multiples of two
// as required.
public List()
{
_items = s_emptyArray;
}
....
}
那么问题就来了,既然初始化的时候,内部数组指向的是一个只读的empty数组,那么为什么我们还可以自如地向List中增加或删除元素呢?他是如何实现可变长机制的呢?
直接跳到List的Add方法中查看一下实现。其增加元素主要跟三个方法有联系,分别是Add,AddWithResize以及EnsureCapacity,下面是它们的源码部分。
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Add(T item)
{
_version++;
T[] array = _items;
int size = _size;
if ((uint)size < (uint)array.Length)
{
_size = size + 1;
array[size] = item;
}
else
{
AddWithResize(item);
}
}
// Non-inline from List.Add to improve its code quality as uncommon path
[MethodImpl(MethodImplOptions.NoInlining)]
private void AddWithResize(T item)
{
int size = _size;
EnsureCapacity(size + 1);
_size = size + 1;
_items[size] = item;
}
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;
}
}
public int Capacity
{
get
{
return _items.Length;
}
set
{
if (value < _size)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
}
if (value != _items.Length)
{
if (value > 0)
{
T[] newItems = new T[value];
if (_size > 0)
{
Array.Copy(_items, 0, newItems, 0, _size);
}
_items = newItems;
}
else
{
_items = s_emptyArray;
}
}
}
}
根据以上代码,可以了解以下情况:
- 当List的容量尚且足够时,会自动向内部的数组后面增加数据
- 当List的容量不足(即内部维护的_size大于等于实际数组的长度)时,调用AddWithResize方法,而AddWithResize又会调用EnsureCapacity方法进行扩容。
- 调用EnsureCapacity时,如果当前List容量为空(即我们使用无参构造方法new出List时),会让当前容量增加一个默认值(即DefaultCapacity),如果当前容量不为空,那么就让当前容量翻倍。
在EnsureCapacity方法中仅仅只是对容量(Capacity)进行了赋值,而没有去动真正的数组。实际上玄机在Capacity的set方法中,当容量改变时,会生成一个新的数组,然后将当前数组的所有值拷贝到新数组中。
这样,List为什么能自动扩容就基本清楚了。
总结一下,实