本篇内容主要讲解“React怎么实现核心Diff算法”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“React怎么实现核心Diff算法”吧!
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中的indexlet 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中的indexlet 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);});
到此,相信大家对“React怎么实现核心Diff算法”有了更深的了解,不妨来实际操作一番吧!这里是编程网网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!