React diff 算法

React 的 diff 算法是保证虚拟 DOM 高效的保证

传统 diff 算法

通过循环递归对节点进行依次对比，新旧 tree 进行遍历,然后还有进行排序,算法复杂度达到 O(n^3) ——如果要展示 1000 个节点，得执行上亿次比较

React 的 diff 策略

1. 忽略 Web UI 中 DOM 节点跨层级移动，因为跨层级的移动操作特别少，可以忽略不计；
2. 拥有相同类的两个组件产生的 DOM 结构也是相似的，不同类的两个组件产生的 DOM 结构则不相同
3. 对于同一层级的一组子节点，通过分配唯一 id 进行区分（key 值和 tag 值）

在 Web UI 的场景下，基于以上三个点，React 对 tree diff、component diff、element diff 进行优化，将普适 diff 的复杂度降低到一个数量级，保证了整体 UI 界面的构建性能！

Tree diff

基于策略一，React 的做法是把 dom tree 分层级，对于两个 dom tree 只比较同一层次的节点，只对同一个父节点下的所有的子节点进行比较，不会做进一步比较，这样只需要对 dom tree 进行一次遍历就完成了两个 tree 的比较。这样就把传统的树的 diff 算法的时间复杂度 O(n^3) 变成线性的 O(n)。

跨级 DOM 的移动

两个 tree 进行对比，右边的新 tree 发现 A 节点已经没有了，则会直接销毁 A 以及下面的子节点 B、C；在 D 节点上面发现多了一个 A 节点，则会重新创建一个新的 A 节点以及相应的子节点。

具体的操作顺序：create A → create B → creact C → delete A。

注意：在开发组件时，保持稳定的 DOM 结构会有助于性能的提升。例如，可以通过 CSS 隐藏或显示节点，而不是真的移除或添加 DOM 节点。

Component diff

React 应用是基于组件构建的，对于组件的比较优化侧重于以下几点：

1. 同一类型组件遵从 tree diff 比较 v-dom 树
2. 不通类型组件，先将该组件归类为 dirty component，替换下整个组件下的所有子节点
3. 同一类型组件 v-dom 没有变化，React 允许开发者使用 shouldComponentUpdate() 来判断该组件是否进行 diff，运用得当可以节省 diff 计算时间，提升性能

父节点更新时,子节点一定会发生渲染更新,即触发 componentDidUpdate, 当 shouldComponentUpdate 返回 true，这个过程是向叶子节点传递的，比如：父节点返回 true，它有两个叶子节点 A 和 B ，那么 A 和 B 会被要求执行 mount 或者 update 的生命周期，如果 A 的 shouldComponentUpdate 返回 false，B 返回 true，那么只有 B 更新。

不同类组件对比：

不同类型的组件直接删除，停止 diff 算法。正如 React 官方博客所言：不同类型的 component 是很少存在相似 DOM tree 的机会，因此这种极端因素很难在实现开发过程中造成重大影响的。

Element diff

设有 key 的普通对比

当节点处于同一层级时，diff 提供三种节点操作：删除、插入、移动

1. 插入：组件 C 不在集合（A,B）中，需要插入

2. 删除： 组件 D 在集合（A,B,D）中，但 D 的节点已经更改，不能复用和更新，所以需要删除 旧的 D ，再创建新的。

   组件 D 之前在 集合（A,B,D）中，但集合变成新的集合（A,B）了，D 就需要被删除。

3. 移动：组件 D 已经在集合（A,B,C,D）里了，且集合更新时，D 没有发生更新，只是位置改变，如新集合（A,D,B,C），D 在第二个，无须像传统 diff，让旧集合的第二个 B 和新集合的第二个 D 比较，并且删除第二个位置的 B，再在第二个位置插入 D，而是 （对同一层级的同组子节点） 添加唯一 key 进行区分，移动即可。

不足之处: 当同级的最后一个节点想要移到列表首部,理想情况是只移动 D，不移动 A,B,C。因此，在开发过程中，尽量减少类似将最后一个节点移动到列表首部的操作，当节点数量过大或更新操作过于频繁时，会影响 React 的渲染性能

例子

如下图，老集合中包含节点：A、B、C、D，更新后的新集合中包含节点：B、A、D、C，此时新老集合进行 diff 差异化对比，发现 B != A，则创建并插入 B 至新集合，删除老集合 A；以此类推，创建并插入 A、D 和 C，删除 B、C 和 D。

面试经验

可以谈谈 React diff 算法吗：

React 通过制定大胆的 diff 策略，将 O(n^3) 复杂度的问题转换成 O(n) 复杂度的问题； React 通过分层求异的策略，对 tree diff 进行算法优化； React 通过相同类生成相似树形结构，不同类生成不同树形结构的策略，对 component diff 进行算法优化； React 通过设置唯一 key 的策略，对 element diff 进行算法优化；

减少 render() 函数的调用：

1. shouldComponentUpdate；
2. PureComponent；PureComponent 的原理是继承了 Component 类，自动加载 shouldComponentUpdate 函数，当组件更新时，shouldComponentUpdate 对 props 和 state 进行了一层浅比较，如果组件的 props 和 state 都没有发生改变，render 方法就不会触发，省去 Virtual DOM 的生成和对比过程，达到提升性能的目的。
3. React.momo: React.momo 与 PureComponent 原理相同, React.momo 在默认情况下，它只会浅比较 props 对象中的复杂对象,同时 React.momo 也可以自定义比较函数 React.memo(MyComponent, areEqual),这个自定义的比较函数和 shouldComponentUpdate() 对返回结果的处理正好相反，也就是说两次的 props 相同的时候返回 true，不同则返回 false。返回 true 会阻止更新，使用上次渲染的结果，而返回 false 则重新渲染
4. onClick 或者 props 的函数属性绑定的函数不要是匿名函数，因为对象的地址不同 props 就不同，会导致触发 component diff