摘要：一向量字典树字典树，一种用空间换取时间的树形数据结构，主要特点是利用字符串的公共前缀来挺升查询性能。还有最终的数组表示的真实存储的键值，存储了，存储了。这其中还有一种节点进行了冲突的处理。
本文受深入探究Immutable.js的实现机制这篇文章启发，结合自己对Map源码的解读，谈谈我对immutable-js中map数据结构的理解，若有不正确的地方，欢迎指正。
一、Vector Trie 向量字典树Trie 字典树，一种用空间换取时间的树形数据结构，主要特点是利用字符串的公共前缀来挺升查询性能。比如一组字符串 ["abc","ab","bd","dda"] 它的字典树结构如下：
红色节点代表按查找路径下来可以组成一个单词，这样在查找是否存在"abc"时，每个字符逐个进行对比，时间复杂度为O(len) = 3，len为要查找的字符串的长度，而按照一般逐个对比的方式，时间复杂度为O(lenxn) = 4x3 = 12，n为字符串的个数，显然字典树的方式效率更高。
Vector Trie 是在 Trie 的基础上实现了以向量数组的形式进行数据分组存储，每一个被存储的值所对应的key都映射为数组的下标。
比如这样的数据结构 {‘000’: ‘banana’, ‘001’: ‘grape’, ‘010’: ‘lemon’, ‘011’: ‘orange’, ‘100’: ‘apple’}，每个key映射为数组的索引值，这样生成简单的两位数组的Vector Trie是这样子的：
我们可以将key映射为数字，然后再对应到数组中，比如一个key为 8899 映射为 5 个长度（即5进制）的数字是241044, 那么他要生成深度为6的数据结构，每一层的索引就是每位的数字，这样对每个索引都要进行数学计算，而immutable-js中使用了效率更高的位运算来生成索引，将数据进行分区。比如，8899 映射为二进制位：10001011000011，1代表此位有数据，0代表没有数据。这样如果每层的数组长度是7，第一层的存储情况可以直接位运算 8899 >> 7 得到 1000101（69），第二层 8899 & 127 (Math.pow(2, 7) - 1) 得到 1000011 (67)。
位运算可以很方便得到每位是否存储值的情况，计算速度也要比数学运算快很多。
Map中有主要的这几种节点类型：ArrayMapNode，ValueNode，BitmapIndexedNode，HashArrayMapNode。在每次set时，节点类型会在这几个之间转换。还有最终的entry数组表示的真实存储的键值，entry[0]存储了key，entry[1]存储了value。ValueNode可以看作叶子节点，存储了entry值。
首先，如果存储的键值对不大于8，那么生成entry直接存储在ArrayMapNode数组中，ArrayMapNode作为_root节点返回，再继续存储值，会调用_root的update方法，也就是ArrayMapNode的update方法，如果存储的数量大于8，会创建ValueNode，并调用它的update方法，在这里会进行一个mergeIntoNode操作，即如果有相同索引到此处的节点，那么要进行一次合并操作，合并后会生成BitmapIndexedNode。
BitmapIndexedNode是经过压缩处理的层，最多存储16个长度的内容，bitmap属性就表示了这个层的存储情况。比如值为1935909891它的存储情况是"1110011011000111010010000000011"，最多32位，不足的话，相当于高位补0。去除0后，1的数量就是这层实际存储的个数。为什么说它经过压缩呢，因为这个bitmap表示了这层的存储情况，是长度为32的数组的每位的存储情况，但这层实际存储的数量最多只是它的一半，为了减少空间占用和查找效率，就没必要记录不存储的位了，那就有疑问了，那直接往数组里存储就行了，要bitmap有什么用，我们继续往下看，再新增数据，使BitmapIndexedNode这层的数据量超过16，此时就会进行一次转换expandNodes展开节点操作，将这层的结构转为HashArrayMapNode，这是一个长度为32的数组，此时，bitmap记录的位存储情况就是把之前的数据一个一个放到32位数组里对应的地方，没有值的地方就是undefined。
再往后如果HashArrayMapNode的存储数量降低小于16了，又会进行packNodes转为BitmapIndexedNode。
Map中，每次set都将对应的层的节点进行类型转换，updateNode这个方法会将受影响的节点生成新的结构返回，不影响其它层的节点，这就实现了结构共享。
这其中还有一种节点HashCollisionNode进行了hash冲突的处理。
在Map中为了找到数据存储位置，使用了很多的位操作，现在对一组map数据进行分析，看看它是如何进行计算的。这里用到的常量，
31 和 5 在TrieUtils.js文件中:
export const SHIFT = 5; // Resulted in best performance after ______? export const SIZE = 1 << SHIFT; export const MASK = SIZE - 1;
我们生成500个长度的map数据结构，使它包含BitmapIndexedNode，HashArrayMapNode这几种结构：
比如我们选取"KEY6787241"这个节点进行分析，它的hash是这样计算出来的：
我们根据这个hash计算出它在第一层即_root下面的位置：
看到它确实放在了对应位置下的HashArrayMapNode中，那在HashArrayMapNode中12的位置是怎么算出来的呢，我们执行这样的操作：
然后来看看这个bitmap 524352:
可以看出它只有两位保存了数据。为了支持不定长的宽度，位置的计算是从后往前算的，那么，存储数据的情况就是倒数第7位，相当于index为6和倒数第20位，相当于index为19，那么我们再计算下hash：785947024和-137605744是否在对应位置：
每深入一层，将位右移动5位，并且与上31来算出对应位置。
那为啥是 31 和 5 呢，在代码中可以看到：
就是上面对应的两个常量。
785947024的二进制是"101110110110001001100110010000"，31的二进制是"000000000000000000000000011111"，&，位与操作后意思就是留下最后的5位，"10000" 16。再位移5位并位与31后就是，"01100" 12。2 ^ 5 = 32，所以5位二进制就能保存32个数，也就能满足我们每一层最多32个的情况。
那32是怎么来的呢，这里统计了位分区的查找更新效率情况：
可以看到64位查询速度最快，8位更新速度最快。immutable-js选择32是因为实际使用中，查询的频率要比更新多，所以选择了查询速度较优，更新速度不是最差的32。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/98437.html
摘要：数据结构类型扩展相对之类的强类型语言，有一点很大的区别就是，数据结构只有与，并且都是动态可变的，而有等数据结构。所以，为了能在中也使用这些数据结构，就应运而生。扩充了中的不可变集合，即一旦创建就不能改变的数据类型。 js 数据结构类型扩展：immutable-js 相对 java、.net 之类的强类型语言，js 有一点很大的区别就是，数据结构只有 array 与 object，并且都...
摘要：这篇文章是一些操作的整理目前只有基本的操作文档请查看使用过程中遇到的写法我会不会增加在后边当中不可变数据有点不适应需要借鉴一些中的内容更新六月份到十月份我们完成了不可变数据的重构配合简聊的巨大的单一可以整理出来一些常用的方法示例代码用的是 这篇文章是 immutable-js 一些操作的整理, 目前只有基本的操作:文档请查看: http://facebook.github.io/imm...
摘要：例如维护一份在内部，来判断是否有变化，下面这个例子就是一个构造函数，如果将它的实例传入对象作为第一个参数，就能够后面的处理对象中使用其中的方法上面这个构造函数相比源代码省略了很多判断的部分。 showImg(https://segmentfault.com/img/bV27Dy?w=1400&h=544); 博客链接：下一代状态管理工具 immer 简介及源码解析 JS 里面的变量类...
摘要：张伟输出结果这样就实现了在源数据的基础上更改了值并且输出一个与之地址完全不同数组。 本来想将有关于immutability-helper的博文放在一起学React系列博文中，但是考虑到该插件不仅仅在React中实用到，所以就单独拿出来分两期写。 发现问题 immutability意为不变，不变性，永恒性。至于该插件能做什么，我想它的作者对它的标注已经很明确了mutate a copy ...
阅读 1905·2021-11-22 14:44
阅读 1671·2021-11-02 14:46
阅读 3657·2021-10-13 09:40
阅读 2599·2021-09-07 09:58
阅读 1585·2021-09-03 10:28
阅读 1658·2019-08-29 15:30
阅读 976·2019-08-29 15:28
阅读 1468·2019-08-26 12:20
