一，前言
上篇，diff 算法-比对优化（上），主要涉及以下几个点：
本篇，diff 算法-比对优化（下）
二，比对优化
1，前文回顾
上篇介绍了新老儿子节点可能存在的几种情况及处理方法
针对情况 3 新老儿子节点的比对，采用了头尾双指针的方法：
优先对新老儿子的头头、尾尾、头尾、尾头节点进行比对，若都没有命中再进行乱序比对
2，节点比对的结束条件
直至新老节点一方遍历完成，比对才结束；
即："老的头指针和尾指针重合"或"新的头指针和尾指针重合"；
此时，就是循环中最后一次比对了，D 节点比对完成后节点继续后移
与老节点比对完成后（已经识别了可复用的节点），继续将新增节点 E 添加到老儿子节点中
代码实现：
// src/vdom/patch.js
/** * 新老都有儿子时做比对，即 diff 算法核心逻辑 * 备注：采用头尾双指针的方式；优化头头、尾尾、头尾、尾头的特殊情况； * @param {*} el * @param {*} oldChildren 老的儿子节点 * @param {*} newChildren 新的儿子节点 */function updateChildren(el, oldChildren, newChildren) { // 声明头尾指针 let oldStartIndex = 0; let oldStartVnode = oldChildren[0]; let oldEndIndex = oldChildren.length - 1; let oldEndVnode = oldChildren[oldEndIndex];
let newStartIndex = 0; let newStartVnode = newChildren[0]; let newEndIndex = newChildren.length - 1; let newEndVnode = newChildren[newEndIndex];
// 循环结束条件：有一方遍历完了就结束；即"老的头指针和尾指针重合"或"新的头指针和尾指针重合" while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){ // 1，优先做4种特殊情况比对：头头、尾尾、头尾、尾头 // 2，如果没有命中，采用乱序比对 // 3，比对完成后移动指针，继续下一轮比对 }
// 比对完成后 // 新的多，插入新增节点，删除多余节点}
复制代码
备注：由于 diff 算法采用了 while 循环处理，所以复杂度为 O(n)
3，情况 1：新儿子比老儿子多，插入新增的
分为“从头部开始移动指针”和“从尾部部开始移动指针”两种情况
从头部开始移动指针
头头比对：
第一次比配，匹配后移动新老头指针：
第二次匹配，匹配后移动新老头指针：
直至老节点的头尾指针重合，此时，D 节点是 while 最后一次做比对：
比对完成后，指针继续后移，导致老节点的头指针越过尾指针，此时 while 循环结束；
while 循环结束时的指针状态如下：
此时，新节点的头指针指向的节点 E 为新增节点，后面可能还有 F G H 等新增节点，需要将它们（ 指从 newStartIndex 到 newEndIndex 所有节点），添加到老节点儿子集合中
代码实现：
while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){ // 头头比对： if(isSameVnode(oldStartVnode, newStartVnode)){ // isSameVnode只能判断标签和key一样，但属性可能还有不同 // 所以需要patch方法递归更新新老虚拟节点的属性 patch(oldStartVnode, newStartVnode); // 更新新老头指针和新老头节点 oldStartVnode = oldStartVnode[++oldStartIndex]; newStartVnode = newStartVnode[++newStartIndex]; } }
// 1，新的多，插入新增的 if(newStartIndex <= newEndIndex){ // 新的开始指针和新的结束指针之间的节点 for(let i = newStartIndex; i <= newEndIndex; i++){ // 获取对应的虚拟节点，并生成真实节点，添加到 dom 中 el.appendChild(createElm(newChildren[i])) } }h
复制代码
测试效果：
let render1 = compileToFunction(`<div> <li key="A">A</li> <li key="B">B</li> <li key="C">C</li> <li key="D">D</li></div>`);
let render2 = compileToFunction(`<div> <li key="A" style="color:red">A</li> <li key="B" style="color:blue">B</li> <li key="C" style="color:yellow">C</li> <li key="D" style="color:pink">D</li> <li key="E">E</li> <li key="F">F</li></div>`);
复制代码
更新前：
更新后：
备注：将新儿子中新增的节点直接向后添加到老儿子集合中，使用 appendChild 即可但是，如果新增的节点在头部，就不能用 appendChild 了，见下面尾尾比对分析；
复制代码
从尾部开始移动指针
尾尾比对：
指针向前移动，当老节点的头尾指针重合，即 while 循环的最后一次比对：
比对完成指针向前移动后，循环结束时的指针状态如下：
while 比对完成后，需要将剩余新节点添加到老儿子中的对应位置
问题：如何向头部位置新增节点
问题：如何将新增节点 E、F 放到 A 的前面？
分析：
先处理 E 节点，将 E 节点方到 A 节点前的位置：
再处理 F 节点，将 F 节点插入到 A 节点与 E 节点之间的位置：
当新增区域的头尾指针重合，即为最后一次处理；
方案：
新增节点有可能追加到后面，也有可能插入到前面
如何确认该向前还是向后添加节点？
要看 while 循环结束时，newChildren[newEndIndex + 1]新儿子的尾指针是否有节点
代码实现：
// 1，新的多（以新指针为参照）插入新增if (newStartIndex <= newEndIndex) { // 新的开始指针和新的结束指针之间的节点 for (let i = newStartIndex; i <= newEndIndex; i++) { // 判断当前尾节点的下一个元素是否存在： // 1，如果存在：则插入到下一个元素的前面 // 2，如果不存在（下一个是 null） ：就是 appendChild // 取参考节点 anchor:决定新节点放到前边还是后边 // 逻辑：取去newChildren的尾部+1,判断是否为 null // 解释：如果有值说明是向前移动的，取出此虚拟元素的真实节点el，将新节点添加到此真实节点前即可 let anchor = newChildren[newEndIndex + 1] == null ? null : newChildren[newEndIndex + 1].el // 获取对应的虚拟节点，并生成真实节点，添加到 dom 中 // el.appendChild(createElm(newChildren[i])) // 逻辑合并:将 appendChild 改为 insertBefore // 效果：既有appendChild又有insertBefore的功能，直接将参考节点放进来即可; // 解释：对于insertBefore方法,如果anchor为null，等同于appendChild;如果有值，则是insertBefore; el.insertBefore(createElm(newChildren[i]),anchor) }}
复制代码
备注：注意这里的 el.insertBefore 妙用，当 insertBefore 方法的第二个参数为 null 时，等同于 appendChild 方法
复制代码
4，情况 2：老儿子比新儿子多，删除多余
let render1 = compileToFunction(`<div> <li key="A" style="color:red">A</li> <li key="B" style="color:blue">B</li> <li key="C" style="color:yellow">C</li> <li key="D" style="color:pink">D</li></div>`);
let render2 = compileToFunction(`<div> <li key="A" style="color:red">A</li> <li key="B" style="color:blue">B</li> <li key="C" style="color:yellow">C</li></div>`);
复制代码
老的比新的多，在移动过程中就会出现：新的已经到头了时，老的还有
当移动结束时：老的头指针会和尾指针重合，新的头指针会越过新的尾指针
代码实现：
将老儿子集合，“从头指针到尾指针”区域的多余真实节点删除
// 2，老儿子比新儿子多，（以旧指针为参照）删除多余的真实节点if(oldStartIndex <= oldEndIndex){ for(let i = oldStartIndex; i <= oldEndIndex; i++){ let child = oldChildren[i]; el.removeChild(child.el); }}
复制代码
5，情况 3：反序情况
反序情况
这种情况下，可以使用“旧的头指针”和“新的尾指针”进行比较，即头尾比较
每次比较完成后，“旧的头指针”向后移动，“新的尾指针”向前移动
并且比较完成后，直接将老节点 A 放到老节点最后去
更确切的说，是插入到尾指针的下一个节点的前面（移动前，尾指针指向的 D 节点的下一个节点为 null）
继续比较 B，比较完成后移动指针
移动 B ：插入到尾指针的下一个的前面（这时尾指针 D 的下一个是上一次移动过来的 A）
继续 C 和 C 比，之后再移动指针：
移动 C ：插入到尾指针的下一个的前面（这时尾指针 D 的下一个是上一次移动过来的 B）
接下来比较 D，此时会发现“旧的头指针”和“新的头指针”一样了，都是 D
这时就比较完成了，D 无需再移动，结果就是 D C B A（整个反序过程，共移动了 3 次，移动而不是重新创建）
所以，对于反序操作来说，需要去比对头尾指针（老的头和新的尾），
每次比对完成后头指针向后移，尾指针向左移
代码部分，添加“头尾比较”逻辑：
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) { if (isSameVnode(oldStartVnode, newStartVnode)) { patch(oldStartVnode, newStartVnode); oldStartVnode = oldChildren[++oldStartIndex]; newStartVnode = newChildren[++newStartIndex]; }else if(isSameVnode(oldEndVnode, newEndVnode)){ patch(oldEndVnode, newEndVnode); oldEndVnode = oldChildren[--oldEndIndex]; newEndVnode = newChildren[--newEndIndex]; // 头尾比较：老的头节点和新的尾节点做对比 }else if(isSameVnode(oldStartVnode, newEndVnode)){ // patch方法只会duff比较并更新属性，但元素的位置不会变化 patch(oldStartVnode, newEndVnode);// diff:包括递归比儿子 // 移动节点：将当前的节点插入到最后一个节点的下一个节点的前面去 el.insertBefore(oldStartVnode.el, oldEndVnode.el.nextSibling); // 移动指针 oldStartVnode = oldChildren[++oldStartIndex]; newEndVnode = newChildren[--newEndIndex]; }}
复制代码
注意：
要先插入节点，再移动指针insertBefore是有移动效果的，会把原来的节点移走，这时 dom 的移动性appendChild、insertBefore操作 dom 都有移动性，都会吧原来的 dom 移走
复制代码
测试效果：
更新前：
更新后：
同理尾头比对的情况：
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) { if (isSameVnode(oldStartVnode, newStartVnode)) { patch(oldStartVnode, newStartVnode); oldStartVnode = oldChildren[++oldStartIndex]; newStartVnode = newChildren[++newStartIndex]; }else if(isSameVnode(oldEndVnode, newEndVnode)){ patch(oldEndVnode, newEndVnode); oldEndVnode = oldChildren[--oldEndIndex]; newEndVnode = newChildren[--newEndIndex]; }else if(isSameVnode(oldStartVnode, newEndVnode)){ patch(oldStartVnode, newEndVnode); el.insertBefore(oldStartVnode.el, oldEndVnode.el.nextSibling); oldStartVnode = oldChildren[++oldStartIndex]; newEndVnode = newChildren[--newEndIndex]; // 尾头比较 }else if(isSameVnode(oldEndVnode, newStartVnode)){ patch(oldEndVnode, newStartVnode); // patch方法只会更新属性，元素的位置不会变化 // 移动节点:将老的尾节点移动到老的头节点前面去 el.insertBefore(oldEndVnode.el, oldStartVnode.el);// 将尾部插入到头部 // 移动指针 oldEndVnode = oldChildren[--oldEndIndex]; newStartVnode = newChildren[++newStartIndex]; }}
复制代码
测试效果：
let render1 = compileToFunction(`<div> <li key="E">E</li> <li key="A">A</li> <li key="B">B</li> <li key="C">C</li> <li key="D">D</li></div>`);
let render2 = compileToFunction(`<div> <li key="D" style="color:pink">D</li> <li key="C" style="color:yellow">C</li> <li key="B" style="color:blue">B</li> <li key="A" style="color:red">A</li></div>`);
复制代码
更新前：
更新后：
三，结尾
本篇，diff 算法-比对优化（下），主要涉及以下几个点：
下篇，diff 算法-乱序比对;
评论