40行代碼實現(xiàn)React核心Diff算法
作者：卡頌
簡介：《React技術(shù)揭秘》作者
來源：SegmentFault 思否社區(qū)
大家好，我卡頌。
凡是依賴虛擬DOM的框架，都需要比較前后節(jié)點變化的Diff算法。
網(wǎng)上有大量講解Diff算法邏輯的文章。然而，即使作者語言再精練，再圖文并茂，相信大部分同學(xué)看完用不了多久就忘了。
今天，我們換一種一勞永逸的學(xué)習(xí)方法 —— 實現(xiàn)React的核心Diff算法。
不難，只有40行代碼。不信？往下看。
Diff算法的設(shè)計思路
試想，Diff算法需要考慮多少種情況呢？大體分三種，分別是：
節(jié)點屬性變化，比如：
// 更新前
<ul>
<li key="0" className="before">0</li>
<li key="1">1</li>
</ul>
// 更新后
<ul>
<li key="0" className="after">0</li>
<li key="1">1</li>
</ul>
節(jié)點增刪，比如：
// 更新前
<ul>
<li key="0">0</li>
<li key="1">1</li>
<li key="2">2</li>
</ul>
// 更新后 情況1 —— 新增節(jié)點
<ul>
<li key="0">0</li>
<li key="1">1</li>
<li key="2">2</li>
<li key="3">3</li>
</ul>
// 更新后 情況2 —— 刪除節(jié)點
<ul>
<li key="0">0</li>
<li key="1">1</li>
</ul>
節(jié)點移動，比如：
// 更新前
<ul>
<li key="0">0</li>
<li key="1">1</li>
</ul>
// 更新后
<ul>
<li key="1">1</li>
<li key="0">0</li>
</ul>
首先判斷當(dāng)前節(jié)點屬于哪種情況 如果是增刪，執(zhí)行增刪邏輯 如果是屬性變化，執(zhí)行屬性變化邏輯 如果是移動，執(zhí)行移動邏輯
Demo介紹
type Flag = 'Placement' | 'Deletion';
interface Node {
key: string;
flag?: Flag;
index?: number;
}
Placement對于新生成的node，代表對應(yīng)DOM需要插入到頁面中。對于已有的node，代表對應(yīng)DOM需要在頁面中移動
Deletion代表node對應(yīng)DOM需要從頁面中刪除
type NodeList = Node[];
function diff(before: NodeList, after: NodeList): NodeList {
// ...代碼
}
// 更新前
const before = [
{key: 'a'}
]
// 更新后
const after = [
{key: 'd'}
]
// diff(before, after) 輸出
[
{key: "d", flag: "Placement"},
{key: "a", flag: "Deletion"}
]
// 更新前
const before = [
{key: 'a'},
{key: 'b'},
{key: 'c'},
]
// 更新后
const after = [
{key: 'c'},
{key: 'b'},
{key: 'a'}
]
// diff(before, after) 輸出
[
{key: "b", flag: "Placement"},
{key: "a", flag: "Placement"}
]
Diff算法實現(xiàn)
遍歷前的準備工作 遍歷after 遍歷后的收尾工作
function diff(before: NodeList, after: NodeList): NodeList {
const result: NodeList = [];
// ...遍歷前的準備工作
for (let i = 0; i < after.length; i++) {
// ...核心遍歷邏輯
}
// ...遍歷后的收尾工作
return result;
}
遍歷前的準備工作
// 保存結(jié)果
const result: NodeList = [];
// 將before保存在map中
const beforeMap = new Map<string, Node>();
before.forEach((node, i) => {
node.index = i;
beforeMap.set(node.key, node);
})
遍歷after
// 更新前
const before = [
{key: 'a'},
{key: 'b'}
]
// 更新后
const after = [
{key: 'b'}
]
不移動 移動
// 遍歷到的最后一個可復(fù)用node在before中的index
let lastPlacedIndex = 0;
nodeBefore.index < lastPlacedIndex
nodeBefore.index >= lastPlacedIndex
// 遍歷到的最后一個可復(fù)用node在before中的index
let lastPlacedIndex = 0;
for (let i = 0; i < after.length; i++) {
const afterNode = after[i];
afterNode.index = i;
const beforeNode = beforeMap.get(afterNode.key);
if (beforeNode) {
// 存在可復(fù)用node
// 從map中剔除該 可復(fù)用node
beforeMap.delete(beforeNode.key);
const oldIndex = beforeNode.index as number;
// 核心判斷邏輯
if (oldIndex < lastPlacedIndex) {
// 移動
afterNode.flag = 'Placement';
result.push(afterNode);
continue;
} else {
// 不移動
lastPlacedIndex = oldIndex;
}
} else {
// 不存在可復(fù)用node，這是一個新節(jié)點
afterNode.flag = 'Placement';
result.push(afterNode);
}
遍歷后的收尾工作
// 更新前
const before = [
{key: 'a'},
{key: 'b'}
]
// 更新后
const after = [
{key: 'b'}
]
beforeMap.forEach(node => {
node.flag = 'Deletion';
result.push(node);
});
最后
評論
圖片
表情