24. immutable.js 数据结构

[funfish]

前言

前文《初识immutable》介绍 immutable 的一些基本操作和特色，但是其重点部分结构共享，即数据结构留在了这里。这不是平时接触到的简单的数组、对象亦或则字典的形式，而是 tree ！日常开发基本就遇不到树结构，再复杂一个字典表就可以搞定了，于是乎 immutable.js 提供了一次很好的学习数据结构，学习算法的体验。

共享结构

共享结构还是比较简单的。对于已有的数据结构，若需要更新其中的某个节点（中间节点或则子叶），并不会把整个数据结构都拷贝一份，再修改该节点并返回新的数据结构。immutable.js 里面会采用路径修改的方式来实现更新。

简单的来讲，对于数组或则对象的形式，更新的时候，仅仅会修改该节点，浅拷贝该层级所有节点，修改所有父节点，以及浅拷贝该父节点的所有同父级节点。这么说可能有点绕口，来看看大神 camsong 做的图：

如图所示，当更新黄色节点的时候，黄色节点所在的同一父节点的元素都会被浅拷贝，同时黄色节点的所有父节点也会被更新，以及浅拷贝父节点的同一级节点。于是就有了路径修改这一说，相当于其他节点也就是树结构左下角蓝色的四个节点，对于新旧结构就是处于共享状态的。所以这应该就很清晰了，通过这样的树结构减少拷贝数量，而对于其他节点而言，由于都是浅拷贝，是不影响旧结构指向的。只是在新的父节点处修改对子节点的指向，也就是上图中右边分支。

同样的对于 List 结构，也是树结构，也会浅拷贝，所以这里就不多谈了。

数据结构

看了上篇博客的，基本可以发现，列表 List 的数据结构就是一个 32 阶树。查找和更新都是根据 5 bit 为标准的，一个分支最多有 32 个子分支。所以通过对索引序号 index 进行位移操作，就是 index >>> level，再取 31 的模。从 index 的高位到低位来读取树结构从上到下的数据。而这里用到的是什么技巧呢？

Bitmapped Vector Trie

总所周知，对于普通的数组结构，其读取的时间复杂度为 O(1)，只是插入更新的时间复杂度为 O(n)，对于海量数据是不可取的。而二叉树 BST 呢，读取的速度为 1.39 O(lg n)，插入平均速度也为 1.39 O(lg n)。相较于线性的读写，还是要优秀不少的。**所以是不可能采用线性结构来存储数据的。**List 结构采用 32 阶的树结构，其读写的时间复杂度更加优秀，是 O(lg n)，其底数是 32，也就是说时间复杂度是二叉树的 1/5。

Bitmapped Vector Trie，位图数列前缀树，名字有点长，但是意思很明显。先看看维基中的 trie：

trie 前缀树，是树的一种，只是 trie 的键是由位置决定的。比如数字 3 ，其就是有 t 节点， e 节点和子叶 a 节点决定的，是由其路径决定的。通过 tea 这个键，就可以找到值 3，而对于键 inn，则可以找到 9 这个数值。这个就是 trie 的功能，多用由于字典查询~~

Bitmap 算法则是，将数据通过位移运算映射到位上，从而实现内存开销的减少。如果能用一个 bit 位来识别这样一个数字，就会很方便了。如数字 3，通过位运算 1 << 3 得到映射的二进制 1 000，从而当的映射数据的第四位为 1 的时候，则说明 3 这个数存在！为 0，则不存在，通过位图算法可以大大减少内存使用。对于 java，int 类型的长度为 32 位，所以也就是为原来 1/32 的样子。

在普通数组中要如何结合 trie/Bitmap 呢。trie 和 Bitmap 的结合可以加快树结构里面的查询。具体操作可以看下图，

在该图中，对于数组 zoo，当要取索引为 5 的数，要如何获取呢？可以看到存储的数据结构是 trie 的形式，只是每个节点上面的键名都不是之前介绍的字符串，而是 0/1 的形式。将索引 5 二进制化为：101。通过二进制数 101，从高位到低位依次读取 1 bit，来读取现有的 trie 结构上节点的数组的值，就能够确定路径，从而现实 Bitmap 位图的查询，都不用什么复杂的判断，只要每次取索引 5 的映射值，也就是二进制 101，就能够轻松读到数据。

对于 32 阶的数结构，则是每次都读取最高位的 5 bit，来实现 Trie 查询。对于长度为 65 的数组，如索引值为 60，则其第一次 60 >> 5 & 31 为 1，第二次为 28，所以第 60 个数据，在第一个 32 阶分支的第二个分支下面的第 28 个元素就是目标值。是不是很快，飞一般的速度。

32 阶的选择

选择 32 阶树结构是要远远快于二叉树的，理论上是二叉树时间复杂度的 1/5。使用 32 底数的时候，若层级超过 7，就已经有超过数十亿个数了，这个时候内存可能都不够了吧。所以在实际开发中可以把这个 32阶的 Bitmapped Vector Trie 的时间复杂度当作常数。

那为何不继续使用更大的底数呢，底数更大，其时间复杂度应该是更加优秀的吧？

事实上，选择 32 作为 m 阶的分叉，是有其特殊性的。可以看到下图：

可以看到上面是更新操作，下面接近 x 轴的是查询操作。而当底数为 32 的时候，在更新和查询操作上都有良好的平衡性。当然这么一看不是最好的选择，可能看客会觉得似乎 8 要远远优于 32。只是这个考虑是不周全，在日常使用持久化操作的时候，查询操作的比例是要远远高于更新操作的。所以很显然会选择 32 而不是 8，前者的查询耗时是后者的 66% 左右。

只是为什么选择 32，而不是 33/31/29 之类的呢？原因很简单，因为选择 32 的时候，对索引的取模操作，可以被优化为位运算，也就是上文中出现的 index >>> level。在现代计算机下，位运算可以大大的减少计算时间。

另外由于计算机的高速缓存行的问题，阶数少的时候，其缓存效果更加，导致了底数为 2 的查询速度只是 32 的 1/4 而已，而不是 1/5。

HAMT

上面介绍 Bitmapped Vector Trie 的时候，讲的是 List 结构。那对于 Map 结构又要如何处理，毕竟没有 List 结构的索引，好像就无从下手了。

Map 是没有索引，没有错，但是我们可以把键名的哈希值变为索引呀~~

HAMT：Hash Arrey Mapped Trie，就是这样一个结构，将 key 的哈希值存储在 Trie 节点上。如同索引一样，需要对哈希值取模，也就是 32 bit 的位操作。只是不同的是 List 结构上面是从高位往低位的索引读取的，而 Map 是从 key 哈希值的低位往高位顺序读取的。为什么这么设计呢？List 一开始就能够知道数组的容量 capacity 是多少，通过 capacity 和 index 索引可以知道数据的位置，而容量肯定是大于等于索引的，排在索引前面的是必然有数据内容的。而 Map 结构，如果从哈希值的高位往低位读取的话，那就有点恐怖的，小于该哈希值的字段，却不一定有呀，这样就导致在没有什么数据下，树的层级就可以很深了。这样就达到了压缩层级的效果。

为了更好的解释 HAMT 结构，这里举个例子，对于 key = Aa，其计算出来的哈希值为 2112，取模 2112 & 31 为 0，所以他将会在数组的下角标为 0 的对象里面，至于该对象是不就是这个 key 生成的对象呢？取决于还有没有其他低 5 位也是 0 的元素，如果有那还要取下一个高 5 位来查询，直到找到数组。这样就很明朗了，通过每次取 31 的模，从低位到高位，这样的 Bitmapped 的方式就可以确定元素的位置了。

每次取 31 的模，这样每个层最多都有 32 个元素。于是就形成了 32 分叉的结构。但是并不是每次都是 32 个数据的，这样看数量量的大小。当字段比较少，少于 8 个的时候，Map 结构只是个简单的数组结构，每次读取 key，通过循环判断就好了。

如果字段介于 8 和 16 个之间（普通情况下），则是采用 BitmapIndexedNode 的对象，通过 bitmap 方式：计算出每个键 key 的哈希值，再将哈希值做基于 1 的位移操作，如哈希值为 A，将会得到新的 bit = 1 << A，如下所示：

class BitmapIndexedNode {
  constructor(ownerID, bitmap, nodes) {
    this.ownerID = ownerID;
    this.bitmap = bitmap;
    this.nodes = nodes;
  }
  // 省略部分内容
}
// 省略部分内容
const newBitmap =  bitmap | bit;

上面的 BitmapIndexedNode 对象的 bitmap 则是通过将所有字段的 bit 做或操作得到的，从而实现 bitmap 算法。再加上 popCount 操作，毕竟数据是以数组的形式存储在 BitmapIndexedNode 里面，而 BitmapIndexedNode 里面数组的长度为 16，所以不是字段 key 的 bit 是第几位就在第几位数组上，而是要同通过 popCount 来获得当前 bit 前面有多少个 1，也就是有多少个字段，从而得到对应的位置。

BitmapIndexedNode 里面最大数是 16，也就是在 32 个哈希值中选取 16 个不同的哈希值，为什么是 16 不是 17/18 个之类的呢？BitmapIndexedNode 这里其实起到一个压缩的作用，因为哈希分布不可能是从小开始出现，而是随机的，若是给随机的哈希，配置到同样的位置，就会造成很多内存的浪费，比如，对于 key = '0'，其计算出来的 bit 因该是 28，若前面没有什么数据，不可能就让数据的第 28 位存储 key = 0 的数据的，这只是浪费，它理所应当排在第一个位置，这样就有效的压缩了树内存大小。

如果这个时候字段数持续增多，如果得到的新的 Bit 和存在的值是重复的，比如字段 Aa 和 11 的哈希值 31 （哈希函数在下方）的模都是 0，但是却有完全不同的哈希值，前者是 2112 后者是 1568，于是下角标为 0 的元素就升级为 BitmapIndexedNode 对象，这个 BitmapIndexedNode 对象的 bitmap 则由 Aa 和 11 的下一个高 5 位的哈希值，再位移，做或操作来得到。

当字段持续增加，而对应的低位哈希量已经超过 16 个的时候，就会升级为 HashArrayMapNode 对象，可以没有 16 位的限制，根据取模 31，则最多有 32 的长度。通过每次读 5 bit 的方式，来实现读写。

哈希计算如下：

function hashString(string) {
  let hashed = 0;
  for (let ii = 0; ii < string.length; ii++) {
    hashed = (31 * hashed + string.charCodeAt(ii)) | 0;
  }
  return smi(hashed);
}
function smi(i32) {
  return ((i32 >>> 1) & 0x40000000) | (i32 & 0xbfffffff);
}

上面的 hashString 和 jvm 里面的 string 类型的 hashCode 计算是一致的。都是乘以 31，看这里又有 31，这个必然是 31 可以被计算机转换为位移操作啦，当然也有统计结果下性能好的原因。

但是这样的哈希值，以及取 31 的模的方式会出现另外一个问题。hashString 确实可以计算出一个独立的哈希值，只是独立的哈希值，却不意味着不会发生重复碰撞的情况，比如 key = 'Aa' key = 'BB'，其哈希值是完全一样的，这个时候就会启动 HashCollisionNode 对象，将相同的哈希值的对象都放在同一个 HashCollisionNode 里面，而这里面就是简单的线性读写数组了，没有之前的 Bitmapped 操作，毕竟一次性不可能有太多相同哈希值的键名出现。

另外 immutable.js 里面认为 splice 操作是昂贵，基本上都写了自己的 api 来替换掉 splice

总结

难得有一次学习数据结构的机会，大学好像就没有学过相关知识吧，这个月才开始看《算法》一书，很是感动，第一次如此接触到二叉树，红黑树，觉得前端，原来不止有三大框架，不止有三大框架的 API，生态圈里的的组件，nodejs，更有数据结构的存在，希望还是能更多的接触。

参考

1. Anjana Vakil: Immutable data structures for functional JS | JSConf EU 2017，非常好的视频，通俗易懂；
2. RRB-Trees: Efficient Immutable Vectors，很无聊的论文，语法怪怪的，但是键 RRB-Trees 的都会说到这篇文章，翻译了一半不到。
3. Striving to Make Things Simple and Fast - Phil Bagwell，Clojure 的一个讲座，说的挺好的，就是没有怎么听懂，和上面的论文比较搭。
4. Immutable 结构共享是如何实现的，很优秀的讨论。
5. Use RRB-Tree in Vector，immutable.js 里面对 RRB-Tree 的讨论。