40行代码实现React核心Diff算法
大家好,我卡颂。
凡是依赖虚拟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>
该如何设计Diff算法呢?考虑到只有以上三种情况,一种常见的设计思路是:
- 首先判断当前节点属于哪种情况。
- 如果是增删,执行增删逻辑。
- 如果是属性变化,执行属性变化逻辑。
- 如果是移动,执行移动逻辑。
按这个方案,其实有个隐含的前提—— 「不同操作的优先级是相同的」。但在日常开发中,「节点移动」发生较少,所以Diff算法会优先判断其他情况。
基于这个理念,主流框架(React、Vue)的Diff算法都会经历多轮遍历,先处理「常见情况」,后处理「不常见情况」。
所以,这就要求「处理不常见情况的算法」需要能给各种边界case兜底。
换句话说,完全可以仅使用「处理不常见情况的算法」完成Diff操作。主流框架之所以没这么做是为了性能考虑。
本文会砍掉「处理常见情况的算法」,保留「处理不常见情况的算法」。
这样,只需要40行代码就能实现Diff的核心逻辑。
Demo介绍
首先,我们定义虚拟DOM节点的数据结构:
type Flag = 'Placement' | 'Deletion';
interface Node {
key: string;
flag?: Flag;
index?: number;
}
key是node的唯一标识,用于将节点在变化前、变化后关联上。
flag代表node经过Diff后,需要对相应的真实DOM执行的操作,其中:
- Placement对于新生成的node,代表对应DOM需要插入到页面中。对于已有的node,代表对应DOM需要在页面中移动。
- Deletion代表node对应DOM需要从页面中删除。
index代表该node在同级node中的索引位置。
注:本Demo仅实现「为node标记flag」,没有实现「根据flag执行DOM操作」。
我们希望实现的diff方法,接收更新前与更新后的NodeList,为他们标记flag:
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"}
]
{key: "d", flag: "Placement"}代表d对应DOM需要插入页面。
{key: "a", flag: "Deletion"}代表a对应DOM需要被删除。
执行后的结果就是:页面中的a变为d。
再比如:
// 更新前
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"}
]
由于b之前已经存在,{key: "b", flag: "Placement"}代表b对应DOM需要向后移动(对应parentNode.appendChild方法)。abc经过该操作后变为acb。
由于a之前已经存在,{key: "a", flag: "Placement"}代表a对应DOM需要向后移动。acb经过该操作后变为cba。
执行后的结果就是:页面中的abc变为cba。
Diff算法实现
核心逻辑包括三步:
- 遍历前的准备工作。
- 遍历after。
- 遍历后的收尾工作。
function diff(before: NodeList, after: NodeList): NodeList {
const result: NodeList = [];
// ...遍历前的准备工作
for (let i = 0; i < after.length; i++) {
// ...核心遍历逻辑
}
// ...遍历后的收尾工作
return result;
}
遍历前的准备工作
我们将before中每个node保存在以node.key为key,node为value的Map中。
这样,以O(1)复杂度就能通过key找到before中对应node:
// 保存结果
const result: NodeList = [];
// 将before保存在map中
const beforeMap = new Map<string, Node>();
before.forEach((node, i) => {
node.index = i;
beforeMap.set(node.key, node);
})
遍历after
当遍历after时,如果一个node同时存在于before与after(key相同),我们称这个node可复用。
比如,对于如下例子,b是可复用的:
// 更新前
const before = [
{key: 'a'},
{key: 'b'}
]
// 更新后
const after = [
{key: 'b'}
]
对于可复用的node,本次更新一定属于以下两种情况之一:
- 不移动。
- 移动。
如何判断可复用的node是否移动呢?
我们用lastPlacedIndex变量保存「遍历到的最后一个可复用node在before中的index」:
// 遍历到的最后一个可复用node在before中的index
let lastPlacedIndex = 0;
当遍历after时,每轮遍历到的node,一定是当前遍历到的所有node中最靠右的那个。
如果这个node是可复用的node,那么nodeBefore与lastPlacedIndex存在两种关系:
注:nodeBefore代表该可复用的node在before中的对应node。
- nodeBefore.index < lastPlacedIndex。
代表更新前该node在lastPlacedIndex对应node左边。
而更新后该node不在lastPlacedIndex对应node左边(因为他是「当前遍历到的所有node中最靠右的那个」)。
这就代表该node向右移动了,需要标记Placement。
- nodeBefore.index >= lastPlacedIndex。
该node在原地,不需要移动。
// 遍历到的最后一个可复用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);
}
遍历后的收尾工作
经过遍历,如果beforeMap中还剩下node,代表这些node没法复用,需要被标记删除。
比如如下情况,遍历完after后,beforeMap中还剩下{key: 'a'}:
// 更新前
const before = [
{key: 'a'},
{key: 'b'}
]
// 更新后
const after = [
{key: 'b'}
]
这意味着a需要被标记删除。
所以,最后还需要加入标记删除的逻辑:
beforeMap.forEach(node => {
node.flag = 'Deletion';
result.push(node);
});
完整代码见在线Demo地址[1]。
总结
整个Diff算法的难点在于lastPlacedIndex相关逻辑。
跟着Demo多调试几遍,相信你能明白其中原理。
参考资料
[1]在线Demo地址:
https://codesandbox.io/s/naughty-matan-6fq7n6?file=/src/diff.ts。
相关文章
- Jgit的使用笔记
- 利用Github Action实现Tornadofx/JavaFx打包
- 叹息!GitHub Trending 即将成为历史!
- 微软软了?开源社区讨论炸锅,GitHub CEO 亲自来答
- GitHub Trending 列表频现重复项,前后端都没去重?
- Photoshop Elements 2021版本软件安装教程(mac+windows全版本都有)
- (ps全版本)Photoshop 2020的安装与破解教程(mac+windows全版本都有)
- (ps全版本)Photoshop cc2018的安装与破解教程(mac+windows全版本,包括2023
- 环境搭建:Oracle GoldenGate 大数据迁移到 Redshift/Flat file/Flume/Kafka测试流程
- 每个开发人员都要掌握的:最小 Linux 基础课
- 来撸羊毛了!Windows 环境下 Hexo 博客搭建,并部署到 GitHub Pages
- 超实用!手把手入门 MongoDB:这些坑点请一定远离
- 【GitHub日报】22-10-09 zustand、neovim、webtorrent、express 等4款App今日上新
- 【GitHub日报】22-10-10 brew、minio、vite、seaweedfs、dbeaver 等8款App今日上新
- 【GitHub日报】22-10-11 cobra、grafana、vue、ToolJet、redwood 等13款App今日上新
- Photoshop 2018 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2017 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2020 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2023 资源免费下载(mac+windows全版本都有,包括最新的2023)
- 最新版本Photoshop CC2018软件安装教程(mac+windows全版本都有,包括2023