react VS Vue diff 算法

Question

相同点：Vue 和 react 的 diff 算法，都是不进行跨层级比较，只做同级比较。

不同点：Vue 进行 diff 时，调用 patch 打补丁函数，一边比较一边给真实的 DOM 打补丁 Vue 对比节点，当节点元素类型相同，但是 className 不同时，认为是不同类型的元素，删除重新创建，而react则认为是同类型节点，进行修改操作：

• Vue 的列表比对，采用从两端到中间的方式，旧集合和新集合两端各存在两个指针，两两进行比较，如果匹配上了就按照新集合去调整旧集合，每次对比结束后，指针向队列中间移动；
• 而 react 则是从左往右依次对比，利用元素的 index 和标识 lastIndex 进行比较，如果满足 index < lastIndex 就移动元素，删除和添加则各自按照规则调整；
• 当一个集合把最后一个节点移动到最前面，react 会把前面的节点依次向后移动，而 Vue 只会把最后一个节点放在最前面，这样的操作来看，Vue 的 diff 性能是高于 react 的。

react diff

diff 算法的作用：数据更改，生成相应的虚拟 DOM，与真实 DOM 作对比，通过 diff 算法，对比出有变化的部分，通过原生的 dom 操作只更新有变化的部分。这样就不用想原生 DOM，有一处修改就会造成整个页面的整改。

传统 diff 算法：循环递归地方式遍历节点，时间复杂度为 O(n^3)

react 的 diff：通过最少的步骤，将虚拟 DOM 转化为真实 DOM，时间复杂度为 O(n)

树的 diff：跨层级的 dom 操作很少，可以忽略不计

1. 通过uodateDepth对虚拟数进行层级控制
2. 只对两棵树同一层级进行比较，节点不存在就直接删掉，遍历一次就能完成比较
3. 如果出现跨层操作，比如 a 从原位置移动到 b 位置，就删除原位置的 a，在 b 新建 a，所以 a 以下的树会被重建，所以官方不建议跨层操作，建议通过隐藏显示来操作，比如 visibility:hidden

组件 diff：相同类型组件生成相同树结构；不同类型组件生成不同树结构

1. 同一类型的组件，按原策略（层级比较）
2. 同一类型的组件，a 变化时，虚拟 DOM 没有变，可以在这里进行 shouldComponentUpdate 操作
3. 如果被判定为不同类型的组件，删除原组件，构建新组件

元素diff：同一层级的一组子节点，通过唯一id进行区分

1. 插入：如果元素不在原集合，就插入
2. 删除：d在集合中，但是d节点被更改，不能更新复用，就删除重建；或者d没有了，直接删除
3. 移动：d在集合中，并且没有变化，只是换了位置，通过key来区分并移动。所以通过map出来的元素，如果不加key，就会报错

比较元素的新旧 index：lastIndex，index；只有 index < lastIndex 才会移动，也就是往右移动，往左不移动。所以！如果在一长串集合中，如果最后一个元素移动到第一个，前面的所有元素都会移动，性能不佳要尽量避免

所以不难理解为什么不要把 index 作为 key 值（当数组变化了，index 也会变化，从而 lastIndex 和 index 不再能正确代表新旧 index），应该用元素的唯一标识 id 作为 key 值

Vue diff

虚拟 DOM 是将真实的 DOM 的数据抽取出来，以对象的形式模拟树结构。（虚拟 DOM 和 oldVNode 都是对象）

比较新旧节点的时候，比较只会在同层级进行，不会跨层级比较。

当数据改变，set 方法会通知所有订阅者 watcher，订阅者会调用 patch(oldVnode, Vnode) 给真实的 DOM 打补丁，更新相应的视图。是否是同一个 VNode？不是就替换，是就继续进行 patch

patch 接收

oldVnode和Vnode

来代表新的节点和之前的旧节点

判断两节点是否值得比较，值得就继续比较；不值得直接替换

当确定值得比较后，会对两个节点指定 patchVnode 方法

• 找到对应的真实 DOM，称 el，判断 Vnode 和 oldVnode 是否指向同一对象，如果是直接 return
• 都有文本对象且不相等，就将el的文本节点设置为 Vnode 的文本节点
• 如果 oldVnode 没有子节点，而 Vnode 有，将 Vnode 子节点真实化后添加到 el
• 如果两个都有子节点，执行 updateChildren 函数比较子节点！

updateChilldren(parentElement,oldCh,newCh)

• oldCh 旧的子节点，newCh 新的子节点提取出来，oldCh 和 newCh 各有两个头尾变量，startIdx 和 EndIdx；2个变量互相比较。涉及到4种比较方式，如果4种都不成功，就用 key 来比较，比较过程中，变量会向中间靠拢，一旦 startIdx > endIdx，表明 oldCh 和 newCh 至少有一个已经遍历结束。如果 old 先结束，那么 newCh 中的节点按照其 index 插入到 DOM 中去；如果 newCh 先遍历完，就将真实 DOM 中多余的节点删掉。