vue和react的diff算法

vue2的diff算法

patch.js/updateChildren (opens new window)

diff算法是一种通过同层的树节点进行比较的高效算法。

其有两个特点：

1. 比较只会在同层级进行，不会跨层级比较。
2. 在diff比较的过程中，循环从两边向中间比较。

在vue中，作用于虚拟DOM渲染成真实DOM的新旧VNode节点比较。

当数据发生改变时，set方法会调用Dep.notify通知所有订阅者Watcher，订阅者就会调用patch给真实的DOM打补丁，更新相应的视图。

patch函数前两个参数位为oldVnode和Vnode，分别代表新的节点和之前的旧节点，主要做了四个判断：

1. 没有新节点，直接触发旧节点的destory钩子。
2. 没有旧节点，说明是页面刚开始初始化的时候，所有节点都是新建，所以只调用createElm。
3. 旧节点和新节点自身一样，通过sameVnode判断节点是否一样，一样时，直接调用patchVnode去处理这两个节点。
4. 旧节点和新节点自身不一样，当两个节点不一样的时候，直接创建新节点，删除旧节点。

function sameVnode (a, b) {
  return (
    // key值是否一样
    a.key === b.key && (
      (
        // 标签名是否一样
        a.tag === b.tag &&
        // 是否都为注释节点
        a.isComment === b.isComment &&
        // 是否都定义了data
        isDef(a.data) === isDef(b.data) &&
        // 当标签为input时，type必须是否相同
        sameInputType(a, b)
      ) || (
        isTrue(a.isAsyncPlaceholder) &&
        a.asyncFactory === b.asyncFactory &&
        isUndef(b.asyncFactory.error)
      )
    )
  )
}

patchVnode主要做了几个判断：

1. 新节点是否是文本节点，如果是，则直接更新DOM的文本内容为新节点的文本内容。
2. 新节点和旧节点如果都有子节点，则处理比较更新子节点。
3. 只有新节点有子节点，旧节点没有，那么直接全部新建。
4. 只有旧节点有子节点而新节点没有，那么删除旧节点的子节点。

子节点不完全一致，则调用updateChildren，循环做如下满足条件的判断：

1. 如果oldStartVnode（旧前）不存在，则oldStartVnode右移。（由于在之前的比较中，某些节点已经被处理过并从旧子节点列表中移除了）

2. 如果oldEndVnode（旧后）不存在，则oldEndVnode左移。

3. 旧前新前：如果oldStartVnode与newStartVnode相同，直接patchVnode，同时oldStartVnode右移，newStartVnode右移。

4. 旧后新后：如果oldEndVnode与newEndVnode相同，直接patchVnode，同时oldEndVnode左移，newEndVnode左移。

5. 旧前新后：如果oldStartVnode与newEndVnode相同，patchVnode后将oldStartVnode对应的真实DOM移动到oldEndVnode对应的真是DOM之后，同时oldStartVnode右移，newEndVnode左移。

6. 旧后新前：如果oldEndVnode与newStartVnode相同，patchVnode后将oldEndVnode对应的真实DOM移动到oldStartVnode对应的真是DOM之前，同时oldEndVnode左移，newStartVnode右移。

7. 如果上述4种四种通过前后指针对比的方式都没找到相同节点，则：

   1. 如果newStartVnode指定了key，则把剩余的旧节点（[oldStartIdx, oldEndIdx]区间内）映射成{child.key: index}，找到key相同的节点。如果newStartVnode未指定key，则遍历[oldStartIdx, oldEndIdx]区间内，找到与newStartVnode相同的节点。
   2. 如果上述步骤未找到节点，则在newStartIdx处新建并插入；如果找到了节点，判断与newStartVnode是否相同，如果相同则移动到旧开始节点oldStartVnode对应的真实DOM之前，如果不同则说明即使元素key相同，但是是不同元素，则在newStartIdx处新建并插入。

   最后newStartVnode右移。

循环结束：

• 旧开始索引大于旧结束索引

  说明旧节点列表遍历完，新节点列表剩余节点全部需要新增，对应[newStartIdx, newEndIdx]，插入到新结束节点的后一个节点之前。

• 新开始索引大于新结束索引

  说明新节点列表遍历完，旧节点列表剩余节点全部需要移除，对应[oldStartIdx, oldEndIdx]。

vue3的diff算法

renderer.ts/patchKeyedChildren (opens new window)

1. 前置预处理：定义指针i指向新旧节点列表的头节点，依次往右循环比较，判断节点是否相同，如相同则更新，不同则结束循环（任意指针移动到节点列表末尾时终止循环）。

2. 后置预处理：定义指针e1、e2分别指向旧节点列表和新节点列表的结束节点，依次往左循环比较，判断节点是否相同，如相同则更新，不同则结束循环（任意指针小于前置预处理得到的i时终止循环）。

3. 普通序列新增：如果旧节点列表遍历完（i > e1）并且新节点列表存在剩余（i <= e2），则在区间[i, e2]内的节点都需要新增，新建的节点插入到c2[e2 + 1]（c2代表新节点列表）之前。

4. 普通序列删除：如果新节点列表遍历完（i > e2）并且旧节点列表存在剩余（i <= e1），则在区间[i, e1]内的节点都需要删除，直接依次执行卸载操作。

5. 其余序列（可能包含新增、删除、移动）

   • 5.1 根据新节点列表创建新节点的key与索引对应的映射（keyToNewIndexMap）。

   • 5.2 遍历旧节点列表剩余节点并尝试更新，匹配节点并删除不存在的节点。

     • 创建新节点索引与旧节点索引的映射表newIndexToOldIndexMap，并初始为0。
     • 记录待更新节点的数量和已更新节点的数量，如果已更新节点的数量达到了待更新节点数量，则说明剩余旧节点都需要卸载。
     • 如果旧节点有key值，则通过key在keyToNewIndexMap中找到新节点对应的索引，否则再次遍历剩余新节点通过isSameVNodeType方法判断是否是相同节点，得到对应索引newIndex。如果找不到对应节点则说明该节点需要卸载，有对应节点则进行更新（更新节点数量加1）并且newIndexToOldIndexMap对应的索引（newIndex - s2，s2代表前置预处理之后的索引i）设置为旧节点索引加1（i + 1，加1为了与新增节点为0做区分，如果第一个节点就相同，i就为0），如果当前的newIndex大于之前更新能达到的新节点的最大索引值（maxNewIndexSoFar），否则设置移动标识为true。

   • 5.3 从后往前遍历新节点的剩余节点（也就是遍历newIndexToOldIndexMap），根据newIndexToOldIndexMap对应的值判断。

     • 如果是0则说明该节点需要新增，新建并插入到新节点列表的末尾节点之前。
     • 否则根据之前的移动标识判断是否需要对节点进行移动，根据新旧节点索引映射（newIndexToOldIndexMap）找到其中最长的递增子序列（目的是最小化的移动DOM）并返回对应索引，判断递增子序列的对应索引与当前遍历的索引是否相等，不相等则需要移动该节点到新节点列表中对应位置的下一个节点之前（newIndex + 1之前）。

上述是提供了key的逻辑，如果没有提供key，则以新旧节点最小长度的节点作为复用，依次更新每个节点（原地复用），如果旧节点有剩余则卸载，新节点有剩余则新增。

• patchFlag：用于标记虚拟节点的动态部分，帮助Vue3在对比新旧节点时快速定位需要更新的部分，从而避免全量对比。

值（二进制）	常量名	描述
1	TEXT	动态文本内容（例如：）
2	CLASS	动态class（例如：:class="{ active: isActive }"）
4	STYLE	动态style（例如：:style="{ color: textColor }"）
8	PROPS	动态属性（例如：:id="dynamicId"）

• shapeFlag：用于标记虚拟节点的结构特征，帮助Vue3快速判断节点的类型和内容，从而优化对比和渲染逻辑。

值（二进制）	常量名	描述
1	ELEMENT	普通元素节点（例如：<div>）
2	FUNCTIONAL_COMPONENT	函数式组件
4	STATEFUL_COMPONENT	有状态组件
8	TEXT_CHILDREN	子节点是文本（例如：<div>Hello</div>）
16	ARRAY_CHILDREN	子节点是数组（例如：<div><span></span></div>）

const vnode = {
  type: 'div',
  patchFlag: 1, // 动态文本内容，告诉Vue3只需要对比文本内容，而不需要对比其他部分。
  shapeFlag: 9, // 普通元素节点+文本子节点，告诉Vue3这是一个普通元素节点，且子节点是文本。
  children: 'Hello, {{ name }}'
};

react的diff算法

react是基于vdom的前端框架，组件渲染产生vdom，渲染器把vdom渲染成DOM。浏览器下使用react-dom的渲染器，会先把vdom转成fiber，找到需要更新DOM的部分，打上增删改的effectTag标记，这个过程叫做reconcile，可以打断，由scheducler调度执行。reconcile结束之后一次性根据effectTag更新DOM，叫做commit。打上effectTag可以标识这个fiber发生了怎样的变化，例如：新增（Placement）、更新（Update）、删除（Deletion），这些被打上flag的fiber会在complete阶段被收集起来，形成一个effectList链表，只包含这些需要操作的fiber，最后在commit阶段被更新掉。

这就是react的基于fiber的渲染流程，分成render（reconcile+schedule）、commit两个阶段。当渲染完一次，产生了fiber之后，再次渲染的vdom要和之前的fiber对比下，再决定如何产生新的fiber，目标是尽可能复用已有的fiber节点，这叫做diff算法。

react的diff算法采用分层对比的策略，即只对比同一层级的节点，而不是跨层级对比。

1. 对比根节点

   • 如果根节点的类型不同，react会直接销毁旧树，创建新树，没有移动操作。
   • 如果根节点的类型相同，react会对比属性和子节点。

2. 对比子节点

• 单节点

reconcileSingleElement (opens new window)

对于单节点的diff，只有更新操作，单节点的更新会调用reconcileSingleElement函数处理。单节点指newChildren为单一节点，但是oldFiber的数量不一定，如果oldFiber为空则新建newFiber节点，如果不为空则尝试从oldFiber中找到相同节点并再用匹配的oldFiber，newChildren中新节点的props来生成新的fiber节点，无法找到则新建。

• 多节点

reconcileChildrenArray (opens new window)

分成两次遍历：

1. 第一轮遍历：从头开始遍历newChildren，逐个与oldFiber链中的节点进行比较，判断节点的key或者tag是否有变化。

   • 没变则从oldFiber节点clone一个props被更新的fiber节点，新的props来自newChildren中的新节点，实现节点更新。

   • 有变化说明不满足复用条件，立即中断遍历进入下边的遍历。

   • 如果newChildren遍历完，则把剩下的oldFiber删掉。删除不仅仅是标记了effectTag为Deletion，还会将这个被删除的fiber节点添加到父级的effectList中。

   • 如果oldFiber遍历完，则把newChildren中剩下的节点全部新建。新建fiber节点并以sibling（指向下一个兄弟节点）为指针连成fiber链。

   • 如果oldFiber和newChildren都没有遍历完，则进行第二次遍历，第一轮遍历完会得到一个最新固定节点的位置lastPlacedIndex（之前的节点都是已经处理完成的）。

2. 第二轮遍历，把剩下的oldFiber放到映射existingChildren里（key值为键（如果没有key则使用index），值为fiber节点）。

   • 遍历剩余的newChildren，从existingChildren里查找，如果找到了就移动（并且删除existingChildren对应的旧节点），没有找到则新建。

   移动的逻辑是：newChildren中剩余的节点，都是不确定要不要移动的，遍历它们，检查节点在oldFiber链中的位置（旧fiber节点索引：newFiber.alternate.index）：

   • 如果旧位置在lastPlacedIndex的右边，说明这个节点位置不变。原因是旧位置在lastPlacedIndex的右边，而新节点的位置也在它的右边，所以它的位置没变化。因为位置不变，所以它成了固定节点，把lastPlacedIndex更新成新位置。
   • 如果旧位置在lastPlacedIndex的左边，当前这个节点的位置要往右挪。原因是旧位置在lastPlacedIndex的左边，新位置却在lastPlacedIndex的右边，所以它要往右挪，但它不是固定节点。此时无需更新lastPlacedIndex。

   第二轮遍历完了之后，把剩余的oldFiber删掉。

参考：

• 面试官：了解过vue中的diff算法吗？说说看 (opens new window)
• 深入理解React Diff算法 (opens new window)