Vue和React都是基于vdom的前端框架。组件渲染会返回vdom，渲染器会通过增删改查的api将vdom同步到dom。再次渲染时，会生成一个新的vdom，renderer会比较两棵vdom树，针对差异通过增删改api来更新dom。这里，比较两棵vdom树，找出不同部分的算法称为diff算法。diff算法是渲染器中最复杂的部分，也是面试的热门话题。今天我们就通过Vue的diff算法来探究diff算法。Diff算法我们知道，比较两棵树的复杂度是O(n^3)，因为每个节点都要和另一棵树的所有节点比较一次，也就是n。如果找到一个变化的节点，执行插入、删除和修改也是一个n的复杂度。所有节点都是这样，然后乘以n，所以是O(n*n*n)复杂度。这样的复杂度对于前端框架来说是无法接受的，也就是说对于1000个节点，渲染会处理1000*1000*1000次，总共10亿次。因此，前端框架的diff约定了两个处理原则：只比较同一层，如果类型发生变化不再比较子节点。因为dom节点的跨层级移动还是比较少见的，一般来说就是dom在同层级的增删改查。这样只需要遍历一次，比较类型即可。复杂度为O(n)，如果类型发生变化，就不再比较子节点，可以省去大量的节点遍历。另外，由于关联的dom节点记录在vdom中，所以dom的增删改查不需要遍历，为O(1)，整体diff算法复杂度为O(n)。1000个节点一次最多可以渲染1000次，这个复杂度是可以接受的。然而，尽管这种算法的复杂度较低，但仍然存在问题。比如一组节点，假设有5个节点，类型是ABCDE，接下来渲染会是EABCD。这时候如果一一比较，发现类型不一样，就会重新渲染这5个节点。并且根据不再根据不同类型比较子节点的原则，如果这些节点有子节点，也会重新渲染。DOM操作比较慢，所以虽然diff的算法复杂度低，但是重新渲染的性能不高。因此，diff算法除了考虑自身的时间复杂度外，还需要考虑一个因素：dom操作的次数。上例中的ABCDE变为EABCD。显然，你只需要移动E，根本不需要创建新的元素。但是如何比较同一个节点的移动呢？你会判断类型吗？那不行，同类型的节点可能有很多，无法区分。每个节点最好有一个唯一的标识符。所以在渲染一组节点时，前端框架会让开发者指定一个key，通过key来判断一些节点是否刚刚移动过，这样就可以直接复用了。这样，diff算法在处理一组节点的比较时，需要根据key再次优化算法。我们将两组节点的基于key的diff算法称为多节点diff算法，它是整个vdomdiff算法的一部分。接下来学习多节点diff算法：简单diff假设渲染了一组ABCD节点，第二次渲染是DCAB。这个时候怎么处理呢？多节点diff算法的目的是尽可能重用节点，通过移动节点来代替创建。因此，对于新的vnode数组中的每一个节点，我们都要去查找旧的vnode数组中是否有对应的key，如果有就移动到新的位置，如果没有就新建一个。就是这样：constoldChildren=n1.childrenconstnewChildren=n2.childrenletlastIndex=0//遍历新的childrenfor(leti=0;ivnode.key===oldVNode.key)if(!has){//ifIf没有找到相同的节点，去掉unmount(oldVNode)}}这样我们就完成了两组vnode的diff和对应dom的增删改查。总结一下：diff算法的目的是根据key重用dom节点，通过移动节点而不是创建新节点来减少dom操作。对于每一个新的vnode，根据旧vnode中的key进行查找，如果没有找到，则添加一个新的dom节点，如果找到，就可以复用。对于复用，是否移动取决于下标。如果下标在lastIndex之后，就不用移动了，因为已经在后面了，否则就需要移动。最后，将不在新vnode中的旧vnode中的节点从dom树中删除。这是diff算法的完整实现。我们从一端一一处理这种diff算法，称为简单diff算法。简单diff算法的性能实际上并不是最好的。比如旧的vnode数组是ABCD，新的vnode数组是DABC。根据简单的diff算法，A、B、C都需要移动。那么如何优化这个算法呢？从一个方向依次处理会有这个问题，但是同时从两个方向比较呢？这就是双端diff算法：双端diff简单的diff算法可以实现dom节点的复用，但是有时候会做一些不必要的动作。双端diff算法通过比较两端的数据来解决这个问题。我们需要4个指针，分别指向新旧vnode数组的头尾：头尾的指针往中间移动，直到oldStartIdx<=oldEndIdx和newStartIdx<=newEndIdx，表示所有节点都处理完了.每次比较两个head指针指向的节点，两个tail指针指向的节点，head和tail指向的节点是否有相同的key，即可重用。如果是reusable，直接使用，调用patch更新，如果是head和tail，需要移动位置。下载下载：while(oldStartIdx<=oldEndIdx&&newStartIdx<=newEndIdx){if(oldStartVNode.key===newStartVNode.key){//头patch(oldStartVNode,newStartVNode,container)oldStartVNode=oldChildren[++oldStartIdx]newStartVNode=newChildren[++newStartIdx]}elseif(oldEndVNode.key===newEndVNode.key){//尾尾patch(oldEndVNode,newEndVNode,container)oldEndVNode=oldChildren[--oldEndIdx]newEndVNode=newChildren[--newEndIdx]}elseif(oldStartVNode.key===newEndVNode.key){//头尾，电影电影的TVpatch(oldStartVNode,newEndVNode,container)insert(oldStartVNode.el,container,oldEndVNode.el.nextSibling)oldStartVNode=oldChildren[++oldStartIdx]newEndVNode=newChildren[--newEndIdx]}elseif(oldEndVNode.key===newStartVNode.key){//尾头，电影电影补丁(oldEndVNode,newStartVNode,container)insert(oldEndVNode.el,container,oldStartVNode.el)oldEndVNode=oldChildren[--oldEndIdx]newStartVNode=newChildren[++newStartIdx]}else{//head和tail处没有找到可重用的节点}}head和tail的比较比较简单，head和tail的比较需要移动下一个节点。比如oldvnode的头节点是，如果是newvnode的尾节点，就必须移动到oldvnode尾节点的位置。即：insert(oldStartVNode.el,container,oldEndVNode.el.nextSibling)插入节点的锚节点为oldEndVNode对应的dom节点的nextSibling。如果旧vnode的尾节点是新vnode的头节点，则必须移动到旧vnode的头节点。即：insert(oldEndVNode.el,container,oldStartVNode.el)插入节点的锚节点为oldStartVNode对应的dom节点（因为需要在它之前插入）。从两端比较可以尽可能减少节点移动的次数。当然，还需要处理两端都没有可重用节点的情况：如果两端都没有可重用节点，则在旧节点数组中查找，找到则移动，并将原始位置设置为未定义。如果没有找到，则插入一个新节点。就是这样：constidxInOld=oldChildren.findIndex(node=>node.key===newStartVNode.key)if(idxInOld>0){constvnodeToMove=oldChildren[idxInOld]patch(vnodeToMove,newStartVNode,container)insert(vnodeToMove.el,container,oldStartVNode.el)oldChildren[idxInOld]=undefined}else{patch(null,newStartVNode,container,oldStartVNode.el)}因为有一些未定义的节点，需要加入空节点的处理逻辑：if(!oldStartVNode){oldStartVNode=oldChildren[++oldStartIdx]}elseif(!oldEndVNode){oldEndVNode=newChildren[--oldEndIdx]}这样就完成了节点复用和移动的逻辑。那些真正没有可重用节点的节点呢？在上一次移动之后，剩余的节点被移动到中间。如果有剩余的新vnode，它们将被分批添加。如果还有旧的vnode，会被批量删除。因为上一个循环的判断条件是oldStartIdx<=oldEndIdx&&newStartIdx<=newEndIdx，所以如果oldvnode太多，最后newStartIdx会小于newEndIdx。如果新的vnode太多，最后的oldStartIdx会小于oldEndIdx。所以判断条件是这样的：if(oldEndIdx
