40行代码实现React核心Diff算法

大家好，我是Kason。任何依赖虚拟DOM的框架都需要Diff算法来比较前后节点的变化。网上有大量的文章讲解Diff算法的逻辑。然而，无论作者的语言多么简洁，图文多么丰富，相信大多数同学看完后都会忘乎所以。今天，我们换一种一劳永逸的学习方式——实现React的核心Diff算法。不难，只有40行代码。不相信？向下看。欢迎加入人类优质前端框架群。拿Diff算法的设计思路想象一下。Diff算法需要考虑多少种情况？大致分为三种，分别是：节点属性变化，如：//beforeupdate

01li>

//更新后

01

节点增删，例如：//更新前

012

//更新后的情况1-新节点

0123

//更新后的情况2——删除节点

01

节点移动，例如：//beforeupdate

01

//更新后

10

如何设计Diff算法？考虑到只有以上三种情况，一个常见的设计思路是：先判断当前节点属于哪种情况。如果是增删改查，则执行增删改逻辑。如果是属性变化，则执行属性变化逻辑。如果是移动，则执行移动逻辑。根据这个方案，其实有一个隐含的前提——不同操作的优先级是一样的，但是在日常开发中，节点移动发生的比较少，所以Diff算法会优先考虑其他情况。基于这个理念，主流框架（React、Vue）的Diff算法会经过多轮遍历，先处理常见情况，再处理不常见情况。因此，这就要求处理不常见情况的算法需要能够覆盖各种边界情况。换句话说，完全有可能只使用处理不常见情况的算法来进行Diff运算。主流框架之所以不这样做，是出于性能的考虑。本文将削减处理常见情况的算法，并保留处理不常见情况的算法。这样只需要40行代码就可以实现Diff的核心逻辑。Demo介绍首先我们定义虚拟DOM节点的数据结构：typeFlag='Placement'|'删除';接口节点{键：字符串；标志？：旗帜；index?:number;}key是节点的唯一标识，用来关联变化前后的节点。Flag表示节点通过Diff后需要对对应的真实DOM进行的操作，其中：Placement对于新生成的节点，表示需要将对应的DOM插入到页面中。对于已经存在的节点，意味着需要在页面上移动对应的DOM。删除是指需要将DOM对应的节点从页面中删除。索引表示该节点在同级节点中的索引位置。执行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中都存在（同一个key），我们称这个节点为reusable。例如，对于以下示例，b是可重用的：//constbefore=[{key:'a'},{key:'b'}]//constafter=[{key:'b'}]用于可重用节点，本次更新一定属于以下两种情况之一：如何判断一个可重用节点是否移动而不移动？我们使用lastPlacedIndex变量来保存之前遍历的最后一个可重用节点的索引：//TheindexofthelastreusablenodetraverseedinbeforeletlastPlacedIndex=0;after遍历时，每一轮节点中遍历的索引必须是当前遍历的所有节点中最右边的一个。如果节点是可复用节点，则nodeBefore和lastPlacedIndex有两种关系：注：nodeBefore表示before中可复用节点对应的节点。更新后该节点不在lastPlacedIndex对应节点的左边（因为它是当前遍历的所有节点中最右边的一个）。这意味着该节点已向右移动，需要标记Placement。nodeBefore.index>=lastPlacedIndex节点就位，不需要移动。//indexletlastPlacedIndex=0;for(leti=0;i{node.flag='Deletion';result.push(node);});完整代码见在线Demo地址。整个Diff算法的难点在于lastPlacedIndex相关逻辑。跟着demo调试几次，相信你就能明白其中的原理了。