40行代码实现React核心Diff算法
SegmentFault
共 6771字，需浏览 14分钟
·
2022-04-19 10:37
作者：卡颂
简介：《React技术揭秘》作者
来源：SegmentFault 思否社区
大家好，我卡颂。
凡是依赖虚拟DOM的框架，都需要比较前后节点变化的Diff算法。
网上有大量讲解Diff算法逻辑的文章。然而，即使作者语言再精练，再图文并茂，相信大部分同学看完用不了多久就忘了。
今天，我们换一种一劳永逸的学习方法 —— 实现React的核心Diff算法。
不难，只有40行代码。不信？往下看。
Diff算法的设计思路
试想，Diff算法需要考虑多少种情况呢？大体分三种，分别是：
节点属性变化，比如：
// 更新前
<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>
节点增删，比如：
// 更新前
<ul>
<li key="0">0</li>
<li key="1">1</li>
<li key="2">2</li>
</ul>
// 更新后 情况1 —— 新增节点
<ul>
<li key="0">0</li>
<li key="1">1</li>
<li key="2">2</li>
<li key="3">3</li>
</ul>
// 更新后 情况2 —— 删除节点
<ul>
<li key="0">0</li>
<li key="1">1</li>
</ul>
节点移动，比如：
// 更新前
<ul>
<li key="0">0</li>
<li key="1">1</li>
</ul>
// 更新后
<ul>
<li key="1">1</li>
<li key="0">0</li>
</ul>
首先判断当前节点属于哪种情况 如果是增删，执行增删逻辑 如果是属性变化，执行属性变化逻辑 如果是移动，执行移动逻辑
Demo介绍
type Flag = 'Placement' | 'Deletion';
interface Node {
key: string;
flag?: Flag;
index?: number;
}
Placement对于新生成的node，代表对应DOM需要插入到页面中。对于已有的node，代表对应DOM需要在页面中移动
Deletion代表node对应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算法实现
遍历前的准备工作 遍历after 遍历后的收尾工作
function diff(before: NodeList, after: NodeList): NodeList {
const result: NodeList = [];
// ...遍历前的准备工作
for (let i = 0; i < after.length; i++) {
// ...核心遍历逻辑
}
// ...遍历后的收尾工作
return result;
}
遍历前的准备工作
// 保存结果
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'}
]
不移动 移动
// 遍历到的最后一个可复用node在before中的index
let lastPlacedIndex = 0;
nodeBefore.index < lastPlacedIndex
nodeBefore.index >= lastPlacedIndex
// 遍历到的最后一个可复用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) {
// 存在可复用node
// 从map中剔除该 可复用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 {
// 不存在可复用node，这是一个新节点
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);
});
最后
评论