.NET 不變集合深究

　　自從我們 1 月份報道了不可變集合后，該 API 進一步發展，并公布了更多關于內部機制的內容。首先是關于最新版本中做出了哪些改變的概要：

　　構造函數

　　盡管不可變集合仍然不提供構造函數，但不必再使用 Empty 對象了。以前你會看到這樣的代碼：

　　var list = ImmutableList<int>.Empty.Add (1, 2, 3);

　　新版本中有一個 Create 靜態工廠方法，可以使用泛型類型推斷。表達式將簡化為：

　　var list = ImmutableList.Create (1, 2, 3);

　　兼容性

　　是否實現 IList<T>接口是熱議的話題。該接口的支持者認為，與引入 IReadOnlyList<T>之前的庫進行交互是十分必要的。而反對者則抱怨對于同樣的舊庫，沒有必要在修改集合的值之前判斷 IList.IsReadOnly 是否為 false。

　　最終，BCL 小組為遺留問題做出妥協，實現了 IList<T>。盡管所有人都同意如果沒有 IList.IsReadOnly ()會更好，但現在這背后已經有了太多復雜的因素。

　　對于公開的不可變類和接口的完整列表，請參閱兼容性表。

　　相等性語義

　　與其他集合類型一樣，不可變集合將只支持引用相等性。BCL 小組寫到：

　　計算集合的值相等性是十分昂貴的，并且對嵌套集合（如 ImmutableDictionary<string, ImmutableList<string>>）相等性的比較也很難定義。最終，提供這種功能在設計不同比較器時會導致更多的問題，就像客戶指出的那樣。

　　之前這些集合覆蓋了 Object.Equals 而不是 op_equals。

　　還有人詢問是否支持 IStructuralEquatable。由于其“很難泛化”，BCL 小組已經放棄了支持該接口。例如，在有些場景下可能需要跳過集合中的某些項（如解析器中的空格節點），如果沒有特殊的實現，這幾乎是不可能的。

　　而且遺憾的是，為了防止使用繼承來添加 IStructualEquatable，不可變類被設計為密封的。

　　平臺支持

　　不可變集合庫專為 .NET 4.5 及以后的版本而設計。它利用了新的只讀接口，并且開發者不想為舊庫維護一個單獨的版本。它還可用于 Windows 8 和“protable-net45+win8”配置。

　　序列化

　　不可變集合不支持使用 Serializable 特性的舊序列化設計。目前還沒有確定是否支持其他序列化設計，如 DataContractSerializer。

　　本質

　　不可變集合基于 AVL 樹（除棧和隊列外）。你可以在不重新復制整個樹的情況下在列表的開頭、中間或結尾執行插入操作。在維基百科關于持久數據結構這篇文章的樹這一節中，有關于這種插入的示例。

　　不可變散列表也使用了 AVL 樹。它沒有使用在散列值上執行模操作這種普通散列表的桶設計，而是根據原始散列值對樹進行排序。這意味著檢索操作需要執行一個平均檢索時間為O(log n)的二進制搜索。

　　請記住在使用多線程操作時，大O標記法會帶來誤導。不可變集合的一個替代方案是使用并發集合，它需要昂貴的內部鎖來確保線程安全。

　　不可變集合有一個有意思的特性，它的內部節點并不是不可變的。為了降低構建集合時創建的垃圾，每個節點都起始于一個可編輯的狀態。這允許構造函數改變已有的 AVL 樹，因為它添加了節點，而不是廢棄并重新創建。當構造結束、不可變包裝器返回的時候，節點將被凍結，以防止進一步修改。

　　另一個令人感到意外的設計決策是枚舉器使用了對象池。在 .NET 中，很多枚舉器被設計為不會分配任何內存。如果從 IList<T>上獲取枚舉器，需要兩次內存分配。但對于 List<T>，枚舉器是一個結構，不需要任何內存分配。

　　同樣，不可變集合也使用了結構作為枚舉器。但由于其內部結構是一個樹，因此枚舉器需要用一個棧來保存之前訪問過的節點，以進行跟蹤。為了減少內存分配，將很多這樣的棧存儲在對象池中（實際也是一個棧），并由一個鎖來進行保護。實際上，這是整個不可變集合庫中唯一的鎖。對枚舉器調用 Dispose 方法是至關重要的，否則棧將不能返回到對象池中。

　　更多信息請觀看 Chinnel 9 的視頻不可變集合的內部工作原理。

　　使用建議

　　在創建不可變集合時，最好是使用 Create 函數一次性創建整個集合。這將允許集合對樹進行預分配并直接填充節點。第二好的方法是使用 builder，不過要調用 ToImmutable 才能凍結節點。

　　在枚舉不可變集合中的項時，要使用 foreach 循環。由于其內部是樹形結構，因此 foreach 要比 for 快很多。（注：從 .NET 2.0 開始，即使是普通的列表，用 foreach 讀取也比用 for 快很多。）

　　如果集合在創建之后不會改變，那么不可變集合的性能將比用只讀包裝器保護的普通集合差很多。不可變集合更適用于高效創建與其他集合有少許不同的集合。