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

最近看了 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 解决形式等等。

先说思路，
当初比如说由若干个新老节点（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 算法

以上。

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

前言

React_diff

基本思路

图例解说

代码实现

初版

优化版

总结

参考