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

深入探究Immutable.js的实现机制（一） 本篇

深入探究Immutable.js的实现机制（二）

Immutable.js 由 Facebook 花费 3 年时间打造，为前端开发提供了很多便利。我们知道 Immutable.js 采用了持久化数据结构，保证每一个对象都是不可变的，任何添加、修改、删除等操作都会生成一个新的对象，且通过结构共享等方式大幅提高性能。

网上已经有很多文章简单介绍了 Immutable.js 的原理，但大多浅尝辄止，针对 Clojure 或 Go 中持久化数据结构实现的文章倒是有一些。下面结合多方资料、Immutable.js 源码以及我自己的理解，深入一些探究 Immutable.js 实现机制。

本系列文章可能是目前关于 Immutable.js 原理最深入、全面的文章，欢迎点赞收藏σ`∀´)σ。

简单的例子

在深入研究前，我们先看个简单的例子：

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 的人可能已经猜到了这里`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 进制形式的过程就是不断进行除法并取余得到每一位上的数，我们无须预先转换好，类似的操作可以在每一层上依次执行。

运用进制转换相关的知识，我们可以采用这个方法 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是当前树的深度。这种计算方式跟上面列出的式子是等价的，但可以避免多次指数计算。这个size就是上面的radix^level - 1
  for (let size = Math.pow(RADIX, (depth - 1)); size > 1; size /= RADIX) {
    node = node[Math.floor(key / size) % RADIX];
  }

  return node[key % RADIX];
}

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

function find(key) {
  let node = root; 

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

  return node[key & MASK];
}

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;
}