深入探究immutable.js的實現機制（一）
本文是我正在更新的深入探究immutable.js系列的第一篇。
深入探究immutable.js的實現機制（一） 本篇
Immutable.js 由Facebook 花費3 年時間打造，為前端開發提供了很多便利，如今React+Redux+Immutable.js 的組合已經成為許多項目的標配。我們知道Immutable.js採用了持久化数据结构和结构共享，保證每一個對像都是不可變的，任何添加、修改、刪除等操作都會生成一個新的對象，且通過结构共享等方式大幅提高性能。
網上已經有很多文章簡單介紹了Immutable.js 的原理，但基本都是淺嚐輒止，我也是搜了很久沒找到針對Immutable.js 原理的相對深入詳細的文章，針對Clojure 或Go 中持久化數據結構實現的文章倒是有一些。本文會集合多方資料以及我自己的一些理解，深入一些探究Immutable.js 實現機制。
由於需要探討的內容較長，寫起來也比較費時，所以該系列會分成二到三篇文章完成。
Immutable.js部分參考了Clojure中的
PersistentVector的實現方式，並有所優化和取捨，本文的一些內容也是基於它，想了解的可以閱讀這裡（共五篇，這是第一篇）
例子
在深入研究前，我們先看個簡單的例子：
letmap1=Immutable.Map({});for(leti=0;i<800;i++){map1=map1.set(Math.random(),Math.random());}console.log(map1);這段代碼先後往map裡寫入了800對隨機生成的key和value。我們先看一下控制台的輸出結果，對它的數據結構有個大致的認知（粗略掃一眼就行了）：
可以看到這是一個樹的結構，子節點以數組的形式放在nodes屬性裡，nodes的最大長度似乎是32個。了解過bitmap的人可能已經猜到了這裡bitmap屬性是做什麼的，它涉及到對於樹寬度的壓縮，這些後面會說。
其中一個節點層層展開後長這樣：
這個ValueNode存的就是一組值了， entry[0]是key， entry[1]是value。
大致看個形狀就行了，下面我們會由淺入深逐步揭開它的面紗。
基本原理
我們先看下維基對於持久化数据结构的定義：
In computing, a persistent data structure is a data structure that always preserves the previous version of itself when it is modified.
通俗點解釋就是，對於一個持久化数据结构，每次修改後我們都會得到一個新的版本，且舊版本可以完好保留。
Immutable.js用樹實現了持久化数据结构，先看下圖這顆樹：
假如我們要在g下面插入一個節點h ，如何在插入後讓原有的樹保持不變？最簡單的方法當然是重新生成一顆樹：
但這樣做顯然是很低效的，每次操作都需要生成一顆全新的樹，既費時又費空間，因而有瞭如下的優化方案：
我們新生成一個根節點，對於有修改的部分，把相應路徑上的所有節點重新生成，對於本次操作沒有修改的部分，我們可以直接把相應的舊的節點拷貝過去，這其實就是结构共享。這樣每次操作同樣會獲得一個全新的版本（根節點變了，新的a !==舊的a ），歷史版本可以完好保留，同時也節約了空間和時間。
至此我們發現，用樹實現持久化数据结构還是比較簡單的，Immutable.js提供了多種數據結構，比如回到開頭的例子，一個map如何成為持久化数据结构呢？
Vector Trie
實際上對於一個map，我們完全可以把它視為一顆扁平的樹，與上文實現持久化数据结构的方式一樣，每次操作後生成一個新的對象，把舊的值全都依次拷貝過去，對需要修改或添加的屬性，則重新生成。這其實就是Object.assign ，然而這樣顯然效率很低，有沒有更好的方法呢？
在實現持久化数据结构時，Immutable.js參考了Vector Trie這種數據結構（其實更準確的叫法是persistent bit-partitioned vector trie或bitmapped vector trie ，這是Clojure裡使用的一種數據結構，Immutable .js 裡的相關實現與其很相似），我們先了解下它的基本結構。
假如我們有一個map ，key全都是數字（當然你也可以把它理解為數組） {0: 'banana', 1: 'grape', 2: 'lemon', 3: 'orange', 4: 'apple'} ，為了構造一棵二叉Vector Trie ，我們可以先把所有的key轉換為二進制的形式： {'000': 'banana', '001': 'grape', '010': 'lemon', '011': 'orange', '100': 'apple'} ，然後如下圖構建Vector Trie ：
可以看到， Vector Trie的每個節點是一個數組，數組裡有0和1兩個數，表示一個二進制數，所有值都存在葉子節點上，比如我們要找001的值時，只需順著0 0 1找下來，即可得到grape 。那麼想實現持久化数据结构當然也不難了，比如我們想添加一個5: 'watermelon' ：
可見對於一個key全是數字的map，我們完全可以通過一顆Vector Trie來實現它，同時實現持久化数据结构。如果key不是數字怎麼辦呢？轉成數字就行了。 Immutable.js實現了一個hash函數，可以把一個值轉換成相應數字。
這里為了簡化，每個節點數組長度僅為2，這樣在數據量大的時候，樹會變得很深，查詢會很耗時，所以可以擴大數組的長度，Immutable.js 選擇了32。為什麼不是31？40？其實數組長度必須是2的整數次冪，這裡涉及到實現Vector Trie時的一個優化，接下來我們先研究下這點。
數字分區（Digit partitioning）
数字分区指我們把一個key作為數字對應到一棵前綴樹上，正如上節所講的那樣。
假如我們有一個key 9128 ，以7為基數，即數組長度是7，它在Vector Trie裡是這麼表示的：
需要5層數組，我們先找到3這個分支，再找到5 ，之後依次到0 。為了依次得到這幾個數字，我們可以預先把9128轉為7進制的35420 ，但其實沒有這個必要，因為轉為7進制形式的過程就是不斷進行除法並取餘得到每一位上的數，我們無須預先轉換好，類似的操作可以在每一層上依次執行。
運用進制轉換相關的知識，我們可以採用這個方法得到每一位的數（為了簡便，本文除代碼外所有
/符號皆表示除法且向下取整），其中radix是每層數組的長度，即轉換成幾進制， level是當前在第幾層，即第幾位數。比如這裡key是9128 ， radix是7 ，一開始level是5 ，通過這個式子我們可以得到第一層的數3 。
代碼實現如下：
constRADIX=7;functionfind(key){letnode=root;// root是根節點，在別的地方定義了// depth是當前樹的深度。這種計算方式跟上面列出的式子是等價的，但可以避免多次指數計算for(letsize=Math.pow(RADIX,(depth-1));size>1;size/=RADIX){node=node[Math.floor(key/size)%RADIX];}returnnode[key%RADIX];}位分區（Bit Partitioning）
顯然，以上数字分区的方法是有點耗時的，在每一層我們都要進行兩次除法一次取模，顯然這樣並不高效，位分区就是對其的一種優化。
位分区實際上是数字分区的一個子集，所有以2的整數次冪（2，4，8，16，32…）為基數的数字分区前綴樹，都可以轉為位分区。基於一些位運算相關的知識，我們就能避免一些耗時的計算。
数字分区把key拆分成一個個數字，而位分区把key分成一組組bit。以一個32路的前綴樹為例，数字分区的方法是把key以32為基數拆分（實際上就是32進制），而位分区是把它以5個bits拆分，因為 ，那我們就可以把32 進制數的每一位看做5 個二進制位。實際上就是把32 進制數當成2進制進行操作，這樣原本的很多計算就可以用更高效的位運算的方式代替。因為現在基數是32，即
radix為32，所以前面的式子現在是 ，而
，那麼該式子可以寫成這樣
。根據位運算相關的知識我們知道
=== a >>> n 、 === a & () 。所以該式子的計算可以用位運算來完成。
如果你對位運算不太熟悉的話，大可不看上面的式子，舉個例子就好理解了：比如數字666666的二進制形式是10100 01011 00001 01010 ，這是一個20位的二進制數。如果我們要得到第二層那五位數01011 ，我們可以先把它右移>>> (左側補0)10位，得到00000 00000 10100 01011 ，再&一下00000 00000 00000 11111 ，就得到了01011 。
這樣我們可以得到下面的代碼：
constSHIFT=5;constWIDTH=1<<SHIFT,// 32constMASK=WIDTH-1;// 31，即11111functionfind(key){letnode=root;for(letshift=(depth-1)*SHIFT;shift>0;shift-=SHIFT){node=node[(key>>>shift)&MASK];}returnnode[key&MASK];}這樣我們每次查找的速度就會得到提升。可以看一張圖進行理解，為了簡化展示，假設我們用了一個4路前綴樹， ，所以用兩位二進制數分區。對於
626 ，我們的查找過程如下：
626的二進制形式是10 01 11 00 10 ，所以通過上面的位運算方法，我們便可以高效地依次得到10 、 01 …
源碼
說了這麼多，我們看一下Immutable.js 的源碼吧。我們主要看一下查找的部分就夠了，這是Vector Trie的核心。
get(shift,keyHash,key,notSetValue){if(keyHash===undefined){keyHash=hash(key);}constidx=(shift===0?keyHash:keyHash>>>shift)&MASK;constnode=this.nodes[idx];returnnode?node.get(shift+SHIFT,keyHash,key,notSetValue):notSetValue;}可以看到， Immutable.js 也正是採用了位分區的方式，通過位運算得到當前數組的index 選擇相應分支。
不過它的實現方式與上文所講的有一點不同，上文中對於一個key ，我們是“正序”存儲的，比如上圖那個626的例子，我們是從根節點往下依次按照10 01 11 00 10去存儲，而Immutable.js裡則是“倒序”，按照10 00 11 01 10存儲。所以通過源碼這段你會發現Immutable.js 查找時先得到的是key 末尾的SHIFT 個bit ，然後再得到它們之前的SHIFT 個bit ，依次往前下去，而前面我們的代碼是先得到key 開頭的SHIFT 個bit，依次往後。
用這種方式的原因之一是key的大小（二進制長度）不固定。
時間複雜度
因為採用了结构共享，在添加、修改、刪除操作後，我們避免了將map中所有值拷貝一遍，所以特別是在數據量較大時，這些操作相比Object.assign有明顯提升。
然而，查詢速度似乎減慢了？我們知道map裡根據key查找的速度是O(1) ，這裡由於變成了一棵樹，查詢的時間複雜度變成了O(log N) ，準確說是O( ) 。
等等32 叉樹？這棵樹可不是一般地寬啊，Javascript裡對象可以擁有的key的最大數量一般不會超過個（ ECMA-262第五版裡定義了JS裡由於數組的長度本身是一個32位數，所以數組長度不應大於
，JS裡對象的實現相對複雜，但大部分功能是建立在數組上的，所以在大部分場景下對象裡key 的數量不會超過
。相關討論見這裡），這樣就可以把查找的時間複雜度當做是“
O( ) ”，差不多就是“ O(log 7) ”，所以我們可以認為在實際運用中，5bit (32路)的Vector Trie查詢的時間複雜度是常數級的，32叉樹就是用了空間換時間。
空間…這個32 叉樹佔用的空間也太大了吧？即便只有三層，我們也會有超過32 × 32 × 32 = 32768個節點。當然Immutable.js 在具體實現時肯定不會傻乎乎的佔用這麼大空間，它對樹的高度和寬度都做了“壓縮”，此外，還對操作效率進行了其它一些優化，比如對list 進行了“ tail優化”。相關內容我們下一篇討論。
如果文章裡有什麼問題歡迎指正。
該文章是我正在更新的深入探究immutable.js系列的第一篇，我花了不少功夫才完成這篇文章，如果對你有幫助，希望能點個贊~
本文是我正在更新的深入探究immutable.js系列的第一篇。目前完成到第二篇。
深入探究immutable.js的實現機制（一） 本篇
參考：
https:// hypirion.com/musings/un derstanding-persistent-vector-pt-1
https:// io-meter.com/2016/09/03 /Functional-Go-persist-datastructure-intro
https:// cdn.oreillystatic.com/e n/assets/1/event/259/Immutable%20data%20structures%20for%20functional%20JavaScript%20Presentation.pdf
https:// michael.steindorfer.name /publications/oopsla15.pdf
https:// github.com/facebook/imm utable-js/blob/e65e5af806ea23a32ccf8f56c6fabf39605bac80/src