“哪種集合是最好的？”答案是：“視情況而定。” 不同的集合有不同的性能，而且在不同的行為上有不同的優化。.Net框架支持很 多類似的集合：鏈表，數組，隊列，棧，以及其它的一些集合。C#支持多維的數 組，它的性能與一維的數組和鋸齒數組都有所不同。.Net框架同樣包含了很多特 殊的集合，在你創建你自己的集合類之前，請仔細參閱這些集合。你可以發現很 多集合很快，因為所有的集合都實現了ICollection接口。在說明文檔中列出了 所有實現了ICollection接口的集合，你將近有20多個集合類可用。
為了 選擇適合你使用的集合，你須要考慮在該集合上使用的操作。為了創建一個有伸 縮性的程序，你須要使用一些實現了接口的集合類，這樣當你發現某個假設的集 合不正確時，你可以用其它不同的集合來代替它(參見原則19)。
.Net框 架有三種不同類型的集合：數組，類似數組的集合，以及基於散列值的集合。數 組是最簡單的也是一般情況下最快的集合，因此我們就從它開始。這也是你經常 要使用到的集合類。
你的第一選擇應該經常是System.Array類，確切的 說，應該是一個數組類型的類。 選擇數組類的首要原因，也是最重要的原因是 數組是類型安全的。所有其它集合都是存儲的System.Object引用，直到C#2.0才 引入了范型(參見原則49)。當你申明一個數組時，編譯器為你的類型創建一個特 殊的System.Array派生類。例如：這樣創建了申明並創建了一個整型的數組：
private int [] _numbers = new int[100];
這個 數組存儲的是整型，而不是System.object的引用。這很重要，因為你在一個數 組上添加，訪問，刪除值類型時，可以避免裝箱與拆箱操作的性能損失(參見原 則17)。上面的初始化操作創建了一個一維的數組，裡面存放了100個整數。所有 被數組占用的內存都被清0了。值類型數組都是0，而引用數組都是null。所有在 數組裡的元素可以用索引訪問：
int j = _numbers[ 50 ];
另外，訪問數組時還可以用foreach迭代，或者使用枚舉器：
foreach ( int i in _numbers )
Console.WriteLine( i.ToString( ) );
// or:
IEnumerator it = _numbers.GetEnumerator( );
while( it.MoveNext( ))
{
int i = (int) it.Current;
Console.WriteLine( i.ToString( ) );
}
如果准備存儲單一次序的對象，你應該使用數組。但 實際上你的數據結構往往比這復雜的多。這很快誘使我們回到了C風格上的鋸齒 數組，那就是一個數組裡存儲另一個數組。有些時候這確實是你想要的，每個外 層元素都是內層的一個數組：
public class MyClass
{
// Declare a jagged array:
private int[] [] _jagged;
public MyClass()
{
// Create the outer array:
_jagged = new int[5][];
// Create each inner array:
_jagged[0] = new int[5];
_jagged[1] = new int[10];
_jagged[2] = new int[12];
_jagged[3] = new int[7];
_jagged[4] = new int[23];
}
}
每個內層的 一維數組可以有同不的大小。在需要不同大小的數組時可以使用鋸齒數據。使用 鋸齒數組的缺點是在列方面上的訪問是底效的。檢查一個每行上有三個列的鋸齒 數組時，每次訪問都要做兩個檢測 。在行0列3上的元素和在行1列3的元素沒有 任何關系。只有多維數組才可在以列方面上的訪問有一定的效率。過去，C和C++ 程序使用二維或多維數組時是把它們映射到一個一維數組上。對於老式的C和C++ 程序員，這樣的標記應該很清楚：
double num = MyArray[ i * rowLength + j ];
這個世界上的其它人可能更喜歡這樣：
double num = MyArray[ i, j ];
但，C和C++其實 並不支持多維數組。C#可以，而且對於多維數組的語法：當你創建一個真實的多 維數組時，對於編譯器和你來說意義都是很清楚的。創建多維數組時只用在熟悉 的一維數組標記上擴展一下就行了：
private int[ , ] _multi = new int[ 10, 10 ];
前面的申明創建了一個二維數組，而且是 10X10的100個元素。在多維數組上的每一維的長度總是一致的。編譯器利用這一 特性，可以創建更高效的代碼。初始化鋸齒數組時須要多次使用初始語句。而在 我前面的例子裡(譯注：指這裡：private int[] [] _jagged;)，你須要5個語句 。更大的數組或者更多維的數組須要更多的初始代碼，而且你要手動編寫。然而 ，多維數組在初始化時只要指定多少維就行了。此外，多維數組在初始化元素時 更有效。以於值類型數組在初始化時是直接在有效的數組索引上包含該值，所有 的內容就是0。而引用類型的數組則是null。數組的數組在內層上都包含null引 用。
訪問多維數組時比訪問鋸齒數組要快得多，特殊是在列或者對角線 上訪問時。編譯器在數組的每個維上是使用的指針算法。鋸齒數組則要為每個一 維數組查找正確的(指針引用)值。
多維數組可以當成數組在很多情況下 使用。假設你創建一個棋盤游戲，你可能須要在一個格子上創建一個64個方格的 棋盤：
private Square[ , ] _theBoard = new Square[ 8, 8 ];
這個初始化創建了數組來存儲方格，假設這些方格是引用類型 ，這些方格自己還沒有創建，而且每個元素還是null。為了初始化每個元素，你 還要檢測數組上的每一維元素：
for ( int i = 0; i < _theBoard.GetLength( 0 ); i++ )
for( int j = 0; j < _theBoard.GetLength( 1 ); j++ )
_theBoard[ i, j ] = new Square( );
你你還有更靈活的方法來訪問多維數組，你可以給定 個別的元素索引來訪問該元素：
Square sq = _theBoard[ 4, 4 ];
如果你要迭代整個集合，你還可以使用迭代器：
foreach( Square sq in _theBoard )
sq.PaintSquare( );
與鋸齒數組相比，你可能要這樣寫：
foreach( Square[] row in _theBoard )
foreach( Square sq in row )
sq.PaintSquare( );
鋸齒數組裡的每一個新的維引用了另一個 foreach語句。然而，對於一個多維數組，每一個foreach語句都要產生代碼來檢 測數組每個維上的界線。foreach語句在每個維上生成特殊的代碼來迭代數組。 foreach循環生成的代碼與你這樣手寫是一樣的：
for ( int i = _theBoard.GetLowerBound( 0 );
i <= _theBoard.GetUpperBound( 0 ); i++ )
for( int j = _theBoard.GetLowerBound( 1 );
j <= _theBoard.GetUpperBound( 1 ); j++ )
_theBoard[ i, j ].PaintSquare( );
考慮在內層循環上所有對GetLowerBound 和 GetUpperBound 的調用，這看上去是認低效的，但這確實是很高效的結構。JIT 編譯器對數組類是很了解的，它們會緩存數組界線，而且可以識別內層的迭代界 線從而省略它們(參見原則11)。
數組類的兩個主要的不利因素可能會讓 你考慮使用.Net框架裡的其它集合類。第一個影響就是改變數組的大小：數組不 能動態的改變大小。如果你須要修改任意數組及任意維數的大小，你必須創建一 個新的數組，然後拷貝所有已經存在的元素到新的數組裡。改變大小要花時間： 因為新的數組要分配，而且所有的元素要拷貝到新的數組裡。盡管拷貝和移動在 托管堆上並不是像使用C和C++的年代那樣開銷昂貴，但還是很花時間。更重要的 是，它會讓數據使用陳舊。考慮下面的代碼：
private string [] _cities = new string[ 100 ];
public void SetDataSources( )
{
myListBox.DataSource = _cities;
}
public void AddCity( string CityName )
{
String[] tmp = new string[ _cities.Length + 1 ];
_cities.CopyTo( tmp, 0 );
tmp[ _cities.Length ] = CityName;
_cities = tmp; // swap the storage.
}
即使在調用AddCity 之後，列表框的數據源還 是使用拷貝前的舊數據。你新添加的城市根本沒有在列表框中顯示。
ArrayList類是在數組上的一個高度抽象類。ArrayList集合混合了一維 數組和鏈表的語義。你可以在ArrayList使用迭代，而且你可以調整它的大小。 ArrayList基本上把所有責任都委托給了它所包含了數組上，這就是說ArrayList 類與數組類在性能上很接近。它的最大好處就是在你不清楚你的集合具體要多大 時，ArrayList類要比數組類好用得多。ArrayList可以隨時擴展和收縮。但你還 是要在移動和拷貝元素上有性能損失，但這些算法的代碼已經寫好了而且經過了 測試。因為內部存儲的數組已經封裝在ArrayList對象內，因此陳舊數據的情況 就不存在了：用戶的指針是指向ArrayList對象而不是內部的數組。.Net框架裡 的ArrayList集合有點類似C++中標准庫裡的向量類。
隊列和棧類在 System.Array類上提供了特殊的接口。這些特殊的接口是自定義的先進先出的隊 列接口和後進先出的棧接口。時刻記住，這些集合的內部存儲都是基於數組的。 在修改集合的大小時同樣會得到性能的損失。
(譯注：對於這樣的一些集 合，在初始化時都有一個大小的參數，應該盡可能的給定集合的容量大小，這裡 的大小並不是一次性申明和使用的，而是集合中的元素小於這個大小時，不會有 移動和拷貝元素的性能損失。因此合理的選擇這些集合的容量大小是很關鍵的。 隊列的默認大小是32，而棧的默認大小是10，ArrayList默認是0。而它們的構造 函數都有一個重載版本可以指定容量。)
.Net中的集合沒有包含鏈表 (linked list)結構。垃圾回收器的高效使得列表(list)結構在實際使用是占用 時間最小，因此也讓它成為了最佳選擇。如果你確實須要鏈表的行為，你有兩個 選擇。如果你因為希望經常添加和刪除裡面的元素而選擇了列表，那麼使用null 引用的字典類。簡單的存儲關鍵字，你就可以使用ListDictionary 類了，而且 它用鍵/值對應方式實現了單向鏈表。或者你可以選擇HybridDictionary類，這 是一個為小集合使用了ListDictionary的類，而且對於大集合會轉化到 HashTable上來。這些集合以及很多其它內容都在 System.Collections.Specialized 名字空間裡。然而，如果因為用戶想控制次 序而你想使用列表結構，你可以使用ArrayList 集合。ArrayList 可以在任何位 置上執行插入操作，即使它的內部是使用的數組存儲方式。
另外兩個類 支持基於字典的集合：SortedList 和Hashtable。它們都是包含鍵/值對應的。 SortedList以鍵進行排序，而Hashtable則沒有。Hashtable在給定的鍵上進行查 找時更快，但SortedList提供了基於鍵的有序迭代。Hashtable 通過鍵的散列值 進行查找。如果散列值是高效的，它的查找時間是一個常量，O(1)。有序列表是 使用的折半查找算法來查找關鍵值。這中一個對數的算法操作 ：O(ln n)。
最後，就是BitArray類。正如它的名字所說的，它存儲位數值。 BitArray是以整數的數組來存儲數據的。每個整型存儲一個32位的二進制值。這 讓BitArray類是壓縮的，但它還是會降低性能。BitArray 上的每個get和set操 作要在存儲的整數上完成位操作，這要查找另外的31個位。BitArray 包含的一 些方法在很多值類型上實現了立即的Boolean操作：OR, XOR, AND, 和NOT。這些 方法用BitArray做為參數，而且BitArray可以用於快速的多位mask操作， BitArray 是一個為位操作進行優化了的容器；經常使用mask操作時，要存儲這 些位標記的數據時應該使用它。但不要用它灰替換一般用圖和Boolean值數組。
對於數組類的概念而言，在C#的1.x發布版中，沒有一個集合類是強類型 的。它們都是存儲的對象引用。C#的范型將會在所有這些拓撲上包含新的版本。 這會是一個最好的方法來創建類型安全的集合。同時，目前的 System.Collections 名字空間中包含了抽象的基類，利用這些基類，你可以在 類型不安全的集合上創建你自己的類型安全的接口：CollectionBase 和 ReadOnlyCollectionBase 提供了列表和向量結構的基類。DictionaryBase 提供 了鍵/值對應的基類。DictionaryBase類是建立在Hashtable上的，它的性能與 Hashtable是一致的。
(譯注：在C#1.x中，我們其實可以合建類型安全的 集合，當然這只是利用編譯器一些特性，例如：
public class MyObject這樣就可以簡單的驗證集合的類型了，當然，本質上還是類型不安全的，這只是 一個折衷的辦法。
{
}
public class MyObjectCollection : ArrayList
{
[ObsoleteAttribute("Please use specify object.",true)]
public override int Add(object value)
{
return base.Add (value);
}
public int Add (MyObject value)
{
return base.Add (value);
}
new public MyObject this[int index]
{
get
{
return base[index] as MyObject;
}
set
{
base[index] = value;
}
}
}
任何時候，你的類型包含集合時，你可能想要把這些 集合在你的類上暴露給你的用戶。你有兩個方法：使用索引或者使用 IEnumerable接口。記住，在這一原則的一開始，我就說明過，你可以直接使用 []標記來訪問一個數組裡的元素，而且你可以用foreach來迭代數組裡的任何元 素。
你可以為你的類創建多維的索引，以C++裡你可能須要重載[]操作。 而在C#裡，你可以創建多維索引：
public int this [ int x, int y ]
{
get
{
return ComputeValue( x, y );
}
}
添加對索引器的支持就是說你的類型包含一 個集合。這也就是說你應該支持IEnumerable 接口。IEnumerable 提供了標准的 機制來迭代所有的集合元素：
public interface IEnumerable
{
IEnumerator GetEnumerator( );
}
GetEnumerator 方法返回一個實現了IEnumerator 接口的對象。 IEnumerator 接口支持集合的歷遍：
public interface IEnumerator
{
object Current
{ get; }
bool MoveNext( );
void Reset( );
}
另外，在使用 IEnumerable 接口時，如果你的類型模型是數組，你應該考慮IList 和 ICollection 接口。如果你的類型模型是字典，你應該考慮實現IDictionary 接 口。你可以自己創建對這些功能強大的接口的實現，而且你可能要花上更多的幾 頁代碼來解釋如何實現。但這裡有一個簡單的解決方案：在你創建自己的特殊集 合類時從CollectionBase 或者DictionaryBase 派生你的類。
讓我們回 顧一下今天的內容，最好的集合取決於你對操作的實現，以及應用程序對空間和 時間的目標要求。在大多數情況下，數組提供了最高效的容器。C#裡擴展的多維 數組，可以簡單的實現多維的結構，而且沒有性能的損失。當我們的應用程序須 要對元素進行更靈活的添加和移動操作時，使用眾多集合中更活越的一個就行了。最後，當你創建自己的集合模型類時，不論什麼時候都實現索引器和 IEnumerable接口。
返回教程目錄
