和面试官聊聊Diff___React

ethanYin 2021-06-15 23:54:14
前端 react.js diff


最近看了 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(节点生成)

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

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

本文注重的是patch过程,具体的细节和边界就没有考虑。

==另 外 注 意==

  • 三篇文章 diff 的讲解,为了方便展示 节点复用, 用了 children 保存内容,实际上这是不合理的,因为children不同还会递归补丁(patch)
  • diff也不是vue optimize的全部,只是其中一部分,例如compile时确定节点类型,不同类型 不同的 mount/patch 处理方式等等。

React_diff

基本思路

先说思路,
现在比如说由若干个新老节点(preNodes / nextNodes )。

  • 先将新节点(nextNodes)与老节点(preNodes)一一比对,
  • 遇到相同的节点(本文假设key相同即相同),根据索引相对大小判断节点是否需要移动
  • 遇到新节点,就挂载到 nextNodes 中上一个节点的前面
  • 最后将移动后的节点(newNodes)与新节点( nextNodes )比对去除多余节点

最后的结果就是由 nextNodespreNodes 产生的 节点树(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-11preNodes 未找到, 为新节点。插入至 0
在这里插入图片描述
i=1, lastIndex=0(默认值),k-0preNodes 未找到, 为新节点。插入至 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-1preNodes 找到索引(j=0 < lastIndex)插入(删除+新增)至 i - 1
在这里插入图片描述

i=5, lastIndex=0,k-7preNodes 未找到,为新节点。插入至 i-1 节点后
在这里插入图片描述

i=6, lastIndex=0,k-16preNodes 未找到,为新节点。插入至 i -1 节点后
在这里插入图片描述

i=7, lastIndex=4,k-3preNodes 找到索引(j=2 < lastIndex)插入(删除+新增)至 i - 1
在这里插入图片描述

i=8, lastIndex=0,k-5preNodes 未找到,为新节点。插入至 i -1 节点后
在这里插入图片描述

i=9, lastIndex=0,k-17preNodes 未找到,为新节点。插入至 i-1 节点 后
在这里插入图片描述i=10, lastIndex=4,k-4 在preNodes找到索引(j=3 < lastIndex)插入(删除+新增)至 i - 1
在这里插入图片描述

i=11, lastIndex=6(更新后),k-6preNodes 找到索引(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也要比对若不同也要递归遍历
  • 插入、删除、添加节点我用的数组。其实应该用 insertbeforedeleteadd。这些方法均是单独封装不能采用相对应的 Dom Api,因为 vue 不止用在浏览器环境
  • ...

[email protected] 已经出来了,[email protected]也快了,哎,框架学不完。还是多看看不变的东西吧(js, 设计模式, 数据结构,算法...)

哎哎哎,,同志,看完怎么不点赞,别看别人就说你呢,你几个意思?
在这里插入图片描述


参考

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

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


以上。
在这里插入图片描述

版权声明
本文为[ethanYin]所创,转载请带上原文链接,感谢
https://segmentfault.com/a/1190000040179618

  1. HTML + CSS + JavaScript to achieve cool Fireworks (cloud like particle text 3D opening)
  2. HTML + CSS + JavaScript realizes 520 advertising love tree (including music), which is necessary for programmers to express themselves
  3. Solve the problem of Web front-end deployment server (it can be deployed online without a server)
  4. HTML + CSS + JS make wedding countdown web page template (520 / Tanabata Valentine's Day / programmer advertisement)
  5. What else can driverless minibus do besides "Park connection"?
  6. Cloud native leads the era of all cloud development
  7. NRM mirror source management tool
  8. Bring it to you, flex Jiugong
  9. Lolstyle UI component development practice (II) -- button group component
  10. Deconstruction assignment in ES6
  11. Luo 2 peerless Tang clan was officially launched. The official gave a key point, and the broadcast time was implied
  12. 20初识前端HTML(1)
  13. 当新零售遇上 Serverless
  14. 20 initial knowledge of front-end HTML (1)
  15. When new retail meets serverless
  16. [golang] - go into go language lesson 5 type conversion
  17. [golang] - go into go language lesson 6 conditional expression
  18. HTML5(八)——SVG 之 path 详解
  19. HTML5 (8) -- detailed explanation of SVG path
  20. 需要开通VIP以后页面内容才能复制怎么办?控制台禁用javascript即可
  21. Web前端|CSS入门教程(超详细的CSS使用讲解,适合前端初学者)
  22. 实践积累 —— 用Vue3简单写一个单行横向滚动组件
  23. Serverless 全能选手,再下一城
  24. What if you need to open a VIP to copy the page content? Just disable JavaScript on the console
  25. Web front end | CSS introductory tutorial (super detailed CSS explanation, suitable for front-end beginners)
  26. Practice accumulation - write a single line horizontal scroll component simply with vue3
  27. Dili Reba is thin again. She looks elegant and high in a strapless hollow skirt, and her "palm waist" is beautiful to a new height
  28. Serverless all-round player, next city
  29. The difference between MySQL semi synchronous replication and lossless semi synchronous replication
  30. Vue表单设计器的终极解决方案
  31. The ultimate solution for Vue form designer
  32. Nginx从理论到实践超详细笔记
  33. Yu Shuxin's red backless swimsuit is split to the waist and tail, with a concave convex figure and excessive color matching, and his face is white to dazzling
  34. Nginx ultra detailed notes from theory to practice
  35. 【动画消消乐|CSS】086.炫酷水波浪Loading过渡动画
  36. typecho全站启用https
  37. CCTV has another popular employee. The off-site interpretation is very professional, and the appearance ability is no less than that of Wang Bingbing
  38. [animation Xiaole | CSS] 086. Cool water wave loading transition animation
  39. Enable HTTPS in Typecho
  40. 50天用JavaScript完成50个web项目,我学到了什么?
  41. 根据JavaScript中原生的XMLHttpRequest实现jQuery的Ajax
  42. What have I learned from completing 50 web projects with JavaScript in 50 days?
  43. "My neighbor doesn't grow up" has hit the whole network. There are countless horse music circles, and actor Zhou Xiaochuan has successfully made a circle
  44. 根据JavaScript中原生的XMLHttpRequest实现jQuery的Ajax
  45. Implement the Ajax of jQuery according to the native XMLHttpRequest in JavaScript
  46. Implement the Ajax of jQuery according to the native XMLHttpRequest in JavaScript
  47. 30 + women still wear less T-shirts and jeans. If they wear them like stars, they will lose weight
  48. 数栈技术分享前端篇:TS,看你哪里逃~
  49. Several stack technology sharing front end: TS, see where you escape~
  50. 舍弃Kong和Nginx,Apache APISIX 在趣链科技 BaaS 平台的落地实践
  51. Abandon the landing practice of Kong and nginx, Apache apisik on the baas platform of fun chain technology
  52. 浪迹天涯king教你用elementui做复杂的表格,去处理报表数据(合并表头,合并表体行和列)
  53. 前端HTML两万字图文大总结,快来看看你会多少!【️熬夜整理&建议收藏️】
  54. Wandering around the world king teaches you to use elementui to make complex tables and process report data (merge header, merge table body rows and columns)
  55. 路由刷新数据丢失 - vuex数据读取的问题
  56. Front end HTML 20000 word graphic summary, come and see how much you can【 Stay up late to sort out & suggestions]
  57. Route refresh data loss - vuex data reading problem
  58. Systemctl系统启动Nginx服务脚本
  59. Systemctl system startup nginx service script
  60. sleepless