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并不是高效的組件，真實情況是，它比數組的效率還要差，它只是一個兼容性比較強的組件而已，好用但效率并不高。