Vue和React都是基于vdom的前端框架，组件渲染会返回vdom，渲染器再把vdom通过增删改的api同步到dom。当再次渲染时，会产生新的vdom，渲染器会对比两棵vdom树，对有差异的部分通过增删改的api更新到dom。这里对比两棵vdom树，找到有差异的部分的算法，就叫做diff算法。

当我们当前组件所依赖的数值更新和组件创建时运行update函数，update函数会调用组件的render函数，render生成新的虚拟dom树，update的到新虚拟dom树的根节点，然后进入update函数内部，将_vnode也就是旧虚拟dom树替换成新的虚拟dom树，然后用一个变量将旧虚拟dom树保存起来，接下来调用patch函数进行diff比对，vue在进行比对时遵循以下原则：1.尽量不动2.能修改属性修改属性3.能移动dom移动dom4.实在不行再删除或新增真实dom然后vue的diff会根据新旧domTree进行深度优先同层比对，如果父节点比对发现不同则父节点的所有子节点无需进行比对跟着父节点一起死去，如果父节点比对发现相同则继续往下比对父节点的子节点然后再进行下一个父节点的子节点进行比较，以此递归比较下去，比较时首先会比较标签名是否一致，然后会比较元素的key值是否相同，如果是input元素则还会比较type类型，如果都相同表示相同，如果有一个不相同表示不相同，vue的diff算法会在新旧dom树的头尾处记录头尾指针位置，相互聚拢，逐渐比较，来保证真实dom的高复用，当新虚拟dom树的头指针大于新虚拟dom树的尾指针则表示新虚拟dom树比对完成，diff结束，然后vue会根据新虚拟dom树的比对结果的真实dom树加入根节点中完成页面真实dom渲染完毕。

diff算法的目的是根据key复用dom节点，通过移动节点而不是创建新节点来减少dom操作。对于每个新的vnode，在旧的vnode中根据key查找一下，如果没查找到，那就新增dom节点，如果查找到了，那就可以复用。复用的话要不要移动要判断下下标，如果下标在lastIndex之后，就不需要移动，因为本来就在后面，反之就需要移动。最后，把旧的vnode中在新vnode中没有的节点从dom树中删除。

vue2是用的双端diff的算法。双端diff是头尾指针向中间移动的同时，对比头头、尾尾、头尾、尾头是否可以复用，如果可以的话就移动对应的dom节点。如果头尾没找到可复用节点就遍历vnode数组来查找，然后移动对应下标的节点到头部。最后还剩下旧的vnode就批量删除，剩下新的vnode就批量新增。