vue中的Diff算法的理解

Diff算法

虚拟dom：表示真实DOM的JS对象

Diff算法是一种对比算法。对比两者是旧虚拟DOM和新虚拟DOM，对比出是哪个虚拟节点更改了，找出这个虚拟节点，并只更新这个虚拟节点所对应的真实节点，而不用更新其他数据没发生改变的节点，实现精准地更新真实DOM，进而提高效率。

使用虚拟DOM算法的损耗计算： 总损耗 = 虚拟DOM增删改+（与Diff算法效率有关）真实DOM差异增删改+（较少的节点）排版与重绘

直接操作真实DOM的损耗计算： 总损耗 = 真实DOM完全增删改+（可能较多的节点）排版与重绘

Diff算法的原理

新旧虚拟DOM对比的时候，Diff算法比较只会在同层级进行, 不会跨层级比较。 所以Diff算法是:深度优先算法。 时间复杂度:O(n)

Diff对比流程

当数据改变时，会触发setter，并且通过Dep.notify去通知所有订阅者Watcher，订阅者们就会调用patch方法，给真实DOM打补丁，更新相应的视图。

newVnode和oldVnode：同层的新旧虚拟节点

patch方法

这个方法作用就是，对比当前同层的虚拟节点是否为同一种类型的标签(同一类型的标准，下面会讲)：

• 是：继续执行patchVnode方法进行深层比对
• 否：没必要比对了，直接整个节点替换成新虚拟节点

patch的核心原理代码：

function patch(oldVnode, newVnode) {
  // 比较是否为一个类型的节点
  if (sameVnode(oldVnode, newVnode)) {
    // 是：继续进行深层比较
    patchVnode(oldVnode, newVnode)
  } else {
    // 否
    const oldEl = oldVnode.el // 旧虚拟节点的真实DOM节点
    const parentEle = api.parentNode(oldEl) // 获取父节点
    createEle(newVnode) // 创建新虚拟节点对应的真实DOM节点
    if (parentEle !== null) {
      api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl)) // 将新元素添加进父元素
      api.removeChild(parentEle, oldVnode.el)  // 移除以前的旧元素节点
      // 设置null，释放内存
      oldVnode = null
    }
  }

  return newVnode
}

sameVnode方法

patch关键的一步就是sameVnode方法判断是否为同一类型节点，那问题来了，怎么才算是同一类型节点呢？这个类型的标准是什么呢？

sameVnode方法的核心原理代码:

function sameVnode(oldVnode, newVnode) {
  return (
    oldVnode.key === newVnode.key && // key值是否一样
    oldVnode.tagName === newVnode.tagName && // 标签名是否一样
    oldVnode.isComment === newVnode.isComment && // 是否都为注释节点
    isDef(oldVnode.data) === isDef(newVnode.data) && // 是否都定义了data
    sameInputType(oldVnode, newVnode) // 当标签为input时，type必须是否相同
  )
}

patchVnode方法

这个函数做了以下事情：

• 找到对应的真实DOM，称为el
• 判断newVnode和oldVnode是否指向同一个对象，如果是，那么直接return
• 如果他们都有文本节点并且不相等，那么将el的文本节点设置为newVnode的文本节点。
• 如果oldVnode有子节点而newVnode没有，则删除el的子节点
• 如果oldVnode没有子节点而newVnode有，则将newVnode的子节点真实化之后添加到el
• 如果两者都有子节点，则执行updateChildren函数比较子节点，这一步很重要

updateChildren方法

这是patchVnode里最重要的一个方法，新旧虚拟节点的子节点对比，就是发生在updateChildren方法中，接下来就结合一些图来讲，让大家更好理解吧

是怎么样一个对比方法呢？就是首尾指针法，新的子节点集合和旧的子节点集合，各有首尾两个指针。

<ul>
    <li>a</li>
    <li>b</li>
    <li>c</li>
</ul>

修改数据后

<ul>
    <li>b</li>
    <li>c</li>
    <li>e</li>
    <li>a</li>
</ul>

那么新旧两个子节点集合以及其首尾指针为：

然后会进行互相进行比较，总共有五种比较情况：

• 1、oldS 和 newS 使用sameVnode方法进行比较，sameVnode(oldS, newS)
• 2、oldS 和 newE 使用sameVnode方法进行比较，sameVnode(oldS, newE)
• 3、oldE 和 newS 使用sameVnode方法进行比较，sameVnode(oldE, newS)
• 4、oldE 和 newE 使用sameVnode方法进行比较，sameVnode(oldE, newE)
• 5、如果以上逻辑都匹配不到，再把所有旧子节点的 key 做一个映射到旧节点下标的 key -> index 表，然后用新 vnode 的 key 去找出在旧节点中可以复用的位置。