关于Virtual DOM 算法的疑惑

Question

刚过年，最近忙着找一份实习的工作。电话面试了几家大公司，他们都提到了Virtual DOM 的 diff 算法，一下子让我慌得不行，网上找来找去，学来学去还是有很多地方不是很明白。希望大佬们指点小妹一番。
深度剖析：如何实现一个 Virtual DOM 算法

这里构建一个真正的DOM树，插到文档当中？这句话的意思应该是全部更新，而react和vue都是按需更新，那么react 和 vue是如何根据最新的状态更新dom的？

Answer 1

简单讲一下我的理解：

先抛开框架本身，理解上述的几个步骤。
1.用javascript对象结构表示DOM树的结构，然后用树构建一个真正的树
2.当状态变更的时候，重新造一颗树，然后用新旧树对比
3.把2所记录的差异应用到步骤1所构建的DOM树上，视图更新。

首先，简单描述就是。所有节点，都是通过js来创建，这样我们才有办法用js来保存一个虚拟dom树。

现在有了虚拟dom树了，我们需要面对两个问题。

1. 虚拟dom 如何更新到界面上
2. 后续如何来修改界面上的dom

第一点，通过虚拟dom，以一定的算法来生成一个真实的dom树，然后以某种方式插入到界面中。可能是这样xxx.innerHtml = xxx...

第二点，也就是更新dom，但是页面上的节点数非常的多，所以我们希望以最快的速度来更新dom。
那么毫无疑问，目前内存中应该是最为方便的，也最快的。

于是就出来了各式各样的diff算法。

首先想想，你能实现的最简单的方式。

遍历最新的节点与之前生成树进行比较，比如你随意修改了一个节点，找到两颗树之间修改的复杂度是o(n3).

这时候React出来了(我就了解react),我们要降低算法复杂度，我对我需要比较的节点来进行限制。就是我认为我们是同级的我才比较。

React 通过同级比较，将算法复杂度降低到o(n),

盗了张图

图片来源

Matt-Esch 一个diff算法
snabbdo 另外一个

diff算法，怎么写都是算法，重点的是不同的diff他们的思路如何实现的。

如何降低算法复杂度，也就是制定规则，或者预处理。

比如react就是通过只比较同层级直接的变化，那么我就可以从一棵树的层级，直接定位到另一颗树的对应层级上，而不需要去遍历整颗树，也就是算法优化问题。

菜鸟愚见。。

Answer 2

react没有深入学习。前段时间看过Vue的diff。

数据更新后setter方法会重新render出一个VNode，也就会有新的虚拟节点树。新旧树同层比较，修正更改的部分，再重新渲染到视图上。

Vue采取了异步更新的策略，setter方法通知的watcher会经过过滤进入一个队列，在nextTick时一次性执行一批，由于watcher会被过滤，短时间内频繁的修改一个数据，也不会重复执行patch和diff的过程。

Answer 3

1. 根据 jsf 或者 js描述一个页面结构，这个结构会被用来构造真正的 DOM 树，然后挂载到 container
   节点（就平时的 <div id="app"/>） 上。
2. 状态树，它是联系虚拟 DOM 和 真实 DOM的桥梁，所谓的双向绑定就是靠这个中间人。页面载入时的初始状态树就是由所有构造函数 (React.Component 之类的东西，里边的 this.state = {...}，就是在描述初始状态树)汇总而来。
3. 每当 UI 事件、网络事件导致新的状态产生，就会导致状态树进行迭代。方式就是根据新的状态构造一棵新的状态树，并与旧的进行比对，扫描出涉及到的虚拟 DOM(因为你通过构造函数里、props等等方式告诉系统哪些状态与哪些节点相关)，这一步有的叫 脏标记，就是 节点脏了，要更新了 的意思。
4. 脏标记完成后，根据这些 脏节点 对真实 DOM 对应的节点（一开始通过 jsf 或继承 Component 等方式登记了这个信息）进行更新，有的是改变样式、有的是增删、有的是重用节点修改内容、有的是修改节点值(value 等等)。

然后 2 3 步循环。

太久没看 react 和 vue 了，不知道现在有没有更新思路，记忆里是这样的。

Answer 4

在react/vue中：

state改变-->虚拟DOM更新-->虚拟DOM比较(diff算法)-->渲染变化部分