在前端面试中，只要涉及到React框架，diff算法便是我们绕不开的话题，这次让我们来系统性的梳理diff算法，不再被这个知识点所困扰。
什么是diff算法？
在了解diff算法之前，我们要直到diff算法并非React独家首创，但是React针对diff算法做了自己的优化，使得diff算法可以帮助我们计算出Virtual Dom中真正变化的部分，并只针对该部分进行实际的DOM操作，而非渲染整个页面，从而保证了每次操作后页面的高效渲染。
传统diff算法
要想了解React的diff算法，我们首先要知道传统的diff算法是如何设计并实现的。
传统diff算法的时间复杂度
传统diff算法的时间复杂度是O(N^3),其中N是树中节点的总数，这样的时间复杂度意味着如果要展示1000个节点，就要执行多达十亿次的比较，这种指数型的性能消耗对于前段渲染场景来说代价太高了。
React只有将diff算法进行改进，才有可能满足前端渲染所要求的的性能。
之所以传统diff算法的时间复杂度是O(N^3)是因为两个二叉树的每一个节点进行两两对比的时间复杂度是O(N^2)，此时如果继续进行树的编辑操作（修改、删除）等还需要O(N)的时间复杂度，所以总的时间复杂度是O（N^3）。
React优化后的diff算法
React通过自己的优化，将O（N^3）的时间复杂度降到了O（N）。
React diff的三个前提策略
- Web UI中DOM节点跨层级的移动操作特别少，可以忽略不计。
- 拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构。
- 对于同一层级的一组子节点，它们可以通过唯一id进行区分。
React进行tree diff、component diff和element diff进行算法优化是基于上面三个前提策略。事实证明上面的三个前提策略是非常有效的。
核心策略1：tree diff（树策略）
对树进行分层比较，两棵树只会对同一层次的节点进行比较。
核心策略2：component diff（组件策略）
React是基于组件构建应用的，对于组件间的比较采用下面的方式：
- 如果是同一类型的组件，按照原策略继续比较虚拟DOM树，对于同一类型的组件，有可能其虚拟DOM树并没有任何变化，如果能够在比较之前准确的知道这一点，可以节省大量的运算时间，所以React向用户提供了shouldComponentUpdate()来判断该组件是否需要进行diff。
- 如果不是同一类型的组件，则将该组件判断为dirty component，从而替换掉整个组件下面的所有子节点。
核心策略3：element diff（元素策略）
对于同一层级的一组子节点，通过唯一id进行区分。
