這篇文章帶給大家的內容是關於Immutable.js源碼之List 類型的詳細解析（附範例），有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。
一、儲存圖解
我以下面這段程式碼為例子，畫出這個List的儲存結構：
let myList = [];
for(let i=0;i<p><span class="img-wrap"><img src="https://img.php.cn//upload/image/772/741/819/1543214651133724.png" title="1543214651133724.png" alt="Immutable.js源碼之List 類型的詳細解析（附範例）"></span></p><p><strong>二、vector trie 的建置過程</strong></p><p>我們用上面的程式碼為範例一步一步的解析。首先是把原生的list轉換為inmutable的list 類型：</p><pre class="brush:php;toolbar:false">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;
}將傳入的資料序列化
// ArraySeq
iter = {
size: 数组的length,
_array: 传入数组的引用
}判斷size是否超過32，size > 0 && size
_root 和_tail 裡面的資料又有以下結構：
// @VNode class
constructor(array, ownerID) {
this.array = array;
this.ownerID = ownerID;
}可以這樣調試查看：
let myList = [];
for(let i=0;i<p>size如果超過32</p><pre class="brush:php;toolbar:false">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 <pre class="brush:php;toolbar:false">function getTailOffset(size) {
// (1100 - 1) / 2^5 % 2^5 = 1088
return size >> SHIFT) <p>經過list. setSize(size);建構好的結構</p><p><span class="img-wrap"><img src="https://img.php.cn//upload/image/732/311/566/1543214714320046.png" title="1543214714320046.png" alt="Immutable.js源碼之List 類型的詳細解析（附範例）"></span></p><p><strong>#三、set 方法</strong></p><p>listiter.forEach( (v, i) => list.set(i, v));這裡是將iter中的_array填入</p><p>這裡主要還是看看set方法如何設定資料</p><pre class="brush:php;toolbar:false">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 <pre class="brush:php;toolbar:false">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 <pre class="brush:php;toolbar:false">function listNodeFor(list, rawIndex) {
if (rawIndex >= getTailOffset(list._capacity)) {
return list._tail;
}
if (rawIndex 0) {
// 循环查找节点所在位置
node = node.array[(rawIndex >>> level) & MASK];
level -= SHIFT;
}
return node;
}
}五、tire 樹的優點
來一張從網路上盜來的圖：
這種樹的資料結構（tire 樹），保證其拷貝引用的次數降到了最低，就是透過極端的方式，大大降低拷貝數量，一個擁有100萬條屬性的對象，淺拷貝需要賦值99.9999萬次，而在tire 樹中，根據其訪問的深度，只有一個層級只需要拷貝31 次，這個數字不隨著對象屬性的增加而增大。而隨著層級的深入，會線性增加拷貝數量，但由於物件存取深度不會特別高，10 層已經幾乎見不到了，因此最多拷貝300次，速度還是非常快的。
我上面所解析的情況有 建構、修改、查詢。其實還有 新增 和 刪除。
以上是Immutable.js源碼之List 類型的詳細解析（附範例）的詳細內容。更多資訊請關注PHP中文網其他相關文章！
