Vue.js将DOM抽象成一个以JavaScript对象为节点的虚拟DOM树，以VNode节点模拟真实DOM，可以对这颗抽象树进行创建节点、删除节点以及修改节点等操作，在这过程中都不需要操作真实DOM。

当数据变化后，会得到一个新的虚拟DOM树，通过diff算法对比新旧虚拟DOM树，只对差异修改。经过diff算法得出需要修改的最小单位，将这些小单位的视图进行更新。这个过程就像打补丁，所以叫patch。

diff算法找差异时做了优化，同层节点如果只是位置变化会复用。

（vue实例._vnode属性可以查看虚拟dom树）

源码分析

patch

patch 为入口，对比根节点

    function patch (oldVnode, vnode, hydrating, removeOnly) {
        const insertedVnodeQueue = []
        if (sameVnode(oldVnode, vnode)) {
            // patch existing root node
            patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
        } else {
            const oldElm = oldVnode.elm
            const parentElm = nodeOps.parentNode(oldElm)
    
            // create new node
            createElm(
              vnode,
              insertedVnodeQueue,
              oldElm._leaveCb ? null : parentElm,
              nodeOps.nextSibling(oldElm)
            )
    
            // destroy old node
            if (isDef(parentElm)) {
              removeVnodes([oldVnode], 0, 0)
            }
        }
        return vnode.elm
    }

patch做了什么？

如果根节点初筛相同(sameVnode为ture)，判断具体差异并进行相应操作(patchVnode)
根节点不同则创建新dom，移除旧dom

sameVnode的条件？看下面

sameVnode

    function sameVnode (a, b) {
      return (
        a.key === b.key &&  //key值
        a.tag === b.tag &&  
        isDef(a.data) === isDef(b.data) //data保存了元素上的属性 如attrs: { class: 'box' }, staticStyle: { color: 'red'}等
        sameInputType(a, b) //input type属性是否相同
      )
    }

isDef作用：判断值是否被定义

    function isDef (v) {
      return v !== undefined && v !== null
    }
    
    function isUndef(v) {   
      return v === undefined || v === null
    }

sameVnode 对key，tag，type等进行简单的判断，通过了就进行具体差异对比, 不通过就新建dom。

怎么对比差异并更新dom，继续往下看

patchVnode

    function patchVnode( 
        oldVnode,
        vnode,
        insertedVnodeQueue,
        ownerArray,
        index,
        removeOnly
    ) {
        if (oldVnode === vnode) return;
        const elm = vnode.elm = oldVnode.elm
    
        const oldCh = oldVnode.children
        const ch = vnode.children
    
        //新节点无文本
        if (isUndef(vnode.text)) {
            if (isDef(oldCh) && isDef(ch)) {
                // 新老节点都有子节点，对子节点进行diff
                if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
            } else if (isDef(ch)) {
                /*如果老节点没有子节点而新节点存在子节点，先清空elm的文本内容，然后为当前节点加入子节点*/
                if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
                addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue) //createEle
            } else if (isDef(oldCh)) {
                /*当新节点没有子节点而老节点有子节点的时候，则移除所有ele的子节点*/
                removeVnodes(oldCh, 0, oldCh.length - 1)
            } else if (isDef(oldVnode.text)) {
                //新老节点都是文本节点，老节点有文本，因为新节点无文本，所以直接去除ele的文本
                nodeOps.setTextContent(elm, '')
            }
        } else if (oldVnode.text !== vnode.text) {
            nodeOps.setTextContent(elm, vnode.text)
        }
    
    }

patchVnode判断如下：

新老节点均有children子节点，则对子节点进行diff操作，调用updateChildren，这个updateChildren也是diff的核心。
如果老节点没有子节点而新节点存在子节点，先清空老节点DOM的文本内容，然后为当前DOM节点加入子节点。
当新节点没有子节点而老节点有子节点的时候，则移除该DOM节点的所有子节点。
当新老节点都无子节点的时候，只是文本的替换。

一开始说了，diff优化中会尽可能复用元素，下面看如何做到的

updateChildren

子元素diff的时候，不是使用2个指针遍历所有新旧children，而是首尾各有1个指针，共4个指针。两两判断，优化在元素顺序变化的情况下，移动dom，而不是新建。

    function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue) {
        let oldStartIdx = 0
        let newStartIdx = 0
        let oldEndIdx = oldCh.length - 1
        let oldStartVnode = oldCh[0]
        let oldEndVnode = oldCh[oldEndIdx]
        let newEndIdx = newCh.length - 1
        let newStartVnode = newCh[0]
        let newEndVnode = newCh[newEndIdx]
        let oldKeyToIdx, idxInOld, vnodeToMove, refElm
    
        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)) {
                // 4次sameVnode判断
                patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
                oldStartVnode = oldCh[++oldStartIdx]
                newStartVnode = newCh[++newStartIdx]
            } else if (sameVnode(oldEndVnode, newEndVnode)) {
                patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
                oldEndVnode = oldCh[--oldEndIdx]
                newEndVnode = newCh[--newEndIdx]
            } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
                patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
                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, newCh, newStartIdx)
                nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
                oldEndVnode = oldCh[--oldEndIdx]
                newStartVnode = newCh[++newStartIdx]
            } else {
                if (isUndef(oldKeyToIdx)) oldKeyToIdx = (oldCh, oldStartIdx, oldEndIdx) // 记录key与位置index的映射 { key0: index0, key1: index1}
    
                // 通过key找新节点在老节点中的位置
                idxInOld = isDef(newStartVnode.key) ?
                    oldKeyToIdx[newStartVnode.key] :
                    findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
                if (isUndef(idxInOld)) { // New element
                    createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
                } else { //相同key
                    vnodeToMove = oldCh[idxInOld]
                    if (sameVnode(vnodeToMove, newStartVnode)) {
                        patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
                        oldCh[idxInOld] = undefined //老节点赋值undefined, while前两个判断就会跳过
                        nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
                    } else {
                        // same key but different element. 比如p改成了div,key仍相同
                        createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
                    }
                }
                newStartVnode = newCh[++newStartIdx]
            }
        }
        if (oldStartIdx > oldEndIdx) {
            refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
            addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
        } else if (newStartIdx > newEndIdx) {
            removeVnodes(oldCh, oldStartIdx, oldEndIdx)
        }
    }

图源自染陌同学

除一开始判断旧节点是否为空之外，主要有4个对比过程

从头得知，新旧节点分别都有2个指针，分别指向各自的头部与尾部。判断如下:

当新旧节点的俩头部相同(sameVnode为ture)，进入patchNode方法，同时各自的头部指针+1；
当新旧节点的俩尾部相同，进入patchNode方法，同时各自的尾部指针-1；
当oldStartVnode，newEndVnode相同，说明oldStartVnode已经跑到了后面，那么就将oldStartVnode.el移到oldEndVnode.el的后边。oldStartIdx+1，newEndIdx-1；
当oldEndVnode，newStartVnode相同，说明oldEndVnode已经跑到了前面，那么就将oldEndVnode.el移到oldStartVnode.el的前边。oldEndIdx-1，newStartIdx+1；

当以上4种对比都不成立时，通过newStartVnode.key 看是否能在oldVnode中找到，如果没有则新建节点，如果有则对比新旧节点中相同key的Node，newStartIdx+1。

当循环结束时，这时候会有两种情况。

oldStartIdx > oldEndIdx，可以认为oldVnode对比完毕，当然也有可能 newVnode也刚好对比完，一样归为此类。此时newStartIdx和newEndIdx之间的vnode是新增的，调用addVnodes，把他们全部插进before的后边。
newStartIdx > newEndIdx，可以认为newVnode先遍历完，oldVnode还有节点。此时oldStartIdx和oldEndIdx之间的vnode在新的子节点里已经不存在了，调用removeVnodes将它们从dom里删除。

总结

patchVnode，updateChildren是核心。patchVnode找两个节点差异并更新dom。updateChildren是找子元素差异，会尽可能的复用DOM以达到优化。
key的判断存在整个diff过程，将key设置为唯一稳定的值才能最大程度的实现复用。

本文在源码基础进行了部分删减简化，查看vue源码可点下面链接:
https://github.com/vuejs/vue/blob/dev/src/core/vdom/patch.js

【参考文章】:
https://juejin.im/post/6844903496232206349
https://juejin.im/post/6844903838261084168

VUE diff算法源码(简化)解析