摘要：本文會(huì)集合多方資料以及我自己的一些理解，深入一些探究實(shí)現(xiàn)機(jī)制。位分區(qū)實(shí)際上是數(shù)字分區(qū)的一個(gè)子集，所有以的整數(shù)次冪，，，，為基數(shù)的數(shù)字分區(qū)前綴樹(shù)，都可以轉(zhuǎn)為位分區(qū)。其實(shí)舉個(gè)例子最好理解比如數(shù)字的二進(jìn)制形式是，這是一個(gè)位的二進(jìn)制數(shù)。

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

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

在深入研究前，我們先看個(gè)簡(jiǎn)單的例子：

let map1 = Immutable.Map({});

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

console.log(map1);

這段代碼先后往map里寫(xiě)入了800對(duì)隨機(jī)生成的key和value。我們先看一下控制臺(tái)的輸出結(jié)果，對(duì)它的數(shù)據(jù)結(jié)構(gòu)有個(gè)大致的認(rèn)知（粗略掃一眼就行了）：

可以看到這是一個(gè)樹(shù)的結(jié)構(gòu)，子節(jié)點(diǎn)以數(shù)組的形式放在nodes屬性里，nodes的最大長(zhǎng)度似乎是32個(gè)。這里的bitmap涉及到對(duì)于樹(shù)寬度的壓縮，這些后面會(huì)說(shuō)。
其中一個(gè)節(jié)點(diǎn)層層展開(kāi)后長(zhǎng)這樣：

這個(gè)ValueNode存的就是一組值了，entry[0]是key，entry[1]是value。

大致看個(gè)形狀就行了，下面來(lái)由淺入深研究一下。

我們先看下維基對(duì)于持久化數(shù)據(jù)結(jié)構(gòu)的定義：

In computing, a persistent data structure is a data structure that always preserves the previous version of itself when it is modified.

通俗點(diǎn)解釋就是，對(duì)于一個(gè)持久化數(shù)據(jù)結(jié)構(gòu)，每次修改后我們都會(huì)得到一個(gè)新的版本，且舊版本可以完好保留。

Immutable.js 用樹(shù)實(shí)現(xiàn)了持久化數(shù)據(jù)結(jié)構(gòu)，先看下圖這顆樹(shù)：

假如我們要在g下面插入一個(gè)節(jié)點(diǎn)h，如何在插入后讓原有的樹(shù)保持不變？最簡(jiǎn)單的方法當(dāng)然是重新生成一顆樹(shù)：

但這樣做顯然是很低效的，每次操作都需要生成一顆全新的樹(shù)，既費(fèi)時(shí)又費(fèi)空間，因而有了如下的優(yōu)化方案：

我們新生成一個(gè)根節(jié)點(diǎn)，對(duì)于有修改的部分，把相應(yīng)路徑上的所有節(jié)點(diǎn)重新生成，對(duì)于本次操作沒(méi)有修改的部分，我們可以直接把相應(yīng)的舊的節(jié)點(diǎn)拷貝過(guò)去，這其實(shí)就是結(jié)構(gòu)共享。這樣每次操作同樣會(huì)獲得一個(gè)全新的版本（根節(jié)點(diǎn)變了，新的a!==舊的a），歷史版本可以完好保留，同時(shí)也節(jié)約了空間和時(shí)間。
至此我們發(fā)現(xiàn)，用樹(shù)實(shí)現(xiàn)持久化數(shù)據(jù)結(jié)構(gòu)還是比較簡(jiǎn)單的，Immutable.js提供了多種數(shù)據(jù)結(jié)構(gòu)，比如回到開(kāi)頭的例子，一個(gè)map如何成為持久化數(shù)據(jù)結(jié)構(gòu)呢？

實(shí)際上對(duì)于一個(gè)map，我們完全可以把它視為一顆扁平的樹(shù)，與上文實(shí)現(xiàn)持久化數(shù)據(jù)結(jié)構(gòu)的方式一樣，每次操作后生成一個(gè)新的對(duì)象，把舊的值全都依次拷貝過(guò)去，對(duì)需要修改或添加的屬性，則重新生成。這其實(shí)就是Object.assign，然而這樣顯然效率很低，有沒(méi)有更好的方法呢？
在實(shí)現(xiàn)持久化數(shù)據(jù)結(jié)構(gòu)時(shí)，Immutable.js 參考了Vector Trie這種數(shù)據(jù)結(jié)構(gòu)（其實(shí)更準(zhǔn)確的叫法是persistent bit-partitioned vector trie或bitmapped vector trie，這是Clojure里使用的一種數(shù)據(jù)結(jié)構(gòu)，Immutable.js 里的相關(guān)實(shí)現(xiàn)與其很相似），我們先了解下它的基本結(jié)構(gòu)。
假如我們有一個(gè) map ，key 全都是數(shù)字（當(dāng)然你也可以把它理解為數(shù)組）{0: "banana", 1: "grape", 2: "lemon", 3: "orange", 4: "apple"}，為了構(gòu)造一棵二叉Vector Trie，我們可以先把所有的key轉(zhuǎn)換為二進(jìn)制的形式：{"000": "banana", "001": "grape", "010": "lemon", "011": "orange", "100": "apple"}，然后如下圖構(gòu)建Vector Trie：

可以看到，Vector Trie的每個(gè)節(jié)點(diǎn)是一個(gè)數(shù)組，數(shù)組里有0和1兩個(gè)數(shù)，表示一個(gè)二進(jìn)制數(shù)，所有值都存在葉子節(jié)點(diǎn)上，比如我們要找001的值時(shí)，只需順著0 0 1找下來(lái)，即可得到grape。那么想實(shí)現(xiàn)持久化數(shù)據(jù)結(jié)構(gòu)當(dāng)然也不難了，比如我們想添加一個(gè)5: "watermelon"：

可見(jiàn)對(duì)于一個(gè) key 全是數(shù)字的map，我們完全可以通過(guò)一顆Vector Trie來(lái)實(shí)現(xiàn)它，同時(shí)實(shí)現(xiàn)持久化數(shù)據(jù)結(jié)構(gòu)。如果key不是數(shù)字怎么辦呢？轉(zhuǎn)成數(shù)字就行了。 Immutable.js 實(shí)現(xiàn)了一個(gè)hash函數(shù)，可以把一個(gè)值轉(zhuǎn)換成相應(yīng)數(shù)字。
這里為了簡(jiǎn)化，每個(gè)節(jié)點(diǎn)數(shù)組長(zhǎng)度僅為2，這樣在數(shù)據(jù)量大的時(shí)候，樹(shù)會(huì)變得很深，查詢(xún)會(huì)很耗時(shí)，所以可以擴(kuò)大數(shù)組的長(zhǎng)度，Immutable.js 選擇了32。為什么不是31？40？其實(shí)數(shù)組長(zhǎng)度必須是2的整數(shù)次冪，這里涉及到實(shí)現(xiàn)Vector Trie時(shí)的一個(gè)優(yōu)化，接下來(lái)我們先研究下這點(diǎn)。

數(shù)字分區(qū)指我們把一個(gè) key 作為數(shù)字對(duì)應(yīng)到一棵前綴樹(shù)上，正如上節(jié)所講的那樣。
假如我們有一個(gè) key 9128，以 7 為基數(shù)，即數(shù)組長(zhǎng)度是 7，它在Vector Trie里是這么表示的：

需要5層數(shù)組，我們先找到3這個(gè)分支，再找到5，之后依次到0。為了依次得到這幾個(gè)數(shù)字，我們可以預(yù)先把9128轉(zhuǎn)為7進(jìn)制的35420，但其實(shí)沒(méi)有這個(gè)必要，因?yàn)檗D(zhuǎn)為 7 進(jìn)制形式的過(guò)程就是不斷進(jìn)行除法并取余得到每一位上的數(shù)，我們無(wú)須預(yù)先轉(zhuǎn)換好，類(lèi)似的操作可以在每一層上依次執(zhí)行。
運(yùn)用進(jìn)制轉(zhuǎn)換相關(guān)的知識(shí)，我們可以采用這個(gè)方法key / radix^{level - 1} % radix得到每一位的數(shù)（為了簡(jiǎn)便，本文除代碼外所有/符號(hào)皆表示除法且向下取整），其中radix是每層數(shù)組的長(zhǎng)度，即轉(zhuǎn)換成幾進(jìn)制，level是當(dāng)前在第幾層，即第幾位數(shù)。比如這里key是9128，radix是7，一開(kāi)始level是5，通過(guò)這個(gè)式子我們可以得到第一層的數(shù)3。
代碼實(shí)現(xiàn)如下：

const RADIX = 7;

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

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

  return node[key % RADIX];
}

顯然，以上數(shù)字分區(qū)的方法是有點(diǎn)耗時(shí)的，在每一層我們都要進(jìn)行兩次除法一次取模，顯然這樣并不高效，位分區(qū)就是對(duì)其的一種優(yōu)化。
位分區(qū)實(shí)際上是數(shù)字分區(qū)的一個(gè)子集，所有以2的整數(shù)次冪（2，4，8，16，32...）為基數(shù)的數(shù)字分區(qū)前綴樹(shù)，都可以轉(zhuǎn)為位分區(qū)?；谝恍┪贿\(yùn)算相關(guān)的知識(shí)，我們就能避免一些耗時(shí)的計(jì)算。
數(shù)字分區(qū)把 key 拆分成一個(gè)個(gè)數(shù)字，而位分區(qū)把 key 分成一組組 bit。比如一個(gè) 32 路的前綴樹(shù)，數(shù)字分區(qū)的方法是把 key 以 32 為基數(shù)拆分（實(shí)際上就是32進(jìn)制），而位分區(qū)是把它以 5bit 拆分，實(shí)際上就是把 32 進(jìn)制數(shù)的每一位看做 5 個(gè) bit ，或者說(shuō)把 32 進(jìn)制數(shù)看做2進(jìn)制進(jìn)行操作，這樣原本的很多計(jì)算就可以用更高效的位運(yùn)算的方式代替。因?yàn)楝F(xiàn)在基數(shù)是 32，即radix為 32，所以前面的式子現(xiàn)在是key / 32^{level - 1} % 32，而 32 又可以寫(xiě)作2⁵，那么該式子可以轉(zhuǎn)成這樣key / 2^{5 × (level - 1)} % 2⁵。根據(jù)位運(yùn)算相關(guān)的知識(shí)我們知道a / 2ⁿ === a >>> n 、a % 2ⁿ === a & 2^n-1。
其實(shí)舉個(gè)例子最好理解：比如數(shù)字666666的二進(jìn)制形式是10100 01011 00001 01010，這是一個(gè)20位的二進(jìn)制數(shù)。如果我們要得到第二層那五位數(shù)01011，我們可以先把它右移>>>(左側(cè)補(bǔ)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];
}

這樣我們每次查找的速度就會(huì)得到提升?？梢钥匆粡垐D進(jìn)行理解，為了簡(jiǎn)化展示，假設(shè)我們只有2位分區(qū)即4路的前綴樹(shù)，對(duì)于626，我們的查找過(guò)程如下：

626的二進(jìn)制形式是10 01 11 00 10，所以通過(guò)以上的位運(yùn)算，我們便依次得到了10、01...

說(shuō)了這么多，我們看一下 Immutable.js 的源碼吧。雖然具體的代碼較長(zhǎng)，但主要看一下查找的部分就夠了，這是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 也正是采用了位分區(qū)的方式，通過(guò)位運(yùn)算得到當(dāng)前數(shù)組的 index 選擇相應(yīng)分支。
不過(guò)它的實(shí)現(xiàn)方式與上文所講的有一點(diǎn)不同，上文中對(duì)于一個(gè) key ，我們是“正序”存儲(chǔ)的，比如上圖那個(gè)626的例子，我們是從根節(jié)點(diǎn)往下依次按照10 01 11 00 10去存儲(chǔ)，而 Immutable.js 里則是“倒序”，按照10 00 11 01 10存儲(chǔ)。所以通過(guò)源碼這段你會(huì)發(fā)現(xiàn) Immutable.js 查找時(shí)先得到的是 key 末尾的 SHIFT 個(gè) bit ，然后再得到它們之前的 SHIFT 個(gè) bit ，依次往前下去，而前面我們的代碼是先得到 key 開(kāi)頭的 SHIFT 個(gè) bit，依次往后。
至于為什么這么做，我一開(kāi)始也沒(méi)理解，但仔細(xì)想想這的確是最好的一種方式了，用這種方式的根本原因是key的大小（二進(jìn)制長(zhǎng)度）不固定，不固定的原因又是為了減小計(jì)算量，同時(shí)也能減小空間占用并讓樹(shù)更“平衡”。仔細(xì)思考一下的話，你應(yīng)該能理解。關(guān)于這塊內(nèi)容，如果有時(shí)間我會(huì)放到之后的文章里說(shuō)。

因?yàn)椴捎昧?b>結(jié)構(gòu)共享，在添加、修改、刪除操作后，我們避免了將 map 中所有值拷貝一遍，所以特別是在數(shù)據(jù)量較大時(shí)，這些操作相比Object.assign有明顯提升。
然而，查詢(xún)速度似乎減慢了？我們知道 map 里根據(jù) key 查找的速度是O(1)，這里由于變成了一棵樹(shù)，查詢(xún)的時(shí)間復(fù)雜度變成了O(log N)，準(zhǔn)確說(shuō)是O(log₃₂ N)。
等等， 32 叉樹(shù)？這棵樹(shù)可不是一般地寬啊，Javascript里對(duì)象可以擁有的key的最大數(shù)量一般不會(huì)超過(guò)2³²個(gè)（ECMA-262第五版里定義了JS里由于數(shù)組的長(zhǎng)度本身是一個(gè) 32 位數(shù)，所以數(shù)組長(zhǎng)度不應(yīng)大于 2³² - 1 ，JS里對(duì)象的實(shí)現(xiàn)相對(duì)復(fù)雜，但大部分功能是建立在數(shù)組上的，所以在大部分場(chǎng)景下對(duì)象里 key 的數(shù)量不會(huì)超過(guò) 2³² - 1。相關(guān)討論見(jiàn)這里），這樣就可以把查找的時(shí)間復(fù)雜度當(dāng)做是“O(log₃₂ 2³²)”，差不多就是“O(log 7)”，所以我們可以認(rèn)為在實(shí)際運(yùn)用中，5bit (32路)的 Vector Trie 查詢(xún)的時(shí)間復(fù)雜度是常數(shù)級(jí)的，32 叉樹(shù)就是用了空間換時(shí)間。
空間...這個(gè) 32 叉樹(shù)占用的空間也太大了吧？即便只有三層，我們也會(huì)有超過(guò)32 × 32 × 32 = 32768個(gè)節(jié)點(diǎn)。當(dāng)然 Immutable.js 在具體實(shí)現(xiàn)時(shí)肯定不會(huì)傻乎乎的占用這么大空間，它對(duì)樹(shù)的高度和寬度都做了“壓縮”，此外，還對(duì)操作效率進(jìn)行了其它一些優(yōu)化，比如對(duì) list 進(jìn)行了“tail優(yōu)化”。相關(guān)內(nèi)容下一篇再討論。

如果文章里有什么問(wèn)題歡迎指正。

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

然后也請(qǐng)期待下一篇吧~預(yù)計(jì)一共會(huì)分2-3篇寫(xiě)完。該文章里有不懂的地方?jīng)]關(guān)系，之后的文章會(huì)討論更多內(nèi)容，同時(shí)會(huì)有助于對(duì)該文章的理解。

第二篇更新到這里了：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...