关于前端:和面试官聊聊DiffReact

37次阅读

共计 5958 个字符，预计需要花费 15 分钟才能阅读完成。

最近看了 vue-design 我的项目，写的很棒，文中 diff 的思路全是来自该我的项目，这里只是做一个学习的记录。作者 (【掘金地址】hcysunyang) 曾经是 vue3 的 contributor 了。值得学习的一位 前端人。再次感激👏👏👏

我是一名前端的小学生。行文中对某些设计原理了解有误 非常欢送 大家探讨斧正😁😁😁，谢谢啦！当然有好的倡议也谢谢提出来

（玩笑）

以后前端框架都有 diff 算法，作用次要是解决比对虚构 Dom（Vnode），最大化复用旧节点，最初渲染为实在 Dom, 最大化升高节点创立、删除的的开销。

老样子，原本写一篇文章的。货色越写越多就裂开了🤣

【第一篇】和面试官聊聊 Diff___React(本文)
【第二篇】和面试官聊聊 Diff___vue2
【第三篇】和面试官聊聊 Diff___Vue3

好了，不说废话了。咱们开始吧。

前言

vue、react 中都是组件形成，每个组件又是标签元素形成。

我次要技术栈是 Vue。略微说一下 vue
vue 编译会波及到几个过程【参考分析 Vue.js 外部运行机制, 举荐看看】

parse（解析）=> optimize（优化）=> generate（节点生成）

  • parse（解析）
    将模板字符串解析为 AST(在计算机科学中，形象语法树（abstract syntax tree 或者缩写为 AST），或者语法树（syntax tree），是源代码的形象语法结构的树状表现形式，这里特指编程语言的源代码），外面含有 class、style 等。如果要学正则，也能够看看，写的真不错的。
  • optimize（优化）
    optimize 的次要作用是标记 static 动态节点，这是 Vue 在编译过程中的一处优化，前面当 update 更新界面时，会有一个 patch 的过程，diff 算法会间接跳过动态节点，从而缩小了比拟的过程，优化了 patch 的性能。
  • generate（节点生成）
    generate 是将 AST 转化成 render function 字符串的过程，失去后果是 render 的字符串以及 staticRenderFns 字符串。

这个 diff 算法是处在 optimize(优化) 阶段的一个操作。

另外，各个框架的节点比对都是同级比对，即同一层级的相应子节点比对。

本文重视的是 patch 过程，具体的细节和边界就没有思考。

== 另 外 注 意 ==

  • 三篇文章 diff 的解说，为了不便展现 节点复用，用了 children 保留内容，实际上这是不合理的，因为 children 不同还会递归补丁（patch）
  • diff 也不是 vue optimize 的全副，只是其中一部分，例如 compile 时确定节点类型，不同类型 不同的 mount/patch 解决形式等等。

React_diff

基本思路

先说思路，
当初比如说由若干个新老节点（preNodes / nextNodes )。

  • 先将新节点 (nextNodes) 与老节点 (preNodes) 一一比对，
  • 遇到雷同的节点（本文假如 key 雷同即雷同），依据索引绝对大小判断节点是否须要挪动
  • 遇到新节点，就挂载到 nextNodes 中上一个节点的后面
  • 最初将挪动后的节点（newNodes）与新节点 (nextNodes ) 比对去除多余节点

最初的后果就是由 nextNodes、preNodes 产生的 节点树（newNodes）。

比方有如下新旧节点：

// 旧节点
const preNodes = [{key: "k-1", children: "<span>old1</span>"},
  {key: "k-2", children: "<span>old2</span>"},
  {key: "k-3", children: "<span>old3</span>"},
  {key: "k-4", children: "<span>old4</span>"},
  {key: "k-5", children: "<span>old5</span>"},
  {key: "k-6", children: "<span>old6</span>"},
]
// 新节点，想要最初出现的节点
const nextNodes = [{key: "k-11", children: "<span>11</span>"},
  {key: "k-0", children: "<span>0</span>"},
  {key: "k-5", children: "<span>5</span>"},
  {key: "k-13", children: "<span>13</span>"},
  {key: "k-1", children: "<span>1</span>"},
  {key: "k-7", children: "<span>7</span>"},
  {key: "k-16", children: "<span>16</span>"},
  {key: "k-3", children: "<span>3</span>"},
  {key: "k-15", children: "<span>15</span>"},
  {key: "k-17", children: "<span>7</span>"},
  {key: "k-4", children: "<span>4</span>"},
  {key: "k-6", children: "<span>6</span>"}
]

如上，在 preNodes 里如果有老节点能够复用，便用老节点代替他。冀望的后果应该是

能够看到老节点都失去了复用~

上面就具体解说失去最初新节点的过程。

图例解说

  • i 是 nextNodes 的索引，j 是 preNodes 的索引，每个 nextNode 都要与所有 preNode 节点作比对。
  • preNodes的上一个索引节点橙色标记，虚线标记以后遍历的节点，绿色为新增节点，j 标记的是相等的节点(如果有）

初始状态，新生成节点（newNodes）基于老节点

i=0, lastIndex=0 (默认值)，k-11 在 preNodes 未找到，为新节点。插入至 0 后

i=1, lastIndex=0（默认值），k-0 在 preNodes 未找到，为新节点。插入至 i -1 节点前面

i=2, lastIndex=4（更新后），k-5 在 preNodes 找到索引（j=4 > lastIndex,index 更新）插入（删除 + 新增），复用节点

i=3, lastIndex=4，k-13 在 preNodes 未找到，为新节点。插入至 i -1 节点 后

i=4, lastIndex=4，k-1 在 preNodes 找到索引（j=0 < lastIndex）插入（删除 + 新增）至 i - 1 后

i=5, lastIndex=0，k-7 在 preNodes 未找到，为新节点。插入至 i-1 节点后

i=6, lastIndex=0，k-16 在 preNodes 未找到，为新节点。插入至 i -1 节点后

i=7, lastIndex=4，k-3 在 preNodes 找到索引（j=2 < lastIndex）插入（删除 + 新增）至 i - 1 后

i=8, lastIndex=0，k-5 在 preNodes 未找到，为新节点。插入至 i -1 节点后

i=9, lastIndex=0，k-17 在 preNodes 未找到，为新节点。插入至 i-1 节点 后
i=10, lastIndex=4，k-4 在 preNodes 找到索引（j=3 < lastIndex）插入（删除 + 新增）至 i - 1 后

i=11, lastIndex=6（更新后），k-6 在 preNodes 找到索引（j=5 > lastIndex,index 更新）插入（删除 + 新增），复用节点

遍历实现，革除多余节点。

最终后果

倡议认真了解。

代码实现

本节是代码的具体实现，不多做解说，如果有任何疑虑倡议精度图例解说。或者留言交换，非常欢送~~~

初版

// React_diff()
function React_diff(){console.log(nextNodes.map(item => item.key));
  const newNodes = JSON.parse(JSON.stringify(preNodes));
  let lastIndex = 0;
  for(let i=0; i< nextNodes.length; i++){const nextNode = nextNodes[i];
    let find = false;
    for(let j=0; j< preNodes.length; j++){const preNode = preNodes[j];
      if(preNode.key === nextNode.key){
        find = true;
        if(j < lastIndex){ // 须要挪动
          /* 
            insertBefore 成果时遇到同样的删除原来的再增加，这里因为是数组模仿，所以须要先增加再删除 ,
            数组解决有点不同，插入和删除索引 都是从老节点找的。[1,2,3].splice(0,0,4) => [4,1,2,3]
          */
          const index = i > 0 ? i-1 : 0;
          const insertPos = newNodes.findIndex(node => node.key === nextNodes[index].key);
          const deleteIndex = newNodes.findIndex(node => node.key === preNode.key);

          // 增加因为 splice 是在某索引后面加。所以 insertPos+1
          newNodes.splice(insertPos+1, 0, preNode)
          // 删除
          newNodes.splice(deleteIndex, 1);
        }else {lastIndex = j;}
      }
    }
    if(!find) {// 插入新节点
      const index = i > 0 ? i-1 : 0;
      const insertPos = newNodes.findIndex(node => node.key === nextNodes[index].key);
      newNodes.splice(insertPos + 1, 0, nextNode);
    }
  }
  
  for(let i = newNodes.length - 1; i>=0; i--){
    let find = false;
    for(let j =0; j<nextNodes.length; j++){if(nextNodes[j].key === newNodes[i].key){
        find = true;
        continue;
      }
    }
    if(!find){newNodes.splice(i, 1);
    }
  }
  console.log('react diff:', newNodes);
}

优化版

优化点能够利用 key 与 index 的做个对应关系，少一层遍历.

function React_diff(){const newNodes = JSON.parse(JSON.stringify(preNodes));
  let lastIndex = 0;

  // 产生 nextNodes 的 keyInIndexmap
  const prekeyInIndex = {};
  for(let i =0; i< preNodes.length; i++){prekeyInIndex[preNodes[i].key] = i;
  }

  for(let i=0; i< nextNodes.length; i++){const nextNode = nextNodes[i];
    let find = false;
    const j = prekeyInIndex[nextNode.key];
    if(typeof j !== 'undefined') {
      find = true;
      const preNode = preNodes[j];
      console.log(j, lastIndex);
      if(j < lastIndex){ // 须要挪动
        /* 
          insertBefore 成果时遇到同样的删除原来的再增加，这里因为是数组模仿，所以须要先增加再删除 ,
          数组解决有点不同，插入和删除索引 都是从老节点找的。[1,2,3].splice(0,0,4) => [4,1,2,3]
        */
        const index = i > 0 ? i-1 : 0;
        const insertPos = newNodes.findIndex(node => node.key === nextNodes[index].key);
        const deleteIndex = newNodes.findIndex(node => node.key === preNode.key);

        // 增加因为 splice 是在某索引后面加。所以 insertPos+1
        newNodes.splice(insertPos+1, 0, preNode)
        // 删除
        newNodes.splice(deleteIndex, 1);
      }else {lastIndex = j;}
    }
    if(!find) {// 插入新节点
      const index = i > 0 ? i-1 : 0;
      const insertPos = newNodes.findIndex(node => node.key === nextNodes[index].key);
      newNodes.splice(insertPos + 1, 0, nextNode);
    }
  }
  
  // 产生 nextNodes 的 keyInIndexmap
  const nextkeyInIndex = {};
  for(let i =0; i< nextNodes.length; i++){nextkeyInIndex[nextNodes[i].key] = i;
  }
  for(let i = newNodes.length - 1; i>=0; i--){const idx = nextkeyInIndex[newNodes[i].key];
    if(typeof idx === 'undefined'){newNodes.splice(i, 1);
    }
  }
  console.log('react diff:', newNodes);
}

总结

本文中例子只是为了更好了解 diff 思路, patch 过程与真实情况还有些差别（上面为与 vue patch 的一些差别。可做参考）

  • 反复节点问题。新老节点有反复节点时，本文 diff 函数没解决这种状况。
  • 仅是用数组模仿了 Vnode, 实在的 Vnode 不止 key 和 children, 还有更多的参数
  • 比对雷同节点时，仅比对了 key, 实在其实还波及到 class（类名）、attrs（属性值）、孩子节点（递归）等属性比对; 另外下面的 children 也要比对若不同也要递归遍历
  • 插入、删除、增加节点我用的数组。其实应该用 insertbefore、delete、add。这些办法均是独自封装不能采纳绝对应的 Dom Api, 因为 vue 不止用在浏览器环境。
  • …

Vue@3.2⇲ 曾经进去了，React@18也快了，哎，框架学不完。还是多看看不变的货色吧（js, 设计模式，数据结构，算法 …）

哎哎哎，，同志，看完怎么不点赞，别看他人就说你呢，你几个意思？

参考

站在他人肩膀能看的更远。

【举荐】vue-design
【掘金小册】分析 Vue.js 外部运行机制
【CSDN】React、Vue2.x、Vue3.0 的 diff 算法

以上。

正文完
前端
发表至： 前端
2021-06-15
 0
618-大促背后的淘系前端技术体系
关于前端:微信小程序分享功能的实现方法有两种
关于前端:Mobx-源码与设计思想
关于前端:BFEdev前端刷题-104-按层遍历DOM树