什么是diff算法

react 作为一款最主流的前端框架之一，在设计的时候除了简化操作之外，最注重的地方就是节省性能了。diff算法就是为节省性能而设计的，diff算法和虚拟DOM的完美结合是react最有魅力的地方。其中，diff 是 different 的简写，这样一来，diff 算法是什么也就顾名思义了——找不同。

diff算法的基本流程：

第一次render在执行的时候会将第一次的虚拟dom做一次缓存，第二次渲染的时候会将新的虚拟dom和老的虚拟dom进行对比。这个对比的过程其实就是diff算法。在diff对比中，首先它会考虑几种情况，第一种情况是如果当前的虚拟dom节点类型和上一次的节点类型不一样的时候(比如新的节点是一个p标签，旧节点是一个div标签)我们就直接替换元素，第二种情况是新旧虚拟dom节点类型一样则对比props属性(元素属性) 如果新的props属性中有新增的属性则进行添加 如果旧的props中有的属性新的props中没有则进行删除

diff算法的作用

在DOM需要更新的时候，通过diff算法可以 计算出 虚拟DOM 中真正变化的部分，从而只针对变化的部分进行更新渲染，避免”牵一发而动全身“，造成性能浪费。

普通的diff算法

虽然完美地实现了找不同的功能，但是傻瓜式的循环递归对节点进行依次的对比，使其算法的时间复杂度为O(n^3)，其中n是dom树的节点数。如果dom数足够大的话，这个算法将对cpu形成绝杀。

React中的diff算法

为了优化diff算法，react中对普通的diff算法实行了三大策略，成功将时间复杂度降为O(n)

1. 策略一：tree diff —— 层级对比

   由于开发过程中极少出现DOM的跨层级移动，所以tree diff 忽略了DOM节点的跨层级移动。（react不建议开发人员跨层级移动DOM）

2. 策略二：component diff —— 组件对比

   同类型的两个组件，直接比较Virtual DOM树，不同类型的组件将会被判定作为脏组件(dirty component)处理，直接删除或创建新组件

3. 策略三：element diff —— 节点对比

   对于同一层级的一组子节点，通过分配唯一唯一key值进行区分

tree diff

tree diff 是diff算法的基础策略，它的重点在于同层比较。

出于对diff算法的优化，react的tree diff对DOM节点的跨层级移动的操作忽略不计，react对Virtual DOM树进行层级控制，也就是说只对相同层级的DOM节点进行比较（即同一个父节点下的所有子节点）。对比时，一旦发现节点不存在，则直接删除掉该节点以及之下的所有子节点。这样秩序对DOM树进行依次遍历，就可以完成整个树的对比。时间复杂度为O(n)

层级控制——图片来自网络

一个疑问：既然tree diff忽略了跨层级移动的操作，如果这种情况出现了，diff算法会怎么处理呢？

答：不管，多了就新增，少了就删除（只有创建节点和删除节点的操作）。所以官方明确建议不要进行DOM节点的跨层级操作。

component diff

component diff是组件间的对比

在遇到组件之间的比较时，有三种策略

1. 对比时，遇到同一类型的组件遵循 tree diff，进行层级对比
2. 对比时，一旦遇到不同类型的组件，直接将这个不同的组件判断为 dirty component（脏组件），并替换该组件和之下所有的子节点。
3. 对比时，在同一类型的两个组件中，如果你知道这个组件的 Virtual DOM没有任何变化，你（开发者）就可以手动使用 shouldComponentUpdate() 来判断组件是否需要进行diff，进一步的提升了diff效率和性能

优化点：

• 避免使用结构相同但是类型不同的组件，因为虽然组件的结构不需要改动，但是由于类型不同的原因，diff会直接销毁该组件并重建，虽然这种情况极少出现，但是造成的性能浪费挺严重的。
• 对于同一类型并且没有变化的组件，合理使用 shouldComponentUpdate() 进行优化

element diff

element diff 是针对同一层级的element节点的

在双方同一层级的节点对比时，有三种情况

1. 面对全新的节点时，执行插入操作 —— INSERT_MARKUP

   这点不需要过多解释

2. 面对多余的节点时，执行删除操作 —— REMOVE_NODE

   删除操作有两种情况：

   • 组件新集合中有组件旧集合中的类型，但对应的element不可更新，只能执行删除
   • 旧组件不在新集合里面，执行删除

3. 面对换位的节点时，执行移动操作 —— MOVE_EXISTING

   比如该层级的组件原本是 [A,B,C,D] ，新的结构为 [A,D,B,C] ，只进行了移动操作。在传统的diff算法中，只要遇见不同（B/D）就删除并重新插入，这样的做法过于粗暴，浪费了很多可以复用的节点，所以在element diff中，对新旧该层级的对比双方都添加了唯一的key值进行区分，只要对应的key值对应的元素没有改变，则只需要执行移动即可。

   细节：

   1. 新旧节点会遍历后对比下标，新的下标称为lastIndex，旧的称为index，如果lastIndex大于index，需要将节点旧的节点移动到新的位置，相反则不动。
   2. 如果没有找到对应位置节点，则执行新增； 如果旧的节点在新的节点组用不到，则执行删除；一般是在最后做删除操作。
   3. 特殊情形，最后一个节点移动到第一个位置，会导致，前面的n-1个节点都进行后移，影响性能。尽量避免这样的操作。

diff算法中，子节点更新的完整流程

子节点更新时，会出现以下几种情况：

• 当旧的子节点是单个的子节点的时候
  • 如果新的子节点也是单个的，则对比子节点的内容，如果不一样则更新内容
  • 如果新的子节点是空的则删除旧的子节点
  • 如果新的子节点是多个的，则需要遍历挂载（创建插入）
• 当旧的子节点是空节点的时候
  • 如果新的子节点是单个的，则进行插入操作
  • 如果新的子节点是多个的，则遍历插入
  • 如果新的子节点是空的，不用管
• 当旧的子节点是多个的时候
  • 如果新的子节点是单个的，则需要遍历删除旧的子节点然后插入新的子节点
  • 如果新的子节点是空的，则需要遍历删除旧的子节点
  • 如果新的子节点也是多个的：
    1. 通过遍历判断有没有拥有相同key值的子节点，如果有的话则更新它的属性和内容
    2. 通过遍历判断新的子节点的位置和旧的子节点的位置是否一致（下标是否一致） ，如果一致则更新内容和属性，如果不一致则将旧的子节点在新的子节点的位置进行插入
    3. 旧的子节点中拥有的虚拟dom，新的子节点中没有，则需要对比删除

react中key值的作用

react中的key值，它不是给开发者使用的。在一般情况下key值是当我们在做子元素遍历的时候需要使用的。因为我们如果要进行数据的更新，就需要进行虚拟dom的对比，而key值就是每个元素节点对应的唯一值。这个时候就需要对比子元素的key值是否有匹配项，如果有的情况下则会进行数据的更新；如果key值没有匹配项，那么这个节点就需要进行删除和重新创建。

因此我们在遍历的时候千万不要用 index下标 或者 时间戳、随机数 等进行key值的赋值。这样会造成元素的移除重新创建浪费性能。

关联文档

• React中的虚拟DOM
• 浏览器是如何绘制页面的