场景
计算两颗树形结构差异并进行转换
文中, 所提及 n 均代表节点的个数
传统 Diff 算法
处理方案: 循环递归每一个节点
传统 diff
如上所示, 左侧树 a 节点依次进行如下对比:
a->e、a->d、a->b、a->c、a->a
之后左侧树其它节点 b、c、d、e 亦是与右侧树每个节点对比, 算法复杂度能达到 O(n^2)
查找完差异后还需计算最小转换方式，这其中的原理我没仔细去看，最终达到的算法复杂度是 O(n^3)
将两颗树中所有的节点一一对比需要 O(n²)的复杂度，在对比过程中发现旧节点在新的树中未找到，那么就需要把旧节点删除，删除一棵树的一个节点 (找到一个合适的节点放到被删除的位置) 的时间复杂度为 O(n), 同理添加新节点的复杂度也是 O(n), 合起来 diff 两个树的复杂度就是 O(n³)
优化的 Diff 算法
vue 和 react 的虚拟 DOM 的 diff 算法大致相同，其核心是基于两个简单的假设:
- 两个相同的组件产生类似的 DOM 结构，不同的组件产生不同的 DOM 结构
- 同一层级的一组节点，他们可以通过唯一的 id 进行区分
(优化的)diff 三点策略:
- web UI 中 DOM 节点跨层级的移动操作特别少，可以忽略不计。
- 拥有相同类型的两个组件将会生成相似的树形结构，拥有不同类型的两个组件将会生成不同树形结构。
- 对于同一层级的一组自节点，他们可以通过唯一 id 进行区分。
即, 比较只会在同层级进行, 不会跨层级比较
React 优化 Diff 算法
基于以上优化的 diff 三点策略，react 分别进行以下算法优化
- tree diff
- component diff
- element diff
tree diff
react 对树的算法进行了分层比较。react 通过 updateDepth 对 Virtual Dom 树进行层级控制，只会对相同颜色框内的节点进行比较，即同一个父节点下的所有子节点。当发现节点不存在，则该节点和其子节点都会被删除。这样是需要遍历一次 dom 树，就完成了整个 dom 树的对比
分层比较 img
如果是跨层级的移动操作，如图
跨层级操作 img
当根结点发现 A 消失了，会删除掉 A 以及他的子节点。当发现 D 上多了一个 A 节点，会创建 A（包括其子节点）节点作为子节点
所以：当进行跨层级的移动操作，react 并不是简单的进行移动，而是进行了删除和创建的操作，这会影响到 react 性能。所以要尽量避免跨层级的操作。（例如：控制 display 来达到显示和隐藏，而不是真的添加和删除 dom）
component diff
- 如果是同类型的组件，则直接对比 virtual Dom tree
- 如果不是同类型的组件，会直接替换掉组件下的所有子组件
- 如果类型相同，但是可能 virtual DOM 没有变化，这种情况下我们可以使用 shouldComponentUpdate() 来判断是否需要进行 diff
component vs img
如果组件 D 和组件 G，如果类型不同，但是结构类似。这种情况下，因为类型不同，所以 react 会删除 D，创建 G。所以我们可以使用 shouldComponentUpdate()返回 false 不进行 diff。
针对 react15, 16 出了新的生命周期
所以：component diff 主要是使用 shouldComponentUpdate() 来进行优化
element diff
element diff 涉及三种操作：插入，移动，删除
不使用 key 的情况 img
不使用 key 的话，react 对新老集合对比，发现新集合中 B 不等于老集合中的 A，于是删除了 A，创建了 B，依此类推直到删除了老集合中的 D，创建了 C 于新集合。=
酱紫会产生渲染性能瓶颈，于是 react 允许添加 key 进行区分
使用 key 的情况 img
react 首先对新集合进行遍历，for(name in nextChildren), 通过唯一 key 来判断老集合中是否存在相同的节点，如果没有的话创建，如果有的话，if (preChild === nextChild) 进行移动操作
移动优化
在移动前，会将节点在新集合中的位置和在老集合中 lastIndex 进行比较，如果 if (child._mountIndex < lastIndex) 进行移动操作，否则不进行移动操作。这是一种顺序移动优化。只有在新集合的位置 小于 在老集合中的位置 才进行移动。
如果遍历的过程中，发现在新集合中没有，但是在老集合中的节点，会进行删除操作
所以：element diff 通过唯一 key 进行 diff 优化。
总结：
1.react 中尽量减少跨层级的操作。2. 可以使用 shouldComponentUpdate() 来避免 react 重复渲染。3. 添加唯一 key，减少不必要的重渲染
Vue 优化 Diff
vue2.0 加入了 virtual dom，和 react 拥有相同的 diff 优化原则
差异就在于, diff 的过程就是调用 patch 函数，就像打补丁一样修改真实 dom
- patchVnode
- updateChildren
updateChildren 是 vue diff 的核心
过程可以概括为：oldCh 和 newCh 各有两个头尾的变量 StartIdx 和 EndIdx，它们的 2 个变量相互比较，一共有 4 种比较方式。如果 4 种比较都没匹配，如果设置了 key，就会用 key 进行比较，在比较的过程中，变量会往中间靠，一旦 StartIdx>EndIdx 表明 oldCh 和 newCh 至少有一个已经遍历完了，就会结束比较
Vue 2.x vs Vue 3.x
Vue2 的核心 Diff 算法采用了双端比较的算法，同时从新旧 children 的两端开始进行比较，借助 key 值找到可复用的节点，再进行相关操作。相比 React 的 Diff 算法，同样情况下可以减少移动节点次数，减少不必要的性能损耗，更加的优雅
Vue3.x 借鉴了 ivi 算法和 inferno 算法。在创建 VNode 时就确定其类型，以及在 mount/patch 的过程中采用位运算来判断一个 VNode 的类型，在这个基础之上再配合核心的 Diff 算法，使得性能上较 Vue2.x 有了提升。(实际的实现可以结合 Vue3.x 源码看
该算法中还运用了动态规划的思想求解最长递归子序列
最后，希望大家早日实现：成为前端高手的伟大梦想！！！
欢迎交流~
著作权归作者所有。转载请联系作者获得授权且注明出处