diff算法

[cheny88]

并不是vue专用的，其他的框架也在用

必要性：（源码中的mountComponent()）vue中一个组件有一个Watcher，一一对应的关系，为了精确的知道在更新的过程中到底谁发生了变化，所以要使用diff。
执行方式：（源码中的patchVnode()）patchVnode()是diff发生的地方。整体策略：深度优先，同层比较
高效性：（源码中的updateChildren()）

当修改数据触发了setter，setter会触发通知，通知的触发方式是尝试把Watcher添加到异步更新队列，在每一次事件循环结束时要清空队列，清空队列的过程中，所有的Watcher尝试它们的更新函数，更新函数在执行时调用了组件的渲染函数以及组件的更新函数，这时候会重新渲染最新的虚拟DOM，然后执行更新函数比较新旧虚拟DOM，此时diff真正的触发了。

结论：

• diff算法是虚拟DOM技术的必然产物：通过新旧虚拟DOM做对比（即diff），将变化的地方更新在真实DOM上；另外，也需要diff高效的执行对比过程，从而降低时间复杂度为O(n)。
• vue2中为了降低Watcher粒度，每个组件只有一个Watcher与之对应，只有引入diff才能精确找到发生变化的地方。
• vue中diff执行的时刻是组件实例执行其更新函数时，它会比对上一次渲染结果oldVnode和新的渲染结果newVnode，此过程称为patch。
• diff过程整体遵循深度优先、同层比较的策略；两个节点之间比较会根据它们是否拥有子节点或者文本节点做不同操作；比较两组子节点是算法的重点，首先假设头尾节点可能相同做4次比对尝试，如果没有找到相同节点才按照通用方式遍历查找，查找结果再按情况处理剩下的节点（要么是批量删除，要么是批量新增）；借助key通常可以非常精确找到相同节点，因此整个patch过程非常高效。