一、概述：
单纯的讲Diff算法，是一个比较宽泛的概念，并非Vue/React等独创。比如linux diff命令、git diff、JS对象间的diff等等，就是一个对比找差别的概念。
在虚拟DOM中，diff算法可以简单认为是在两棵树中找差别。
那为什么要用到Diff算法呢，不用可以么？ 答案是如果不在乎性能，当然是可以的。对于一些简单的页面，DOM操作可能不影响体验。但是对于前端框架来说，将复杂的DOM操作转化成JS对象之间的对比，将DOM创建性能成本转嫁到JS对象上，从而实现DOM复用，进而得到高性能的渲染。
diff 算法的目的就是对比两次渲染结果，找到可复用的部分，然后剩下的该删除删除，该新增新增。
两棵树之间Diff，首先遍历两棵树，然后排序。所以时间复杂度是O(n3)。为了降低复杂度采用了：（1）只做同级比较，不做跨级比较（2）父级元素不相同就删除重建，不再进行深度比较（3）当元素和key二者都相同，可认为是相同节点，不再深度比较。同级比较，不进行深度比较，不较真，虽然简单粗暴，但是直接将时间复杂度O(n3)直接拉回了O(n)
二、React的Diff算法
2.1 Diff算法是什么
先有这样一个意识：Diff算法最终目的是使DOM元素充分复用，即能复用的元素直接复用；其次，能通过移动元素可以渲染的就移动元素；最不济的再创建新的DOM元素。
首先说一下Fiber，Fiber是React采用的新协调引擎，通过对大型复杂任务的分片、 对任务划分优先级，优先调度高优先级的任务、和可以对任务进行挂起、恢复、终止等操作，从而支持虚拟DOM的渐进式渲染。
在 Fiber 中，会把一个耗时很长的任务分成很多小的任务片，每一个任务片的运行时间很短。虽然总的任务执行时间依然很长，但是在每个任务小片执行完之后，都会给其他任务一个执行机会。这样，唯一的线程就不会被独占，其他任务也能够得到执行机会。
Fiber结构如下
{
tag:TypeOfWork,//标识fiber类型
type:'div',//和fiber相关的组件类型
return:Fiber|null,//父节点
child:Fiber|null,//子节点
sibling:Fiber|null,//同级节点
alternate:Fiber|null,//diff的变化记录在这个节点上
...
}
举个例子
也就是说：整体渲染流程分成了两个阶段：
- render 阶段：从 vdom 转换成 fiber，并且对需要 dom 操作的节点打上 effectTag 的标记
- commit 阶段：对有 effectTag 标记的 fiber 节点进行 dom 操作，并执行所有的 effect 副作用函数。
2.2 Diff步骤
React Diff借用了深度优先遍历的思想，其主要步骤：
-
首先，在Fiber构成的map中从左向右新老节点进行比对查找能复用的旧节点，如果有新老节点比对不成功的，则停止这一轮的比对，并记录了停止位置。
-
如果上一轮比对能把所有的新节点都比对完毕，则删除旧节点还没比对的节点。
-
反之，则继续从上一轮的停止位置继续开始循环新节点，拿每一个新节点去老节点fiber里面进行查找，有匹配成功的则复用，没匹配成功的则在协调位置的时候打上 Placement 的标记。
-
在所有新节点比对完毕之后，检查还有没有没进行复用的旧节点，如果有，则全部删除。
