vue和react的diff算法源码

Vue.js 中的虚拟 DOM Diff 算法是其性能优化的关键之一。

Vue.js 的 Diff 算法主要基于 Snabbdom，以下是 Vue.js 中虚拟 DOM Diff 算法的简化版伪代码，以便说明其基本思想：

function patch(oldVnode, vnode) {
  // 如果 oldVnode 不存在，说明是初次渲染，直接创建新的元素
  if (!oldVnode) {
    createElm(vnode);
  } else {
    // 如果 oldVnode 存在，说明是更新操作
    if (sameVnode(oldVnode, vnode)) {
      // 如果新旧节点相同，执行 patchVnode 进行更新
      patchVnode(oldVnode, vnode);
    } else {
      // 如果新旧节点不同，直接替换 oldVnode
      const parent = oldVnode.parentNode;
      const elm = createElm(vnode);
      parent.insertBefore(elm, oldVnode);
      parent.removeChild(oldVnode);
    }
  }
}
 
function patchVnode(oldVnode, vnode) {
  // ... 具体的 Diff 算法实现
}
 
function sameVnode(oldVnode, vnode) {
  // 判断两个节点是否相同，通常通过 key 和 tag 判断
  return oldVnode.key === vnode.key && oldVnode.tag === vnode.tag;
}

这里主要关注 patchVnode 函数，它是 Diff 算法的核心。Vue.js 的 Diff 算法采用了一种双端比较的策略，具体步骤如下：

1.同层级比较： 首先比较新旧节点的同层级，通过 tag 和 key 判断是否为相同节点。
2.更新属性： 如果同层级节点相同，就会比较其属性，更新新旧节点的属性。
3.更新子节点： 进一步比较新旧节点的子节点。这个过程可能会涉及递归调用 patch 函数。
4.删除多余节点： 如果新节点的子节点数量小于旧节点，说明有节点被删除，需要将多余的节点从 DOM 中移除。
5.新增节点： 如果新节点的子节点数量大于旧节点，说明有节点被新增，需要将新增的节点创建并插入到相应位置。

Vue.js 的 Diff 算法通过对比新旧虚拟 DOM 树的节点，最小化了对实际 DOM 的操作，提高了渲染效率。这个算法的时间复杂度是 O(n)，其中 n 是节点的数量，是一种相对高效的算法。
需要注意，上述伪代码只是为了说明基本思想，

Vue.js 中的 Diff 算法还包含了一些优化策略，比如通过设置 key 来提高比较效率，以及对特殊节点（如组件节点）的处理等。

React 的 Diff 算法是虚拟 DOM（Virtual DOM）的核心部分，

用于高效地更新实际 DOM。以下是 React 的 Diff 算法的基本原理和步骤：

1.Tree Diff（树协调）：
React 会对新旧两棵虚拟 DOM 树进行深度优先遍历，对比相应节点，找出差异。
如果节点类型不同，直接替换整个节点及其子树。
如果节点类型相同，进入下一步比较。
2.Component-level（组件级别）比较：
如果节点是组件，React 会比较组件的类型，如果类型相同，会更新组件实例并递归比较其子节点。
如果组件类型不同，React 会拆卸旧组件，挂载新组件，然后递归比较其子节点。

3.Element-level（元素级别）比较：
如果节点是元素（HTML 元素），React 会比较元素的属性，更新发生变化的属性。
React 会进一步比较元素的子节点，递归进行上述的 Tree Diff。
4.Key 的使用：
React 在进行比较时，会根据元素的 key 属性来优化比较过程。
如果两个元素的 key 不同，React 将认为这是两个不同的节点，直接替换整个节点及其子树。
如果两个元素的 key 相同，React 会认为它们可能是同一个节点，进一步比较其子节点。
5.列表（Lists）的优化：
当处理列表时，React 会尽量复用相同位置的元素，而不是移动元素到新位置。
React 使用一种“key-indexed” 的策略，通过元素的 key 和索引来匹配新旧节点。

6.Diff 策略：

React 的 Diff 算法并不会对整个树进行比较，而是采用一种深度优先、单向的比较策略。
在比较过程中，React 会标记节点的更新状态，将差异记录在变更集合（change set）中。
.最终，React 会根据变更集合对实际 DOM 进行最小化的更新，以提高性能。

React 的 Diff 算法的核心思想是尽量减少实际 DOM 操作，通过高效地识别并应用变更，实现快速的页面更新。在 React Fiber 架构中，进一步实现了异步渲染和可中断更新，提升了用户体验。