reactdiff?
发布网友
发布时间：2024-09-25 14:34
共1个回答
热心网友
时间：2024-10-17 15:48
有同学问：能否详细说一下diff算法。
详细的说，请阅读这篇文章，有疑问的地方欢迎留言一起讨论。
因为diff算法是vue2.x，vue3.x以及react中关键核心点，理解diff算法，更有助于理解各个框架本质。
说到「diff算法」，不得不说「虚拟Dom」，因为这两个息息相关。
比如：
等等
我们先来说说虚拟Dom，就是通过JS模拟实现DOM，接下来难点就是如何判断旧对象和新对象之间的差异。
Dom是多叉树结构，如果需要完整的对比两棵树的差异，那么算法的时间复杂度O(n^3)，这个复杂度很难让人接收，尤其在n很大的情况下，于是React团队优化了算法，实现了O(n)的复杂度来对比差异。
实现O(n)复杂度的关键就是只对比同层的节点，而不是跨层对比，这也是考虑到在实际业务中很少会去跨层的移动DOM元素。
虚拟DOM差异算法的步骤分为2步：
实际diff算法比较中，节点比较主要有5种规则的比较
部分源码如下：
在reconcileChildren函数的入参中
diff的两个主体是：oldFiber（current.child）和newChildren（nextChildren，新的ReactElement），它们是两个不一样的数据结构。
部分源码
很多时候手工优化dom确实会比virtualdom效率高，对于比较简单的dom结构用手工优化没有问题，但当页面结构很庞大，结构很复杂时，手工优化会花去大量时间，而且可维护性也不高，不能保证每个人都有手工优化的能力。至此，virtualdom的解决方案应运而生。
virtualdom是“解决过多的操作dom影响性能”的一种解决方案。
virtualdom很多时候都不是最优的操作，但它具有普适性，在效率、可维护性之间达到平衡。
virutaldom的意义：
vue2.x的diff位于patch.js文件中，该算法来源于snabbdom，复杂度为O(n)。了解diff过程可以让我们更高效的使用框架。react的diff其实和vue的diff大同小异。
最大特点：比较只会在同层级进行,不会跨层级比较。
对比之前和之后：可能期望将直接移动到
的后边，这是最优的操作。
但是实际的diff操作是：
vue中也使用diff算法，有必要了解一下Vue是如何工作的。通过这个问题，我们可以很好的掌握，diff算法在整个编译过程中，哪个环节，做了哪些操作，然后使用diff算法后输出什么？
解释：
mount函数主要是获取template，然后进入compileToFunctions函数。
compileToFunction函数主要是将template编译成render函数。首先读取缓存，没有缓存就调用compile方法拿到render函数的字符串形式，在通过newFunction的方式生成render函数。
compile函数将template编译成render函数的字符串形式。后面我们主要讲解render
完成render方法生成后，会进入到mount进行DOM更新。该方法核心逻辑如下：
上面提到的compile就是将template编译成render函数的字符串形式。核心代码如下：
compile这个函数主要有三个步骤组成：
分别输出一个包含
parse函数：主要功能是将template字符串解析成AST（抽象语法树）。前面定义的ASTElement的数据结构，parse函数就是将template里的结构（指令，属性，标签）转换为AST形式存进ASTElement中，最后解析生成AST。
optimize函数（src/compiler/optomizer.js）:主要功能是标记静态节点。后面patch过程中对比新旧VNode树形结构做优化。被标记为static的节点在后面的diff算法中会被直接忽略，不做详细比较。
generate函数（src/compiler/codegen/index.js）:主要功能根据AST结构拼接生成render函数的字符串。
其中genElement函数（src/compiler/codgen/index.js）是根据AST的属性调用不同的方法生成字符串返回。
总之：
就是compile函数中三个核心步骤介绍，
patch函数就是新旧VNode对比的diff函数，主要是为了优化dom，通过算法使操作dom的行为降低到最低，diff算法来源于snabbdom，是VDOM思想的核心。snabbdom的算法是为了DOM操作跨级增删节点较少的这一目标进行优化，它只会在同层级进行，不会跨层级比较。
总的来说：
在创建VNode就确定类型，以及在mount/patch的过程中采用位运算来判断一个VNode的类型，在这个优化的基础上再配合Diff算法，性能得到提升。
可以看一下vue3.x的源码：
对oldFiber和新的ReactElement节点的比对，将会生成新的fiber节点，同时标记上effectTag，这些fiber会被连到workInProgress树中，作为新的WIP节点。树的结构因此被一点点地确定，而新的workInProgress节点也基本定型。在diff过后，workInProgress节点的beginWork节点就完成了，接下来会进入completeWork阶段。
snabbdom算法：
定位：一个专注于简单性、模块化、强大功能和性能的虚拟DOM库。
snabbdom中定义Vnode的类型()
init函数的地址：
init()函数接收一个模块数组moles和可选的domApi对象作为参数，返回一个函数，即patch()函数。
domApi对象的接口包含了很多DOM操作的方法。
源码：
源码：
h()函数接收多种参数，其中必须有一个sel参数，作用是将节点内容挂载到该容器中，并返回一个新VNode。
在vue2.x不是完全snabbdom算法，而是基于vue的场景进行了一些修改和优化，主要体现在判断key和diff部分。
1、在snabbdom中通过key和sel就判断是否为同一节点，那么在vue中，增加了一些判断在满足key相等的同时会判断，tag名称是否一致，是否为注释节点，是否为异步节点，或者为input时候类型是否相同等。
2、diff差异，patchVnode是对比模版变化的函数，可能会用到diff也可能直接更新。
reactdiff失效React的diff基于两个假设：
1、相同类型的节点结构是相似的，不同类型的节点结构是不同的，当节点类型不同时会直接将原节点删除，并添加新节点。
2、通过keyprops来暗示哪些子元素在不同的渲染下能保持稳定，如果节点类型和key都一样，就认为在两次渲染中此节点没有改变，可以复用。
React的diff算法详解一、什么是diff算法？
为了增强用户体验，React从版本16开始将同步更新重构成了可中断的异步更新，即采用了新的Reconciler(协调器，用于找出变化的组件），而新的Reconciler中采用了fiber架构。fiber架构的原理在此不再详细解释，我们目前只需要知道fiber节点可以保存dom信息，fiber节点构成的树叫fiber树，而更新dom是要用到‘双缓存技术’，即比较旧的fiber树与此次要渲染的jsx对象，返回新的fiber树进行渲染。在旧fiber树与jsx对象比较时，决定哪些节点要复用的过程，就是diff算法。
由于diff本身也会带来性能消耗，为了降低算法复杂度，React对diff做了三个预设*：
更新后
如果没有key会走第二条*，有了key，react就可以判断div和p节点是存在的，可以复用，只需要交换顺序。
diff算法会根据不同的jsx对象执行不同的处理函数，根据jsx对象的不同，我们可以分为两类：
1.JSX对象（之后都用newChildren表示）的类型为object、number、string，代表同级只有一个节点
2.newChildren的类型为Array，代表同级有多个节点。
二、单节点diff
对于单节点diff，用一个流程图就可以解释
更新后
由于key的默认值为null，所以更新前与更新后满足key相同且元素类型不同，那么我们要删除更新前的三个div节点，新增p节点
三、多节点diff
对于多节点diff,我们要遍历newChildren和oldFiber进行比较。由于React团队发现dom节点一般有更新，增加，删除这三种操作，而更新更为频繁，所以他们设置更新的优先级高于增加删除。基于以上原因，在多节点diff算法的实现中有两层遍历，第一层遍历处理更新的节点，第二层遍历处理更新以外的节点。
第一层遍历
遍历newChildren与oldFiber,判断节点是否可复用，如果可以复用，则继续遍历。
如果不能复用，分为两种情况：
第二层遍历
第二层遍历从第一层遍历的结束位开始
第一层遍历结束后有4种结果
首先我们要判断newChildren中遍历到的节点，在oldFiber中是否存在，基于此，React将oldFiber中的节点以key-oldfiber键值对的形式存在Map中，只需要newChildren的key，就可以判断oldFiber中有没有相应的节点。
如果oldFiber中没有相应的节点，则将newChildren生成的fiber打上placement标记
如果有相应的节点，将它的索引记为oldIndex，与上一次可复用节点在oldFiber的索引位置lastPlacedIndex比较，如果每次可复用的节点在上一次可复用右边就说明位置没有变化，即
若oldIndex=lastPlacedIndex,说明相对位置没有变化，那么令lastPlacedIndex=oldIndex
若oldIndexlastPlacedIndex,代表本节点需要向右移动。
例如:
参考文档：
React技术揭秘(iamkasong.com)
Reactdiff算法react作为一款最主流的前端框架之一，在设计的时候除了简化操作之外，最注重的地方就是节省性能了。diff算法就是为节省性能而设计的，diff算法和虚拟DOM的完美结合是react最有魅力的地方。其中，diff是different的简写，这样一来，diff算法是什么也就顾名思义了——找不同。
在DOM需要更新的时候，通过diff算法可以计算出虚拟DOM中真正变化的部分，从而只针对变化的部分进行更新渲染，避免”牵一发而动全身“，造成性能浪费。
虽然完美地实现了找不同的功能，但是傻瓜式的循环递归对节点进行依次的对比，使其算法的时间复杂度为O(n^3)，其中n是dom树的节点数。如果dom数足够大的话，这个算法将对cpu形成绝杀。
为了优化diff算法，react中对普通的diff算法实行了三大策略，成功将时间复杂度降为O(n)
treediff是diff算法的基础策略，它的重点在于同层比较。
出于对diff算法的优化，react的treediff对DOM节点的跨层级移动的操作忽略不计，react对VirtualDOM树进行层级控制，也就是说只对相同层级的DOM节点进行比较（即同一个父节点下的所有子节点）。对比时，一旦发现节点不存在，则直接删除掉该节点以及之下的所有子节点。这样秩序对DOM树进行依次遍历，就可以完成整个树的对比。时间复杂度为O(n)
一个疑问：既然treediff忽略了跨层级移动的操作，如果这种情况出现了，diff算法会怎么处理呢？
答：不管，多了就新增，少了就删除（只有创建节点和删除节点的操作）。所以官方明确建议不要进行DOM节点的跨层级操作。
componentdiff是组件间的对比
在遇到组件之间的比较时，有三种策略
优化点：
elementdiff是针对同一层级的element节点的
在双方同一层级的节点对比时，有三种情况
子节点更新时，会出现以下几种情况：
react中的key值，它不是给开发者使用的。在一般情况下key值是当我们在做子元素遍历的时候需要使用的。因为我们如果要进行数据的更新，就需要进行虚拟dom的对比，而key值就是每个元素节点对应的唯一值。这个时候就需要对比子元素的key值是否有匹配项，如果有的情况下则会进行数据的更新；如果key值没有匹配项，那么这个节点就需要进行删除和重新创建。
因此我们在遍历的时候千万不要用index下标或者时间戳、随机数等进行key值的赋值。这样会造成元素的移除重新创建浪费性能。
react多节点diff简易实现
react是一个数据驱动的框架，通过将数据与UI关联起来达到数据更新时同时更新UI更新的目的。对于reactwebapp来说，数据的变动最终会转化为dom的变化。当然react并不会对dom进行直接比较，而是对比变化前的fiber。对fiber的diff最终会反映到dom上。
先假设在fiber变化时不使用diff算法，即一旦fiber改变则删除变化前的所有fiber并插入变化后的fiber。这种方法虽然简便，但存在性能问题，因为dom的删除和创建都需要耗费时间。例如，fiber从a,b,c变为a,c,b。只需要将b插入到c之后即可，无需创建任何fiber。因此，需要一种方法来标记元素的变更，这就是diff算法。
如果变化后都存在多个元素，则属于多节点的diff。多节点的fiberdiff对于每一个fiber实际只存在两种情况:
为什么移动或新增dom都属于同一种情况，因为react实际上最终会调用Node.insertBefore()来进行placement操作，其定义如下:
因此react并不关心该fiber是移动(已经存在)还是新增(不存在需要创建)。例如fiber从a,b,c,d变为a,c,b,d，那么react会将b这个fiber标记为Placement。其余fiber不变。在最终进行dom变化时调用parent.insertBefore(d,b)。因此diff的目的并不是要严格的找出fiber从哪个位置移动到哪个位置，只需要得出哪些需要删除，哪些需要Placement即可。
假设存在now以及before两个fiber集合。为了简化场景，认为now中的fiber在before中都存在。这时候问题可以转换为如何移动before中的元素将其转换为now。react处理办法为右移before中的部分fiber将其转换为now。例如，before以及after中key的顺序为:
那么标记b为Placement即可。对于这个任务，我们将上一个位置不变的元素在now中的位置记为lastKeepIndex，当遍历now数组中的每个fiber时，如果该fiber在before数组中存在，且。则说明当前所遍历到得fiber在:
这就意味这这个fiber是需要移动的。如果不满足这个条件，则需要该fiber相对lastKeepIndex所标记的fiber位置没有变动，无需改变。
当然，实际上不可能now中的fiber在before中都能找到。但这种同样直接标记为Placement即可。同时在before中却不在now中的需要元素标记为Deletion。为了方便这里我们定义4种类型的Diff:
整个diff的逻辑为:
在得到diff的结果后，react通过两个dom操作函数来将diff应用到真实的dom:
第一个函数对应于变化后需要进行Placement有兄弟节点的情况，例如fiber从a,b,c,d变化为a,c,b,d。此时b被标记为Placement。react会找到变化后它的第一个不需要变动的兄弟节点即为d，并调用parent.insertBefore(d,b)。完成后真实的dom就从a,b,c,d变成a,c,b,d。
第二个函数对应于变化后需要进行Placement不存在兄弟节点的情况，例如fiber从a,b,c变化为a,c,b此时b被标记为Placement，但其不存在兄弟节点。react会调用parent.appendChild(b)。完成后真实的dom就从a,b,c变成a,c,b。
当然，真实的情况比这要更复杂。因此插入dom必定要先找到fiber树中真正的dom节点。而fiber树实际上是用户自定义组件fiber以及真实domfiber组合在一起的，如何找到真实的兄弟dom节点对应的fiber也是一个比较复杂的任务。
react通过diff算法来进行性能优化，减少dom的创建和删除。那么react采用的优化是否为最优化呢？答案是：否。例如存在这样一个特殊的例子：
由于reactdiff算法的局限，这里需要将1从998移动到999之后，但实际上我们一眼就能看出最简单的方法是将999移动到1之前。这也就是最近很多框架开始使用最长上升子序列来优化diff算法的原因。那么问题来了，你知道为什么这里react需要移动998个元素，或者说为什么最长上升子序列可以解决整个问题吗?
40行代码实现React核心Diff算法该如何设计Diff算法呢？考虑到只有以上三种情况，一种常见的设计思路是：
按这个方案，其实有个隐含的前提——不同操作的优先级是相同的。但在日常开发中，节点移动发生较少，所以Diff算法会优先判断其他情况。
基于这个理念，主流框架（React、Vue）的Diff算法都会经历多轮遍历，先处理常见情况，后处理不常见情况。
所以，这就要求处理不常见情况的算法需要能给各种边界case兜底。
换句话说，完全可以仅使用处理不常见情况的算法完成Diff操作。主流框架之所以没这么做是为了性能考虑。
本文会砍掉处理常见情况的算法，保留处理不常见情况的算法。
这样，只需要40行代码就能实现Diff的核心逻辑。
首先，我们定义虚拟DOM节点的数据结构：
key是node的唯一标识，用于将节点在变化前、变化后关联上。
flag代表node经过Diff后，需要对相应的真实DOM执行的操作，其中：
index代表该node在同级node中的索引位置
注：本Demo仅实现为node标记flag，没有实现根据flag执行DOM操作。
我们希望实现的diff方法，接收更新前与更新后的NodeList，为他们标记flag：
比如对于：
{key:"d",flag:"Placement"}代表d对应DOM需要插入页面。
{key:"a",flag:"Deletion"}代表a对应DOM需要被删除。
执行后的结果就是：页面中的a变为d。
再比如：
由于b之前已经存在，{key:"b",flag:"Placement"}代表b对应DOM需要向后移动（对应parentNode.appendChild方法）。abc经过该操作后变为acb。
由于a之前已经存在，{key:"a",flag:"Placement"}代表a对应DOM需要向后移动。acb经过该操作后变为cba。
执行后的结果就是：页面中的abc变为cba。
核心逻辑包括三步：
我们将before中每个node保存在以node.key为key，node为value的Map中。
这样，以O(1)复杂度就能通过key找到before中对应node：
当遍历after时，如果一个node同时存在于before与after（key相同），我们称这个node可复用。
比如，对于如下例子，b是可复用的：
对于可复用的node，本次更新一定属于以下两种情况之一：
如何判断可复用的node是否移动呢？
我们用lastPlacedIndex变量保存遍历到的最后一个可复用node在before中的index：
当遍历after时，每轮遍历到的node，一定是当前遍历到的所有node中最靠右的那个。
如果这个node是可复用的node，那么nodeBefore与lastPlacedIndex存在两种关系：
注：nodeBefore代表该可复用的node在before中的对应node
代表更新前该node在lastPlacedIndex对应node左边。
而更新后该node不在lastPlacedIndex对应node左边（因为他是当前遍历到的所有node中最靠右的那个）。
这就代表该node向右移动了，需要标记Placement。
该node在原地，不需要移动。
经过遍历，如果beforeMap中还剩下node，代表这些node没法复用，需要被标记删除。
比如如下情况，遍历完after后，beforeMap中还剩下{key:'a'}：
这意味着a需要被标记删除。
所以，最后还需要加入标记删除的逻辑：
