参考资料

[1] .netCore 源码 https://github.com/dotnet/corefx
[2] 《Unity 3D脚本编程 使用C#语言开发跨平台游戏》陈嘉栋著
[3] 《数据结构 第四版》 叶核亚编著
[4] @InCerry【浅析C# Dictionary实现原理】https://www.cnblogs.com/InCerry/p/10325290.html

基础知识

1. 在C#中，List是最常用的可变长泛型列表，类似数组，用于存储一系列数据，使用下标进行索引。
2. Dictionary（字典）是C#中最常用的键值对存储数据结构，通过键（须为不可变类型）来对其中的值进行索引。

疑难解答

1. List如何实现可变长机制？
2. List增删查改的效率如何？
3. Dictionary底层如何实现？
4. Dictionary的增删查改效率如何？

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;
                }
            }
        }
    }

根据以上代码，可以了解以下情况：

1. 当List的容量尚且足够时，会自动向内部的数组后面增加数据
2. 当List的容量不足（即内部维护的_size大于等于实际数组的长度）时，调用AddWithResize方法，而AddWithResize又会调用EnsureCapacity方法进行扩容。
3. 调用EnsureCapacity时，如果当前List容量为空（即我们使用无参构造方法new出List时），会让当前容量增加一个默认值（即DefaultCapacity），如果当前容量不为空，那么就让当前容量翻倍。

在EnsureCapacity方法中仅仅只是对容量（Capacity）进行了赋值，而没有去动真正的数组。实际上玄机在Capacity的set方法中，当容量改变时，会生成一个新的数组，然后将当前数组的所有值拷贝到新数组中。

这样，List为什么能自动扩容就基本清楚了。

总结一下，实