virtual DOM及diff算法

什么是virtual dom？

从本质上而言，Vdom只是一个用于描述DOM节点的原生JS对象，并且最少包括tag，props，和children三个属性，下面是一个经典的Vdom例子：

{
    tag: "div",
    props: {},
    children: [
        "Hello World", 
        {
            tag: "ul",
            props: {},
            children: [{
                tag: "li",
                props: {
                    id: 1,
                    class: "li-1"
                },
                children: ["第", 1]
            }]
        }
    ]
}

Vdom和实际的dom对象有着意一一对应的关系，上述的Vdom就是由以下HTML生成的

<div>
    Hello World
    <ul>
        <li id="1" class="li-1">
            第1
        </li>
    </ul>

当数据发生变化时，Vue如何更新节点？

渲染真实的DOM的开销是很庞大的，如果直接渲染到真实的DOM上会引起整个DOM树的重排重绘，通过diff算法来实现只更新一小块DOM而不更新整个DOM。首先，根据真实的DOM生成一颗Virtual DOM。当vitrual DOM的某个节点的数据发生变化的时候会生成一个新的VNode。(vue.js中采用createElement方法来创建Vnode)。然后Vnode和old vnode做对比，发现有不一样的地方就修改在真实的DOM上，然后使old Vnode的值为Vnode。

diff算法的过程就是调用名为patch的函数，比较新旧节点，一边比较，一边给真实的节点打补丁。

注意

1. Vnode和old vnode都是对象
2. 在采用diff算法进行新旧节点比较的时候，比较只会在同一层级上比较，不会跨层级去比较。

patch函数有两个参数，Vnode和old Vnode也就是新旧俩个虚拟节点，具体而言有两个步骤：

1. 判断两个节点是否值得比较，值得比较就调用patch vnode算法（此处调用的是sameVnode函数）

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)
            )
        )
    )
}
sameVnode的逻辑比较简单，如果两个vnode的key不相等，则是不等的，否则继续判断tag值，data等类型是否相等

1. 不值得比较就直接用VNode替换掉old Vnode

patchVnode做的事情：

1. 找到old vnode对应的真实Vdom，称为el
2. 如果oldVnode===vnode，他们的引用一致，可以认为没有变化，则直接return
3. 如果两者都有文本节点，且文本节点不相等，则将el的文本节点设置为vnode的文本节点
4. 如果新节点有子节点而oldnode没有子节点，则将vnode的子节点真实化后添加到el上
5. 如果新节点没有子节点而oldnode有子节点，则将el的子节点删除掉
6. 如果两者都有子节点，则调用updatechildren函数比较子节点。

updateChildren函数的作用

1. 处理头部的同类型节点：即oldStart和newStart指向同类节点的情况。—->将oldStart和newStart向后移动一位
2. 处理尾部的同类型节点：即oldEnd和newEnd指向同类节点的情况。—->将oldEnd和newEnd向前移动一位。
3. 处理头尾/尾头的同类型节点：即oldStart和newEnd以及oldEnd和newStart指向同类节点的情况。

节点2后移到oldEnd指向的节点（节点9）的后面，移动后标记该节点，并将oldstart后移一位，newEnd前移一位，变为：

同样地，节点9也是类似的处理，处理完之后成了下面这样

newStart来到了节点11的位置，在oldVdom中找不到节点11，说明它是新增的。那么就创建一个新的节点，插入DOM树，插到什么位置？插到oldStart指向的节点（即节点3）前面，然后将newStart后移1位标记为已处理（注意oldVdom中没有节点11，所以标记过程中它的指针不需要移动），处理之后如下图

处理更新的节点：

经过第（4）步之后，newStart来到了节点7的位置，在oldVdom中能找到它而且不在指针位置（查找oldVdom中oldStart到oldEnd区间内的节点），说明它的位置移动了，那么需要在DOM树中移动它，移到哪里？移到oldStart指向的节点（即节点3）前面。与此同时将节点标记为已处理

处理之后就成了下面这样：

处理需要删除的节点：

经过前面处理之后，newStart跨过了newEnd，它们相遇啦！而这个时候，oldStart和oldEnd还没有相遇，说明这2个指针之间的节点（包括它们指向的节点，即上图中的节点7、节点8）是此次更新中被删掉的节点。

OK，那我们在DOM树中将它们删除，再回到前面我们对节点7做了标记，为什么标记是必需的？标记的目的是告诉Vue它已经处理过了，是需要出现在新DOM中的节点，不要删除它，所以在这里只需删除节点8。

在应用中也可能会遇到oldVdom的起止点相遇了，但是newVdom的起止点没有相遇的情况，这个时候需要对newVdom中的未处理节点进行处理，这类节点属于更新中被加入的节点，需要将他们插入到DOM树中。

key的作用

key的作用是给每个节点做一个唯一标识，从而在diff算法执行时更快的找到对应的节点，提高diff速度。

在交叉对比的时候，当新节点跟旧节点头尾交叉对比没有结果的时候，会根据新节点的key去对比旧节点数组中的key，从而找到相应的旧节点，如果没找到就认为是新增加一个节点，而如果没有key，就会采用遍历查找的方式去找对应的旧节点。