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

发表于 4年以前 | 总阅读数：730 次

深入探究immutable.js的实现机制一我们研究了 Immutable.js 持久化数据结构的基本实现原理，对其核心数据结构Vector Trie进行了介绍，并着重探究了其中的位分区机制。采用位分区的根本原因是为了优化速度，而对于空间的优化， Immutable.js 是怎么做的呢？接下来先探讨下这点。

HAMT

[HAMT](https://en.wikipedia.org/wiki/Hash_array_mapped_trie "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](https://en.wikipedia.org/wiki/Bit_array "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](https://en.wikipedia.org/wiki/Hamming_weight "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方法，我把源码也贴出来：

functionpopCount(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](http://facebook.github.io/immutable-js#batching-mutations "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时的区别：

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

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

下面先我们看下 Immutable.js 中开启Transient的相关源码：

functionOwnerID() {}

functionasMutable() {
    return this.__ownerID ? this : this.__ensureOwner(new OwnerID());
}

functionwithMutations(fn) {
    const mutable = this.asMutable();
    fn(mutable);
    return mutable.wasAltered() ? mutable.__ensureOwner(this.__ownerID) : this;
}

它给了根节点一个ownerID，这个ownerID会在接下来的操作中按照上面的逻辑使用。注意这段代码是用 JS 的对象地址去作为 ID ，因为每次 new 之后的对象的地址肯定与之前的对象不同，所以用这种方法可以很简便高效地构造一套 ID 体系。下面再看下开启后进行操作时的一段源码（ Map 中的set操作就会调用这个update方法）：

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

    returnnew HashArrayMapNode(ownerID, newCount, newNodes);
}

与前面讲的逻辑一样，先比较该节点ownerID与传进来父节点的是否一致，然后直接在节点上操作或生成新的节点。

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数组里。大家也可以自己试试，代码如下：

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)

如果文章里有什么问题欢迎指正。

该文章是我正在更新的深入探究immutable.js系列的第二篇，说实话这两篇文章写了挺久，现成的资料很少很散，而且基本都是别的编程语言里的。有时间和精力我会继续更新第三篇甚至第四篇，感觉还是有些内容可以展开。

参考资料

[1]深入探究immutable.js的实现机制（一）: https://www.codingsky.com/doc/2020/7/30/649.html
[2]hypirion.com/musings/und…: https://hypirion.com/musings/understanding-persistent-vector-pt-1
[3]io-meter.com/2016/11/06/…: https://io-meter.com/2016/11/06/functional-go-intro-to-hamt
[4]cdn.oreillystatic.com/en/assets/1…: https://cdn.oreillystatic.com/en/assets/1/event/259/Immutable%20data%20structures%
20for%20functional%20JavaScript%20Presentation.pdf
[5]infoscience.epfl.ch/record/1698…: https://infoscience.epfl.ch/record/169879/files/RMTrees.pdf
[6]lampwww.epfl.ch/papers/idea…: http://lampwww.epfl.ch/papers/idealhashtrees.pdf
[7]github.com/funfish/blo…: https://github.com/funfish/blog
[8]github.com/facebook/im…: https://github.com/facebook/immutable-js/blob/e65e5af806ea23a32ccf8f56c6fabf39605bac80/src