2021/03/03 - diff算法简析

[lxinr]

diff算法介绍

diff算法是一种通过同层的树节点进行比较的高效算法，避免了对树进行逐层搜索遍历，所以时间复杂度只有 O(n)

diff算法特点：

1. 比较只会在同层级进行, 不会跨层级比较
2. 在 diff 比较的过程中，循环从两边向中间收拢

diff 流程

1. 虚拟DOM渲染真实DOM过程中首先会对新老VNode的开始和结束位置进行标记
2. 开始执行迭代处理
   1. 首先对新老VNode节点的头尾进行比较，寻找相同节点，如果有相同节点满足可服用的情况则直接复用
   2. 根据具体情形，移动新老节点的 VNode 索引，从而进入下一次循环
   3. 如果没有可复用的节点，则根据索引判断，新的VNode节点在不在旧的VNode队列中，存在则复用，不存在则新建一个DOM节点放在当前位置
3. 当迭代处理结束后，根据新老节点的数目不同，做相应的节点添加或者删除，新的大于老的，则把多的加入到真实DOM中，否则则删除多余的

参考：
Vue 的 diff 算法解析