本文是我正在更新的深入探究immutable.js系列的第二篇。

深入探究immutable.js的實現機制（一）

深入探究immutable.js的實現機制（二） 本篇

上一篇我們研究了Immutable.js持久化數據結構的基本實現原理，對其核心數據結構Vector Trie進行了介紹，並著重探究了其中的位分区機制。採用位分区的根本原因是為了優化速度，而對於空間的優化， Immutable.js是怎麼做的呢？接下來先探討下這點。

HAMT

HAMT全稱hash array mapped trie ，其基本原理與上篇所說的Vector Trie非常相似，不過它會對樹進行壓縮，以節約一些空間。 Immutable.js參考了HAMT對樹進行了高度和節點內部的壓縮。

樹高壓縮

假設我們有一個2叉Vector Trie ，現在存了一個值，key為110 ，它會被存到0 1 1這條路徑下，如下圖：

顯然，這圖裡展示的結構已經進行了最簡單的優化，因為現在只存了一個值，所以把與110無關的節點去掉了。還能進行什麼優化嗎？我們發現，中間那兩個節點也是可以去掉的，如下圖：

獲取該值時，我們先從0找下來，發現這直接是一個根節點，那取它存儲的值就行了。就是說在不產生混淆的情況下，我們可以用盡可能少的二進制位去標識這個key 。這樣我們就進行了高度上的壓縮，既減少了空間，又減少了查找和修改的時間。
如果要添加一個值，它的key結尾也是0 ，該怎麼做呢？很簡單，如下圖：

我們只要在需要的時候增加或減少節點即可。

節點內部壓縮-Bitmap

上一篇我們提到， Immutable.js 的Trie 裡，每個節點數組的長度是32 ，然而在很多情況下，這32 個位置大部分是用不到的，這麼大的數組顯然也佔用了很大空間。使用Bitmap ，我們就可以對數組進行壓縮。
我們先拿長度為8 的數組舉例：

我們實際上只是用了數組的下標對key 進行索引，這樣想數組第5、6、7 位顯然目前是毫無作用的，那0、2、3 呢？我們有必要為了一個下標4 去維持一個長度為5的數組嗎？我們只需要指明“假想數組”中下標為1 和為4 的位置有數就可以了。這裡就可以用到bitmap ，如下：

我們採用了一個數，以其二進制形式表達“假想的長度為8的數組”中的佔位情況，1 表示數組里相應下標位置有值，0 則表示相應位置為空。比如這個二進制數第4 位（從右往左，從0 開始數）現在是1 ，就表示數組下標為4 的位置有值。這樣原本的長度為8 的數組就可以壓縮到2 。
注意這個數組中的元素還是按照“假想數組”中的順序排列的，這樣我們若要取“假想數組”中下標為i 的元素時，首先是判斷該位置有沒有值，若有，下一步就是得到在它之前有幾個元素，即在二進制數里第i 位之前有多少位為1 ，假設數量為a ，那麼該元素在當前壓縮後的數組裡下標就是a 。
具體操作中，我們可以通過bitmap & (1 << i - 1) ，得到一個二進制數，該二進制數中只有第i位之前有值的地方為1 ，其餘全為0 ，下面我們只需統計該二進制數里1 的數量即可得到下標。計算二進制數中1數量的過程被稱作popcount ，具體算法有很多，我了解不多就不展開了，前麵點擊後是維基的地址，感興趣的可以研究下。
下面我們看一下這部分的源碼：

get(shift,keyHash,key,notSetValue){if(keyHash===undefined){keyHash=hash(key);}constbit=1<<((shift===0?keyHash:keyHash>>>shift)&MASK);constbitmap=this.bitmap;return(bitmap&bit)===0?notSetValue:this.nodes[popCount(bitmap&(bit-1))].get(shift+SHIFT,keyHash,key,notSetValue);}

可見它與我們上一篇看到的源碼並沒有太大不同（Immutable.js 裡如果一個數組佔用不超過一半（ 16 個），就會對其進行壓縮，上一篇的源碼就是沒有壓縮下的情況），就是多了一個用bitmap計算數組下標的過程，方式也跟上文所講的一樣，對於這個popCount方法，我把源碼也貼出來：

functionpopCount(x){x-=(x>>1)&0x55555555;x=(x&0x33333333)+((x>>2)&0x33333333);x=(x+(x>>4))&0x0f0f0f0f;x+=x>>8;x+=x>>16;returnx&0x7f;}

為什麼是32

上一篇我們提到了Immutable.js的Vector Trie採用了32作為數組的長度，也解釋了由於採用了位分区，該數字只能是2的整數次冪，所以不能是31、33等。但8、16、64等等呢？這是通過實際測試得出的，見下圖：

圖中分別是查找和更新的時間，看上去似乎8 或16 更好？考慮到平時的使用中，查找比更新頻次高很多，所以Immutable.js 選擇了32。
回顧現在，我們就能理解第一篇文章開頭的截圖了：

我們可以看到， map 裡主要有三種類型的節點：

• HashArrayMapNode ，擁有的子節點數量＞16 ，擁有的數組長度為32
• BitmapIndexedNode ，擁有的子節點數量≤16 ，擁有的數組長度與子節點數量一致，經由bitmap壓縮
• ValueNode ，葉子節點，存儲key和value

此外，每個節點似乎都有個ownerID屬性，這又是做什麼的呢？它涉及到Immutable.js 中的可變數據結構。

Transient

其實可以說Immutable.js 中的數據結構有兩種形態，“不可變”和“可變”。雖然“不可變”是Immutable.js 的主要優勢，但“可變”形態下的操作當然效率更高。有時對於某一系列操作，我們只需要得到這組操作結束後的狀態，若中間的每一個操作都用不可變數據結構去實現顯然有些多餘。這種情景下，我們就可以使用withMutations方法對相應數據結構進行臨時的“可變”操作，最後再返回一個不可變的結構，這就是Transient ，比如這樣：

let map = new Immutable . Map ({}); map = map . withMutations (( m ) => { // 开启Transient m . set ( 'a' , 1 ); // 我们可以直接在m上进行修改，不需要m = m.set('a', 1) m . set ( 'b' , 2 ); m . set ( 'c' , 3 ); }); // Transient结束

實際上， Immutable.js裡很多方法都使用了withMutations構造臨時的可變數據結構來提高效率，比如Map中的map 、 deleteAll方法以及Map的構造函數。而在一個不可變數據結構中實現臨時的可變數據結構的關鍵（有點拗口XD），就是這個ownerID 。下圖對比了使用與不使用Transient時的區別：

顯然，使用Transient後由於無需每次生成新的節點，效率會提高空間佔用會減少。在開啟Transient時，根節點會被賦與一個新的ownerID ，在Transient完成前的每一步操作只需遵循下面的邏輯即可：

1. 若要操作的節點的ownerID與父節點的不一致，則生成新的節點，把舊節點上的值拷貝過來，其ownerID更新為父節點的ownerID ，然後進行相應操作；
2. 若要操作的節點的ownerID與父節點的一致，則直接在該節點上操作；

下面先我們看下Immutable.js中開啟Transient的相關源碼：

functionOwnerID(){}

functionasMutable(){returnthis.__ownerID?this:this.__ensureOwner(newOwnerID());}

functionwithMutations(fn){constmutable=this.asMutable();fn(mutable);returnmutable.wasAltered()?mutable.__ensureOwner(this.__ownerID):this;}

它給了根節點一個ownerID ，這個ownerID會在接下來的操作中按照上面的邏輯使用。這段代碼有個“騷操作”，就是用JS 的對像地址去作為ID ，因為每次new 之後的對象的地址肯定與之前的對像不同，所以用這種方法可以很簡便高效地構造一套ID體系。
下面再看下開啟後進行操作時的一段源碼（ Map中的set操作就會調用這個update方法）：

update(ownerID,shift,keyHash,key,value,didChangeSize,didAlter){// ...省略前面的代碼constisEditable=ownerID&&ownerID===this.ownerID;constnewNodes=setAt(nodes,idx,newNode,isEditable);if(isEditable){this.count=newCount;this.nodes=newNodes;returnthis;}returnnewHashArrayMapNode(ownerID,newCount,newNodes);}

與前面講的邏輯一樣，先比較該節點ownerID與傳進來父節點的是否一致，然後直接在節點上操作或生成新的節點。

hash衝突

這塊的內容就沒什麼新東西了，任何語言或庫裡對於hashMap 的實現都需考慮到hash 衝突的問題。我們主要看一下Immutable.js 是怎麼處理的。
要上一篇我們知道了，在往Map 裡存一對key、value 時， Immutable.js 會先對key 進行hash ，根據hash 後的值存到樹的相應位置裡。不同的key 被hash 後的結果是可能相同的，即便概率應當很小。
hash 衝突是一個很基本的問題，解決方法有很多，這裡最簡單適用的方法就是把衝突的節點擴展成一個線性結構，即數組，數組裡直接存一組組key 和value ，查找到此處時則遍歷該數組找到匹配的key 。雖然這裡的時間複雜度會變成線性的，但考慮到發生hash 衝突的概率很低，所以時間複雜度的增加可以忽略不計。
我發現Immutable.js的hash函數對abc和bCc的hash結果都是96354 ，在同一個map裡用這兩個key就會造成hash衝突，我們把這個map log出來如下：

Immutable.js用了一個叫做HashCollisionNode的節點去處理髮生衝突的鍵值，它們被放在entries數組裡。
大家也可以自己試試，代碼如下：

letmap=newImmutable.Map({});for(leti=0;i<10;i++){map=map.set(Math.random(),i);// 随便塞一点别的数据
}map=map.set('abc','value1');map=map.set('bCc','value2');console.log(map)

如果文章裡有什麼問題歡迎指正。

該文章是我正在更新的深入探究immutable.js系列的第二篇，說實話這兩篇文章寫了挺久，現成的資料很少很散，而且基本都是別的編程語言裡的。有時間和精力我會繼續更新第三篇甚至第四篇，感覺還是有些內容可以展開。
據說點贊或關注可以給我回血
|･ω･｀)
|ω･｀）
|｀）
|

參考：
hypirion.com/musings/und…
io-meter.com/2016/11/06/…
cdn.oreillystatic.com/en/assets/1…
infoscience.epfl.ch/record/1698…
lampwww.epfl.ch/papers/idea…
github.com/funfish/blo…
github.com/facebook/im…