我们都知道，Vue中是使用了基于HTML的模板语法，允许开发者声明式地将DOM绑定至底层Vue实例的数据。而初始化的时候，Vue就会将该模板语法转化为真实DOM，渲染到页面中。

  1. <template>
  2.         <div>{{msg}}</div>
  3. </template>
  5. <script>
  6.       export.default {
  7.           data() {
  8.               return {
  9.                   msg: 'HelloWorld'
  10.             }
  11.         }
  12.     }
  13. </script>

但当数据发生变化的时候，Vue会如何去更新页面呢？

如果选择重新渲染整个DOM，那必然会引起整个DOM树的重绘和重排，而在真实项目中，不可能就跟上面的例子一样只有一句<div>{{msg}}</div>。当我们的页面非常复杂的情况下，且修改的数据只影响到一小部分页面数据的更新的时候，重新渲染页面一定是不可取的。

而这时候，最便捷的方式，就是找到该修改的数据所影响到的DOM，然后只更新那一个DOM就可以了。这就是Vue更新页面的方法。

Vue在初始化页面后，会将当前的真实DOM转换为虚拟DOM（Virtual DOM），并将其保存起来，这里称为oldVnode。然后当某个数据发变化后，Vue会先生成一个新的虚拟DOM——vnode，然后将vnode和oldVnode进行比较，找出需要更新的地方，然后直接在对应的真实DOM上进行修改。当修改结束后，就将vnode赋值给oldVnode存起来，作为下次更新比较的参照物。

而这个更新中的难点，也是我们今天要聊的内容，就是新旧vnode的比较，也就是我们常说的Diff算法。

什么是虚拟DOM

前面我们提到了虚拟DOM（Virtual DOM），那虚拟DOM是什么呢？

我们可能曾经打印过真实DOM，它实质上是个对象，但是它的元素是非常的多的，即使是很简单的几句代码。
dom.png

因此，在真实DOM下，我们不太敢随便去直接操作和改动。

这时候，虚拟DOM就诞生了。它也是一个对象，而它其实是将真实DOM的数据抽取出来，以对象的形式模拟树形结构，使其更加简洁明了。

虚拟DOM没有很固定的模板，每个框架上的实现都存在差异，但是大部分结构都是相同的。下面我们就用Vue的虚拟DOM举个例子。

<div id="app">
          <p class="text">HelloWorld</p>
</div>

上面的DOM通过Vue生成了下面的虚拟DOM（有删减），对象中包含了根节点的标签tag、key值，文本信息text等等，同时也含有elm属性存放真实DOM，同时有个children数组，存放着子节点，子节点的结构也是一致的。

{
    "tag": "div",                                          // 标签
    "key": undefined,                              // key值
    "elm": div#app,                                // 真实DOM
    "text": undefined,                             // 文本信息
    "data": {attrs: {id:"app"}},      // 节点属性
    "children": [{                                    // 孩子属性
        "tag": "p",
        "key": undefined,
        "elm": p.text,
        "text": undefined,
        "data": {attrs: {class: "text"}},
        "children": [{
            "tag": undefined,
            "key": undefined,
            "elm": text,
            "text": "helloWorld",
            "data": undefined,
            "children": []
        }]
    }]
}

当我们把一些常用的信息提取出来，并且使用对象嵌套的形式，去存放子节点信息，从而形成一个虚拟DOM,这时候我们用其来进行比较的话，就会比两个真实DOM做比较简单多了。

在Vue中，有个render函数，这个函数返回的VNode就是一个虚拟DOM。当然，你也可以使用virtual-dom或snabbdom去体验一下虚拟DOM。

Diff的实现

在使用Diff算法比较两个节点的时候，只会在同层级进行比较，而不会跨层级比较。

diff.gif

流程

在Vue中，主要是patch()、patchVnode()和updateChildren()这三个主要方法来实现Diff的。

  • 当我们Vue中的响应式数据变化的时候，就会触发页面更新函数updateComponent()（如何触发可以通过阅读Vue源码进行学习或者看一下我之前一篇《简单手写实现Vue2.x》）；
  • 此时updateComponet()就会调用patch()方法，在该方法中进行比较是否为相同节点，是的话执行patchVnode()方法，开始比较节点差异；而如果不是相同节点的话，则进行替换操作，具体后面会讲到；
  • 在patchVnode()中，首先是更新节点属性，然后会判断有没有孩子节点，有的话则执行updateChildren()方法，对孩子节点进行比较；如果没有孩子节点的话，则进行节点文本内容判断更新；（文本节点是不会有孩子节点的）
  • updateChildren()中，会对传入的两个孩子节点数组进行一一比较，当找到相同节点的情况下，调用patchVnode()继续节点差异比较。

diff.jpg

准备工作

为了后面更好的看核心代码，我们先在前面捋清楚一些函数。

isDef 和 isUndef

在源码中会用isDef()和isUndef()判断vnode是否存在，实质上是判断vnode是不是undefined或null，毕竟vnode虚拟DOM是个对象。

export function isUndef (v: any): boolean %checks {
  return v === undefined || v === null
}

export function isDef (v: any): boolean %checks {
  return v !== undefined && v !== null
}

sameVnode

在源码中会用sameVnode()方法去判断两个节点是否相同，实质上是通过去判断key值，tag标签等静态属性从而去判断两个节点是否为相同节点。

注意的是，这里的相同节点不意味着为相等节点，比如<div>HelloWorld</div>和<div>HiWorld</div>为相同节点，但是它们并不相等。在源码中是通过vnode1 === vnode2去判断是不是为相等节点。

// 比较是否相同节点
function sameVnode(a, b) {
    return (
        a.key === b.key &&
        a.asyncFactory === b.asyncFactory && (
            (
                a.tag === b.tag &&
                a.isComment === b.isComment &&
                isDef(a.data) === isDef(b.data) &&
                sameInputType(a, b)
            ) || (
                isTrue(a.isAsyncPlaceholder) &&
                isUndef(b.asyncFactory.error)
            )
        )
    )
}

function sameInputType(a, b) {
    if (a.tag !== 'input') return true
    let i
    const typeA = isDef(i = a.data) && isDef(i = i.attrs) && i.type
    const typeB = isDef(i = b.data) && isDef(i = i.attrs) && i.type
    return typeA === typeB || isTextInputType(typeA) && isTextInputType(typeB)
}

patch

接下来开始看源码了，看看Vue是如何实现Diff算法。

下面的所有代码都只保留核心的代码，想看全部代码可以去看Vue的源码（patch文件路径：https://github.com/vuejs/vue/blob/2.6/src/core/vdom/patch.js）。

首先看看patch()方法，该方法接收新旧虚拟Dom，即oldVnode，vnode，这个函数其实是对新旧虚拟Dom做一个简单的判断，而还没有进入详细的比较阶段。

  • 首先判断vnode是否存在，如果不存在的话，则代表这个旧节点要整个删除；
  • 如果vnode存在的话，再判断oldVnode是否存在，如果不存在的话，则代表只需要新增整个vnode节点就可以；
  • 如果vnode和oldVnode都存在的话，判断两者是不是相同节点，如果是的话，这调用patchVnode方法，对两个节点进行详细比较判断；
  • 如果两者不是相同节点的话，这种情况一般就是初始化页面，此时oldVnode其实是真实Dom，这是只需要将vnode转换为真实Dom然后替换掉oldVnode，具体就不多讲，这不是今天讨论的范围内。
// 更新时调用的__patch__
function patch(oldVnode, vnode, hydrating, removeOnly) {
    // 判断新节点是否存在
    if (isUndef(vnode)) {
        if (isDef(oldVnode)) invokeDestroyHook(oldVnode)  // 新的节点不存在且旧节点存在：删除
        return
    }

        // 判断旧节点是否存在
    if (isUndef(oldVnode)) {
                // 旧节点不存在且新节点存在：新增
        createElm(vnode, insertedVnodeQueue)  
    } else {
        if (sameVnode(oldVnode, vnode)) {
            // 比较新旧节点 diff算法
            patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
        } else {
            // 初始化页面（此时的oldVnode是个真实DOM）
                oldVnode = emptyNodeAt(oldVnode)
            }
            // 创建新的节点
            createElm(
                vnode,
                insertedVnodeQueue,
                oldElm._leaveCb ? null : parentElm,
                nodeOps.nextSibling(oldElm)
            )
        }
    }

    return vnode.elm
}

diff2.jpg

patchVnode

在patchVnode()中，同样是接收新旧虚拟Dom，即oldVnode，vnode；在该函数中，即开始对两个虚拟Dom进行比较更新了。

  • 首先判断两个虚拟Dom是不是全等，即没有任何变动；是的话直接结束函数，否则继续执行；
  • 其次更新节点的属性；
  • 接着判断vnode.text是否存在，即vnode是不是文本节点。是的话，只需要更新节点文本既可，否则的话，这继续比较；
  • 判断vnode和oldVnode是否有孩子节点：
    • 如果两者都有孩子节点的话，执行updateChildren()方法，进行比较更新孩子节点；
    • 如果vnode有孩子节点而oldVnode没有的话，则直接新增所有孩子节点，并将该节点文本属性设为空；
    • 如果oldVnode有孩子节点而vnode没有的话，则直接删除所有孩子节点；
    • 如果两者都没有孩子节点，就判断oldVnode.text是否有内容，有的话清空内容既可。
// 比较两个虚拟DOM
function patchVnode(oldVnode, vnode,  insertedVnodeQueue, ownerArray, index, removeOnly) {
    // 如果两个虚拟DOM一样，无需比较直接返回
    if (oldVnode === vnode) {
        return
    }

    // 获取真实DOM
    const elm = vnode.elm = oldVnode.elm

    // 获取两个比较节点的孩子节点
    const oldCh = oldVnode.children
    const ch = vnode.children

    // 属性更新
    if (isDef(data) && isPatchable(vnode)) {
        for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
        if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode)
    }

    if (isUndef(vnode.text)) {   // 没有文本 -> 该情况一般都是有孩子节点
        if (isDef(oldCh) && isDef(ch)) {  // 新旧节点都有孩子节点 -> 比较子节点
            if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
        } else if (isDef(ch)) {  // 新节点有孩子节点，旧节点没有孩子节点 -> 新增
            if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')  // 如果旧节点有文本内容，将其设置为空
            addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
        } else if (isDef(oldCh)) {   // 旧节点有孩子节点，新节点没有孩子节点 -> 删除
            removeVnodes(oldCh, 0, oldCh.length - 1)
        } else if (isDef(oldVnode.text)) {   // 旧节点有文本，新节点没有文本 -> 删除文本
            nodeOps.setTextContent(elm, '')
        }
    } else if (oldVnode.text !== vnode.text) {  // 新旧节点文本不同 -> 更新文本
        nodeOps.setTextContent(elm, vnode.text)
    }
}

diff3.jpg

updateChildren

最后就来看看updateChildren方法了，这个也是最难理解的一部分，所以就先带大家一步步捋清楚后，手写一下，再看源码。

首先这个方法传入三个比较重要的参数，即parentElm父级真实节点，便于直接节点操作；oldCh为oldVnode的孩子节点；newCh为Vnode的孩子节点。

oldCh和newCh都是一个数组。 这个方法的作用，就是对这两个数组一一比较，找到相同的节点，执行patchVnode再次进行比较更新，剩下的少退多补。

这个方法我们想到最简单的方法，就是两个数组进行遍历匹配，但是这样子的复杂度是很大的，时间复杂度为O(NM)，而且我们真实项目中，页面结构是非常庞大和复杂的，所以这个方案是非常耗性能的。

在Vue中，主要的实现是用四个指针进行实现。四个指针初始位置分别在两个数组的头尾。因此我们先来初始化必要的变量。

let oldStartIdx = 0;                                   // oldCh数组左边的指针位置
let oldStartVnode = oldCh[0];                // oldCh数组左边的指针对应的节点
let oldEndIdx = oldCh.length - 1;         // oldCh数组右边的指针位置
let oldEndVnode = oldCh[oldEndIdx];     // oldCh数组右边的指针对应的节点
let newStartIdx = 0;                                    // newCh数组左边的指针位置
let newStartVnode = newCh[0];                    // newCh数组左边的指针对应的节点
let newEndIdx = newCh.length - 1;            // newCh数组右边的指针位置
let newEndVnode = newCh[newEndIdx];     // newCh数组右边的指针对应的节点

diff4.jpeg

然而这四个指针不会一直不动的，它们会进行相互比较，如果比较得出是相同节点后，对应两个指针就会向另一侧移动，而直至两两重合的时候，这个循环也就结束了。

当然看到这里，你会有很多疑问，但先把疑问记起来，后面都会一一作答的。我们接着写一个循环语句。

while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      // TODO
}

接着我们开始相互比较。

首先是oldStartVnode和newStartVnode进行比较，如果比较相同的话，我们就可以执行patchVnode语句，并且移动oldStartIdx和newStartIdx。

diff2.gif

while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if(sameVnode(oldStartVnode, newStartVnode)){
                patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
            oldStartVnode = oldCh[++oldStartIdx];
            newStartVnode = newCh[++newStartIdx];
      }
}

如果oldStartVnode和newStartVnode匹配不上的话，接下来就是oldEndVnode和newEndVnode做比较了。

diff3.gif

while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if(sameVnode(oldStartVnode, newStartVnode)){
                ...
      }else if(sameVnode(oldEndVnode, newEndVnode)){
            patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
            oldEndVnode = oldCh[--oldEndIdx]
            newEndVnode = newCh[--newEndIdx]
      }
}

但如果两头比较和两尾比较都不是相同节点的话，这时候就开始交叉比较了。首先是oldStartVnode和newEndVnode做比较。

diff4.gif

但交叉比较的时候如果匹配上的话，就需要注意到一个问题，这时候你不仅仅要比较更新节点的内容，你还需要移动节点的位置，因此我们可以借助insertBefore和nextSibling的DOM操作方法去实现，这个自行去学习叭。

while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if(sameVnode(oldStartVnode, newStartVnode)){
                ...
      }else if(sameVnode(oldEndVnode, newEndVnode)){
            ...
      }else if(sameVnode(oldStartVnode, newEndVnode)){
            patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
            // 将oldStartVnode节点移动到对应位置，即oldEndVnode节点的后面
            nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))

            oldStartVnode = oldCh[++oldStartIdx]
            newEndVnode = newCh[--newEndIdx]
      }
}

如果oldStartVnode和newEndVnode匹配不上的话，就oldEndVnode和newStartVnode进行比较。

diff5.gif

while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if(sameVnode(oldStartVnode, newStartVnode)){
                ...
      }else if(sameVnode(oldEndVnode, newEndVnode)){
            ...
      }else if(sameVnode(oldStartVnode, newEndVnode)){
            ...
      }else if(sameVnode(oldEndVnode, newStartVnode)){
            patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
            // 将oldEndVnode节点移动到对应位置，即oldStartVnode节点的前面
            nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)

            oldEndVnode = oldCh[--oldEndIdx]
            newStartVnode = newCh[++newStartIdx]
      }
}

此时，如果四种比较方法都匹配不到相同节点的话，我们就只能使用暴力解法去实现了，也就是针对于newStartVnode这个节点，我们去遍历oldCh中剩余的节点，一一匹配。

在Vue中，我们知道标签会有一个属性——key值，而在同一级的Dom中，如果key有值的话，它必须是唯一的；如果不设值就默认为undefined。所以我们可以先用key来配对一下。

我们可以先生成一个oldCh的key->index的映射表，我们可以创建一个函数createKeyToOldIdx实现，返回的结果用一个变量oldKeyToIdx去存储。

function createKeyToOldIdx(children, beginIdx, endIdx) {
    let i, key
    const map = {}
    for (i = beginIdx; i <= endIdx; ++i) {
        key = children[i].key
        if (isDef(key)) map[key] = i
    }
    return map
}

这时候，如果newStartVnode存在key的话，我们就可以直接用oldKeyToIdx[newStartVnode.key]拿到对应旧孩子节点的下标index。

但如果newStartVnode没有key值的话，就只能通过遍历oldCh中剩余的节点，一一进行匹配获取对应下标index，这个也可以封装成一个函数去实现。

function findIdxInOld(node, oldCh, start, end) {
    for (let i = start; i < end; i++) {
        const c = oldCh[i]
        if (isDef(c) && sameVnode(node, c)) return i
    }
}

这时候我们先继续手写代码。

let oldKeyToIdx, idxInOld;

while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if(sameVnode(oldStartVnode, newStartVnode)){
                ...
      }else if(sameVnode(oldEndVnode, newEndVnode)){
            ...
      }else if(sameVnode(oldStartVnode, newEndVnode)){
            ...
      }else if(sameVnode(oldEndVnode, newStartVnode)){
            ...
      }else{
                // 遍历剩余的旧孩子节点，将有key值的生成index表 <{key: i}>
            if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)

            // 如果newStartVnode存在key，就进行匹配index值；如果没有key值，遍历剩余的旧孩子节点，一一与newStartVnode匹配，相同节点的返回index
            idxInOld = isDef(newStartVnode.key)
                ? oldKeyToIdx[newStartVnode.key]
                : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
      }
}

当然，这个情况下，idxInOld下标值还是有可能为空，这种情况就代表那个newStartVnode是一个全新的节点，这时候我们只需要新增节点就可以了。

如果idxInOld不为空的话，我们就获取对应的oldVnode，然后与newStartVnode进行比较，如果是相同节点的话，调用patchVnode()函数， 并且将对应的oldVnode设置为undefined；如果匹配出来时不同节点，那就直接创建一个节点既可。

最后，移动一下newStartIdx。

let oldKeyToIdx, idxInOld, vnodeToMove;

while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if(sameVnode(oldStartVnode, newStartVnode)){
                ...
      }else if(sameVnode(oldEndVnode, newEndVnode)){
            ...
      }else if(sameVnode(oldStartVnode, newEndVnode)){
            ...
      }else if(sameVnode(oldEndVnode, newStartVnode)){
            ...
      }else{
                // 遍历剩余的旧孩子节点，将有key值的生成index表 <{key: i}>
            if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)

            // 如果newStartVnode存在key，就进行匹配index值；如果没有key值，遍历剩余的旧孩子节点，一一与newStartVnode匹配，相同节点的返回index
            idxInOld = isDef(newStartVnode.key)
                ? oldKeyToIdx[newStartVnode.key]
                : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
            if (isUndef(idxInOld)) { 
                // 如果匹配不到index，则创建新节点
                createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
            } else {
                // 获取对应的旧孩子节点
                vnodeToMove = oldCh[idxInOld]
                if (sameVnode(vnodeToMove, newStartVnode)) {
                    patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
                    // 因为idxInOld是处于oldStartIdx和oldEndIdx之间，因此只能将其设置为undefined，而不是移动两个指针
                    oldCh[idxInOld] = undefined
                    nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
                } else {
                    // 如果key相同但节点不同，就创建一个新的节点
                    createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
                }
            }
            // 移动新节点的左边指针
            newStartVnode = newCh[++newStartIdx]
      }
}

diff6.gif

这里有个重点，如果我们匹配到对应的oldVnode的话，需要将其设置为undefined，同时当后面我们的oldStartIdx和oldEndIdx移动后，如果判断出对应的vnode为undefined时，就需要选择跳过。

let oldKeyToIdx, idxInOld, vnodeToMove;

while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) {
                // 当oldStartVnode为undefined的时候，oldStartVnode右移
                oldStartVnode = oldCh[++oldStartIdx] 
      } else if (isUndef(oldEndVnode)) {
                // 当oldEndVnode为undefined的时候，oldEndVnode左移
                oldEndVnode = oldCh[--oldEndIdx]
      } else if(sameVnode(oldStartVnode, newStartVnode)){
                ...
      }else if(sameVnode(oldEndVnode, newEndVnode)){
            ...
      }else if(sameVnode(oldStartVnode, newEndVnode)){
            ...
      }else if(sameVnode(oldEndVnode, newStartVnode)){
            ...
      }else{
                ...
      }
}

diff7.gif

diff8.gif

到这个时候，我们已经完成的差不多了，只剩下最后的收尾工作了。

如果这时候，oldCh的两个指针已经重叠并越过，而newCh的两个指针还未重叠；或者说是相反情况下。

diff5.jpeg

这时候，如果oldCh有多余的vnode，我们只需要将其都删除既可；如果是newCh有多余的vnode，我们只需新增它们就可以了。

let oldKeyToIdx, idxInOld, vnodeToMove, refElm;

while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) {
                ...
      } else if (isUndef(oldEndVnode)) {
                ...
      } else if(sameVnode(oldStartVnode, newStartVnode)){
                ...
      }else if(sameVnode(oldEndVnode, newEndVnode)){
            ...
      }else if(sameVnode(oldStartVnode, newEndVnode)){
            ...
      }else if(sameVnode(oldEndVnode, newStartVnode)){
            ...
      }else{
                ...
      }

      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)
           }
}

这时候，我们就完成了updateChildren()方法了，整体代码如下：

// 比较两组孩子节点
function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
    // 设置首尾4个指针和对应节点
    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]

    // diff查找是所需的变量
    let oldKeyToIdx, idxInOld, vnodeToMove, refElm

    // 循环结束条件：新旧节点的头尾指针都重合
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
        if (isUndef(oldStartVnode)) {
            // 当oldStartVnode为undefined的时候，oldStartVnode右移
            oldStartVnode = oldCh[++oldStartIdx] 
        } else if (isUndef(oldEndVnode)) {
            // 当oldEndVnode为undefined的时候，oldEndVnode左移
            oldEndVnode = oldCh[--oldEndIdx]
        } else if (sameVnode(oldStartVnode, newStartVnode)) {
            // 当oldStartVnode与newStartVnode节点相同，对比节点
            patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
            // 对应两个指针更新
            oldStartVnode = oldCh[++oldStartIdx]
            newStartVnode = newCh[++newStartIdx]
        } else if (sameVnode(oldEndVnode, newEndVnode)) {
            // 当oldEndVnode与newEndVnode节点相同，对比节点
            patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
            // 对应两个指针更新
            oldEndVnode = oldCh[--oldEndIdx]
            newEndVnode = newCh[--newEndIdx]
        } else if (sameVnode(oldStartVnode, newEndVnode)) {
            // 当oldStartVnode与newEndVnode节点相同，对比节点
            patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
            // 将oldStartVnode节点移动到对应位置，即oldEndVnode节点的后面
            nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
            // 对应两个指针更新
            oldStartVnode = oldCh[++oldStartIdx]
            newEndVnode = newCh[--newEndIdx]
        } else if (sameVnode(oldEndVnode, newStartVnode)) {
            // 当oldEndVnode与newStartVnode节点相同，对比节点
            patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
            // 将oldEndVnode节点移动到对应位置，即oldStartVnode节点的前面
            nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
            // 对应两个指针更新
            oldEndVnode = oldCh[--oldEndIdx]
            newStartVnode = newCh[++newStartIdx]
        } else {   // 暴力解法 使用key匹配
            // 遍历剩余的旧孩子节点，将有key值的生成index表 <{key: i}>
            if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)

            // 如果newStartVnode存在key，就进行匹配index值；如果没有key值，遍历剩余的旧孩子节点，一一与newStartVnode匹配，相同节点的返回index
            idxInOld = isDef(newStartVnode.key)
                ? oldKeyToIdx[newStartVnode.key]
                : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)

            if (isUndef(idxInOld)) { 
                // 如果匹配不到index，则创建新节点
                createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
            } else {
                // 获取对应的旧孩子节点
                vnodeToMove = oldCh[idxInOld]
                if (sameVnode(vnodeToMove, newStartVnode)) {
                    patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
                    // 因为idxInOld是处于oldStartIdx和oldEndIdx之间，因此只能将其设置为undefined，而不是移动两个指针
                    oldCh[idxInOld] = undefined
                    nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
                } else {
                    // 如果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)
    }
}

流程图

diff6.png

为什么要用key值

我们在前面的sameVnode()可以看到，我们在比较两个节点是否相同的时候，第一个判断条件就是vnode.key；并且在后面使用暴力解法的时候，第一选择也是通过key去匹配，而这样会有什么好处呢？我们通过下面一个简单的例子来解答这个问题叭。

假设我们此时的新旧节点如下：

<!--  old  -->
<div>
      <p>A</p>
      <p>B</p>
      <p>C</p>
</div>

<!--  new  -->
<div>
      <p>B</p>
      <p>C</p>
      <p>A</p>
</div>

在上面的例子，我们可以看出，<p>A</p>被移动到最后面去了。

但如果我们没有设置key值的话，通过diff需要操作Dom的次数会很多，因为当key为undefined的情况下，每个p标签其实都是相同节点，因此这是执行diff的话，它会将第一个A改成B，把第二个B改成C，把第三个C改成A，这时一共操作了三次Dom。

diff9.gif

但如果，我们分别给对应添加了key值，通过diff只需操作一次Dom，即将第一个节点移动到最后既可。

diff10.gif