深入探究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，具体算法有很多，我了解不多就不展开了，前面点击后是维基的地址，感兴趣的可以研究下。
下面我们看一下这部分的源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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方法，我把源码也贴出来：
1
2
3
4
5
6
7
8
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，拥有的子节点数量 ＞16 ，拥有的数组长度为 32
  • BitmapIndexedNode，拥有的子节点数量 ≤16 ，拥有的数组长度与子节点数量一致，经由 bitmap 压缩
  • ValueNode，叶子节点，存储 key 和 value

此外，每个节点似乎都有个ownerID属性，这又是做什么的呢？它涉及到 Immutable.js 中的可变数据结构。

Transient

其实可以说 Immutable.js 中的数据结构有两种形态，“不可变”和“可变”。虽然“不可变”是 Immutable.js 的主要优势，但“可变”形态下的操作当然效率更高。有时对于某一系列操作，我们只需要得到这组操作结束后的状态，若中间的每一个操作都用不可变数据结构去实现显然有些多余。这种情景下，我们就可以使用withMutations方法对相应数据结构进行临时的“可变”操作，最后再返回一个不可变的结构，这就是Transient，比如这样：

1
2
3
4
5
6
7
8
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时的区别：

显然，使用Transient后由于无需每次生成新的节点，效率会提高空间占用会减少。在开启Transient时，根节点会被赋与一个新的ownerID，在Transient完成前的每一步操作只需遵循下面的逻辑即可：

  1. 若要操作的节点的ownerID与父节点的不一致，则生成新的节点，把旧节点上的值拷贝过来，其ownerID更新为父节点的ownerID，然后进行相应操作；
  2. 若要操作的节点的ownerID与父节点的一致，则直接在该节点上操作；
    下面先我们看下 Immutable.js 中开启Transient的相关源码：
    1
    function OwnerID() {}
    1
    2
    3
    function asMutable() {
      return this.__ownerID ? this : this.__ensureOwner(new OwnerID());
    }
    1
    2
    3
    4
    5
    function withMutations(fn) {
      const mutable = this.asMutable();
      fn(mutable);
      return mutable.wasAltered() ? mutable.__ensureOwner(this.__ownerID) : this;
    }
    它给了根节点一个ownerID，这个ownerID会在接下来的操作中按照上面的逻辑使用。这段代码有个“骚操作”，就是用 JS 的对象地址去作为 ID ，因为每次 new 之后的对象的地址肯定与之前的对象不同，所以用这种方法可以很简便高效地构造一套 ID 体系。
    下面再看下开启后进行操作时的一段源码（ Map 中的set操作就会调用这个update方法）：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    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);
    }
    与前面讲的逻辑一样，先比较该节点ownerID与传进来父节点的是否一致，然后直接在节点上操作或生成新的节点。

hash冲突

这块的内容就没什么新东西了，任何语言或库里对于 hashMap 的实现都需考虑到 hash 冲突的问题。我们主要看一下 Immutable.js 是怎么处理的。
要上一篇我们知道了，在往 Map 里存一对 key、value 时， Immutable.js 会先对 key 进行 hash ，根据 hash 后的值存到树的相应位置里。不同的 key 被 hash 后的结果是可能相同的，即便概率应当很小。
hash 冲突是一个很基本的问题，解决方法有很多，这里最简单适用的方法就是把冲突的节点扩展成一个线性结构，即数组，数组里直接存一组组 key 和 value ，查找到此处时则遍历该数组找到匹配的 key 。虽然这里的时间复杂度会变成线性的，但考虑到发生 hash 冲突的概率很低，所以时间复杂度的增加可以忽略不计。
我发现 Immutable.js 的 hash 函数对abc和bCc的 hash 结果都是 96354，在同一个 map 里用这两个 key 就会造成 hash 冲突，我们把这个 map log 出来如下：

Immutable.js 用了一个叫做HashCollisionNode的节点去处理发生冲突的键值，它们被放在entries数组里。
大家也可以自己试试，代码如下：

1
2
3
4
5
6
7
8
9
10
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)

参考：

https://hypirion.com/musings/understanding-persistent-vector-pt-1
https://io-meter.com/2016/11/06/functional-go-intro-to-hamt
https://cdn.oreillystatic.com/en/assets/1/event/259/Immutable%20data%20structures%20for%20functional%20JavaScript%20Presentation.pdf
https://infoscience.epfl.ch/record/169879/files/RMTrees.pdf
http://lampwww.epfl.ch/papers/idealhashtrees.pdf
https://github.com/funfish/blog
https://github.com/facebook/immutable-js/blob/e65e5af806ea23a32ccf8f56c6fabf39605bac80/src