Immutable ?Collections(3)Immutable List實現原理(中)變化中的不變

文/玄魂

前言

在上一篇文章（Immutable Collections（2）ImmutableList<T>實現原理.（上））,分析了）ImmutableList<T>的初始化過程，本篇博客分析除初始化之外的行為，當然概括起來也很簡單——添加、刪除、修改。這些行為的背后，我們會看到不可變集合的不變性是如何保持的，如何在不完全拷貝的情況下返回新的集合等等特性的秘密。

博文中引用的代碼并非是.NET源碼，而是反編譯得來，不正確之處，還望指教。

3.1? ADD

接上篇博文，當初始化一個沒有任何元素的ImmutableList<T>對象之后，對象會獲得一個EmptyNode。

下面看看添加一個元素的流程，及數據結構的變化。

測試代碼：

?static?void?Main(string[]?args)

????????{

????????????var?fruitBasket?=?ImmutableList.Create<string>();

??????????var?ass??=?fruitBasket.Add("ddd");}

?

如上圖，在Add方法內部，會調用Node類型的Add方法，返回一個新的的Node實例。Add方法源碼如下：

??????????????????? internal?ImmutableList<T>.Node?Add(T?key)

??????????????????? {

?????????????????????????? return?this.Insert(this.count,?key);

??????????????????? }

Add方法又調用了Insert方法，此時count=0，key=”ddd”。在Insert內部先判斷了左子樹是否為空，如果為空則創建新的Node，調用具有四個輸入參數的構造函數。

????? if?(this.IsEmpty)//

?????????????????????????? {

????????????????????????????????? return?new?ImmutableList<T>.Node(key,?this,?this,?false);

?????????????????????????? }

這一步很巧妙的完成了樹的構造，代碼如下：

private?Node(T?key,?ImmutableList<T>.Node?left,?ImmutableList<T>.Node?right,?bool?frozen?=?false)

??????????????????? {

?????????????????????????? Requires.NotNull<ImmutableList<T>.Node>(left,?"left");

?????????????????????????? Requires.NotNull<ImmutableList<T>.Node>(right,?"right");

?????????????????????????? this.key?=?key;

?????????????????????????? this.left?=?left;

?????????????????????????? this.right?=?right;

?????????????????????????? this.height?=?1?+?Math.Max(left.height,?right.height);

?????????????????????????? this.count?=?1?+?left.count?+?right.count;

?????????????????????????? this.frozen?=?frozen;

??????????????????? }

原來的root（empty node）這里變成新Node的左右子節點，新節點key字段（即value）被賦值“ddd”，height和count都等于1，此時frozen=false。需要注意的細節是，調用Node(T key, ImmutableList<T>.Node left, ImmutableList<T>.Node right, bool frozen = false)之前傳入的this指針和函數內部的this指針指向的是不同的內存區域。

注意，傳入的Node對象沒有做任何修改，返回的是新New的Node。

當前創建的Node對象的結構如下：

?

繼續運行，從Node類里出來，回到ImmutableList<T>的Add方法：

????? public?ImmutableList<T>?Add(T?value)

???????????? {

??????????????????? ImmutableList<T>.Node?node?=?this.root.Add(value);

??????????????????? return?this.Wrap(node);

???????????? }

在得到新的的Node后，會執行Wrap方法。

?

同理，內部的Node完成了樹形結構的轉換，外部的ImmutableList<T>也要完成這一轉換，返回新的ImmutableList<T>對象，將新的Node賦值到自己的root字段上，并初始化相關字段。

????? private?ImmutableList(ImmutableList<T>.Node?root,?IEqualityComparer<T>?valueComparer)

???????????? {

??????????????????? Requires.NotNull<ImmutableList<T>.Node>(root,?"root");

Requires.NotNull<IEqualityComparer<T>>(valueComparer,?"valueComparer");

??????????????????? root.Freeze();

??????????????????? this.root?=?root;

??????????????????? this.valueComparer?=?valueComparer;

???????????? }

OK，終于又回到了Main函數中，完成了一次輪回：

?

ImmutableList<T>通過更新樹結構，新建ImmutableList<T>對象同時更新對Node的引用創建新的集合。樹結構雖然發生了變化，但是原來的集合對節點的引用并沒有發生變化，從而保證了集合的不變性。

繼續修改Main函數的代碼:

??static?void?Main(string[]?args)

????????{

????????????var?fruitBasket?=?ImmutableList.Create<string>();

??????????var?a2??=?fruitBasket.Add("ddd");

??????????var?a3?=?a2.Add("ccc");

????????}

我們觀察執行var a3 = a2.Add("ccc")時的行為變化。

?

當前代碼沿著上圖所示的路徑再次來到Node類的Insert方法。

?

第一次執行Add時的情景上面分析過了，當Node的左右子樹不為空時，首先要判斷元素應該添加左還是右，判斷邏輯很簡單，判斷當前準備添加元素的索引是否小于等于左子樹元素的個數。由于當前左子樹只有一個Empty節點，所以元素會被添加到右子樹上去。可以設想一下，如果再次執行添加操作，元素還是會被添加到右子樹上去，左邊會一直為空。所以在每次添加操作執行完畢之后，會調用MakeBalanced方法來使左右平衡。如果您熟悉紅黑樹的話，對保持樹的平衡時使用的扭轉算法應該不會陌生。這里我不想深入解釋ImmutableList 的“平衡扭轉”算法，我覺得單獨拿出來一篇博文來講解會更好。

下一篇博客中，我們繼續分析ImmutableList的其他行為的原理。

轉載于:https://www.cnblogs.com/xuanhun/p/3159823.html

總結

以上是生活随笔為你收集整理的Immutable Collections(3)Immutable List实现原理(中)变化中的不变的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。