Immutable.js源码之List 类型的详细解析（附示例）

本篇文章给大家带来的内容是关于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  {      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

_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 = 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 >> 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

更新后的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 < 0) {      // 循环查找节点所在位置      node = node.array[(rawIndex >>> level) & MASK];      level -= SHIFT;    }    return node;  }}

登录后复制

五、tire 树 的优点

来一张从网上盗来的图：

这种树的数据结构（tire 树），保证其拷贝引用的次数降到了最低，就是通过极端的方式，大大降低拷贝数量，一个拥有100万条属性的对象，浅拷贝需要赋值 99.9999万次，而在 tire 树中，根据其访问的深度，只有一个层级只需要拷贝 31 次，这个数字不随着对象属性的增加而增大。而随着层级的深入，会线性增加拷贝数量，但由于对象访问深度不会特别高，10 层已经几乎见不到了，因此最多拷贝300次，速度还是非常快的。

我上面所解析的情况有 构建、修改、查询。其实还有 添加 和 删除。

以上就是Immutable.js源码之List 类型的详细解析（附示例）的详细内容，更多请关注【创想鸟】其它相关文章！