一、存储图解
我以下面这段代码为例子，画出这个 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;
}
将传入的数据序列化
// ArraySeq
iter = {
size: 数组的 length,
_array: 传入数组的引用
}
判断 size 是否超过 32，size > 0 && size < SIZE 这里 SIZE：export const SIZE = 1 << SHIFT; 即 32。若没有超过 32，所有数据都放在_tail 中。
_root 和 _tail 里面的数据又有以下结构：
// @VNode class
constructor(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 方法
iter.forEach((v, i) => list.set(i, v)); 这里是将 iter 中的_array 填充到 list
这里主要还是看看 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 部分参考了 Clojure 中的 PersistentVector 的实现方式。所以可以看看下面这篇文章：
https://hypirion.com/musings/…