react diff算法面试题（面试中的网红Vue源码解析之虚拟DOM，你知多少呢深入解读diff算法）

本文目录

• 面试中的网红Vue源码解析之虚拟DOM，你知多少呢深入解读diff算法
• 看完你也能弄懂diff算法规则! 简述key的作用
• 简单几句话，知道什么是回流重绘、vue虚拟dom、diff算法和key
• React中的什么机制可帮助我们避免手动操作DOM,提高代码性能
• react 多节点 diff 简易实现
• React diff算法

面试中的网红Vue源码解析之虚拟DOM，你知多少呢深入解读diff算法

众所周知，在前端的面试中，面试官非常爱考dom和diff算法。比如，可能会出现在以下场景

滴滴滴，面试官发来一个面试邀请。接受邀请

我们都知道， key 的作用在前端的面试是一道很普遍的题目，但是呢，很多时候我们都只浮于知识的表面，而没有去深挖其原理所在，这个时候我们的竞争力就在这被拉下了。所以呢，深入学习原理对于提升自身的核心竞争力是一个必不可少的过程。

在接下来的这篇文章中，我们将讲解面试中很爱考的虚拟DOM以及其背后的diff算法。 请认真阅读本文～文末有学习资源免费共享！！！

虚拟DOM是用JavaScript对象描述DOM的层次结构。DOM中的一切属性都在虚拟DOM中有对应的属性。本质上是JS 和 DOM 之间的一个映射缓存。

要点：虚拟 DOM 是 JS 对象；虚拟 DOM 是对真实 DOM 的描述。

diff发生在虚拟DOM上。diff算法是在新虚拟DOM和老虚拟DOM进行diff（精细化比对），实现最小量更新，最后反映到真正的DOM上。

我们前面知道diff算法发生在虚拟DOM上，而虚拟DOM是如何实现的呢？实际上虚拟DOM是有一个个虚拟节点组成。

h函数用来产生虚拟节点（vnode）。虚拟节点有如下的属性：
1）sel： 标签类型，例如 p、div；
2）data： 标签上的数据，例如 style、class、data-*；
3）children ：子节点；
4） text： 文本内容；
5）elm：虚拟节点绑定的真实 DOM 节点；

通过h函数的嵌套，从而得到虚拟DOM树。

我们编写了一个低配版的h函数，必须传入3个参数，重载较弱。

形态1：h(’div’, {}, ’文字’)
形态2：h(’div’, {}, )
形态3：h(’div’, {}, h())

首先定义vnode节点，实际上就是把传入的参数合成对象返回。

然后编写h函数，根据第三个参数的不同进行不同的响应。

当我们进行比较的过程中，我们采用的4种命中查找策略：
1）新前与旧前：命中则指针同时往后移动。
2）新后与旧后：命中则指针同时往前移动。
3）新后与旧前：命中则涉及节点移动，那么新后指向的节点，移到 旧后之后 。
4）新前与旧后：命中则涉及节点移动，那么新前指向的节点，移到 旧前之前 。

命中上述4种一种就不在命中判断了，如果没有命中，就需要循环来寻找，移动到旧前之前。直到while(新前《=新后&&旧前《=就后)不成立则完成。

如果是新节点先循环完毕，如果老节点中还有剩余节点(旧前和旧后指针中间的节点)，说明他们是要被删除的节点。

如果是旧节点先循环完毕，说明新节点中有要插入的节点。

1.什么是Virtual DOM 和Snabbdom
2.手写底层源码h函数
3.感受Vue核心算法之diff算法
4.snabbdom之核心h函数的工作原理

1、零基础入门或者有一定基础的同学、大中院校学生
2、在职从事相关工作1-2年以及打算转行前端的朋友
3、对前端开发有兴趣人群

看完你也能弄懂diff算法规则! 简述key的作用

key 其实就是虚拟 dom 中的标识; 当状态发生变化时, 在 react 、vue 中数据会生成 新的虚拟dom 与 旧数据的虚拟dom 的diff 进行比较.从而减少消耗;

欢迎一起留言讨论; 多健身不掉头发哦~

简单几句话，知道什么是回流重绘、vue虚拟dom、diff算法和key

1.什么是vue虚拟dom。先知道什么是dom树。
众所周知，一个页面形成的流程。（顺便聊一下回流和重绘）
（1） 解析 HTML===》生成DOM树
（2） 解析CSS===》生成CSSDOM树
（3） Render Tree ===》 从Dom树的根节点开始遍历每个可见的节点（因为这里面有display：none、scrpi等的，不被遍历。）
对于每个可见的节点，找到其对应的CSSDOM规则，并且应用。
生成Render Tree 。
fine，问题来了，什么是回流呢？就是在生成render Tree 的时候，有的CSS涉及到了HTML的尺寸（width/height）、布局改变、隐藏等。详细的可以去搜一下怎么会造成回流。《h3》所有的页面都至少会有一次回流，因为第一次生成render tree一定会回流《/h3》
Render Tree生成后，layout（布局）就完成了开始绘制（添加属性，类似于颜色啊，大小啊之类的不会影响布局的属性）。如果说不出意外你不去改的话这辈子和个Render Tree就永远是这个树了。HTML页面就渲染结束了。
但是如果你想改。好嘛，我们就要开始判断你改的是什么了。如果说是影响布局的，那就是回流===》重绘
如果说你只想改个颜色啥的那就直接是重绘，没有回流。
《h3》杰伦：回流必然会带来重绘，但是重绘不一定会回流《/h3》
关于如何优化，可以搜索回流和重绘
参考图：

好了，简单的理解了一些html解析和dom树的生成流程。就可以解释什么是虚拟dom了。
虚拟dom也还是那个dom。那为啥不用真实的dom呢？因为真实的DOM你一操作，它立马给你回流重绘，可能你有10个事件在等着干，一个个都要回流重绘一遍太影响性能了。
（高光打过来！）虚拟dom就站出来了。
虚拟dom：如果有10次更新dom的动作，虚拟dom不会立即操作dom，而是将这10次更新的内容储存起来，通过diff算法，把新的dom（vue刚构造的虚拟dom）和旧的dom（可能是页面上现在显示的真实的dom）进行对比。然后渲染对比完的DOM。
问题来了：什么是diff呢？这是一个算法，有兴趣的可以自己搜一下详细了解诶。我这里只是简单的介绍说这个东西就是 ：头头对比。肚子肚子对比。脚脚对比。同级对比，不会跨级对比。就是我的新头和我的旧头对比。我的新肚子和我的旧肚子对比。对比完了去页面上生成一个新的我。

上面提到了patch阶段，顺便说一下key diff算法会通过key可以判断这两个虚拟dom是不是同一个dom，所以我们key尽量都要写上，并且尽量不要使用索引作为key。可以使用 ’xx-index’ 方式写key。方便你我它~~

好了。本文over _{以上都是自己复习的时候总结的内容，如果有问题请留言} Thanks♪(･ω･)ﾉ

React中的什么机制可帮助我们避免手动操作DOM,提高代码性能

React中通过使用Virtual DOM机制来避免手动操作DOM，提高代码性能。Virtual DOM是在内存中创建的一个抽象的虚拟DOM树，用来描述页面的结构和内容，与真实的DOM树相对应。当页面需要更新时，React通过比较新旧两个Virtual DOM树的差异，再将差异部分更新到真实的DOM树中，从而节省了大量手动操作DOM的代码。
具体来说，React通过以下几个步骤来实现Virtual DOM机制：
1. 当数据发生变化时，React会创建一个新的Virtual DOM树。
2. React会将新旧两个Virtual DOM树进行比较，并找出两者之间的差异。React使用Diff算法来进行比较，该算法能够高效地找出不同之处。
3. React将差异部分以最小的代价更新到真实的DOM树中。
通过使用Virtual DOM机制，React能够最大限度地减少对真实DOM的直接操作，提高代码的性能和可维护性。而且，React的组件化思想能够使得代码更加清晰，更加易于复用和维护。

react 多节点 diff 简易实现

react 是一个数据驱动的框架，通过将数据与 UI 关联起来达到数据更新时同时更新 UI 更新的目的。对于 react web app 来说，数据的变动最终会转化为 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。多节点的 fiber diff 对于每一个 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 以及真实 dom fiber 组合在一起的，如何找到真实的兄弟 dom 节点对应的 fiber 也是一个比较复杂的任务。

react 通过 diff 算法来进行性能优化，减少 dom 的创建和删除。那么 react 采用的优化是否为 最优化 呢？答案是：否。例如存在这样一个特殊的例子：

由于 react diff 算法的局限，这里需要将 1 从 998 移动到 999 之后，但实际上我们一眼就能看出最简单的方法是将 999 移动到 1 之前。这也就是最近很多框架开始使用 最长上升子序列 来优化 diff 算法的原因。那么问题来了，你知道为什么这里 react 需要移动 998 个元素，或者说为什么最长上升子序列可以解决整个问题吗?

React diff算法

react 作为一款最主流的前端框架之一，在设计的时候除了简化操作之外，最注重的地方就是节省性能了。diff算法就是为 节省性能 而设计的，diff算法和虚拟DOM的完美结合是react最有魅力的地方。其中，diff 是 different 的简写，这样一来，diff 算法是什么也就顾名思义了——找不同。

在DOM需要更新的时候，通过diff算法可以 计算出 虚拟DOM 中真正变化的部分，从而只针对变化的部分进行更新渲染，避免”牵一发而动全身“，造成性能浪费。

虽然完美地实现了找不同的功能，但是傻瓜式的 循环递归对节点进行依次的对比 ，使其算法的时间复杂度为 O(n^3) ，其中n是dom树的节点数。如果dom数足够大的话，这个算法将对cpu形成绝杀。

为了优化diff算法，react中对普通的diff算法实行了三大策略，成功将时间复杂度降为 O(n)

tree diff 是diff算法的基础策略，它的重点在于 同层比较 。

出于对diff算法的优化，react的tree diff对DOM节点的跨层级移动的操作忽略不计，react对Virtual DOM树进行层级控制，也就是说 只对相同层级的DOM节点进行比较 （即同一个父节点下的所有子节点）。对比时，一旦发现节点不存在，则直接删除掉该节点以及之下的所有子节点。这样秩序对DOM树进行依次遍历，就可以完成整个树的对比。时间复杂度为O(n)

一个疑问：既然tree diff忽略了跨层级移动的操作，如果这种情况出现了，diff算法会怎么处理呢？

答：不管，多了就新增，少了就删除（ 只有创建节点和删除节点的操作 ）。所以官方明确建议不要进行DOM节点的跨层级操作。

component diff是组件间的对比

在遇到组件之间的比较时，有三种策略

优化点：

element diff 是针对同一层级的element节点的

在双方同一层级的节点对比时，有三种情况

子节点更新时，会出现以下几种情况：

react中的key值，它不是给开发者使用的。在一般情况下key值是当我们在做子元素遍历的时候需要使用的。因为我们如果要进行数据的更新，就需要进行虚拟dom的对比，而key值就是每个元素节点对应的唯一值。这个时候就需要对比子元素的key值是否有匹配项，如果有的情况下则会进行数据的更新；如果key值没有匹配项，那么这个节点就需要进行删除和重新创建。

因此我们在遍历的时候千万不要用 index下标 或者 时间戳、随机数 等进行key值的赋值。这样会造成元素的移除重新创建浪费性能。