前言

本系列主要整理前端面试中需要掌握的知识点。本节介绍diff算法流程以及相关例子。
如果想看源码推荐YK菌的【Vue源码】图解 diff算法 与 虚拟DOM-snabbdom-最小量更新原理解析-手写源码-updateChildren哦~
如果想一步一步跟着写源码推荐尚硅谷的【尚硅谷】Vue源码解析之虚拟DOM和diff算法哦~

一、diff算法是什么

• diff算法是一种通过同层的树节点进行比较的高效算法；
• 他的比较只会在同层级进行，不会跨层级比较；
• 在diff比较的过程中，循环从两边向中间比较。
• diff可以用在虚拟DOM更新时的新老虚拟节点比较的过程中。

二、虚拟节点之间进行比较的流程

1. patch()函数是什么？patch函数是用于节点上树，更新DOM的函数，也就用将新旧节点进行比较的函数。
2. 如果输入的新节点不是虚拟DOM , 那么就需要将DOM节点转换为虚拟DOM，这也印证了，diff算法是针对虚拟DOM的。
3. 比较新旧节点的sel和key是否相同，这里的sel指的是标签名，key就是节点的唯一标识。如果不同，那就直接删除+重新创建。如果相同那就继续往下判断。

if (oldVnode.key == newVnode.key && oldVnode.sel == newVnode.sel)

1. 继续判断新旧是否就是一个对象，如果是，那就什么都不用

if (oldVnode === newVnode)

1. 判断新节点是否有text属性（这里的因为是虚拟节点，就把text称为属性，实际上在DOM中，就是标签的文本内容）。如果有，再判断旧的虚拟节点是否有text，且两者是否相同，相同就不用做，不相同就需要修改节点的text。
2. 如果没有，继续判断老的虚拟节点是否有子节点，如果老节点没有孩子，那么就把新节点的孩子添加到DOM中。
3. 如果新老节点都有孩子，此时就要用diff算法来比较了！！！！

三、diff算法比较原则

diff算法包含四种命中查找：
①新前与旧前
②新后与旧后
③新后与旧前（此种发生后，涉及到移动节点，新后指向的节点，移动到旧后之后）
④新前与旧后（此种发生后，涉及到移动节点，新前指向的节点，移动到旧前之前）
命中一种就不再进行命中判断了，如果都没有命中，就需要用循环来寻找，移动到旧前之前。
结束查找的条件是：旧前<旧后 或者 新前<新后

1. 新前与旧前

• 如果命中，则新前+1，旧前+1
  
• 如果没有命中，则看②新后与旧后能否命中，还不能就③新后与旧前能否命中，还不能就④新前与旧后能否命中。

2. 新后和旧后

• 如果命中，则旧后-1 ， 新后-1；
  
• 如果没有命中，则看③新后与旧前能否命中，还不能就④新前与旧后能否命中。

3. 旧前和新后

• 如果命中，则将新后所指的节点移动到旧后之后，新后-1，旧前+1；
  

• 如果没有命中，则看④新前与旧后能否命中。

4. 旧后与新前

• 如果命中，则将新前所指的节点移动到旧前之前，新前+1，旧后-1；
  
• 如果没有命中，则遍历旧节点的key。

5. 四种都没有命中，遍历旧节点的key

• 下图的新节点中key=D的节点四种命中方式都不能命中，因此以新前指向的key=D为标准，遍历旧节点，直到找到了key=D;
• 找到以后，将key=D的节点放在旧前指向之前，找到的节点设为undefined，新前指向+1
  
  
• 没找的就是新节点，直接插入所有未处理旧节点之前

6. 循环结束

（1）如果新节点中还有剩余：就将新节点中剩余的都插入旧后之后或者旧前之前（旧后之后和旧前之前指的是同一个位置）。

（2）如果旧节点中还有剩余：就将旧前和旧后之间的（包括旧前和旧后）的节点删除。

四、diff算法举例