一文带你彻底搞定Diff算法

时间:2021-09-12 04:00:10

一文带你彻底搞定Diff算法

一、基础

Diff算法实现的是最小量更新虚拟DOM。这句话虽然简短,但是涉及到了两个核心要素:虚拟DOM、最小量更新。

1.虚拟DOM

虚拟DOM指的就是将真实的DOM树构造为js对象的形式,从而解决浏览器操作真实DOM的性能问题。

例如:如下DOM与虚拟DOM之间的映射关系

一文带你彻底搞定Diff算法

2.最小量更新

Diff的用途就是在新老虚拟DOM之间找到最小更新的部分,从而将该部分对应的DOM进行更新。

二、整个流程

Diff算法真的很美,整个流程如下图所示:

一文带你彻底搞定Diff算法

  1. 首先比较一下新旧节点是不是同一个节点(可通过比较sel(选择器)和key(唯一标识)值是不是相同),不是同一个节点则进行暴力删除(注:先以旧节点为基准插入新节点,然后再删除旧节点)。
  2. 若是同一个节点则需要进一步比较

完全相同,不做处理

新节点内容为文本,直接替换完事

新节点有子节点,这个时候就要仔细考虑一下了:若老节点没有子元素,则直接清空老节点,将新节点的子元素插入即可;若老节点有子元素则就需要按照上述的更新策略老搞定了(记住更新策略,又可以吹好几年了,666666)。

三、实战

光说不练假把式,下面直接输出diff算法的核心内容。

3.1 patch函数

Diff算法的入口函数,主要判断新旧节点是不是同一个节点,然后交由不同的逻辑进行处理。

  1. export default function patch(oldVnode, newVnode) { 
  2.     // 判断传入的第一个参数,是DOM节点还是虚拟节点 
  3.     if (oldVnode.sel === '' || oldVnode.sel === undefined) { 
  4.         // 传入的第一个参数是DOM节点,此时要包装成虚拟节点 
  5.         oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], undefined, oldVnode); 
  6.     } 
  7.  
  8.     // 判断oldVnode和newVnode是不是同一个节点 
  9.     if (oldVnode.key === newVnode.key && oldVnode.sel === newVnode.sel) { 
  10.         //是同一个节点,则进行精细化比较 
  11.         patchVnode(oldVnode, newVnode); 
  12.     } 
  13.     else { 
  14.         // 不是同一个节点,暴力插入新的,删除旧的 
  15.         let newVnodeElm = createElement(newVnode); 
  16.  
  17.         // 将新节点插入到老节点之前 
  18.         if (oldVnode.elm.parentNode && newVnodeElm) { 
  19.             oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm); 
  20.         } 
  21.         // 删除老节点 
  22.         oldVnode.elm.parentNode.removeChild(oldVnode.elm); 
  23.     } 

3.2 patchVnode函数

该函数主要负责精细化比较,通过按照上述流程图中的逻辑依次判断属于哪一个分支,从而采取不同的处理逻辑。(思路清晰,算法太牛了)

  1. export default function patchVnode(oldVnode, newVnode) { 
  2.     // 判断新旧vnode是否是同一个对象 
  3.     if (oldVnode === newVnode) { 
  4.         return
  5.     } 
  6.     // 判断vnode有没有text属性 
  7.     if (newVnode.text !== undefined && (newVnode.children === undefined || newVnode.children.length === 0)) { 
  8.         console.log('新vnode有text属性'); 
  9.         if (newVnode.text !== oldVnode.text) { 
  10.             oldVnode.elm.innerText = newVnode.text; 
  11.         } 
  12.     } 
  13.     else { 
  14.         // 新vnode没有text属性,有children 
  15.         console.log('新vnode没有text属性'); 
  16.         // 判断老的有没有children 
  17.         if (oldVnode.children !== undefined && oldVnode.children.length > 0) { 
  18.             // 老的有children,新的也有children 
  19.             updateChildren(oldVnode.elm, oldVnode.children, newVnode.children); 
  20.         } 
  21.         else { 
  22.             // 老的没有children,新的有children 
  23.             // 清空老的节点的内容 
  24.             oldVnode.elm.innerHTML = ''
  25.             // 遍历新的vnode的子节点,创建DOM,上树 
  26.             for (let i = 0; i < newVnode.children.length; i++) { 
  27.                 let dom = createElement(newVnode.children[i]); 
  28.                 oldVnode.elm.appendChild(dom); 
  29.             } 
  30.         } 
  31.     } 

3.3 updateChildren函数

核心函数,主要负责旧虚拟节点和新虚拟节点均存在子元素的情况,按照比较策略依次进行比较,最终找出子元素中变化的部分,实现最小更新。对于该部分,涉及到一些指针,如下所示:

一文带你彻底搞定Diff算法

  1. 旧前指的就是更新前虚拟DOM中的头部指针
  2. 旧后指的就是更新前虚拟DOM中的尾部指针
  3. 新前指的就是更新后虚拟DOM中的头部指针
  4. 新后指的就是更新后虚拟DOM中的尾部指针

按照上述的更新策略,上述旧虚拟DOM更新为新虚拟DOM的流程为:

  1. 命中“新后旧前”策略,然后将信后对应的DOM节点(也就是节点1)移动到旧后节点(节点3)后面,然后旧前节点指针下移,新后节点指针上移。
  2. 仍然命中“新后旧前”策略,做相同的操作,将节点2移动到旧后节点(节点3)后面,下移旧前节点,上移新后节点。
  3. 命中“新前旧前”策略,DOM节点不变,旧前和新前节点均下移。
  4. 跳出循环,移动结束。
  1. export default function updateChildren(parentElm, oldCh, newCh) { 
  2.     // 旧前 
  3.     let oldStartIdx = 0; 
  4.     // 新前 
  5.     let newStartIdx = 0; 
  6.     // 旧后 
  7.     let oldEndIdx = oldCh.length - 1; 
  8.     // 新后 
  9.     let newEndIdx = newCh.length - 1; 
  10.     // 旧前节点 
  11.     let oldStartVnode = oldCh[0]; 
  12.     // 旧后节点 
  13.     let oldEndVnode = oldCh[oldEndIdx]; 
  14.     // 新前节点 
  15.     let newStartVnode = newCh[0]; 
  16.     // 新后节点 
  17.     let newEndVnode = newCh[newEndIdx]; 
  18.  
  19.     let keyMap = null
  20.  
  21.     while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { 
  22.         // 略过已经加undefined标记的内容 
  23.         if (oldStartVnode == null || oldCh[oldStartIdx] === undefined) { 
  24.             oldStartVnode = oldCh[++oldStartIdx]; 
  25.         } 
  26.         else if (oldEndVnode == null || oldCh[oldEndIdx] === undefined) { 
  27.             oldEndVnode = oldCh[--oldEndIdx]; 
  28.         } 
  29.         else if (newStartVnode == null || newCh[newStartIdx] === undefined) { 
  30.             newStartVnode = newCh[++newStartIdx]; 
  31.         } 
  32.         else if (newEndVnode == null || newCh[newEndIdx] === undefined) { 
  33.             newEndVnode = newCh[--newEndIdx]; 
  34.         } 
  35.         else if (checkSameVnode(oldStartVnode, newStartVnode)) { 
  36.             // 新前与旧前 
  37.             console.log('新前与旧前命中'); 
  38.             patchVnode(oldStartVnode, newStartVnode); 
  39.             oldStartVnode = oldCh[++oldStartIdx]; 
  40.             newStartVnode = newCh[++newStartIdx]; 
  41.         } 
  42.         else if (checkSameVnode(oldEndVnode, newEndVnode)) { 
  43.             // 新后和旧后 
  44.             console.log('新后和旧后命中'); 
  45.             patchVnode(oldEndVnode, newEndVnode); 
  46.             oldEndVnode = oldCh[--oldEndIdx]; 
  47.             newEndVnode = newCh[--newEndVnode]; 
  48.         } 
  49.         else if (checkSameVnode(oldStartVnode, newEndVnode)) { 
  50.             console.log('新后和旧前命中'); 
  51.             patchVnode(oldStartVnode, newEndVnode); 
  52.             // 当新后与旧前命中的时候,此时要移动节点,移动新后指向的这个节点到老节点旧后的后面 
  53.             parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling); 
  54.             oldStartVnode = oldCh[++oldStartIdx]; 
  55.             newEndVnode = newCh[--newEndIdx]; 
  56.         } 
  57.         else if (checkSameVnode(oldEndVnode, newStartVnode)) { 
  58.             // 新前和旧后 
  59.             console.log('新前和旧后命中'); 
  60.             patchVnode(oldEndVnode, newStartVnode); 
  61.             // 当新前和旧后命中的时候,此时要移动节点,移动新前指向的这个节点到老节点旧前的前面 
  62.             parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm); 
  63.             oldEndVnode = oldCh[--oldEndIdx]; 
  64.             newStartVnode = newCh[++newStartIdx]; 
  65.         } 
  66.         else { 
  67.             // 四种都没有命中 
  68.             // 制作keyMap一个映射对象,这样就不用每次都遍历老对象了 
  69.             if (!keyMap) { 
  70.                 keyMap = {}; 
  71.                 for (let i = oldStartIdx; i <= oldEndIdx; i++) { 
  72.                     const key = oldCh[i].key
  73.                     if (key !== undefined) { 
  74.                         keyMap[key] = i; 
  75.                     } 
  76.                 } 
  77.             } 
  78.             // 寻找当前这项(newStartIdx)在keyMap中的映射的位置序号 
  79.             const idxInOld = keyMap[newStartVnode.key]; 
  80.             if (idxInOld === undefined) { 
  81.                 // 如果idxInOld是undefined表示踏实全新的项,此时会将该项创建为DOM节点并插入到旧前之前 
  82.                 parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm); 
  83.             } 
  84.             else { 
  85.                 // 如果不是undefined,则不是全新的项,则需要移动 
  86.                 const elmToMove = oldCh[idxInOld]; 
  87.                 patchVnode(elmToMove, newStartVnode); 
  88.                 // 把这项设置为undefined,表示已经处理完这项了 
  89.                 oldCh[idxInOld] = undefined; 
  90.                 // 移动 
  91.                 parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm); 
  92.             } 
  93.             // 指针下移,只移动新的头 
  94.             newStartVnode = newCh[++newStartIdx]; 
  95.         } 
  96.     } 
  97.  
  98.     // 循环结束后,处理未处理的项 
  99.     if (newStartIdx <= newEndIdx) { 
  100.         console.log('new还有剩余节点没有处理,要加项,把所有剩余的节点插入到oldStartIdx之前'); 
  101.         // 遍历新的newCh,添加到老的没有处理的之前 
  102.         for (let i = newStartIdx; i <= newEndIdx; i++) { 
  103.             // insertBefore方法可以自动识别null,如果是null就会自动排到队尾去 
  104.             // newCh[i]现在还没有真正的DOM,所以要调用createElement函数变为DOM 
  105.             parentElm.insertBefore(createElement(newCh[i]), oldCh[oldStartIdx].elm); 
  106.         } 
  107.     } 
  108.     else if (oldStartIdx <= oldEndIdx) { 
  109.         console.log('old还有剩余节点没有处理,要删除项'); 
  110.         // 批量删除oldStart和oldEnd指针之间的项 
  111.         for (let i = oldStartIdx; i <= oldEndIdx; i++) { 
  112.             if (oldCh[i]) { 
  113.                 parentElm.removeChild(oldCh[i].elm); 
  114.             } 
  115.         } 
  116.     } 

原文链接:https://mp.weixin.qq.com/s/RKbOTFAJJ7VEpAJdUI3iTA