Vue中的 DOM與Diff詳情

更新時(shí)間：2022年08月15日 11:32:42 作者：夏日

這篇文章主要介紹了Vue中的 DOM與Diff詳情，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，感興趣的小伙伴可以參考一下，希望對(duì)你的學(xué)習(xí)有所幫助

DOM Diff

Vue創(chuàng)建視圖分為倆種情況：

首次渲染，會(huì)用組件template轉(zhuǎn)換成的真實(shí)DOM來(lái)替換應(yīng)用中的根元素
當(dāng)數(shù)據(jù)更新后，視圖重新渲染，此時(shí)并不會(huì)重新通過(guò)組件template對(duì)應(yīng)的虛擬節(jié)點(diǎn)來(lái)創(chuàng)建真實(shí)DOM，而是會(huì)用老的虛擬節(jié)點(diǎn)和新的虛擬節(jié)點(diǎn)進(jìn)行比對(duì)，根據(jù)比對(duì)結(jié)果來(lái)更新DOM

第二種情況就是Vue中經(jīng)常談到的DOM Diff，接下來(lái)我們將詳細(xì)介紹新老節(jié)點(diǎn)的比對(duì)過(guò)程。

整體思路

老的虛擬節(jié)點(diǎn)和新的虛擬節(jié)點(diǎn)是倆棵樹，會(huì)對(duì)倆棵樹每層中的虛擬節(jié)點(diǎn)進(jìn)行比對(duì)操作：

在每一層進(jìn)行對(duì)比時(shí)，會(huì)分別為老節(jié)點(diǎn)和新節(jié)點(diǎn)設(shè)置頭尾指針:

整體的孩子節(jié)點(diǎn)比對(duì)思路如下：

在老的虛擬節(jié)點(diǎn)和新的虛擬節(jié)點(diǎn)的頭尾指針之間都有元素時(shí)進(jìn)行遍歷
對(duì)以下情況進(jìn)行優(yōu)化
老節(jié)點(diǎn)的頭指針和新節(jié)點(diǎn)的頭指針相同
老節(jié)點(diǎn)的尾指針和新節(jié)點(diǎn)的尾指針相同
老節(jié)點(diǎn)的頭指針和新節(jié)點(diǎn)的尾指針相同
老節(jié)點(diǎn)的尾指針和新節(jié)點(diǎn)的頭指針相同
亂序排列時(shí)，要用新節(jié)點(diǎn)的頭節(jié)點(diǎn)到老節(jié)點(diǎn)中查找，如果能找到，對(duì)其復(fù)用并移動(dòng)到相應(yīng)的位置。如果沒(méi)有找到，將其插入到真實(shí)節(jié)點(diǎn)中
遍歷完成后，將新節(jié)點(diǎn)頭指針和尾指針之間的元素插入到真實(shí)節(jié)點(diǎn)中，老節(jié)點(diǎn)頭指針和尾指針之間的元素刪除

在我們渲染視圖之前，需要保存當(dāng)前渲染的虛擬節(jié)點(diǎn)。在下一次渲染視圖時(shí)，它就是老的虛擬節(jié)點(diǎn)，要和新的虛擬節(jié)點(diǎn)進(jìn)行對(duì)比：

// src/lifecycle.js
Vue.prototype._update = function (vNode) {
  const vm = this;
  const preVNode = vm._vNode;
  vm._vNode = vNode;
  if (!preVNode) { // 首次渲染，沒(méi)有前一次的虛擬節(jié)點(diǎn)
    vm.$el = patch(vm.$el, vNode);
  } else { // vm._vNode中存儲(chǔ)了前一次的虛擬節(jié)點(diǎn)，進(jìn)行dom diff
    patch(preVNode, vNode);
  }
};

下面我們實(shí)現(xiàn)patch方法中的邏輯

處理簡(jiǎn)單情況

在patch方法中，首先會(huì)判斷oldVNode是否為真實(shí)DOM。如果不是，會(huì)進(jìn)行DOM diff。

如果新的虛擬節(jié)點(diǎn)和老的虛擬節(jié)點(diǎn)標(biāo)簽不一樣，直接用新的虛擬節(jié)點(diǎn)創(chuàng)建真實(shí)節(jié)點(diǎn)，然后替換老的真實(shí)節(jié)點(diǎn)即可：

const vm1 = new Vue();
const html1 = `
  <div id="app">
    111
  </div>
`;
// 將模板編譯為render函數(shù)
const render1 = compileToFunctions(html1);
const vNode1 = render1.call(vm1);
// 當(dāng)oldVNode為DOM元素時(shí)，會(huì)用新節(jié)點(diǎn)直接替換老節(jié)點(diǎn)
patch(document.getElementById('app'), vNode1);
const html2 = `
  <span id="app">
    333
  </span>
`;
// 將新的模本編譯為render函數(shù)
const render2 = compileToFunctions(html2);
// 生成新的虛擬節(jié)點(diǎn)
const vNode2 = render2.call(vm1);
// 老節(jié)點(diǎn)和新節(jié)點(diǎn)進(jìn)行對(duì)比
patch(vNode1, vNode2);

上述代碼會(huì)直接通過(guò)新的虛擬節(jié)點(diǎn)創(chuàng)建的真實(shí)節(jié)點(diǎn)來(lái)替換老的真實(shí)節(jié)點(diǎn)，patch中的代碼如下：

export function patch (oldVNode, vNode) {
  if (oldVNode.nodeType) { // 舊的節(jié)點(diǎn)為真實(shí)節(jié)點(diǎn)
    // some code...  
  } else { // 新舊節(jié)點(diǎn)都為虛擬節(jié)點(diǎn)，要進(jìn)行dom diff
    if (oldVNode.tag !== vNode.tag) { // 標(biāo)簽不相同，直接用新節(jié)點(diǎn)替換老節(jié)點(diǎn)
      const newEle = createElement(vNode);
      replaceChild(newEle, oldVNode.el);
      return newEle;
    }
  }
}

如果老節(jié)點(diǎn)和新節(jié)點(diǎn)都是文本標(biāo)簽，那么直接用新節(jié)點(diǎn)的文本替換老節(jié)點(diǎn)即可：

// 老的模板
const html1 = `
  <div id="app">
    111
  </div>
`;
// 新的模板
const html2 = `
  <div id="app">
    333
  </div>
`;

上例中的新的文本333會(huì)替換掉老的文本111，patch中的實(shí)現(xiàn)如下：

export function patch (oldVNode, vNode) {
  if (oldVNode.nodeType) { // 舊的節(jié)點(diǎn)為真實(shí)節(jié)點(diǎn)
    // some code ...
  } else { // 新舊節(jié)點(diǎn)都為虛擬節(jié)點(diǎn)，要進(jìn)行dom diff
    if (oldVNode.tag !== vNode.tag) { // 不相等直接替換
      // some code ...
    }
    if (!oldVNode.tag) { // 文本節(jié)點(diǎn),tag相同，都為undefined
      oldVNode.el.textContent = vNode.text;
      return oldVNode.el;
    }
  }
}

當(dāng)老節(jié)點(diǎn)和新節(jié)點(diǎn)的標(biāo)簽相同時(shí)，要更新標(biāo)簽對(duì)應(yīng)真實(shí)元素的屬性，更新規(guī)則如下：

用新節(jié)點(diǎn)中的屬性替換老節(jié)點(diǎn)中的屬性
刪除老節(jié)點(diǎn)中多余的屬性

function updateProperties (vNode, oldProps = {}) { // 老節(jié)點(diǎn)和新節(jié)點(diǎn)的屬性
  const { el, props } = vNode;
  // 用新節(jié)點(diǎn)替換老節(jié)點(diǎn)中的屬性
  for (const key in props) { // 為真實(shí)DOM設(shè)置新節(jié)點(diǎn)的所有屬性
    if (props.hasOwnProperty(key)) {
      const value = props[key];
      if (key === 'style') {
        for (const styleKey in value) {
          if (value.hasOwnProperty(styleKey)) {
            el.style[styleKey] = value[styleKey];
          }
        }
      } else {
        el.setAttribute(key, value);
      }
    }
  }
  // 如果老節(jié)點(diǎn)中有，而新節(jié)點(diǎn)中沒(méi)有，需要將其刪除
  for (const key in oldProps) {
    if (oldProps.hasOwnProperty(key) && !props.hasOwnProperty(key)) {
      el.removeAttribute(key);
    }
  }
  const style = oldProps.style || {};
  const newStyle = props.style || {};
  // 刪除老節(jié)點(diǎn)中多余的樣式
  for (const key in style) {
    if (!newStyle.hasOwnProperty(key) && style.hasOwnProperty(key)) {
      el.style[key] = '';
    }
  }
}

在比對(duì)完當(dāng)前節(jié)點(diǎn)后，要繼續(xù)比對(duì)孩子節(jié)點(diǎn)。孩子節(jié)點(diǎn)可能有以下情況：

老節(jié)點(diǎn)孩子為空，新節(jié)點(diǎn)有孩子：將新節(jié)點(diǎn)的每一個(gè)孩子節(jié)點(diǎn)創(chuàng)建為真實(shí)節(jié)點(diǎn)，插入到老節(jié)點(diǎn)對(duì)應(yīng)的真實(shí)父節(jié)點(diǎn)中
老節(jié)點(diǎn)有孩子，新節(jié)點(diǎn)孩子為空：將老節(jié)點(diǎn)的父節(jié)點(diǎn)的孩子節(jié)點(diǎn)清空
老節(jié)點(diǎn)和新節(jié)點(diǎn)都有孩子: 采用雙指針進(jìn)行對(duì)比

patch中對(duì)應(yīng)的代碼如下：

export function patch (oldVNode, vNode) {
  if (oldVNode.nodeType) { // 舊的節(jié)點(diǎn)為真實(shí)節(jié)點(diǎn)
    // some code ...  
  } else { // 新舊節(jié)點(diǎn)都為虛擬節(jié)點(diǎn)，要進(jìn)行dom diff
    // 元素相同，需要比較子元素
    const el = vNode.el = oldVNode.el;
    // 更新屬性
    updateProperties(vNode, oldVNode.props);
    const oldChildren = oldVNode.children;
    const newChildren = vNode.children;
    // 老的有，新的沒(méi)有，將老的設(shè)置為空
    // 老的沒(méi)有，新的有，為老節(jié)點(diǎn)插入多有的新節(jié)點(diǎn)
    // 老的和新的都有,遍歷每一個(gè)進(jìn)行比對(duì)
    if (!oldChildren.length && newChildren.length) {
      for (let i = 0; i < newChildren; i++) {
        const child = newChildren[i];
        el.appendChild(createElement(child));
      }
      return;
    }
    if (oldChildren.length && !newChildren.length) {
      return el.innerHTML = '';
    }
    if (oldChildren.length && newChildren.length) {
      updateChildren(oldChildren, newChildren, el);
    }
    return el;
  }
}

下面我們的邏輯便到了updateChildren中。

比對(duì)優(yōu)化

在對(duì)孩子節(jié)點(diǎn)的比對(duì)中，對(duì)一些常見(jiàn)的DOM操作通過(guò)雙指針進(jìn)行了優(yōu)化：

列表尾部新增元素
列表頭部新增元素
列表開始元素移動(dòng)到末尾
列表結(jié)尾元素移動(dòng)到開頭

我們?cè)诖a中先聲明需要的變量：

function updateChildren (oldChildren, newChildren, parent) {
  let oldStartIndex = 0, // 老孩子的開始索引
    oldStartVNode = oldChildren[0], // 老孩子的頭虛擬節(jié)點(diǎn) 
    oldEndIndex = oldChildren.length - 1, // 老孩子的尾索引
    oldEndVNode = oldChildren[oldEndIndex]; // 老孩子的尾虛擬節(jié)點(diǎn)
  let newStartIndex = 0, // 新孩子的開始索引
    newStartVNode = newChildren[0], // 新孩子的頭虛擬節(jié)點(diǎn)
    newEndIndex = newChildren.length - 1, // 新孩子的尾索引
    newEndVNode = newChildren[newEndIndex]; // 新孩子的尾虛擬節(jié)點(diǎn)
}

當(dāng)節(jié)點(diǎn)的tag和key都相同時(shí)，我們認(rèn)為這倆個(gè)節(jié)點(diǎn)是同一個(gè)節(jié)點(diǎn)，可以進(jìn)行復(fù)用：

function isSameVNode (oldVNode, newVNode) {
  return oldVNode.key === newVNode.key && oldVNode.tag === newVNode.tag;
}

下面我們分別來(lái)講解對(duì)應(yīng)的優(yōu)化邏輯

尾部新增元素

我們?cè)诶瞎?jié)點(diǎn)孩子的末尾新增一個(gè)元素作為新節(jié)點(diǎn)，其對(duì)應(yīng)的template如下：

const template1 = `
  <div id="app">
    <ul>
      <li key="A" style="color:red">A</li>
      <li key="B" style="color:yellow">B</li>
      <li key="C" style="color:blue">C</li>
      <li key="D" style="color:green">D</li>
    </ul>
  </div>
`;
const template2 = `
  <div id="app">
    <ul>
      <li key="A" style="color:red">A</li>
      <li key="B" style="color:yellow">B</li>
      <li key="C" style="color:blue">C</li>
      <li key="D" style="color:green">D</li>
      <li key="E" style="color:purple">E</li>
    </ul>
  </div>
`;

此時(shí)oldChildren中的頭節(jié)點(diǎn)和newChildren中的頭節(jié)點(diǎn)相同，其比對(duì)邏輯如下：

繼續(xù)對(duì)oldStartVNode和newStartVNode執(zhí)行patch方法，比對(duì)它們的標(biāo)簽、屬性、文本以及孩子節(jié)點(diǎn)
oldStartVNode和newStartVNode同時(shí)后移，繼續(xù)進(jìn)行比對(duì)
遍歷完老節(jié)點(diǎn)后，循環(huán)停止
將新節(jié)點(diǎn)中剩余的元素插入到老的虛擬節(jié)點(diǎn)的尾節(jié)點(diǎn)對(duì)應(yīng)的真實(shí)節(jié)點(diǎn)的下一個(gè)兄弟節(jié)點(diǎn)oldEndVNode.el.nextSibling之前

畫圖演示下詳細(xì)的比對(duì)邏輯：

代碼如下：

function updateChildren (oldChildren, newChildren, parent) {
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    if (isSameVNode(oldStartIndex, newStartIndex)) { // 頭和頭相等
      // 1. 可能是文本節(jié)點(diǎn)：需要繼續(xù)比對(duì)文本節(jié)點(diǎn)
      // 2. 可能是元素：先比對(duì)元素的屬性，然后再比對(duì)子節(jié)點(diǎn)
      patch(oldStartVNode, newStartVNode);
      oldStartVNode = oldChildren[++oldStartIndex];
      newStartVNode = newChildren[++newStartIndex];
    }
  }
  // 新節(jié)點(diǎn)中剩余元素插入到真實(shí)節(jié)點(diǎn)中
  for (let i = newStartIndex; i <= newEndIndex; i++) {
    const child = newChildren[i];
    const refEle = oldChildren[oldEndIndex + 1] || null;
    parent.insertBefore(createElement(child), refEle);
  }
}

頭部新增元素

老節(jié)點(diǎn)的孩子的頭部新增元素E，此時(shí)新老節(jié)點(diǎn)的template結(jié)構(gòu)如下：

const template1 = `
  <div id="app">
    <ul>
      <li key="A" style="color:red">A</li>
      <li key="B" style="color:yellow">B</li>
      <li key="C" style="color:blue">C</li>
      <li key="D" style="color:green">D</li>
    </ul>
  </div>
`;
const template2 = `
  <div id="app">
    <ul>
      <li key="E" style="color:purple">E</li>
      <li key="A" style="color:red">A</li>
      <li key="B" style="color:yellow">B</li>
      <li key="C" style="color:blue">C</li>
      <li key="D" style="color:green">D</li>
    </ul>
  </div>
`;

其比對(duì)邏輯和尾部新增類似，只不過(guò)此時(shí)是oldEndVNode和newEndVNode相同：

繼續(xù)通過(guò)patch比對(duì)oldEndVNode和newEndVNode的標(biāo)簽、屬性、文本及孩子節(jié)點(diǎn)
此時(shí)要將oldEndVNode和newEndVNode同時(shí)前移，繼續(xù)進(jìn)行比對(duì)
遍歷完老節(jié)點(diǎn)后，循環(huán)停止
將新節(jié)點(diǎn)中剩余的元素插入到老的虛擬節(jié)點(diǎn)的尾節(jié)點(diǎn)對(duì)應(yīng)的真實(shí)節(jié)點(diǎn)的下一個(gè)兄弟節(jié)點(diǎn)oldEndVNode.el.nextSibling之前

該邏輯的示意圖如下：

patch中新增代碼如下：

function updateChildren (oldChildren, newChildren, parent) {
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    if (isSameVNode(oldStartIndex, newStartIndex)) { // 頭和頭相等
      // some code ...  
    } else if (isSameVNode(oldEndVNode, newEndVNode)) { // 尾和尾相等
      patch(oldEndVNode, newEndVNode);
      oldEndVNode = oldChildren[--oldEndIndex];
      newEndVNode = newChildren[--newEndIndex];
    }
  }
  // some code ...  
}

開始元素移動(dòng)到末尾

在新節(jié)點(diǎn)中，我們將開始元素A移動(dòng)到末尾，對(duì)應(yīng)的template如下：

const template1 = `
  <div id="app">
    <ul>
      <li key="A" style="color:red">A</li>
      <li key="B" style="color:yellow">B</li>
      <li key="C" style="color:blue">C</li>
      <li key="D" style="color:green">D</li>
    </ul>
  </div>
`;
const template2 = `
  <div id="app">
    <ul>
      <li key="B" style="color:yellow">B</li>
      <li key="C" style="color:blue">C</li>
      <li key="D" style="color:green">D</li>
      <li key="A" style="color:red">A</li>
    </ul>
  </div>
`;

此時(shí)oldStartVNode和newEndVNode相同：

繼續(xù)通過(guò)patch比對(duì)oldStartVNode和newEndVNode的標(biāo)簽、屬性、文本及孩子節(jié)點(diǎn)
將oldStartVNode對(duì)應(yīng)的真實(shí)節(jié)點(diǎn)插入到oldEndVNode對(duì)應(yīng)的真實(shí)節(jié)點(diǎn)之后
oldStartVNode后移，newEndVNode前移
遍歷完新老節(jié)點(diǎn)后，循環(huán)停止，此時(shí)元素已經(jīng)移動(dòng)到了正確的位置

用圖來(lái)演示該過(guò)程：

在patch方法中編寫代碼：

function updateChildren (oldChildren, newChildren, parent) {
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    if (isSameVNode(oldStartIndex, newStartIndex)) { // 頭和頭相等
      // some code ...
    } else if (isSameVNode(oldEndVNode, newEndVNode)) { // 尾和尾相等
      // some code ...
    } else if (isSameVNode(oldStartVNode, newEndVNode)) { // 將開頭元素移動(dòng)到了末尾：尾和頭相同
      // 老節(jié)點(diǎn)：需要將頭節(jié)點(diǎn)對(duì)應(yīng)的元素移動(dòng)到尾節(jié)點(diǎn)之后
      parent.insertBefore(oldStartVNode, oldEndVNode.el.nextSibling);
      patch(oldStartVNode, newEndVNode);
      oldStartVNode = oldChildren[++oldStartIndex];
      newEndVNode = newChildren[--newEndIndex];
    }
  }
}

末尾元素移動(dòng)到開頭

講解到這里，大家可以先停下閱讀的腳步，參考一下之前的邏輯，想想這里會(huì)如何進(jìn)行比對(duì)？

在新節(jié)點(diǎn)中，我們將末尾元素D移動(dòng)到開頭，對(duì)應(yīng)的template如下：

const template1 = `
  <div id="app">
    <ul>
      <li key="A" style="color:red">A</li>
      <li key="B" style="color:yellow">B</li>
      <li key="C" style="color:blue">C</li>
      <li key="D" style="color:green">D</li>
    </ul>
  </div>
`;
const template2 = `
  <div id="app">
    <ul>
      <li key="D" style="color:green">D</li>
      <li key="A" style="color:red">A</li>
      <li key="B" style="color:yellow">B</li>
      <li key="C" style="color:blue">C</li>
    </ul>
  </div>
`;

此時(shí)oldEndVNode和newStartVNode相同：

繼續(xù)通過(guò)patch比對(duì)oldEndVNode和newStartVNode的標(biāo)簽、屬性、文本及孩子節(jié)點(diǎn)
將oldEndVNode對(duì)應(yīng)的真實(shí)節(jié)點(diǎn)插入到oldStartVNode對(duì)應(yīng)的真實(shí)節(jié)點(diǎn)之前
oldEndVNode前移，newStartVNode后移
遍歷完新老節(jié)點(diǎn)后，循環(huán)停止，此時(shí)元素已經(jīng)移動(dòng)到了正確的位置

畫圖來(lái)演示該過(guò)程：

在patch方法中添加處理該邏輯的代碼：

function updateChildren (oldChildren, newChildren, parent) {
  // 更新子節(jié)點(diǎn):
  //  1. 一層一層進(jìn)行比較，如果發(fā)現(xiàn)有一層不一樣，直接就會(huì)用新節(jié)點(diǎn)的子集來(lái)替換父節(jié)點(diǎn)的子集。
  //  2. 比較時(shí)會(huì)采用雙指針，對(duì)常見(jiàn)的操作進(jìn)行優(yōu)化
  let oldStartIndex = 0,
    oldStartVNode = oldChildren[0],
    oldEndIndex = oldChildren.length - 1,
    oldEndVNode = oldChildren[oldEndIndex];
  let newStartIndex = 0,
    newStartVNode = newChildren[0],
    newEndIndex = newChildren.length - 1,
    newEndVNode = newChildren[newEndIndex];

  function makeMap () {
    const map = {};
    for (let i = 0; i < oldChildren.length; i++) {
      const child = oldChildren[i];
      child.key && (map[child.key] = i);
    }
    return map;
  }

  // 將老節(jié)點(diǎn)的key和索引進(jìn)行映射，之后可以直接通過(guò)key找到索引，然后通過(guò)索引找到對(duì)應(yīng)的元素
  // 這樣提前做好映射關(guān)系，可以將查找的時(shí)間復(fù)雜度降到O(1)
  const map = makeMap();
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    if (isSameVNode(oldStartIndex, newStartIndex)) { // 頭和頭相等
      // some code ...
    } else if (isSameVNode(oldEndVNode, newEndVNode)) { // 尾和尾相等
      // some code ...
    } else if (isSameVNode(oldStartVNode, newEndVNode)) { // 將開頭元素移動(dòng)到了末尾：尾和頭相同
      // some code ...
    } else if (isSameVNode(oldEndVNode, newStartVNode)) { // 將結(jié)尾元素移動(dòng)到了開頭
      // 老節(jié)點(diǎn)： 將尾指針元素插入到頭指針之前
      parent.insertBefore(oldEndVNode.el, oldStartVNode.el);
      patch(oldEndVNode, newStartVNode);
      oldEndVNode = oldChildren[--oldEndIndex];
      newStartVNode = newChildren[++newStartIndex];
    }
  }
}

到這里，patch方法中已經(jīng)完成了所有的優(yōu)化操作，下面我們來(lái)看下如何對(duì)比亂序的孩子節(jié)點(diǎn)

亂序比對(duì)

當(dāng)進(jìn)行比對(duì)的元素不滿足優(yōu)化條件時(shí)，就要進(jìn)行亂序?qū)Ρ?。下面是倆個(gè)亂序的template，看下它們的具體比對(duì)過(guò)程：

const html1 = `
  <div id="app">
    <ul>
      <li key="D" style="color:red">D</li>
      <li key="B" style="color:yellow">B</li>
      <li key="Z" style="color:blue">Z</li>
      <li key="F" style="color:green">F</li>
    </ul>
  </div>
`;
const html2 = `
  <div id="app">
    <ul>
      <li key="E" style="color:green">E</li>
      <li key="F" style="color:red">F</li>
      <li key="D" style="color:yellow">D</li>
      <li key="Q" style="color:blue">Q</li>
      <li key="B" style="color:#252a34">B</li>
      <li key="M" style="color:#fc5185">M</li>
    </ul>
  </div>
`;

亂序比對(duì)的邏輯如下：

用新節(jié)點(diǎn)中的頭節(jié)點(diǎn)的key在老節(jié)點(diǎn)中進(jìn)行查找
如果在老節(jié)點(diǎn)中找到key相同的元素，將對(duì)應(yīng)的真實(shí)節(jié)點(diǎn)移動(dòng)到oldStartVNode.el(老虛擬頭節(jié)點(diǎn)對(duì)應(yīng)的真實(shí)節(jié)點(diǎn))之前，并且將其對(duì)應(yīng)的虛擬節(jié)點(diǎn)設(shè)置為null，之后遇到null跳過(guò)即可，不再對(duì)其進(jìn)行比對(duì)。
繼續(xù)通過(guò)patch方法比對(duì)移動(dòng)的節(jié)點(diǎn)和newStartVNode的標(biāo)簽、屬性、文本以及孩子節(jié)點(diǎn)
如果在老節(jié)點(diǎn)中沒(méi)有找到key相同的元素，會(huì)為新節(jié)點(diǎn)的頭節(jié)點(diǎn)創(chuàng)建對(duì)應(yīng)的真實(shí)節(jié)點(diǎn)，將其插入到oldStartVNode.el之前
遍歷完成后，將老節(jié)點(diǎn)中頭指針和尾指針之間多余的元素刪除

畫圖演示下template中節(jié)點(diǎn)的比對(duì)過(guò)程：

在比對(duì)開始之前，我們要先遍歷老的孩子節(jié)點(diǎn)，生成key與索引對(duì)應(yīng)的map:

function updateChildren (oldChildren, newChildren, parent) {
  function makeMap () {
    const map = {};
    for (let i = 0; i < oldChildren.length; i++) {
      const child = oldChildren[i];
      child.key && (map[child.key] = i);
    }
    return map;
  }
  const map = makeMap();
}

有了map之后，便可以很方便的通過(guò)key來(lái)找到老孩子節(jié)點(diǎn)的索引，然后通過(guò)索引直接找到對(duì)應(yīng)的孩子節(jié)點(diǎn)，而不用再次進(jìn)行遍歷操作。

接下來(lái)書寫處理亂序節(jié)點(diǎn)的代碼：

function updateChildren (oldChildren, newChildren, parent) {
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    if (oldStartVNode == null) { // 老節(jié)點(diǎn)null時(shí)跳過(guò)該次循環(huán)
      oldStartVNode = oldChildren[++oldStartIndex];
      continue;
    } else if (oldEndVNode == null) {
      oldEndVNode = oldChildren[--oldEndIndex];
      continue;
    } else if (isSameVNode(oldStartIndex, newStartIndex)) { // 頭和頭相等
      // some code ...  
    } else if (isSameVNode(oldStartVNode, newEndVNode)) { // 將開頭元素移動(dòng)到了末尾：尾和頭相同
      // some code ...  
    } else if (isSameVNode(oldEndVNode, newStartVNode)) { // 將結(jié)尾元素移動(dòng)到了開頭
      // some code ...  
    } else {
      // 1. 用key來(lái)進(jìn)行尋找，找到將其移動(dòng)到頭節(jié)點(diǎn)之前
      // 2. 沒(méi)有找到，將新頭節(jié)點(diǎn)插入到老頭節(jié)點(diǎn)之前
      let moveIndex = map[newStartVNode.key]; // 通過(guò)key在map中找到相同元素的索引
      if (moveIndex != null) { // 找到了
        const moveVNode = oldChildren[moveIndex];
        parent.insertBefore(moveVNode.el, oldStartVNode.el);
        oldChildren[moveIndex] = null; // 將移動(dòng)這項(xiàng)標(biāo)記為null，之后跳過(guò)，不再進(jìn)行比對(duì)
        // 還有對(duì)其屬性和子節(jié)點(diǎn)再進(jìn)行比較
        patch(moveVNode, newStartVNode);
      } else {
        // 為新頭節(jié)創(chuàng)建對(duì)應(yīng)的真實(shí)節(jié)點(diǎn)并插入到老節(jié)點(diǎn)的頭節(jié)點(diǎn)之前
        parent.insertBefore(createElement(newStartVNode), oldStartVNode.el);
      }
      newStartVNode = newChildren[++newStartIndex];
    }
  }
  // some code ...
  // 老節(jié)點(diǎn)中從頭指針到尾指針為多余的元素，需要?jiǎng)h除掉
  for (let i = oldStartIndex; i <= oldEndIndex; i++) {
    const child = oldChildren[i];
    parent.removeChild(child.el);
  }
}

當(dāng)新節(jié)點(diǎn)在老節(jié)點(diǎn)中存在時(shí)，我們會(huì)將找到的真實(shí)節(jié)點(diǎn)移動(dòng)到相應(yīng)的位置。此時(shí)老節(jié)點(diǎn)中的該節(jié)點(diǎn)不需要再被遍歷，為了防止數(shù)組塌陷，便將該節(jié)點(diǎn)設(shè)置為null。之后再遍歷時(shí)，如果發(fā)現(xiàn)節(jié)點(diǎn)的值為null，便跳過(guò)本次循環(huán)。

現(xiàn)在我們便完成了Vue在數(shù)組更新時(shí)所有的DOM Diff邏輯。