Dom Diff算法的对比过程

简介: Dom Diff算法的对比过程

本文仅用于笔者在学习Dom Diff算法的学习记录,如果想深入源码完整的学习,那么本篇文章可能不适合你。点个赞出门左转谢谢!(调皮)

若出现错误或者不严谨的地方,请大家指出!!!


React的假设



React需要同时维护两棵虚拟DOM树:一棵表示当前的DOM结构,另一棵在React状态变更将要重新渲染时生成。React通过比较这两棵树的差异,决定是否需要修改DOM结构,以及如何修改。这种算法称作Diff算法。


为了降低算法复杂度,React的diff会预设三个限制:


  1. 只对同级元素进行Diff。如果一个DOM节点在前后两次更新中跨越了层级,那么React不会尝试复用他。
  2. 两个不同类型的元素会产生出不同的树。如果元素由div变为p,React会销毁div及其子孙节点,并新建p及其子孙节点。
  3. 开发者可以通过 key属性 来暗示哪些子元素在不同的渲染下能保持稳定


tree diff



tree diff主要针对的是React dom节点跨层级的操作。由于跨层级的DOM移动操作较少,所以React diff算法的tree diff没有针对此种操作进行深入比较,只是简单进行了删除和创建操作


如图所示,A 节点(包括其子节点)整个被移动到 D 节点下,由于 React 只会简单地考虑同层级节点的位置变换,而对于不同层级的节点,只有创建和删除操作。

当根节点发现子节点中 A 消失了,就会直接销毁 A;当 D 发现多了一个子节点 A,则会创建新的 A(包括子节点)作为其子节点。此时,diff 的执行情况:create A → create B → create C → delete A

image.png


由此可以发现,当出现节点跨层级移动时,并不会出现想象中的移动操作,而是以 A 为根节点的整个树被重新创建。这是一种影响 React 性能的操作,因此官方建议不要进行 DOM 节点跨层级的操作。


component diff



component diff是专门针对更新前后的同一层级间的React组件比较的diff 算法:

component diff组件比较React对于组件的策略有两种方式,一种是相同类型的组件和不同类型的组件

  • 对同种类型组件对比,按照层级比较继续比较虚拟DOM树即可,但有种特殊的情况,当组件A如果变化为组件B的时候,有可能子组件并没有任何变化。但是React会将父节点下的所有子节点删除再重新挂载,所以用户可以通过shouldComponentUpdate() 来判断是否需要更新子组件
  • 对于不同组件来说,React会直接判定该组件为dirty component(脏组件) ,无论结构是否相似,只要判断为脏组件就会直接替换整个组件的所有节点


element diff



element diff是专门针对同一层级的所有节点(包括元素节点和组件节点)的diff算法。当节点处于同一层级时,diff 提供了 3 种节点操作,分别为 INSERT_MARKUP(插入)MOVE_EXISTING(移动)REMOVE_NODE(删除)


同一层级只有一个元素


React通过先判断key是否相同,如果key相同则判断type是否相同,只有都相同时一个DOM节点才能复用。

image.png


同级有多个元素



同一层级多个元素的diff算法,会涉及到上述INSERT_MARKUP(插入)MOVE_EXISTING(移动)REMOVE_NODE(删除)的一种或者多种情况


宏观思路:

  1. 该节点能否进行复用,复用时是否需要移动位置,如果要移动位置应该移动到哪里?
  2. 新节点元素中在老节点元素中没有找到可以复用的,就要新建节点插入
  3. 老节点中存在剩余元素,就要进行删除


我们来推导一下如何复用节点:

复用子节点的前提是什么?---> 存在可以复用的节点 ---> 新的子节点在旧的节点中有对应节点---> 如果有相同的key和type,则代表可以复用节点,只需要通过移动Dom操作就可以完成更新。


移动操作的过程


diff算法整体会进行两轮的遍历


  • 第一轮:处理可以复用,需要更新的节点


复用时判断需不需要移动,其实移动的过程,整体是向后移动的


如果不需要移动的话,lastIndex应该是0,1,2,3...递增的,如果顺序被打乱,则需要移动,则oldIndex < lastPlacedIndex。

image.png

  • 第二轮:处理剩下不属于更新的节点,包括删除和插入


在遍历之前,会将旧节点的key(如果没有key会存index)和对应的节点存到map中


image.png


第一次遍历


  • 遍历newChildreni = 0,将newChildren[i]oldFiber比较,判断DOM节点是否可复用。
  • 如果可复用,i++,比较newChildren[i]oldFiber.sibling是否可复用。可以复用则重复步骤2。
  • 如果不可复用,立即跳出整个遍历。
  • 如果newChildren遍历完或者oldFiber遍历完(即oldFiber.sibling === null),跳出遍历。


第二次遍历


newChildren遍历完,oldFiber没遍历完, 就把多余的节点删除newChildren没遍历完,oldFiber遍历完, 就将新节点新增

那么如果两个都没有遍历完呢?


处理位置交换的节点


由于有节点交换了位置,所以不能再用位置索引对比前后的节点,那么怎样才能将同一个节点在两次更新中对应上呢?


你一定想到了,我们需要用key属性了。


为了快速的找到key对应的oldFiber,我们将所有还没处理的oldFiber放进以key属性为key,Fiber为value的map


再遍历剩余的newChildren,通过newChildren[i].key就能在existingChildren中找到key相同的oldFiber


再利用我们之前说的, 复用时判断需不需要移动,其实移动的过程,整体是向后移动的

如果不需要移动的话,lastIndex应该是0,1,2,3...递增的,如果顺序被打乱,则需要移动,则oldIndex < lastPlacedIndex。

type NodeList = Node[];
type Flag = "Placement" | "Deletion";
interface Node {
    key: string;
    flag?: Flag;
    index?: number;
}
// 用于调试 Diff算法 的Demo
export default function diff(before: NodeList, after: NodeList): NodeList {
    let lastPlacedIndex = 0;
    const result: NodeList = [];
    const beforeMap = new Map<string, Node>();
before.forEach((node, i) => {
    node.index = i;
    beforeMap.set(node.key, node);
});
for (let i = 0; i < after.length; i++) {
    const afterNode = after[i];
    afterNode.index = i;
    const beforeNode = beforeMap.get(afterNode.key);
    if (beforeNode) {
        // 复用老节点
        beforeMap.delete(beforeNode.key);
        const oldIndex = beforeNode.index as number;
        // 需要移动节点
        if (oldIndex < lastPlacedIndex) {
            afterNode.flag = "Placement";
            result.push(afterNode);
            continue;
         } else {
               lastPlacedIndex = oldIndex;
         }
   } else {
        // 创建新节点
        afterNode.flag = "Placement";
        result.push(afterNode);
    }
}
beforeMap.forEach((node) => {
    node.flag = "Deletion";
    result.push(node);
});
return result;
}


存在的问题



明明只需要将D移动到最开头就可以完成目的,却分别将ABC移动到D的后面,移动了三次。所以在开发的过程中应该尽量减少节点移入首部的操作,会影响其性能。

image.png


在vue中,引入了双端Diff算法来进行优化,大家感兴趣的可以去了解一下。但是React却不能通过双端Diff算法进行优化,因为在目前的Fiber架构中,Fiber还没有设置反向的链表。



目录
打赏
0
0
2
0
3
分享
相关文章
Diff 算法的实现原理
【10月更文挑战第18天】Diff 算法是 Vue.js 中实现高效 DOM 更新的核心机制,通过合理的比较和优化策略,能够在保证界面正确性的同时,最大程度地减少 DOM 操作,提高应用的性能和用户体验。
74 2
|
4月前
|
Vue 中的 Diff 算法
【10月更文挑战第18天】需要注意的是,Diff 算法虽然能够提高性能,但在某些复杂的场景下,可能仍然会存在一些性能瓶颈。因此,在实际开发中,我们需要根据具体情况合理地使用 Diff 算法,并结合其他优化手段来提高应用的性能。
35 1
vue 中diff算法
【10月更文挑战第10天】
65 1
面试中的网红虚拟DOM,你知多少呢?深入解读diff算法
该文章深入探讨了虚拟DOM的概念及其diff算法,解释了虚拟DOM如何最小化实际DOM的更新,以此提升web应用的性能,并详细分析了diff算法的实现机制。
学习react基础(1)_虚拟dom、diff算法、函数和class创建组件
本文介绍了React的核心概念,包括虚拟DOM、Diff算法以及如何通过函数和类创建React组件。
54 3
基于GA遗传算法的多机无源定位系统GDOP优化matlab仿真
本项目基于遗传算法(GA)优化多机无源定位系统的GDOP,使用MATLAB2022A进行仿真。通过遗传算法的选择、交叉和变异操作,迭代优化传感器配置,最小化GDOP值,提高定位精度。仿真输出包括GDOP优化结果、遗传算法收敛曲线及三维空间坐标点分布图。核心程序实现了染色体编码、适应度评估、遗传操作等关键步骤,最终展示优化后的传感器布局及其性能。
基于深度学习的路面裂缝检测算法matlab仿真
本项目基于YOLOv2算法实现高效的路面裂缝检测,使用Matlab 2022a开发。完整程序运行效果无水印,核心代码配有详细中文注释及操作视频。通过深度学习技术,将目标检测转化为回归问题,直接预测裂缝位置和类别,大幅提升检测效率与准确性。适用于实时检测任务,确保道路安全维护。 简介涵盖了算法理论、数据集准备、网络训练及检测过程,采用Darknet-19卷积神经网络结构,结合随机梯度下降算法进行训练。
一级倒立摆平衡控制系统MATLAB仿真,可显示倒立摆平衡动画,对比极点配置,线性二次型,PID,PI及PD五种算法
本课题基于MATLAB对一级倒立摆控制系统进行升级仿真,增加了PI、PD控制器,并对比了极点配置、线性二次型、PID、PI及PD五种算法的控制效果。通过GUI界面显示倒立摆动画和控制输出曲线,展示了不同控制器在偏转角和小车位移变化上的性能差异。理论部分介绍了倒立摆系统的力学模型,包括小车和杆的动力学方程。核心程序实现了不同控制算法的选择与仿真结果的可视化。
31 15
基于SOA海鸥优化算法的三维曲面最高点搜索matlab仿真
本程序基于海鸥优化算法(SOA)进行三维曲面最高点搜索的MATLAB仿真,输出收敛曲线和搜索结果。使用MATLAB2022A版本运行,核心代码实现种群初始化、适应度计算、交叉变异等操作。SOA模拟海鸥觅食行为,通过搜索飞行、跟随飞行和掠食飞行三种策略高效探索解空间,找到全局最优解。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等