diff算法知多少

不念不忘少年蓝@ 2023-01-17 07:49 84阅读 0赞

# diff算法知多少 #

## 一、虚拟DOM ##

> 什么是虚拟DOM？  
> 虚拟DOM就是把真实DOM树的结构和信息抽象出来，以对象的形式模拟树形结构

如下：

真实DOM:

<div>
        <p>Hello World</p>
    </div>

对应的虚拟DOM就是：

let vnode = { 
        tag: 'div',
        children:[ { tag:'p', text:'Hello World'}]
    }

> 为什么需要虚拟DOM？  
> 渲染真实DOM会有一定的开销，如果每次修改数据都进行真实DOM渲染，都会引起DOM树的重绘和重排，性能开销很大。那么有没有可能只修改一小部分数据而不渲染整个DOM呢？虚拟DOM和Diff算法可以实现。

> 怎么实现？
> 
> > 先根据真实DOM生成一颗虚拟DOM树  
> > 当某个DOM节点数据发生改变时，生成一个新的Vnode  
> > 新的Vnode和旧的oldVnode进行对比  
> > 通过patch函数一边比对一边给真实DOM打补丁或者创建Vnode、移除oldVnode等  
> > 有什么不一样？  
> > 真实DOM操作为一个属性一个属性去修改，开销较大。  
> > 虚拟DOM直接修改整个DOM节点再替换真实DOM  
> > 还有什么好处？  
> > Vue的虚拟DOM数据更新机制是异步更新队列，并不是数据变更马上更新DOM，而是被推进一个数据更新异步队列统一更新。想要马上拿到DOM更新后DOM信息？有个API叫 Vue.nextTick

## 二、 Diff算法 ##

### 传统Diff算法 ###

> 遍历两棵树中的每一个节点，每两个节点之间都要做一次比较。  
> 比如 a->e 、a->d 、a->b、a->c、a->a

*  遍历完成的时间复杂度达到了O(n^2)
 *  对比完差异后还要计算最小转换方式，实现后复杂度来到了O(n^3)  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1ajE5MzU_size_16_color_FFFFFF_t_70]

Vue优化的Diff算法

> Vue的diff算法只会比较同层级的元素，不进行跨层级比较

![在这里插入图片描述][14cbda20b4154985bbf1ec3a043e370a.png]

## 三、 Vue中的Diff算法实现 ##

### Vnode分类 ###

EmptyVNode: 没有内容的注释节点  
TextVNode: 文本节点  
ElementVNode: 普通元素节点  
ComponentVNode: 组件节点  
CloneVNode: 克隆节点，可以是以上任意类型的节点，唯一的区别在于isCloned属性为true

## Patch函数 ##

> patch函数接收以下参数：

1.  oldVnode：旧的虚拟节点
2.  Vnode：新的虚拟节点
3.  hydrating：是否要和真实DOM混合
4.  removeOnly：特殊的flag，用于 transition-group

> 处理流程大致分为以下步骤：

1.  vnode不存在，oldVnode存在时，移除oldVnode
2.  vnode存在，oldVnode不存在时，创建vnode
3.  vnode和oldVnode都存在时
4.  如果vnode和oldVnode是同一个节点（通过sameVnode函数对比 后续详解），通过patchVnode进行后续比对工作
5.  如果vnode和oldVnode不是同一个节点，那么根据vnode创建新的元素并挂载至oldVnode父元素下。如果组件根节点被替换，遍历更新父节点element。然后移除旧节点。如果oldVnode是服务端渲染元素节点，需要用hydrate函数将虚拟dom和真是dom进行映射

> 源码如下，已写好注释便于阅读

return function patch(oldVnode, vnode, hydrating, removeOnly) { 
        // 如果vnode不存在，但是oldVnode存在，移除oldVnode
        if (isUndef(vnode)) { 
          if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
          return
        }
    
        let isInitialPatch = false
        const insertedVnodeQueue = []
    
        // 如果oldVnode不存在，但是vnode存在时，创建vnode
        if (isUndef(oldVnode)) { 
          isInitialPatch = true
          createElm(vnode, insertedVnodeQueue)
        } else { 
          // 剩余情况为vnode和oldVnode都存在
    
          // 判断是否为真实DOM元素
          const isRealElement = isDef(oldVnode.nodeType)
          if (!isRealElement && sameVnode(oldVnode, vnode)) { 
            // 如果vnode和oldVnode是同一个（通过sameVnode函数进行比对 后续详解）
            // 受用patchVnode函数进行后续比对工作 （函数后续详解）
            patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly)
          } else { 
            // vnode和oldVnode不是同一个的情况
            if (isRealElement) { 
              // 如果存在真实的节点，存在data-server-render属性
              if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) { 
                // 当旧的Vnode是服务端渲染元素，hydrating记为true
                oldVnode.removeAttribute(SSR_ATTR)
                hydrating = true
              }
              // 需要用hydrate函数将虚拟DOM和真实DOM进行映射
              if (isTrue(hydrating)) { 
                // 需要合并到真实DOM上
                if (hydrate(oldVnode, vnode, insertedVnodeQueue)) { 
                  // 调用insert钩子
                  invokeInsertHook(vnode, insertedVnodeQueue, true)
                  return oldVnode
                } else if (process.env.NODE_ENV !== 'production') { 
                  warn(
                    'The client-side rendered virtual DOM tree is not matching ' +
                    'server-rendered content. This is likely caused by incorrect ' +
                    'HTML markup, for example nesting block-level elements inside ' +
                    '<p>, or missing <tbody>. Bailing hydration and performing ' +
                    'full client-side render.'
                  )
                }
              }
              // 如果不是服务端渲染元素或者合并到真实DOM失败，则创建一个空的Vnode节点去替换它
              oldVnode = emptyNodeAt(oldVnode)
            }
    
            // 获取oldVnode父节点
            const oldElm = oldVnode.elm
            const parentElm = nodeOps.parentNode(oldElm)
    
            // 根据vnode创建一个真实DOM节点并挂载至oldVnode的父节点下
            createElm(
              vnode,
              insertedVnodeQueue,
              oldElm._leaveCb ? null : parentElm,
              nodeOps.nextSibling(oldElm)
            )
    
            // 如果组件根节点被替换，遍历更新父节点Element
            if (isDef(vnode.parent)) { 
              let ancestor = vnode.parent
              const patchable = isPatchable(vnode)
              while (ancestor) { 
                for (let i = 0; i < cbs.destroy.length; ++i) { 
                  cbs.destroy[i](ancestor)
                }
                ancestor.elm = vnode.elm
                if (patchable) { 
                  for (let i = 0; i < cbs.create.length; ++i) { 
                    cbs.create[i](emptyNode, ancestor)
                  }
                  // #6513
                  // invoke insert hooks that may have been merged by create hooks.
                  // e.g. for directives that uses the "inserted" hook.
                  const insert = ancestor.data.hook.insert
                  if (insert.merged) { 
                    // start at index 1 to avoid re-invoking component mounted hook
                    for (let i = 1; i < insert.fns.length; i++) { 
                      insert.fns[i]()
                    }
                  }
                } else { 
                  registerRef(ancestor)
                }
                ancestor = ancestor.parent
              }
            }
    
            // 销毁旧节点
            if (isDef(parentElm)) { 
              // 移除老节点
              removeVnodes(parentElm, [oldVnode], 0, 0)
            } else if (isDef(oldVnode.tag)) { 
              // 调用destroy钩子
              invokeDestroyHook(oldVnode)
            }
          }
        }
        // 调用insert钩子并返回节点
        invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch)
        return vnode.elm
      }

### sameVnode函数 ###

> Vue怎么判断是不是同一个节点？流程如下：

1.  判断Key值是否一样
2.  tag的值是否一样
3.  isComment，这个不用太关注。
4.  数据一样
5.  sameInputType()，专门对表单输入项进行判断的：input一样但是里面的type不一样算不同的inputType

> 从这里可以看出key对diff算法的辅助作用，可以快速定位是否为同一个元素，必须保证唯一性。  
> 如果你用的是index作为key，每次打乱顺序key都会改变，导致这种判断失效，降低了Diff的效率。  
> 因此，用好key也是Vue性能优化的一种方式。

*  源码如下：

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)
          )
        )
      )
    }

### patchVnode函数 ###

> 前置条件vnode和oldVnode是同一个节点  
> 执行流程：

1.  如果oldVnode和vnode引用一致，可以认为没有变化，return
2.  如果oldVnode的isAsyncPlaceholder属性为true，跳过检查异步组件，return
3.  如果oldVnode跟vnode都是静态节点，且具有相同的key，同时vnode是克隆节点或者v-once指令控制的节点时，只需要把oldVnode.elm和oldVnode.child都复制到vnode上，也不用再有其他操作，return
4.  如果vnode不是文本节或注释节点
5.  如果vnode和oldVnode都有子节点并且两者子节点不一致时，就调用updateChildren更新子节点
6.  如果只有vnode有自子节点，则调用addVnodes创建子节点
7.  如果只有oldVnode有子节点，则调用removeVnodes把这些子节点都删除
8.  如果vnode文本为undefined，则清空vnode.elm文本
9.  如果vnode是文本节点但是和oldVnode文本内容不同，只需更新文本。

> 源代码如下，已写好注释便于阅读

function patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly) { 
    
        // 如果新老节点引用一致，直接返回。
        if (oldVnode === vnode) { 
          return
        }
    
        const elm = vnode.elm = oldVnode.elm
    
        // 如果oldVnode的isAsyncPlaceholder属性为true，跳过检查异步组件
        if (isTrue(oldVnode.isAsyncPlaceholder)) { 
          if (isDef(vnode.asyncFactory.resolved)) { 
            hydrate(oldVnode.elm, vnode, insertedVnodeQueue)
          } else { 
            vnode.isAsyncPlaceholder = true
          }
          return
        }
    
        // 如果新旧都是静态节点，vnode的key也相同
        // 新vnode是克隆所得或新vnode有 v-once属性
        // 则进行赋值，然后返回。vnode的componentInstance 保持不变
        if (isTrue(vnode.isStatic) &&
          isTrue(oldVnode.isStatic) &&
          vnode.key === oldVnode.key &&
          (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
        ) { 
          vnode.componentInstance = oldVnode.componentInstance
          return
        }
    
        let i
        const data = vnode.data
        // 执行data.hook.prepatch 钩子
        if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) { 
          i(oldVnode, vnode)
        }
    
        // 获取子元素列表
        const oldCh = oldVnode.children
        const ch = vnode.children
    
        if (isDef(data) && isPatchable(vnode)) { 
          // 遍历调用 cbs.update 钩子函数，更新oldVnode所有属性
          // 包括attrs、class、domProps、events、style、ref、directives
          for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
          // 执行data.hook.update 钩子
          if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode)
        }
        // Vnode 的 text选项为undefined
        if (isUndef(vnode.text)) { 
          if (isDef(oldCh) && isDef(ch)) { 
            //新老节点的children不同，执行updateChildren方法
            if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
          } else if (isDef(ch)) { 
            // oldVnode children不存在 执行 addVnodes方法
            if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
            addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
          } else if (isDef(oldCh)) { 
            // vnode不存在执行removeVnodes方法
            removeVnodes(elm, oldCh, 0, oldCh.length - 1)
          } else if (isDef(oldVnode.text)) { 
            // 新旧节点都是undefined，且老节点存在text，清空文本。
            nodeOps.setTextContent(elm, '')
          }
        } else if (oldVnode.text !== vnode.text) { 
          // 新老节点文本内容不同，更新文本
          nodeOps.setTextContent(elm, vnode.text)
        }
        if (isDef(data)) { 
          // 执行data.hook.postpatch钩子，至此 patch完成
          if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
        }
      }

### updateChildren函数 ###

> 重点！！！  
> 前置条件：vnode和oldVnode的children不相等

整体的执行思路如下：

1.  vnode头对比oldVnode头
2.  vnode尾对比oldVnode尾
3.  vnode头对比oldVnode尾
4.  vnode尾对比oldVnode头
5.  只要符合一种情况就进行patch，移动节点，移动下标等操作
6.  都不对再在oldChild中找一个key和newStart相同的节点
7.  找不到，新建一个。
8.  找到，获取这个节点，判断它和newStartVnode是不是同一个节点

*  如果是相同节点，进行patch 然后将这个节点插入到oldStart之前，newStart下标继续移动
 *  如果不是相同节点，需要执行createElm创建新元素

> 为什么会有头对尾、尾对头的操作？

*  可以快速检测出reverse操作，加快diff效率。

> 源码如下 已写好注释便于阅读：

function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) { 
    
        // 定义变量
        let oldStartIdx = 0  // 老节点Child头下标
        let newStartIdx = 0  // 新节点Child头下标
        let oldEndIdx = oldCh.length - 1  // 老节点Child尾下标
        let oldStartVnode = oldCh[0]      // 老节点Child头结点
        let oldEndVnode = oldCh[oldEndIdx] // 老节点Child尾结点
        let newEndIdx = newCh.length - 1   // 新节点Child尾下标
        let newStartVnode = newCh[0]       // 新节点Child头结点
        let newEndVnode = newCh[newEndIdx]  // 新节点Child尾结点
        let oldKeyToIdx, idxInOld, vnodeToMove, refElm  
    
        // removeOnly is a special flag used only by <transition-group>
        // to ensure removed elements stay in correct relative positions
        // during leaving transitions
        const canMove = !removeOnly
    
        if (process.env.NODE_ENV !== 'production') { 
          checkDuplicateKeys(newCh)
        }
    
        // 定义循环
        while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { 
          // 存在检测
          if (isUndef(oldStartVnode)) { 
            oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
          } else if (isUndef(oldEndVnode)) { 
            oldEndVnode = oldCh[--oldEndIdx]
    
          // 如果老结点Child头和新节点Child头是同一个节点
          } else if (sameVnode(oldStartVnode, newStartVnode)) { 
            // patch差异
            patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
            // patch完成 移动节点位置 继续比对下一个节点
            oldStartVnode = oldCh[++oldStartIdx]
            newStartVnode = newCh[++newStartIdx]
    
          // 如果老结点Child尾和新节点Child尾是同一个节点
          } else if (sameVnode(oldEndVnode, newEndVnode)) { 
            // patch差异
            patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
            // patch完成 移动节点位置 继续比对下一个节点
            oldEndVnode = oldCh[--oldEndIdx]
            newEndVnode = newCh[--newEndIdx]
    
          // 如果老结点Child头和新节点Child尾是同一个节点
          } else if (sameVnode(oldStartVnode, newEndVnode)) {  // Vnode moved right
             // patch差异
            patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
            // 把oldStart节点放到oldEnd节点后面
            canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
            // patch完成 移动节点位置 继续比对下一个节点
            oldStartVnode = oldCh[++oldStartIdx]
            newEndVnode = newCh[--newEndIdx]
          // 如果老结点Child尾和新节点Child头是同一个节点
          } else if (sameVnode(oldEndVnode, newStartVnode)) {  // Vnode moved left
             // patch差异
            patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
            // 把oldEnd节点放到oldStart节点前面
            canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
            // patch完成 移动节点位置 继续比对下一个节点
            oldEndVnode = oldCh[--oldEndIdx]
            newStartVnode = newCh[++newStartIdx]
          } else { 
            // 如果没有相同的Key，执行createElm方法创建元素
            if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
            idxInOld = isDef(newStartVnode.key) ?
              oldKeyToIdx[newStartVnode.key] :
              findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
            if (isUndef(idxInOld)) {  // New element
              createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
            } else { 
              // 有相同的Key，判断这两个节点是否为sameNode
              vnodeToMove = oldCh[idxInOld]
              if (sameVnode(vnodeToMove, newStartVnode)) { 
                // 如果是相同节点，进行patch 然后举将oldStart插入到oldStart之前，newStart下标继续移动
                patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue)
                oldCh[idxInOld] = undefined
                canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
              } else { 
                // 如果不是相同节点，需要执行createElm创建新元素
                createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
              }
            }
            newStartVnode = newCh[++newStartIdx]
          }
        }
    
        // oldStartIdx > oldEndIdx说明oldChild先遍历完，使用addVnode方法添加newStartIdx指向的节点到newEndIdx的节点
        if (oldStartIdx > oldEndIdx) { 
          refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
          addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
        } else if (newStartIdx > newEndIdx) { 
          // 如果newStartIdx > newEndIdx说明newChild先遍历完，remove掉oldChild未遍历完的节点
          removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
        }
      }

## 四、总结 ##

1.  正确使用key，可以快速执行sameVnode比对，加速Diff效率，可以作为性能优化的一个点。
2.  DIff只做同级比较，使用sameVnode函数比对，文本节点直接替换文本内容。  
    子元素列表的Diff，进行头对头、尾对尾、头对尾等系列比较，直到遍历完两个元素的子元素列表。
3.  或一个列表先遍历完了，直接addVnode / removeVnode。

--------------------

![在这里插入图片描述][14cbda20b4154985bbf1ec3a043e370a.png]

1.  diff 算法是虚拟dom生成的必然产物，通过新旧dom比较，将变化的地方更新到真是的dom上，另外也需要diff的高效执行来降低意见复杂度
2.  vue2.x中为了降低watcher的粒度， 每一个组件都只有一个watcher与之对应，只有引入diff算法才能准确的找到发生变化的地方。
3.  vue中的diff的执行时刻是组件实例执行其更新函数时，他会对比上一次的俨然结果oldVnodeh和新的渲染结果newVnode,此过程成为patch.
4.  diff 过程整体遵循 深度优先，同层比较。两个节点之间比较即根据它们是否拥有子节点或者文本节点做不同的操作，比较两组节点是diff的重点，首先假设头尾节点可能相同做4次节点比对尝试，如果找到相同的节点，按照通用方式遍历查找，查找结束才按情况处理剩下的节点，借助key通常可以非常精确的找到相同的节点，因此整个patch 会很高效

--------------------

1.  概念：vue中的diff算法叫patch，发生在程序更新阶段，目标是通过新旧虚拟DOM的对比，将变化的地方更新在真是DOM上。
2.  必要性：vue2.x中降低了Watcher粒度，每个组件会有一个渲染Watcher与之对应，只有引入diff才能精确找到组件中发生变化的地方
3.  执行过程：diff过程整体遵循深度优先，同层比较的策略；两个节点之间的比较时，先做属性更新，然后会根据它们是否拥有子节点或文本节点的情况做不同操作；比较两组子节点是算法的重点，首先假设尾节点可能相同做4次对比尝试，找到直接更新，没找到则按照通用方式遍历查找，查找结束在按情况处理剩下的节点，老数组剩余批量删除，新数组剩余批量创建

--------------------

diff 算法是指生成更新补丁的方式，主要应用于虚拟 DOM 树变化后，更新真实 DOM。所以 diff 算法一定存在这样一个过程：触发更新 → 生成补丁 → 应用补丁。
     
     React 的 diff 算法，触发更新的时机主要在 state 变化与 hooks 调用之后。此时触发虚拟 DOM 树变更遍历，采用了深度优先遍历算法。但传统的遍历方式，效率较低。为了优化效率，使用了分治的方式。将单一节点比对转化为了 3 种类型节点的比对，分别是树、组件及元素，以此提升效率。
     
     树比对：由于网页视图中较少有跨层级节点移动，两株虚拟 DOM 树只对同一层次的节点进行比较。
     
     组件比对：如果组件是同一类型，则进行树比对，如果不是，则直接放入到补丁中。
     
     元素比对：主要发生在同层级中，通过标记节点操作生成补丁，节点操作对应真实的 DOM 剪裁操作。
     
     以上是经典的 React diff 算法内容。自 React 16 起，引入了 Fiber 架构。为了使整个更新过程可随时暂停恢复，节点与树分别采用了 FiberNode 与 FiberTree 进行重构。fiberNode 使用了双链表的结构，可以直接找到兄弟节点与子节点。
     
     整个更新过程由 current 与 workInProgress 两株树双缓冲完成。workInProgress 更新完成后，再通过修改 current 相关指针指向新节点。
     
     然后拿 Vue 和 Preact 与 React 的 diff 算法进行对比。
     
     Preact 的 Diff 算法相较于 React，整体设计思路相似，但最底层的元素采用了真实 DOM 对比操作，也没有采用 Fiber 设计。Vue 的 Diff 算法整体也与 React 相似，同样未实现 Fiber 设计。
     
     然后进行横向比较，React 拥有完整的 Diff 算法策略，且拥有随时中断更新的时间切片能力，在大批量节点更新的极端情况下，拥有更友好的交互体验。
     
     Preact 可以在一些对性能要求不高，仅需要渲染框架的简单场景下应用。
     
     Vue 的整体 diff 策略与 React 对齐，虽然缺乏时间切片能力，但这并不意味着 Vue 的性能更差，因为在 Vue 3 初期引入过，后期因为收益不高移除掉了。除了高帧率动画，在 Vue 中其他的场景几乎都可以使用防抖和节流去提高响应性能。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1ajE5MzU_size_16_color_FFFFFF_t_70]: /images/20221021/08e81b92f70c4c9ebdb49b666f55b714.png
[14cbda20b4154985bbf1ec3a043e370a.png]: /images/20221021/96e0a31077cc46a9a80dac7fb3733317.png