简述Diff 算法执行过程

前言

diff 算法是对比2颗 dom 树上不同节点的差异，相同的节点则继续保持，不同节点则进行更新

一般情况有2种算法：

• 把第一棵树上，每个节点，与第二棵树上每个节点对比，n个节点，对比n2次，非常损耗性能。
• 只比较同级别的节点

下面我们重点看，只比较同级别的节点

比较同级别的节点

一般比较时会有4种情况：

1. 旧开始节点与，新开始节点比较
2. 旧结束节点与，新结束节点比较

上面2种原理类似：
按照索引，通过sameVnode方法，比较新旧节点是否相同，即 key 和 sel。
如果是相同节点则，重用之前旧节点的DOM元素，调用patchVnode，比较内部差异，并更新节点，此时索引 ++ 或 –，把下一个节点作为开始节点或结束节点

3. 旧开始节点，新结束节点比较

同样的，使用sameVnode方法，比较内部，相同则调用patchVnode比较差异，并把旧开始节点移动到最后。更新索引，旧开始节点++，新结束节点–

4. 旧结束节点，新开始节点比较

也是使用sameVnode方法，比较内部，相同则调用patchVnode比较差异，并把旧结束节点移动到最前面。更新索引，旧结束节点–，新开始节点++

如果以上4中都不满足:

说明开始节点和结束节点都不相同，那么就从旧节点中依次查找是否有相同的新节点：

1. 比较是否有相同 key 的节点
2. 如果没找到，或，key相同，sel 不同， 则说明是新节点，直接创建新DOM，并插入到最前面
3. 如果 key、sel 都相同，找到的旧节点会赋值给 elmToMove，然后用 patchVnode 对比差异，将 elmToMove 移到最前面

循环结束

如果循环结束，新旧节点个数不同，还没对比完，怎么办呢？

1. 新节点个数 > 老节点个数

先比较新旧开始节点，如果相同则index++，直到遇到不同节点；再比较结束节点，同样，结束节点相同，则index–，直到遇到不同节点，则将中间剩余的放到老节点的元素末尾

2. 老节点个数 > 新节点个数

新节点会先遍历完，老节点剩余，同样，先比较新旧开始节点，如果相同则index++，直到遇到不同节点；再比较结束节点，结束节点相同，则index–，直到遇到不同节点。再把中间剩余的删除