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

本文是我正在更新的 深入探究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);
  }
  const bit = 1 << ((shift === 0 ? keyHash : keyHash >>> shift) & MASK);
  const bitmap = this.bitmap;
  return (bitmap & bit) === 0
    ? notSetValue
    : this.nodes[popCount(bitmap & (bit - 1))].get(
        shift + SHIFT,
        keyHash,
        key,
        notSetValue
      );
}复制代码

可见它与我们上一篇看到的源码并没有太大不同（Immutable.js 里如果一个数组占用不超过一半（ 16 个），就会对其进行压缩，上一篇的源码就是没有压缩下的情况），就是多了一个用 bitmap 计算数组下标的过程，方式也跟上文所讲的一样，对于这个 popCount 方法，我把源码也贴出来：

function popCount(x) {
  x -= (x >> 1) & 0x55555555;
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  x = (x + (x >> 4)) & 0x0f0f0f0f;
  x += x >> 8;
  x += x >> 16;
  return x & 0x7f;
}复制代码

为什么是32

上一篇我们提到了 Immutable.js 的 Vector Trie 采用了 32 作为数组的长度，也解释了由于采用了 位分区 ，该数字只能是2的整数次幂，所以不能是 31、33 等。但8、16、64等等呢？这是通过实际测试得出的，见下图：

图中分别是查找和更新的时间，看上去似乎 8 或 16 更好？考虑到平时的使用中，查找比更新频次高很多，所以 Immutable.js 选择了 32。

回顾

现在，我们就能理解第一篇文章开头的截图了：

我们可以看到， map 里主要有三种类型的节点：

HashArrayMapNode
BitmapIndexedNode
ValueNode

此外，每个节点似乎都有个 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 时的区别：

完成前的每一步操作只需遵循下面的逻辑即可：

1. 若要操作的节点的 ownerID 与父节点的不一致，则生成新的节点，把旧节点上的值拷贝过来，其 ownerID 更新为父节点的 ownerID ，然后进行相应操作；
2. 若要操作的节点的 ownerID 与父节点的一致，则直接在该节点上操作；

function OwnerID() {}复制代码

function asMutable() {
  return this.__ownerID ? this : this.__ensureOwner(new OwnerID());
}复制代码

function withMutations(fn) {
  const mutable = this.asMutable();
  fn(mutable);
  return mutable.wasAltered() ? mutable.__ensureOwner(this.__ownerID) : this;
}复制代码

update(ownerID, shift, keyHash, key, value, didChangeSize, didAlter) {
  // ...省略前面的代码
  const isEditable = ownerID && ownerID === this.ownerID;
  const newNodes = setAt(nodes, idx, newNode, isEditable);

  if (isEditable) {
    this.count = newCount;
    this.nodes = newNodes;
    return this;
  }

  return new HashArrayMapNode(ownerID, newCount, newNodes);
}复制代码

let map = new Immutable.Map({});

for (let i = 0; i < 10; i++) {
  map = map.set(Math.random(), i); // 随便塞一点别的数据
}

map = map.set('abc', 'value1');
map = map.set('bCc', 'value2');

console.log(map)复制代码