大家好，我是Kason。任何依赖虚拟DOM的框架都需要一个Diff算法来“比较前后节点的变化”。网上有大量的文章讲解Diff算法的逻辑。然而，无论作者的语言多么简洁，图文多么丰富，相信大多数同学看完后都会忘乎所以。今天，我们换一种一劳永逸的学习方式——实现React的核心Diff算法。不难，只有40行代码。不相信我？继续阅读。Diff算法的设计思路试想一下，Diff算法需要考虑多少种情况？大致分为三种，分别是：节点属性变化，例如：//更新前
//更新后
节点增删改例，例如：//beforeupdate
//更新后的情况1-新节点
//更新后的情况2-删除节点
节点移动，例如：//更新前
//更新后
如何设计差异算法？考虑到只有以上三种情况，一个常见的设计思路是：先判断当前节点属于哪种情况。如果是增删改查，则执行增删改逻辑。如果是属性变化，则执行属性变化逻辑。如果它正在移动，则执行移动逻辑。根据这个方案，其实有一个隐含的前提——“不同操作的优先级相同”。但是在日常开发中，“节点移动”很少发生，所以Diff算法会优先考虑其他情况。基于这个理念，主流框架（React、Vue）的Diff算法会经过多轮遍历，先处理“commoncase”，再处理“uncommoncase”。因此，这就要求“处理异常情况的算法”需要能够涵盖各种边界情况。换句话说，完全可以仅使用“处理不常见情况的算法”来完成Diff操作。主流框架之所以不这样做，是出于性能的考虑。本文将砍掉“处理常见情况的算法”，保留“处理不常见情况的算法”。这样只需要40行代码就可以实现Diff的核心逻辑。Demo介绍首先我们定义虚拟DOM节点的数据结构：typeFlag='Placement'|'删除';接口节点{键：字符串；标志？：旗帜；index?:number;}key是节点的唯一标识，用来关联变化前后的节点。Flag表示节点通过Diff后需要对对应的真实DOM进行的操作，其中：Placement对于新生成的节点，表示需要将对应的DOM插入到页面中。对于已经存在的节点，意味着需要在页面中移动对应的DOM。删除是指需要将DOM对应的节点从页面中删除。index表示该节点在对等节点中的索引位置。注意：本Demo只实现了“节点的flag”，没有实现“根据flag执行DOM操作”。我们要实现的diff方法接收更新前后的NodeList，并用flag标记它们：typeNodeList=Node[];functiondiff(before:NodeList,after:NodeList):NodeList{//...code}例如For://constbeforeupdate=[{key:'a'}]//constafterupdate=[{key:'d'}]??//diff（之前，之后）输出[{key:"d",flag:"Placement"},{key:"a",flag:"Deletion"}]{key:"d",flag:"Placement"}表示d对应需要插入DOM的页面。{key:"a",flag:"Deletion"}表示需要删除a对应的DOM。执行后的结果是：页面上的a变成了d。另一个例子：//更新之前constbefore=[{key:'a'},{key:'b'},{key:'c'},]//更新之后constafter=[{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算法核心逻辑的实现包括三个步骤：遍历前的准备工作。遍历之后。遍历后完成工作。functiondiff(before:NodeList,after:NodeList):NodeList{constresult:NodeList=[];//...遍历前的准备工作for(leti=0;i
();before.forEach((node,i)=>{node.index=i;beforeMap.set(node.key,node);})遍历after遍历after时，如果一个节点同时存在于before和after(samekey)中，我们称这个节点为reusable。例如，对于以下示例，b是可重用的：//constbefore=[{key:'a'},{key:'b'}]//constafter=[{key:'b'}]用于可重用节点，本次更新必然属于以下两种情况之一：没有动静。移动。如何判断可重用节点是否被移动？我们使用lastPlacedIndex变量来保存“之前遍历的最后一个可重用节点的索引”：//indexletofthelastPlacedIndexbeforelastPlacedIndex=0;之后遍历时，每一轮遍历的节点必须是当前遍历的所有节点中最右边的一个。如果这个节点是一个可重用节点，那么nodeBefore和lastPlacedIndex之间有两种关系：注：nodeBefore表示before中可重用节点对应的节点。节点之前。索引=lastPlacedIndex。节点已就位，无需移动。//indexletlastPlacedIndex=0;for(leti=0;i{node.flag='Deletion';result.push(node);});完整代码见在线Demo地址[1]。总结整个Diff算法的难点在于lastPlacedIndex相关的逻辑。跟着demo调试几次，相信你就能明白其中的原理了。参考[1]在线Demo地址：https://codesandbox.io/s/naughty-matan-6fq7n6?file=/src/diff.ts。
