[數據結構1.2-線性表] 動態數組ArrayList（.NET源碼學習）

在C#中，存在常見的九種集合類型：動態數組ArrayList、列表List、排序列表SortedList、哈希表HashTable、棧Stack、隊列Queue、鏈表LinkedList、字典Dictionary、點列陣BitArray。本文將基於動態數組ArrayList，從源碼的角度出發，分析其內部定義以及常用方法的實現。

【# 請先閱讀註意事項】

【註：（1）以下提到的複雜度僅為演算法本身，不計入演算法之外的部分（如，待排序數組的空間占用）且時間複雜度為平均時間複雜度 。

（2）除特殊標識外，測試環境與代碼均為.NET 6/C# 。

（3）預設情況下，所有解釋與用例的目標數據均為升序。

（4）預設情況下，圖片與文字的關係：圖片下方，是該幅圖片的解釋。

（5）本文內容基本為本人理解所得，可能存在較多錯誤，歡迎指出並提出意見，請見諒。】

一、ArrayList的實現

(一) 構造函數

該數據結構有三種構造方法。即，三種初始化的方法：

創建一個（當前容量為0）空的Array對象。

創建一個有大小的空的Array對象。

將某個非空集合轉換為ArrayList類型。

從這三個構造方法可以初步得出以下結論：

1. 欄位_items儲存了動態集合本身。

2. 動態集合對象的創建調用的是Array中的方法，所以其本質依舊屬於數組。

3. 動態集合的容量必須大於等於0；傳入的其他集合不能為空，但長度可為0。

4. 有關AddRange()方法：

根據上方推斷出的_items，可知此處的_size指的是ArrayList的當前長度。可以發現，該方法的作用是在原動態數組的某一特定位置，插入新數據集。

• Line 420~427：當待插入集合為空 或 插入起始索引非法時，拋出異常。

• Line 428、429：當且僅當待插入數據集長度大於0時，執行插入。

• Line 431：EnsureCapacity()方法的作用是，若當前容量為0，則初始化為4；否則以每次乘2的增長幅度，擴展當前容量。

• Line 432~440：利用Array中的Copy()方法，該方法在文章（[數據結構1.1-線性表] 數組 （.NET源碼學習） - PaperHammer - 博客園 (cnblogs.com)）中有較詳細的解釋。

註意，AddRange()方法和InsertRange()方法均可被調用，前者是在動態集合末尾加上新的數據集；後者可在任意合法位置插入新數據集。但AddRange()方法也調用的是InsertRange()方法，正是因為有Line 432行的if語句。

（1）當調用AddRange()方法時，傳入的index就是_size，所以此時不執行if語句內的內容。直接創建一個新數組array，將新數據集存入其中，再把該數組拼接到原動態數組的末尾。

（2）當調用InsertRange()方法時，若待插入數據集長度大於等於_size，則為情況（1），不執行if內的語句；待插入數據長度小於ArrayList的長度時（index < _size），從索引index開始，將原本在ArrayList中的數據向後移動，保證從index開始足夠插入新的數據。

(二) 欄位與屬性

1.  三個私有欄位：

其中，_items表示動態數組本身；_size表示動態數組當前存儲的元素數；_version表示當前動態集合的版本號，在執行某些操作後，會使版本號+1，所以，理論上對於同一個動態數組這些操作總共只能執行有限次，即int的上限次。這些操作包含：屬性（索引器）this[int indxe]、方法Add()、AddRange()、Clear()、Insert()、InsertRange()、Remove()、RemoveAt()、RemoveRange()、Reapt()、Reverse()、SetRange()、Sort()。

2. 七個公共屬性：

（1）Capacity，讀/寫，表示當前的容量上限，不是當前儲存的元素個數。

• Line 59：get訪問器返回的是_items，即動態數組本身的當前容量。

• Line 63：set訪問器，用於更改當前容量上限。

• Line 65：value表示外部傳入的值。當外部傳值（設定的Capacity）小於當前元素個數（非容量）時，拋出異常。

• Line 71、74：若傳入的值為正且內部已存在元素時（已初始化的動態數組，在不存放任何值時，Capacity為0），則初始化一個長度為value的數組，將原動態數組中的元素Copy進新數組，再賦值回_items；若傳入的值為正但內部不存在元素，即_size為0，則不進行Copy。

• Line 81：某條件下，初始化對象數組為容量為4的數組。

有關Capacity的運行流程參照下圖，圖片分析過程已逐行標號，若存在問題，歡迎在評論區提出。

（2）Count，只讀，返回當前元素個數。區別於容量Capacity。

（3）IsFixedSize，只讀，指示數組是否具有固定大小。此處預設為false且不可更改，因為要保證其動態性。

若要創建大小固定的動態數組，可以調用靜態方法FixedSize()方法，由該方法創建的動態數組不能再添加或移除元素，但是允許修改現有元素。

該屬性包含在一個新的類FixedSize中，是一個內部類。

（4）IsReadOnly，只讀，指示當前對象是否為只讀對象。

（5）IsSynchronSized，只讀，指示對動態數組的訪問是否同步（線程安全）。

（6）   SyncRoot，只讀，獲取可用於同步訪問動態數組的對象，即IsSynchronized值為true的動態數組對象。

【（5）、（6）的詳細內容將在今後的有關線程的文章中論述】

（7）索引器：可以使用索引運算符來訪問某個數據結構中的對象。

其中get屬性為要返回的對象；set屬性用於將對應的元素和索引一一對應，此處的value指代動態數組中的元素。

小結 一

1. 動態數組之所以稱為“動態”，是因為其大小可以在程式運行時改變，而不是像Array一樣，在初始化時就指明長度大小且不可更改。

2. 動態數組中的Capacity是可以保存的元素數，即容量；Count是實際的元素數。

3. 其內部元素可以為null，可以重覆，可以為不同類型；但不能將多維數組作為其元素。

據微軟的說法，多維數組不能作為ArrayList的元素，但實測後似乎沒有問題，有知道如何理解微軟的那句話的學者可以評論交流。

二、ArrayList的常用方法

(一) Add()、AddRange()、Insert()和InsertRange()方法

Add()，公共虛方法，在原動態數組末尾插入單個值。

• Line 8：添加元素時，若當前長度與容量相同，即容量已達上限，則先擴容。

• Line 10：更新索引器的索引。

• Line 11：更新版本號。

• Line 12、13：保存原元素數；將當前元素數+1。

• Line 14：返回值原元素數，等價為末位索引、新加入元素的索引。

AddRange()，公共虛方法，在原動態數組末尾插入新的數據集，其調用的是內部的InsertRange()方法。

InsertRange()，公共虛方法，在某一特定位置插入某一數據集。

• Line 3：index為插入的起始索引/位置。

• Line 5：需要保證待插入的數據集非空。

• Line 9：需要保證指定索引合法。

• Line 14：保證待插入的數據集有元素。

• Line 19：若不插入在末尾，則將一定位置的元素後移，讓出足夠的位置。

• Line 21~25：將待插入數據複製到新數組中，將新數組的值複製到動態數組的對應位置；更新元素數和版本號。

註意到，該方法內部並未顯式更新索引器。原因可能是：此處創建了一個數組，數組本身就是通過索引訪問的，將集合c複製給數組，使得集合c內部的元素可由索引訪問；將array再複製給動態數組，將數組可由索引訪問的特性保留了下來，因此此處無需顯式更新索引器。

Insert()，公共虛方法，在某一特定位置插入單個數據。

形式和之前的Add()方法相差不大，只是增加了一個特定位置的參數。

(二) BinarySearch()方法

該方法為二分查找法，使用的前提是元素有序。其調用的是Array類中的BinarySearch()方法，用於查找某個元素所在的位置/索引，不存在則返回一個較為特殊的值，後文會提到。

• Line 4：index表示查找的起始索引；count表示查找數量；value表示查找的對象；compare表示比較器對象。

• Line 14：需要保證長度 - 起始索引 = 剩餘元素 >= 查找數量。

• Line 1059：GetLowerBound()方法和C++中的LowerBound()方法不是同一個用法。此處的GetLowerBound()方法返回的是，數組中指定維度第一個元素的索引；C++中的LowerBound()方法返回的是，集合中從索引0開始，第一個小於等於目標元素的元素索引，不存在返回-1。

• Line 1072：Array.Rank屬性，表示數組的維度。

• Line 1080~1082：i表示起始位置；num表示長度；array2表示嘗試將array轉換為數組類型的數組對象。

• Line 1087：GetMedian()方法返回的是兩個數的平均值，即中間值。

• Line 1091：num2存儲中間位置元素和value值的大小關係。

• Line 1098~1109：num2 == 0二者相等，直接返回目標元素所在索引；num2 == -1 < 0中間元素小於目標值，則將左界定為 中間位置+1；反之定位 中間位置-1。

• Line1111：若未找到元素，則返回~i。此時的I == num + 1 == index + length，即，搜索區間的長度。其中，運算符 ~ 的作用是將值對應的二進位每位取反。

• Line 1116：判斷數組中的元素是否為基元類型（.NET類庫中預設存在的數據類型）。

• Line 1124：記錄需要查找的區間的起始索引。

• Line 1125：nums3記錄目標元素在數組中的索引。

之後，根據不同的數據類型，進入到不同到重載方法中進行查找（以下以int為例）

所調用的BinarySearch()方法位於類SpanHelpers中，在比較時運用到了指針，所以方法被標記為unsafe。

• Line 28：spanStart為待查找區間；length為查找長度；comparable為比較器對象。

之後的部分就是熟悉的雙指針/折半查找。

進行上述兩個過程的前提分別是轉換後的array != null和比較器對象為預設值，若都不符合，則進行以下麵的方式進行查找。

該方法和第一種成功轉換的方法基本一致，只是直接在原數組中進行查找，使用非預設比較器對象。

(三) Clear()方法

【註：對於該方法的源碼分析，以下多數內容位推斷得出，可能存在較多錯誤，還請各位大佬指正】

由於動態數組本質還是數組，所以調用的大部分方法均是類Array中的方法。

• Line 8：快刀斬亂麻，執行完Clear()方法後，將_size歸零。

可以發現，一個感覺簡單的清除元素的方法，執行起來卻較為複雜。

【註：有關Int與IntPtr的區別會在後文提到，可先行轉跳查看】

• Line 313：array為待清空數組；index為要清空部分的起始索引；length為要清空的長度。

• Line 319：將對象array強制轉換為RawArrayData類型並獲取其數據類型所占的位元組數，供後面的指針偏移使用。

• Line 321：類MethodTable，方法表，內部有一個結構體，包含了7個欄位和6個屬性。（該類將在後文介紹）

• Line 322：IsMultiDimensionalArray屬性，判斷傳入的對象是否為多維數組。其中，運算符 -> 稱為間接引用運算符，用於從某個對象中讀取出某個值。

• Line 324：獲取多維數組維度。

• Line 325：將int類型的source強制轉換為byte類型，並將起始指針向後（偏移）移動。目的是為了重新定位數組的起始索引位置，num中存儲的就相當於是數組的起始索引。其中，Unsafe.Add(T, Int32)方法，用於向給定的托管指針添加偏移量。

• Line 326：更新占用的位元組總數Unsafe.As<TFrom, TTo>(TFrom)方法，將給定的托管指針重新解釋為類型值的新托管指針。

• Line 328：num2 = 清除部分的起始索引 – 數組的起始索引。刪除的長度

• Line 329：若 清除部分的起始索引 < 數組的起始索引（等價於num2 < 0） 或 清空的長度 < 0 或 非清空部分的長度 + 清空部分的長度 > 總長度，則拋出異常。

• Line 333：uintPtr表示array內部單個元素所占的位元組數。

• Line 334：ptr表示從索引0開始到剛好需要清除的元素起（num2 * unitPtr）所占的位元組數，即確定清除起點。

• Line 335：unitPtr2以指針的形式表示需要清除的元素的長度。

【註：關於類Unsafe中的內容會在今後的文章中解釋】

• Line 336：判斷對象是否包含對於該指針對象的垃圾回收器。在C#中指針分為托管指針（ref，out等）與非托管指針（*,&等），在CLR中，對於非托管對象需要手動進行釋放，即手動垃圾回收。

如果運行正常，最終都會進入到SpanHelpers類中的ClearWithReferences()方法。從方法名稱上看，可以推斷出其不僅刪除了集合中的元素，還刪除了該集合用於存儲元素的引用指向。即，刪除了元素和分配給集合存儲元素的記憶體空間位置。

下麵是ClearWithReferences()方法

【註：關於ContainsGCPointer，其相關解釋僅為推斷內容，有待證實】

（1）對於不包含GCPointer的對象，需要自行定義新的清除方法，進入Line 341處的方法：

• Line 3078：b表示開始清除的起始位置；byteLength表示清除長度。

• Line 3080：byteLength為0，相當於不清除。

• Line 3084： (UIntPtr)((IntPtr)768)可能表示基於CLR中的某一規則，允許數組一類的數據結構在記憶體塊中占用的某個上限值，若超過該上限則需要調用類Buffer中的_ZeroMemory()方法

該方法獲取待清除數組的首地址，之後執行一個擴展方法，需要在外部寫一個清除方法，特殊處理；若沒有超過上限則執行下麵的方法。

• Line 3086：InitBlockUnaligned()方法，在給定位置使用給定的初始值初始化記憶體塊。

startAddress表示引用要初始化的記憶體塊開頭的托管指針；value表示要初始化記憶體塊的所有位元組的值；byteCount表示要初始化的位元組數。

據微軟官方的說法，該方法不用於初始化可供使用的運行記憶體。那麼推測其原理應該是通過重置記憶體塊上的分配信息，以達到清除某數據結構中元素的目的。被重置的記憶體塊將不再被任何結構占用，可再次自由分配。

（2）對於內部包含GCPointer的對象，收到GC的管控，可自行回收，進入Line 338處的方法：

• Line 3093：ip也表示清除的起始位置；pointerSizeLength也表示清除的長度。與剛纔方法不同的是，其傳入起點的類型為整形指針，而不是byte。

• Line 3095：若刪除的長度大於等於8，則每次清除以8為單位，即每次清除8個元素在記憶體塊上的內容及分配信息。

• Line 3107~3117：若刪除長度小於等於0，說明刪除長度為0（因為其類型為UIntPtr，本質為無符號整型，最小值為0）則不執行任何操作；若刪除長度大於0且小於2，說明刪除長度為1，則跳轉至標記IL_12F處，直接將ip所代表的指針置為0，使得該數組對ip指針對應的記憶體單元失去所有權；若刪除長度大於2且小於4，說明刪除長度為3，Line 3125處先將ip後移一位並將其置為0（中間），Line 3126處將ip後移3位再前移一位（末尾），Line 3128處將ip置為0（開頭）。

• Line 3118~3124：若刪除的長度小於8，則依舊通過指針位移的方式，將其逐一置為0。

通過簡要分析可以得出，該方法的時間複雜度位O(n)，因為其需要通過指針進行遍歷並修改每一個值；空間複雜度為O(n)，因為其創建了MethodTable，用於存儲傳入數組的相關信息。

雖然其較為複雜，但效率且不低，下麵將通過對比Clear()方法、新建對象和單純遍歷刪除這三種方式的耗時。數據量為10萬，進行100萬次，由於JIT的特性，第一次啟動程式會耗時較高，於是不保留第一次的測試數據。

小結 二

（1）在數據量龐大時，Clear()方法能保持較高的效率，其次是手動清除，最後是創建新對象。

（2）在測試string類型前，也跑了一遍int類型，同樣的到的類似的結果。不過橫向對比可以得出，值類型的清除效率要比引用類型更高。

（3）理論上，從簡單的分析可以知道手動清除只是遍歷，而創建新對象是在堆與棧中反覆讀取與寫入，所以創建新對象效率比較低。這樣的結果或許也得益於CLR等相關架構的優化，具體有關CLR的相關內容，將會在今後專門寫文章進行分析。

（4）以下是有關Clear()方法的執行流程簡圖：【字跡不清，還請見諒】

(四) Contains()方法

Contains()方法不論是在動態數組還是在其他線性數據結構中都經常被使用，其實現原理也很簡單，就是單純的遍曆數組。時間複雜度O(n)，空間複雜度O(1)。

(五) IndexOf()、LastIndexOf()方法

Contains()方法只是查找元素是否包含在集合中，而這兩種方法在查找後還將返回元素所在的索引位置。時間複雜度O(n)，空間複雜度O(n)。

首先是IndexOf()方法，其從索引0開始，返回第一個與目標值相等的索引。

兩個if用於判斷起始索引是否越界；查找長度是否小於0或以startIndex為起點，查找過程中是否會越界。之後調用類Array中的IndexOf()方法。

• Line 1554：array為待查找的數組；value為目標值；starIndex為查找的起始索引；count為查找的長度。

• Line 1560：該方法僅適用於一維數組。

• Line 1564：獲取數組中指定維度第一個元素的索引。其中，0表示第一維度。即，獲取起始索引。

• Line 1565、1569：保證startIndex與count的合法性。

• Line 1573：num表示查找的結束位置。

• Line 1574：嘗試將array轉換為object類型的數組。

• Line 1575~1599：若轉換成功，當value為null時，使用運算符“==”逐項判斷，相等則返回索引；當value不為null時，使用Equals()方法逐項判斷，相等則返回索引。若在序列中未找到與目標元素相等的值，則返回-1。

其中，等於運算符“==”和Equals()方法的區別，在比較值類型時，均比較在棧中的內容；比較引用類型時，運算符“==”比較的是存放在棧中引用地址，Equals()方法比較的是堆中的內容。

• Line 1600、1601：若轉換失敗，則獲取array的元素的類型。由於可以存儲任何類型，所以ArrayList轉換為數組後，其類型為object。

• Line 1607：判斷value的類型是否與array的類型相同。

• Line 1609：此處的adjustIndex相當於startIndex。

• Line 1611：根據不同的類型，調用不同的查找策略。傳入的adjustIndex相當於是將startIndex作為0，開始查找。

• Line 1640：num2用於存儲最後的結果。若>=0說明找到了對於的元素，則返回從startIndex開始，向後num2位。即，索引位置；否則沒有找到，返回-1。

如果不是基元類型，則取出每一個元素，逐一比較，相等返回索引；沒有找到則返回-1。

接下來是LastIndexOf()方法，從方法名上可以推斷出，其查找順序是從後向前。

只看關鍵部分代碼

startIndex為起始索引，向前查找count位，直到num。除此之外，其餘均與IndexOf()方法一致。

(六) Reverse()方法

時間複雜度O(n)，空間複雜度O(1)。

可以發現，其原理是通過交換指針實現的。

• Line 2029：array表示待反轉數組；index表示反轉的起始索引；length表示反轉長度。

• Line 2051：ptr表示要反轉的部分的起始索引。即，index索引對應的記憶體地址。其中，GetArrayDataReference()方法，獲取數組的記憶體地址，據C++中的指針含義，其表示第一個元素的記憶體地址，&array[0]。通過Unsafe.Add()方法，將指針向後偏移index位。

• Line 2052：ptr2表示要反轉部分的末尾索引。即，index+length索引對應的記憶體地址。將ptr向後偏移length位，再向前偏移1位，指向反轉末尾。

• Line 2055~2057：進行記憶體地址的交換。

• Line 2058~2059：分別將兩處的指針向後/前，移動，進行下一次交換。

• Line 2061：直到ptr == ptr2，即，表示同一位置的時候，結束迴圈，完成交換。

小結 三（有關Array、ArrayList和List）

（1）Array是C#中最早的數據結構，其在記憶體中是連續存儲的，且同索引進行訪問及相關操作，有較高的效率。但連續的存儲形式，使得其在插入和刪除上效率低下，且在聲明時需要指定長度，過短會溢出；過長會浪費。

（2）為了彌補數組的缺點，引入了動態數組ArrayList。其本質還是數組，不過是在數組的基礎上增加了一定的靈活性，其多數內部方法依舊基於類Array。但繼承了IList介面的它，具有靈活的長度，同時不受數據類型的限制，可在一個對象中存儲任意類型。但正是因為不受類型的限制，頻繁的裝箱拆箱操作，導致了一定的性能損耗和不安全性。

（3）隨著.NET（以前稱為.NET Framework）的發展，又引入了集合List，每個集合具有固定的類型，只能存放相應類型的數據；在記憶體中不連續；且長度為動態的。可以說相容了數組和動態集合的優點，因此也成為目前使用最為廣泛的數據結構之一。該數據結構在之後的文章中會提到

[# 有關結構體MethodTable（方法表）]

【註：由於關於該結構體的相關資料較少，故以下內容多以推測為主，可能存在較多錯誤。】

該結構體在命名空間System.Runtime.CompilerServices下，據書籍《Pro .NET Performance》的說法：MethodTable是由一個類的所有方法的相關信息所組成。即，主要用於存儲對象的基本信息，在必要時候進行提供。其是一個內部的（internal）結構體，結構體內部包含7個公共的欄位和6個公共屬性。

先來看7個欄位

• Line 74：ComponentSize，直譯為元件大小，表示內部元素所占的位元組數。

• Line 78：Flags，可能用於存儲某些標誌的共性。

• Line 82：BaseSize，用於存儲數組維度的相關信息。

• Line 86：InterfaceCount，據字面意思是表示介面的數量，這裡應該是表示繼承或派生的介面數。

• Line 90：ParentMethodTable指針，表示指向該類型的父對象。

• Line 94：ElementType，表示對象本身的數據類型。

• Line 98：InterfaceMap，map有圖、表的含義。其可能表示和該對象有關的介面關係。

接下來是6個屬性

這幾個屬性均為只讀，都反映了對象的一些信息。其中sizeof(IntPtr)的值據程式的位而定，32位值就為4；64位值就為8。

[# 有關數據類型Int與IntPtr]

整兩種數據類型均可以稱為整型。

對於Int，我們都很熟悉，屬於基元類型，帶符號的32位整數，預設值位0，十進位運算，-2,147,483,648到2,147,483,647，即-2^31到2^31 – 1。若加上首碼‘u’，則表示無符號類型。

對於IntPtr，表示一個有符號整數，用於表示記憶體地址。其中位寬度與指針相同，即其所占位元組大小與基於其派生出的原類型（Int）大小相同。需要註意的是，此類型的實例應在32位進程中為32位，在64位進程中為64位。該類型可由支持指針的語言使用，並作為引用執行和不支持指針的語言之間的數據的常見方法。基本信息如下：

更多詳細信息可參考IntPtr 結構 (System) | Microsoft Docs

總結

（1）ArrayList相較於數組而言具有更高的靈活性和空間利用性，但整體的性能不如泛型集合List<T>。

（2）類ArrayList旨在保存對象的異類集合，因此其通常不能保證排序的有序性和BinarySearch()方法的準確性，這也是整體性能不如泛型集合的主要原因。

（3）由於類ArrayList內部存在一個記錄版本version的整型變數，因此其可能存在操作的上限次數。若的確存在，則不適用於當下的大量數據處理和交互的環境下。

（4）ArrayList里傳入的實例不能訪問到實例的屬性，需要進行判斷和轉型，並賦值給中間變數才能被查看，如下圖：

原因是，無論原本是聲明類型，進入ArrayList後均被轉換為object類型（裝箱），要轉回原本的類型（拆箱）才可以訪問到原本屬於自己的東西。

【感謝您可以抽出時間閱讀到這裡，因個人水平有限，可能存在錯誤，望各位大佬指正，留下寶貴意見，謝謝！】