摘要：本文會集合多方資料以及我自己的一些理解，深入一些探究實現機制。位分區實際上是數字分區的一個子集，所有以的整數次冪，，，，為基數的數字分區前綴樹，都可以轉為位分區。其實舉個例子最好理解比如數字的二進制形式是，這是一個位的二進制數。

Immutable.js 采用了持久化數據結構和結構共享，保證每一個對象都是不可變的，任何添加、修改、刪除等操作都會生成一個新的對象，且通過結構共享等方式大幅提高性能。
網上已經有很多文章簡單介紹了 Immutable.js 的原理，但基本都是淺嘗輒止，我也是搜了很久沒找到針對 Immutable.js 原理的相對深入詳細的文章，中英文都沒有，針對 Clojure 或 Go 中持久化數據結構實現的文章倒是有一些。本文會集合多方資料以及我自己的一些理解，深入一些探究 Immutable.js 實現機制。文章可能會分2-3篇完成。

Immutable.js 部分參考了 Clojure 中的PersistentVector的實現方式，并有所優化和取舍，本文的一些內容也是基于它，想了解的可以閱讀這里（共五篇，這是第一篇）

在深入研究前，我們先看個簡單的例子：

let map1 = Immutable.Map({});

for (let i = 0; i < 800; i++) {
  map1 = map1.set(Math.random(), Math.random());
}

console.log(map1);

這段代碼先后往map里寫入了800對隨機生成的key和value。我們先看一下控制臺的輸出結果，對它的數據結構有個大致的認知（粗略掃一眼就行了）：

可以看到這是一個樹的結構，子節點以數組的形式放在nodes屬性里，nodes的最大長度似乎是32個。這里的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如何成為持久化數據結構呢？

實際上對于一個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時的一個優化，接下來我們先研究下這點。

數字分區指我們把一個 key 作為數字對應到一棵前綴樹上，正如上節所講的那樣。
假如我們有一個 key 9128，以 7 為基數，即數組長度是 7，它在Vector Trie里是這么表示的：

需要5層數組，我們先找到3這個分支，再找到5，之后依次到0。為了依次得到這幾個數字，我們可以預先把9128轉為7進制的35420，但其實沒有這個必要，因為轉為 7 進制形式的過程就是不斷進行除法并取余得到每一位上的數，我們無須預先轉換好，類似的操作可以在每一層上依次執行。
運用進制轉換相關的知識，我們可以采用這個方法key / radix^{level - 1} % radix得到每一位的數（為了簡便，本文除代碼外所有/符號皆表示除法且向下取整），其中radix是每層數組的長度，即轉換成幾進制，level是當前在第幾層，即第幾位數。比如這里key是9128，radix是7，一開始level是5，通過這個式子我們可以得到第一層的數3。
代碼實現如下：

const RADIX = 7;

function find(key) {
  let node = root; // root是根節點，在別的地方定義了

  // depth是當前樹的深度。這種計算方式跟上面列出的式子是等價的，但可以避免多次指數計算
  for (let size = Math.pow(RADIX, (depth - 1)); size > 1; size /= RADIX) {
    node = node[Math.floor(key / size) % RADIX];
  }

  return node[key % RADIX];
}

顯然，以上數字分區的方法是有點耗時的，在每一層我們都要進行兩次除法一次取模，顯然這樣并不高效，位分區就是對其的一種優化。
位分區實際上是數字分區的一個子集，所有以2的整數次冪（2，4，8，16，32...）為基數的數字分區前綴樹，都可以轉為位分區。基于一些位運算相關的知識，我們就能避免一些耗時的計算。
數字分區把 key 拆分成一個個數字，而位分區把 key 分成一組組 bit。比如一個 32 路的前綴樹，數字分區的方法是把 key 以 32 為基數拆分（實際上就是32進制），而位分區是把它以 5bit 拆分，實際上就是把 32 進制數的每一位看做 5 個 bit ，或者說把 32 進制數看做2進制進行操作，這樣原本的很多計算就可以用更高效的位運算的方式代替。因為現在基數是 32，即radix為 32，所以前面的式子現在是key / 32^{level - 1} % 32，而 32 又可以寫作2⁵，那么該式子可以轉成這樣key / 2^{5 × (level - 1)} % 2⁵。根據位運算相關的知識我們知道a / 2ⁿ === a >>> n 、a % 2ⁿ === a & 2^n-1。
其實舉個例子最好理解：比如數字666666的二進制形式是10100 01011 00001 01010，這是一個20位的二進制數。如果我們要得到第二層那五位數01011，我們可以先把它右移>>>(左側補0)10位，得到00000 00000 10100 01011，再&一下00000 00000 00000 11111，就得到了01011。
這樣我們可以得到下面的代碼：

const SHIFT = 5;
const WIDTH = 1 << SHIFT, //  32
const MASK = WIDTH - 1; // 31，即11111

function find(key) {
  let node = root; 

  for (let shift = (depth - 1) * SHIFT; shift > 0; shift -= SHIFT) {
    node = node[(key >>> shift) & MASK];
  }

  return node[key & MASK];
}

這樣我們每次查找的速度就會得到提升。可以看一張圖進行理解，為了簡化展示，假設我們只有2位分區即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);
  }
  const idx = (shift === 0 ? keyHash : keyHash >>> shift) & MASK;
  const node = this.nodes[idx];
  return node
    ? 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(log₃₂ N)。
等等， 32 叉樹？這棵樹可不是一般地寬啊，Javascript里對象可以擁有的key的最大數量一般不會超過2³²個（ECMA-262第五版里定義了JS里由于數組的長度本身是一個 32 位數，所以數組長度不應大于 2³² - 1 ，JS里對象的實現相對復雜，但大部分功能是建立在數組上的，所以在大部分場景下對象里 key 的數量不會超過 2³² - 1。相關討論見這里），這樣就可以把查找的時間復雜度當做是“O(log₃₂ 2³²)”，差不多就是“O(log 7)”，所以我們可以認為在實際運用中，5bit (32路)的 Vector Trie 查詢的時間復雜度是常數級的，32 叉樹就是用了空間換時間。
空間...這個 32 叉樹占用的空間也太大了吧？即便只有三層，我們也會有超過32 × 32 × 32 = 32768個節點。當然 Immutable.js 在具體實現時肯定不會傻乎乎的占用這么大空間，它對樹的高度和寬度都做了“壓縮”，此外，還對操作效率進行了其它一些優化，比如對 list 進行了“tail優化”。相關內容下一篇再討論。

如果文章里有什么問題歡迎指正。

該文章是我正在更新的深入探究immutable.js系列的第一篇，我花了不少功夫才完成這篇文章，如果對你有幫助，希望能點個贊~

然后也請期待下一篇吧~預計一共會分2-3篇寫完。該文章里有不懂的地方沒關系，之后的文章會討論更多內容，同時會有助于對該文章的理解。

第二篇更新到這里了：https://juejin.im/post/5ba4a6...

參考：
https://hypirion.com/musings/...
https://io-meter.com/2016/09/...
https://cdn.oreillystatic.com...
https://michael.steindorfer.n...
https://github.com/facebook/i...