感觉很多仍然理解的还不够透彻,先记录下来,之后有新的理解了再来修改。

在理解diff算法前,需要先理解一下什么是virtual dom

 1virtual dom

我们都知道,操作Dom是一个非常缓慢的过程,因为Dom内的每一个元素包含的属性都实在是太多了,我们试着打印一个空的Dom元素的第一层属性:“`

var div = document.getElementById(‘div’);

    for (var key in div) {          

           console.log(key)                   

     }

上面这段代码可以看出,一个Dom元素里面至少包含着上百种属性,这只是第一层,如果每次修改视图,都要重新生成全部的Dom,这对性能来讲无疑是个巨大的浪费。

virtual Dom的出现就是为了解决这个问题。通俗的来讲,virtual Dom就是一个用JavaScript对象来表示的Dom节点。通过这样简单的对象来代替复杂的Dom

 2Diff

刚才讲述了virtual Dom的概念,现在再来看下它的工作流程。有了virtual Dom后,我们操作视图就不需要直接操作Dom,而是操作virtual Dom,在每次创建/更改视图时,会生成一个新的VNode,它好比是一个快照,会与上一次生成的快照进行对比,只把修改的部分映射到真实Dom上,这个过程就称之为Diff

3、分析Diff工作原理

刚才讲过Diff就是对新旧两个VNode的比较,那么是如何比较的呢?看下图

![xx](https://segmentfault.com/img/bVs5U9)

> 一篇相当经典的文章React’s diff algorithm中的图,reactdiff其实和vuediff大同小异。所以这张图能很好的解释过程。比较只会在同层级进行, 不会跨层级比较。

 源码分析

源码来自:[VueGithub](https://github.com/vuejs/vue/blob/dev/src/core/vdom/patch.js)

Diff的过程就是调用patch() 函数,通过比较两个节点之间的区别,作出相应的操作。

function patch (oldVnode, vnode) {

    if (sameVnode(oldVnode, vnode)) {

        patchVnode(oldVnode, vnode)

    } else {

        const oEl = oldVnode.el

        let parentEle = api.parentNode(oEl)

        createEle(vnode)

        if (parentEle !== null) {

            api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl))

            api.removeChild(parentEle, oldVnode.el)

            oldVnode = null

        }

    }

    return vnode

}

上面这段是patch比较核心的部分,代码来自:[杨敬卓的博客](https://segmentfault.com/a/1190000008782928)

我们可以看到,基本的流程就是:首先判断两个节点是否可以比较,如果可以,调用patchVnode进行比较,如果不能比较,说明不在同一级,那么创建一个新的节点,删除之间的旧节点,相当于直接替换。

下面我们依次来分析下这段代码里涉及到的操作

 1sameNode()

sameNode()这个函数用来判断两个节点是否可以比较:

“`

function sameVnode (a, b) {

  return (

    a.key === b.key && (

      (

        a.tag === b.tag &&

        a.isComment === b.isComment &&

        isDef(a.data) === isDef(b.data) &&

        sameInputType(a, b)

      ) || (

        isTrue(a.isAsyncPlaceholder) &&

        a.asyncFactory === b.asyncFactory &&

        isUndef(b.asyncFactory.error)

      )

    )

  )

}

“`

两个节点的keysel相同才会去比较他们。

##### 2patchVnode()

如果两个节点可以比较,便会调用patchNode()函数来判断具体需要执行的操作。

“`

patchVnode (oldVnode, vnode) {

    const el = vnode.el = oldVnode.el

    let i, oldCh = oldVnode.children, ch = vnode.children

    if (oldVnode === vnode) return

    if (oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text) {

        api.setTextContent(el, vnode.text)

    }else {

        updateEle(el, vnode, oldVnode)

        if (oldCh && ch && oldCh !== ch) {

            updateChildren(el, oldCh, ch)

        }else if (ch){

            createEle(vnode) //create el’s children dom

        }else if (oldCh){

            api.removeChildren(el)

        }

    }

}

“`

上面这段代码可以看到,节点的比较一共分为5种情况:

(1)if(oldVnode === vnode),他们的引用一致,可以认为没有变化。

(2)if(oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text),文本节点的比较,需要修改,则会调用Node.textContent = vnode.text

(3)if( oldCh && ch && oldCh !== ch ), 两个节点都有子节点,而且它们不一样,这样会调用updateChildren函数比较子节点

(4)else if (ch),只有新的节点有子节点,调用createEle(vnode)vnode.el已经引用了老的dom节点,createEle函数会在老dom节点上添加子节点。

(5)else if (oldCh),新节点没有子节点,老节点有子节点,直接删除老节点。

##### 3updateChildren()

这个函数为Diff的核心,用于在新旧两个节点都有子节点是,对子节点的比较。

“`

function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {

       while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {

      if (isUndef(oldStartVnode)) {

        oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left

      } else if (isUndef(oldEndVnode)) {

        oldEndVnode = oldCh[–oldEndIdx]

      } else if (sameVnode(oldStartVnode, newStartVnode)) {

        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)

        oldStartVnode = oldCh[++oldStartIdx]

        newStartVnode = newCh[++newStartIdx]

      } else if (sameVnode(oldEndVnode, newEndVnode)) {

        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)

        oldEndVnode = oldCh[–oldEndIdx]

       newEndVnode = newCh[–newEndIdx]

      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right

        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)

        canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))

        oldStartVnode = oldCh[++oldStartIdx]

        newEndVnode = newCh[–newEndIdx]

      } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left

        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)

        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)

        oldEndVnode = oldCh[–oldEndIdx]

        newStartVnode = newCh[++newStartIdx]

“`

原版的代码太长,只截取了这一部分。为了更好的理解,我们看下面这张图:

![xx](https://segmentfault.com/img/bVK0Zy?w=1215&h=920)

过程可以概括为:oldChnewCh各有两个头尾的变量StartIdxEndIdx,它们的2个变量相互比较,一共有4种比较方式。如果4种比较都没匹配,如果设置了key,就会用key进行比较,在比较的过程中,变量会往中间靠,一旦StartIdx>EndIdx表明oldChnewCh至少有一个已经遍历完了,就会结束比较。

##### Key和不设Key的区别

> key 的特殊属性主要用在 Vue的虚拟DOM算法,在新旧nodes对比时辨识VNodes。如果不使用keyVue会使用一种最大限度减少动态元素并且尽可能的尝试修复/再利用相同类型元素的算法。使用key,它会基于key的变化重新排列元素顺序,并且会移除key不存在的元素。

来自:[Vue文档](https://cn.vuejs.org/v2/api/#key)

我们可以得知:不设keynewCholdCh只会进行头尾两端的相互比较,设key后,除了头尾两端的比较外,还会从用key生成的对象oldKeyToIdx中查找匹配的节点,所以为节点设置key可以更高效的利用dom

举个栗子

a,b,c,d,e假设是4个不同的元素,我们没有设置key时,b没有复用,而是直接创建新的,删除旧的。

![xx](https://segmentfault.com/img/bVK0Z2?w=1038&h=836)

当我们给4个元素加上唯一key时,b得到了的复用。

![xx](https://segmentfault.com/img/bVK0Z6?w=1038&h=828)

以上就我对diff算法的一些理解,理解的不深,等之后有了新的理解再来更新吧。

PS:以上所有图片和部分内容来自:[杨敬卓的个人博客](https://github.com/aooy/blog)