Diff算法
本质
diff本身就是上一帧的元素树与当前帧的元素树进行比对。
react
正常两棵树完全比对的算法复杂度是O(n 3 )。
将两颗树中所有的节点一一对比需要O(n²)的复杂度，在对比过程中发现旧节点在新的树中未找到，那么就需要把旧节点删除，删除一棵树的一个节点(找到一个合适的节点放到被删除的位置)的时间复杂度为O(n),同理添加新节点的复杂度也是O(n),合起来diff两个树的复杂度就是O(n³)
这个开销太过高昂。为了降低算法复杂度，React的diff做了一些优化：
- 只对同级元素进行
Diff。如果一个DOM节点在更新中跨越了层级，那么React不会尝试复用他。 - 如果元素不存在
key prop，两个不同类型的元素会产生出不同的树。如果元素由div变为p，React会销毁div及其子孙节点，并新建p及其子孙节点。 - 可以通过
key prop来显式声明元素，帮助React识别是否可以复用。
// 更新前
<div>
<p key="ka">ka</p>
<h3 key="song">song</h3>
</div>
// 更新后
<div>
<h3 key="song">song</h3>
<p key="ka">ka</p>
</div>
如果没有key，React会认为div的第一个子节点由p变为h3，第二个子节点由h3变为p。则执行2，会销毁并新建。
但是当我们用key指明了节点前后对应关系后，React知道key === “ka"的p在更新后还存在，所以DOM节点可以复用，只是需要交换下顺序。
// 习题1 更新前
<div>ka song</div>
// 更新后
<p>ka song</p>
// 习题2 更新前
<div key="xxx">ka song</div>
// 更新后
<div key="ooo">ka song</div>
// 习题3 更新前
<div key="xxx">ka song</div>
// 更新后
<p key="ooo">ka song</p>
// 习题4 更新前
<div key="xxx">ka song</div>
// 更新后
<div key="xxx">xiao bei</div>
习题1: 未设置key prop默认 key = null;，所以更新前后key相同，都为null，但是更新前type为div，更新后为p，type改变则不能复用。
习题2: 更新前后key改变，不需要再判断type，不能复用。
习题3: 更新前后key改变，不需要再判断type，不能复用。
习题4: 更新前后key与type都未改变，可以复用。children变化，DOM的子元素需要更新。
对比
相同点
- 虚拟DOM在比较时只比较同一层级节点，复杂度都为 O(n)，降低了算法复杂度；
- 都使用key比较是否是相同节点，都是为了尽可能的复用节点
- 都是操作虚拟DOM，最小化操作真实DOM，提高性能（其实虚拟DOM的优势 并不是在于它操作DOM快）
- 都是不要用 index作为 key
区别
- React 是从左向右遍历对比，Vue 是双端交叉对比。
- React 需要维护三个变量（我看源码发现是五个变量），Vue 则需要维护四个变量。
- Vue 整体效率比 React 更高，举例说明：假设有 N 个子节点，我们只是把最后子节点移到第一个，那么
- React 需要进行借助 Map 进行 key 搜索找到匹配项，然后复用节点
- Vue 会发现移动，直接复用节点
算法比对
vue的列表比对，采用从两端到中间的比对方式，而react则采用从左到右依次比对的方式。当一个集合，只是把最后一个节点移动到了第一个，react会把前面的节点依次移动，而vue只会把最后一个节点移动到第一个。总体上，vue的对比方式更高效。
vue比对节点，当节点元素类型相同，但是className不同，认为是不同类型元素，删除重建，而react会认为是同类型节点，只是修改节点属性
react只比较节点类型和key
function sameVnode(vnode1: VNode, vnode2: VNode): boolean {
return vnode1.key === vnode2.key && vnode1.sel === vnode2.sel;
}
vue比较节点类型和key，还有属性
function sameVnode (a, b) {
return (
a.key === b.key && // key值
a.tag === b.tag && // 标签名
a.isComment === b.isComment && // 是否为注释节点
// 是否都定义了data，data包含一些具体信息，例如onclick , style
isDef(a.data) === isDef(b.data) &&
sameInputType(a, b) // 当标签是<input>的时候，type必须相同
)
}
diff算法遍历原理
- React 首位是除删除外是固定不动的,然后依次遍历对比;
- Vue 的compile 阶段的
optimize标记了static 点,可以减少 differ 次数,而且是采用双向遍历方法;
diff算法更新DOM逻辑
- Vue基于snabbdom库，它有较好的速度以及模块机制。Vue Diff使用双向链表，边对比，边更新DOM。
- React主要使用diff队列保存需要更新哪些DOM，得到patch树，再统一操作批量更新DOM。
资料