Diff

传统 diff 算法的复杂度为 O(n^3)，显然这是无法满足性能要求的。React 通过制定一个特定的策略，将 O(n^3) 复杂度的问题转换成 O(n) 复杂度的问题。依次分为以下三个步骤

• tree diff。同层对比
• component diff。整体性
• element diff。插入/移动/删除，借助 key 尽可能复用（只做移动）
  • 用 key 来构建一个老节点的 map，复用一个后要从 map 里删除
  • lastPlacedIndex 表示最后一个不需要移动的节点的索引。移动时的原则是尽量少量的移动，如果必须有一个要动，新地位高的不动，新地位低的动

参考 https://zhuanlan.zhihu.com/p/20346379

vue

vue 的 diff 算法是基于 snabdom，参考

• vue2 和 vue3 diff 对比
• 面试官：你了解 vue 的 diff 算法吗？
• 从:key 的角度，来看 Vue3 中 diff 算法的实现原理

vue2 双端 diff

• 开始遍历时，首先依次进行头头、尾尾、头尾、尾头对比
• 从两端向中间遍历，当指针交叉的时候，就是对比完成了
• 都对比完了，再对比其他没有移动规律的节点

vue3 快速 diff

• 处理新旧两个组子节点中相同的前置节点和后置节点
• 处理完后，如果剩余节点无法简单的通过挂载新节点或者卸载已经不存在的节点来完成更新，则需要根据节点的索引关系，构建出一个最长递增子序列
• 利用最长递增子序列来优化移动逻辑
• 其他优化
  • 静态标记,只对打标记的节点进行 diff

参考

• https://zhuanlan.zhihu.com/p/355576164
• https://juejin.cn/post/7134499769803603999#heading-4

vue 和 react diff 对比

相同点

• 都是两组虚拟 dom 的对比(react16.8 之后是 fiber 与虚拟 dom 的对比)
• 只对同级节点进行对比，简化了算法复杂度
• 都用 key 做为唯一标识，进行查找，只有 key 和标签类型相同时才会复用老节点
• 遍历前都会建立 keyMap

不同点

• react 在 diff 遍历的时候，只对需要修改的节点进行了记录，形成 effect list，最后才会根据 effect list 进行真实 dom 的修改，修改时先删除，然后更新与移动，最后插入
• vue 在遍历的时候就用真实 dominsertBefore 方法，修改了真实 dom，最后做的删除操作
• react 采用单指针从左向右进行遍历; vue2 采用双指针，从两头向中间进行遍历
• react 的虚拟 diff 比较简单，vue 中做了一些优化处理，相对复杂，但效率更高