首先进行总结

diff算法的本质是找出两个对象之间的差异
diff算法的核心是子节点数组对比，思路是通过首尾两端对比
key的作用主要是
- 决定节点是否可以复用
- 建立key-index的索引，主要是替代遍历，提升性能。

diff算法的作用

渲染真实DOM的开销很大，有时候我们修改了某个数据，直接渲染到真实dom上会引起整个dom树的重绘和重排。我们希望只更新我们修改的那一小块dom，而不是整个dom，diff算法就帮我们实现了这点。
diff算法的本质就是：找出两个对象之间的差异，目的是尽可能做到节点复用。
此处说到的对象，指的其实就是vue中的virtual dom（虚拟dom树），即使用js对象来表示页面中的dom结构。

真实dom与虚拟dom

如下一个真实dom节点：

<div id='app'>
   <span id='child'>1</span>
 </div>

可见，一个dom节点主要包含以下三个部分：

自身的标签名（div）
自身的属性（id='app'）
子节点（span）
那我们怎么用js对象结构来表示这样一个dom节点呢？如下即可：

const vnode = {
    tag: 'div', // 自身的标签名
    attts: {id:'app'}, // 自身的属性
    children: [{
        tag:'span', attrs: {id:'child'}, chidlren: ['1']
    }] // 自身的子节点
}

那么当用户对界面进行操作，比如把div的id改为app2，将子节点span的文本子节点1改为2，那么我们就能得到如下vnode：

const vnode = {
    tag: 'div', // 自身的标签名
    attts: {id:'app2'}, // 自身的属性
    children: [{
        tag:'span', attrs: {id:'child'}, chidlren: ['2']
    }] // 自身的子节点
}

我们已经提到，diff算法的本质是找出两个对象之间的差异，目的是尽可能做到节点复用。那么我们运行diff(vnode, vnode2)就能知道vnode与vnode2之间的差异为：

div的id由app改为了app2
span的文本子节点由1改为了2

知道了以上的差异部分，就能根据这些差异来进行视图的局部更新：

document.getElementById('app').setAttribute('id, 'app2') // id改为app2
document.getElementById('child').firstChild.textContent = '2' // 1改为2

在我们改变一个节点的时候，我们其实主要改动了以下两部分：

自身的属性（style、class等）
子节点

那么diff算法就可以抽象为两部分：

function diff(vnoe, newVnode) {
    diffAttr(vnode.attr, newVnode.attr)
    diffChildren(vnode.children, newVnode.children)
}

在vue之前的源码中，是先用diff得到差异，再根据差异去patch真实dom，也就是分两步：

diff
patch

但这样性能上会有损失，因为diff过程中会遍历一整个dom树，patch的时候又会再遍历一遍，其实这两次遍历可以合并成一次，也就是在diff的同时进行patch。
所以我们可以把流程改进为：

    function patchVnode(oldVnode, vnode, parentElm) {
        patchAttr(oldVnode.attr, vnode.attr, parentElm)
        patchChildren(parentElm, oldVnode.children, vnode.children)
    }

patchAttr

    function patchAttr(oldVnode={}, vnode={}, parentElm) {
        each(oldVnode, (key, val) => { // 遍历oldVnode，看newTreeAttr是否还有对应的属性
            if (vnode[key]) {
                val !== vnode[key] && setAttr(parentElm, key, vnode[key])
            }
            else {
                parentElm.removeAttribute(key)
            }
        })

        each(vnode, (key, val) => { // 看oldVnode是否还有对应的属性，没有就新增。
            !oldVnode[key] && setAttr(parentElm, key, val)
        })
    }

    function each(obj, fn) { // 遍历对象
        if (Object.prototype.toString.call(obj) !== '[object object]') {
            console.error('只能遍历对象！')
            return
        }

        for (var key in obj) {
            if (obj.hasOwnProperty(key)) {
                var val = obj[key]
                fn(key, val)
            }
        }
    }

    function setAttr(node, key, value) {
        switch (key) {
            case 'style':
                each(value, (key, val) => {
                    node.style[key] = val
                })
                break
            case 'value':
                var tag = node.tag || ''
                tag = tag.toLowerCase()
                if (
                        tag === 'input' || tag === 'textarea'
                ) {
                    node.value = value
                } else {
                    // if it is not a input or textarea, use 'setAttribute' to set
                    node.setAttribute(key, value)
                }
                break
            default:
                node.setAttribute(key, value)
                break
        }
    }

该函数主要做了如下几件事：

遍历oldVnode，看newTreeAttr是否还有对应的属性；
如果有并且不相等，则修改对应的属性；
如果没有，则直接删除对应的属性；
遍历oldVnode，是否还有对应的属性，没有就新增。

patchChildren

    function patchChildren(parentElm, oldCh, newCh) {
        let oldStartIdx = 0;
        let oldEndIdx = oldCh.length - 1;
        let oldStartVnode = oldCh[0];
        let oldEndVnode = oldCh[oldEndIdx];

        let newStartIdx = 0;
        let newEndIdx = newCh.length - 1;
        let newStartVnode = newCh[0];
        let newEndVnode = newCh[newEndIdx];
        let oldKeyToIdx, idxInOld, elmToMove, refElm;

        while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
            if (!oldStartVnode) {
                oldStartVnode = oldCh[++oldStartIdx];
            } else if (!oldEndVnode) {
                oldEndVnode = oldCh[--oldEndIdx];
            }

            else if (sameVnode(oldStartVnode, newStartVnode)) { //旧首 和 新首相同
                patchVnode(oldStartVnode.elm, oldStartVnode, newStartVnode);
                oldStartVnode = oldCh[++oldStartIdx];
                newStartVnode = newCh[++newStartIdx];
            }

            else if (sameVnode(oldEndVnode, newEndVnode)) { //旧尾 和 新尾相同
                patchVnode(oldEndVnode.elm, oldEndVnode, newEndVnode);
                oldEndVnode = oldCh[--oldEndIdx];
                newEndVnode = newCh[--newEndIdx];
            }

            else if (sameVnode(oldStartVnode, newEndVnode)) { //旧首 和 新尾相同,将旧首移动到 最后面
                patchVnode(oldStartVnode.elm, oldStartVnode, newEndVnode);
                nodeOps.insertBefore(parentElm, oldStartVnode.elm, oldEndVnode.elm.nextSibling)//将 旧首 移动到最后一个节点后面
                oldStartVnode = oldCh[++oldStartIdx];
                newEndVnode = newCh[--newEndIdx];
            }

            else if (sameVnode(oldEndVnode, newStartVnode)) {//旧尾 和 新首相同 ,将 旧尾 移动到 最前面
                patchVnode(oldEndVnode.elm, oldEndVnode, newStartVnode);
                nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
                oldEndVnode = oldCh[--oldEndIdx];
                newStartVnode = newCh[++newStartIdx];
            }

            else {//首尾对比 都不 符合 sameVnode 的话
                //1. 尝试 用 newCh 的第一项在 oldCh 内寻找 sameVnode
                let elmToMove = oldCh[idxInOld];
                if (!oldKeyToIdx) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
                idxInOld = newStartVnode.key ? oldKeyToIdx[newStartVnode.key] : null;
                if (!idxInOld) {//如果 oldCh 不存在 sameVnode 则直接创建一个
                    nodeOps.createElm(newStartVnode, parentElm);
                    newStartVnode = newCh[++newStartIdx];
                } else {
                    elmToMove = oldCh[idxInOld];
                    if (sameVnode(elmToMove, newStartVnode)) {
                        patchVnode(elmToMove, newStartVnode);
                        oldCh[idxInOld] = undefined;
                        nodeOps.insertBefore(parentElm, newStartVnode.elm, oldStartVnode.elm);
                        newStartVnode = newCh[++newStartIdx];
                    } else {
                        nodeOps.createElm(newStartVnode, parentElm);
                        newStartVnode = newCh[++newStartIdx];
                    }
                }
            }
        }

        if (oldStartIdx > oldEndIdx) {
            refElm = (newCh[newEndIdx + 1]) ? newCh[newEndIdx + 1].elm : null;
            nodeOps.addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx);
        } else if (newStartIdx > newEndIdx) {
            nodeOps.removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
        }


    }

上述代码的本质是找出两个数组的差异
比如说：

旧数组[a, b, c, d]
新数组[e, f, g, h]

怎么找出新旧数组之间的差异呢？可以定义以下名词：

旧首（旧数组的第一个元素）
旧尾（旧数组的最后一个元素）
新首（新数组的第一个元素）
新尾（新数组的最后一个元素）

代码中的一些函数工具：

sameVnode：用于判断字节是否应该复用，此处做了一些简化，实际的diff算法要更复杂一些。这里只用tag和key相同我们就复用，执行patchVnode，即对节点进行修改。

function sameVnode(a, b) {
  return a.key === b.key && a.tag === b.tag
}

createKeyToOldIdx：建立key-index的索引，主要是替代遍历，提升性能。

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
}

旧首和新首对比

if (sameVnode(oldStartVnode, newStartVnode)) { 
      patchVnode(oldStartVnode.elm, oldStartVnode, newStartVnode);
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];
    }

旧尾和新尾对比

if (sameVnode(oldEndVnode, newEndVnode)) { //旧尾 和 新尾相同
      patchVnode(oldEndVnode.elm, oldEndVnode, newEndVnode);
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];
    }

旧首和新尾对比

if (sameVnode(oldStartVnode, newEndVnode)) { //旧首 和 新尾相同,将旧首移动到 最后面
      patchVnode(oldStartVnode.elm, oldStartVnode, newEndVnode);
      nodeOps.insertBefore(parentElm, oldStartVnode.elm, oldEndVnode.elm.nextSibling)
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
    }

旧尾和新首对比；将旧尾移动到最前面

if (sameVnode(oldEndVnode, newStartVnode)) {//旧尾 和 新首相同 ,将 旧尾 移动到 最前面
      patchVnode(oldEndVnode.elm, oldEndVnode, newStartVnode);
      nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    }

首位对比都不符合 sameVnode的话

尝试用newCh的第一项在oldCh内寻找sameVnode，如果在oldCh不存在对应的sameVnode，则直接创建一个，存在的话则判断；
符合sameVnode，则移动oldCh对应的节点；
不符合sameVnode，则创建新节点。

最后通过oldStartIdx > oldEndIex，来判断oldCh和newCh哪一个先遍历完成

oldCh先遍历完成，则证明newCh还有多余的节点，需要新增这些节点；
newCh先遍历完成，则证明oldCh还有多余节点，需要删除这些节点。

diff算法原理