本篇文章给大家带来的内容是关于immutable.js源码之list 类型的详细解析（附示例），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。
一、存储图解
我以下面这段代码为例子，画出这个list的存储结构：
let mylist = [];for(let i=0;i<1100;i++) { mylist[i] = i;}debugger;//可以在这里打个断点调试let immutablelist = immutable.list(mylist)debugger;console.log(immutablelist.set(1000, 'remm'));debugger;console.log(immutablelist.get(1000));
二、vector trie 的构建过程
我们用上面的代码为例子一步一步的解析。首先是把原生的list转换为inmutable的list 类型：
export class list extends indexedcollection { // @pragma construction constructor(value) { // 此时的value就是上面的mylist数组 const empty = emptylist(); if (value === null || value === undefined) {//判断是否为空 return empty; } if (islist(value)) {//判断是否已经是imutable的list类型 return value; } const iter = indexedcollection(value);//序列化数组 const size = iter.size; if (size === 0) { return empty; } assertnotinfinite(size); if (size > 0 && size < size) { // 判断size是否超过32 return makelist(0, size, shift, null, new vnode(iter.toarray())); } return empty.withmutations(list => {      list.setsize(size);      iter.foreach((v, i) => list.set(i, v));    });  }  。。。。。。}
首先会创建一个空的list
let empty_list;export function emptylist() {  return empty_list || (empty_list = makelist(0, 0, shift));}
shift的值为5，export const shift = 5; // resulted in best performance after ______?
再继续看makelist，可以清晰看到 list 的主要部分：
function makelist(origin, capacity, level, root, tail, ownerid, hash) {  const list = object.create(listprototype);  list.size = capacity - origin;// 数组的长度  list._origin = origin;// 数组的起始位置 一般是0  list._capacity = capacity;// 数组容量 等于 size  list._level = level;//树的深度，为0时是叶子结点。默认值是5，存储指数部分，用于方便位运算,增加一个深度，level值+5  list._root = root;// trie树实现  list._tail = tail;// 32个为一组，存放最后剩余的数据 其实就是 %32  list.__ownerid = ownerid;  list.__hash = hash;  list.__altered = false;  return list;}
将传入的数据序列化
// arrayseqiter = {size: 数组的length,_array: 传入数组的引用}
判断size是否超过32，size > 0 && size < size 这里 size ： export const size = 1 << shift;即 32。若没有超过32，所有数据都放在_tail中。
_root 和 _tail 里面的数据又有以下结构：
// @vnode classconstructor(array, ownerid) { this.array = array; this.ownerid = ownerid;}
可以这样调试查看：
let mylist = [];for(let i=0;i<30;i++) { mylist[i] = i;}debugger;//可以在这里打个断点调试console.log(immutable.list(mylist));
size如果超过32
return empty.withmutations(list => {    list.setsize(size);//构建树的结构 主要是计算出树的深度    iter.foreach((v, i) => list.set(i, v));//填充好数据});
export function withmutations(fn) {  const mutable = this.asmutable();  fn(mutable);  return mutable.wasaltered() ? mutable.__ensureowner(this.__ownerid) : this;}
list.setsize(size)中有一个重要的方法setlistbounds,下面我们主要看这个方法如何构建这颗树
这个方法最主要的作用是 确定 list的level
function setlistbounds(list, begin, end) {  ......    const newtailoffset = gettailoffset(newcapacity);  // new size might need creating a higher root.  // 是否需要增加数的深度 把 1 左移 newlevel + shift 位 相当于 1 * 2 ^ (newlevel + shift)  // 以 size为 1100 为例子 newtailoffset的值为1088 第一次 1088 > 2 ^ 10 树增加一层深度  // 第二次 1088 < 2 ^ 15 跳出循环 newlevel = 10 while (newtailoffset >= 1 << (newlevel + shift)) { newroot = new vnode( newroot && newroot.array.length ? [newroot] : [], owner ); newlevel += shift; } ......}
function gettailoffset(size) { // (1100 - 1) / 2^5 % 2^5 = 1088 return size < size ? 0 : (((size - 1) >>> shift) << shift);}
经过 list.setsize(size);构建好的结构
三、set 方法
listiter.foreach((v, i) => list.set(i, v));这里是将iter中的_array填充到这里主要还是看看set方法如何设置数据
set(index, value) {    return updatelist(this, index, value);}
function updatelist(list, index, value) {  ......  if (index >= gettailoffset(list._capacity)) {    newtail = updatevnode(newtail, list.__ownerid, 0, index, value, didalter);  } else {    newroot = updatevnode(      newroot,      list.__ownerid,      list._level,      index,      value,      didalter    );  }  ......}
function updatevnode(node, ownerid, level, index, value, didalter) {  // 根据 index 和 level 计算 数据set的位置在哪  const idx = (index >>> level) & mask;  // 利用递归 一步一步的寻找位置 直到找到最终的位置  if (level > 0) {    const lowernode = node && node.array[idx];    const newlowernode = updatevnode(      lowernode,      ownerid,      level - shift,      index,      value,      didalter    );    ......    // 把node节点的array复制一份生成一个新的节点newnode editablevnode函数见下面源码    newnode = editablevnode(node, ownerid);    // 回溯阶段将 子节点的引用赋值给自己    newnode.array[idx] = newlowernode;    return newnode;  }  ......  newnode = editablevnode(node, ownerid);  // 当递归到叶子节点 也就是level <= 0 将值放到这个位置 newnode.array[idx] = value; ...... return newnode;}
function editablevnode(node, ownerid) { if (ownerid && node && ownerid === node.ownerid) { return node; } return new vnode(node ? node.array.slice() : [], ownerid);}
下面我们看看运行了一次set(0,0)的结果
整个结构构建完之后
下面我们接着看刚刚我们构建的list set(1000, 'remm'),其实所有的set的源码上面已经解析过了，我们再来温习一下。
调用上面的set方法，index=1000,value='remm'。调用updatelist，继而调用updatevnode。通过const idx = (index >>> level) & mask;计算要寻找的节点的位置(在这个例子中，idx的值依次是0->31->8)。 不断的递归查找，当 level <= 0 到达递归的终止条件，其实就是达到树的叶子节点，此时通过newnode = editablevnode(node, ownerid);创建一个新的节点，然后 newnode.array[8] = 'remm'。接着就是开始回溯，在回溯阶段，自己把自己克隆一个，newnode = editablevnode(node, ownerid);,注意这里克隆的只是引用，所以不是深拷贝。然后再将idx位置的更新了的子节点重新赋值，newnode.array[idx] = newlowernode;,这样沿着路径一直返回，更新路径上的每个节点，最后得到一个新的根节点。
更新后的list:
四、get 方法
了解完上面的list构建和set，我们再来看 immutablelist.get(1000) 源码就是小菜一碟了。
get(index, notsetvalue) { index = wrapindex(this, index); if (index >= 0 && index < this.size) { index += this._origin; const node = listnodefor(this, index); return node && node.array[index & mask]; } return notsetvalue; }
function listnodefor(list, rawindex) { if (rawindex >= gettailoffset(list._capacity)) {    return list._tail;  }  if (rawindex < 1 << (list._level + shift)) { let node = list._root; let level = list._level; while (node && level > 0) {      // 循环查找节点所在位置      node = node.array[(rawindex >>> level) & mask];      level -= shift;    }    return node;  }}
五、tire 树 的优点
来一张从网上盗来的图：
这种树的数据结构（tire 树），保证其拷贝引用的次数降到了最低，就是通过极端的方式，大大降低拷贝数量，一个拥有100万条属性的对象，浅拷贝需要赋值 99.9999万次，而在 tire 树中，根据其访问的深度，只有一个层级只需要拷贝 31 次，这个数字不随着对象属性的增加而增大。而随着层级的深入，会线性增加拷贝数量，但由于对象访问深度不会特别高，10 层已经几乎见不到了，因此最多拷贝300次，速度还是非常快的。
我上面所解析的情况有 构建、修改、查询。其实还有 添加 和 删除。
以上就是immutable.js源码之list 类型的详细解析（附示例）的详细内容。