温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

React怎么实现核心Diff算法

发布时间:2022-04-16 13:43:08 来源:亿速云 阅读:127 作者:iii 栏目:开发技术

本篇内容主要讲解“React怎么实现核心Diff算法”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“React怎么实现核心Diff算法”吧!

    Diff算法的设计思路

    试想,Diff算法需要考虑多少种情况呢?大体分三种,分别是:

    节点属性变化,比如:

    // 更新前
    <ul>
      <li key="0" className="before">0</li>
      <li key="1">1</li>
    </ul>
    
    // 更新后
    <ul>
      <li key="0" className="after">0</li>
      <li key="1">1</li>
    </ul>

    节点增删,比如:

    // 更新前
    <ul>
      <li key="0">0</li>
      <li key="1">1</li>
      <li key="2">2</li>
    </ul>
    
    // 更新后 情况1 —— 新增节点
    <ul>
      <li key="0">0</li>
      <li key="1">1</li>
      <li key="2">2</li>
      <li key="3">3</li>
    </ul>
    
    // 更新后 情况2 —— 删除节点
    <ul>
      <li key="0">0</li>
      <li key="1">1</li>
    </ul>

    节点移动,比如:

    // 更新前
    <ul>
      <li key="0">0</li>
      <li key="1">1</li>
    </ul>
    
    // 更新后
    <ul>
      <li key="1">1</li>
      <li key="0">0</li>
    </ul>

    该如何设计Diff算法呢?考虑到只有以上三种情况,一种常见的设计思路是:

    • 首先判断当前节点属于哪种情况

    • 如果是增删,执行增删逻辑

    • 如果是属性变化,执行属性变化逻辑

    • 如果是移动,执行移动逻辑

    按这个方案,其实有个隐含的前提&mdash;&mdash; 不同操作的优先级是相同的。但在日常开发中,节点移动发生较少,所以Diff算法会优先判断其他情况。

    基于这个理念,主流框架(React、Vue)的Diff算法都会经历多轮遍历,先处理常见情况,后处理不常见情况

    所以,这就要求处理不常见情况的算法需要能给各种边界case兜底。

    换句话说,完全可以仅使用处理不常见情况的算法完成Diff操作。主流框架之所以没这么做是为了性能考虑。

    本文会砍掉处理常见情况的算法,保留处理不常见情况的算法

    这样,只需要40行代码就能实现Diff的核心逻辑。

    Demo介绍

    首先,我们定义虚拟DOM节点的数据结构:

    type Flag = 'Placement' | 'Deletion';
    
    interface Node {
      key: string;
      flag?: Flag;
      index?: number;
    }

    keynode的唯一标识,用于将节点在变化前、变化后关联上。

    flag代表node经过Diff后,需要对相应的真实DOM执行的操作,其中:

    • Placement对于新生成的node,代表对应DOM需要插入到页面中。对于已有的node,代表对应DOM需要在页面中移动

    • Deletion代表node对应DOM需要从页面中删除

    index代表该node在同级node中的索引位置

    注:本Demo仅实现为node标记flag,没有实现根据flag执行DOM操作

    我们希望实现的diff方法,接收更新前更新后NodeList,为他们标记flag

    type NodeList = Node[];
    
    function diff(before: NodeList, after: NodeList): NodeList {
      // ...代码
    }

    比如对于:

    // 更新前
    const before = [
      {key: 'a'}
    ]
    // 更新后
    const after = [
      {key: 'd'}
    ]
    
    // diff(before, after) 输出
    [
      {key: "d", flag: "Placement"},
      {key: "a", flag: "Deletion"}
    ]

    {key: "d", flag: "Placement"}代表d对应DOM需要插入页面。

    {key: "a", flag: "Deletion"}代表a对应DOM需要被删除。

    执行后的结果就是:页面中的a变为d。

    再比如:

    // 更新前
    const before = [
      {key: 'a'},
      {key: 'b'},
      {key: 'c'},
    ]
    // 更新后
    const after = [
      {key: 'c'},
      {key: 'b'},
      {key: 'a'}
    ]
    
    // diff(before, after) 输出
    [
      {key: "b", flag: "Placement"},
      {key: "a", flag: "Placement"}
    ]

    由于b之前已经存在,{key: "b", flag: "Placement"}代表b对应DOM需要向后移动(对应parentNode.appendChild方法)。abc经过该操作后变为acb

    由于a之前已经存在,{key: "a", flag: "Placement"}代表a对应DOM需要向后移动。acb经过该操作后变为cba

    执行后的结果就是:页面中的abc变为cba。

    Diff算法实现

    核心逻辑包括三步:

    • 遍历前的准备工作

    • 遍历after

    • 遍历后的收尾工作

    function diff(before: NodeList, after: NodeList): NodeList {
      const result: NodeList = [];
    
      // ...遍历前的准备工作
    
      for (let i = 0; i < after.length; i++) {
        // ...核心遍历逻辑
      }
    
      // ...遍历后的收尾工作
    
      return result;
    }

    遍历前的准备工作

    我们将before中每个node保存在以node.keykeynodevalueMap中。

    这样,以O(1)复杂度就能通过key找到before中对应node

    // 保存结果
    const result: NodeList = [];
      
    // 将before保存在map中
    const beforeMap = new Map<string, Node>();
    before.forEach((node, i) => {
      node.index = i;
      beforeMap.set(node.key, node);
    })

    遍历after

    当遍历after时,如果一个node同时存在于beforeafterkey相同),我们称这个node可复用。

    比如,对于如下例子,b是可复用的:

    // 更新前
    const before = [
      {key: 'a'},
      {key: 'b'}
    ]
    // 更新后
    const after = [
      {key: 'b'}
    ]

    对于可复用的node,本次更新一定属于以下两种情况之一:

    • 不移动

    • 移动

    如何判断可复用的node是否移动呢?

    我们用lastPlacedIndex变量保存遍历到的最后一个可复用node在before中的index

    // 遍历到的最后一个可复用node在before中的index
    let lastPlacedIndex = 0;

    当遍历after时,每轮遍历到的node,一定是当前遍历到的所有node中最靠右的那个。

    如果这个node可复用的node,那么nodeBeforelastPlacedIndex存在两种关系:

    注:nodeBefore代表该可复用的nodebefore中的对应node

    • nodeBefore.index < lastPlacedIndex

    代表更新前该nodelastPlacedIndex对应node左边。

    而更新后该node不在lastPlacedIndex对应node左边(因为他是当前遍历到的所有node中最靠右的那个)。

    这就代表该node向右移动了,需要标记Placement

    • nodeBefore.index >= lastPlacedIndex

    node在原地,不需要移动。

    // 遍历到的最后一个可复用node在before中的index
    let lastPlacedIndex = 0;  
    
    for (let i = 0; i < after.length; i++) {
    const afterNode = after[i];
    afterNode.index = i;
    const beforeNode = beforeMap.get(afterNode.key);
    
    if (beforeNode) {
      // 存在可复用node
      // 从map中剔除该 可复用node
      beforeMap.delete(beforeNode.key);
    
      const oldIndex = beforeNode.index as number;
    
      // 核心判断逻辑
      if (oldIndex < lastPlacedIndex) {
        // 移动
        afterNode.flag = 'Placement';
        result.push(afterNode);
        continue;
      } else {
        // 不移动
        lastPlacedIndex = oldIndex;
      }
    
    } else {
      // 不存在可复用node,这是一个新节点
      afterNode.flag = 'Placement';
      result.push(afterNode);
    }

    遍历后的收尾工作

    经过遍历,如果beforeMap中还剩下node,代表这些node没法复用,需要被标记删除。

    比如如下情况,遍历完after后,beforeMap中还剩下{key: 'a'}

    // 更新前
    const before = [
      {key: 'a'},
      {key: 'b'}
    ]
    // 更新后
    const after = [
      {key: 'b'}
    ]

    这意味着a需要被标记删除。

    所以,最后还需要加入标记删除的逻辑:

    beforeMap.forEach(node => {
      node.flag = 'Deletion';
      result.push(node);
    });

    到此,相信大家对“React怎么实现核心Diff算法”有了更深的了解,不妨来实际操作一番吧!这里是亿速云网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

    向AI问一下细节

    免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

    AI