摘要：目前，前端領(lǐng)域中勢(shì)頭正盛，使用者眾多卻少有能夠深入剖析內(nèi)部實(shí)現(xiàn)機(jī)制和原理。當(dāng)發(fā)現(xiàn)節(jié)點(diǎn)已經(jīng)不存在，則該節(jié)點(diǎn)及其子節(jié)點(diǎn)會(huì)被完全刪除掉，不會(huì)用于進(jìn)一步的比較。

目前，前端領(lǐng)域中 React 勢(shì)頭正盛，使用者眾多卻少有能夠深入剖析內(nèi)部實(shí)現(xiàn)機(jī)制和原理。本系列文章希望通過(guò)剖析 React 源碼，理解其內(nèi)部的實(shí)現(xiàn)原理，知其然更要知其所以然。

React diff 作為 Virtual DOM 的加速器，其算法上的改進(jìn)優(yōu)化是 React 整個(gè)界面渲染的基礎(chǔ)，以及性能提高的保障，同時(shí)也是 React 源碼中最神秘、最不可思議的部分，本文從源碼入手，深入剖析 React diff 的不可思議之處。

閱讀本文需要對(duì) React 有一定的了解，如果你不知何為 React，請(qǐng)?jiān)斪x React 官方文檔。

如果你對(duì) React diff 存在些許疑惑，或者你對(duì)算法優(yōu)化感興趣，那么本文值得閱讀和討論。

React 中最值得稱道的部分莫過(guò)于 Virtual DOM 與 diff 的完美結(jié)合，特別是其高效的 diff 算法，讓用戶可以無(wú)需顧忌性能問(wèn)題而”任性自由”的刷新頁(yè)面，讓開(kāi)發(fā)者也可以無(wú)需關(guān)心 Virtual DOM 背后的運(yùn)作原理，因?yàn)?React diff 會(huì)幫助我們計(jì)算出 Virtual DOM 中真正變化的部分，并只針對(duì)該部分進(jìn)行實(shí)際 DOM 操作，而非重新渲染整個(gè)頁(yè)面，從而保證了每次操作更新后頁(yè)面的高效渲染，因此 Virtual DOM 與 diff 是保證 React 性能口碑的幕后推手。

行文至此，可能會(huì)有讀者質(zhì)疑：React 無(wú)非就是引入 diff 這一概念，且 diff 算法也并非其首創(chuàng)，何必吹噓的如此天花亂墜呢？

其實(shí)，正是因?yàn)?diff 算法的普識(shí)度高，就更應(yīng)該認(rèn)可 React 針對(duì) diff 算法優(yōu)化所做的努力與貢獻(xiàn)，更能體現(xiàn) React 開(kāi)發(fā)者們的魅力與智慧！

計(jì)算一棵樹(shù)形結(jié)構(gòu)轉(zhuǎn)換成另一棵樹(shù)形結(jié)構(gòu)的最少操作，是一個(gè)復(fù)雜且值得研究的問(wèn)題。傳統(tǒng) diff 算法通過(guò)循環(huán)遞歸對(duì)節(jié)點(diǎn)進(jìn)行依次對(duì)比，效率低下，算法復(fù)雜度達(dá)到 O(n³)，其中 n 是樹(shù)中節(jié)點(diǎn)的總數(shù)。O(n³) 到底有多可怕，這意味著如果要展示1000個(gè)節(jié)點(diǎn)，就要依次執(zhí)行上十億次的比較。這種指數(shù)型的性能消耗對(duì)于前端渲染場(chǎng)景來(lái)說(shuō)代價(jià)太高了！現(xiàn)今的 CPU 每秒鐘能執(zhí)行大約30億條指令，即便是最高效的實(shí)現(xiàn)，也不可能在一秒內(nèi)計(jì)算出差異情況。

因此，如果 React 只是單純的引入 diff 算法而沒(méi)有任何的優(yōu)化改進(jìn)，那么其效率是遠(yuǎn)遠(yuǎn)無(wú)法滿足前端渲染所要求的性能。

通過(guò)下面的 demo 可以清晰的描述傳統(tǒng) diff 算法的實(shí)現(xiàn)過(guò)程。

let result = [];
// 比較葉子節(jié)點(diǎn)
const diffLeafs = function(beforeLeaf, afterLeaf) {
  // 獲取較大節(jié)點(diǎn)樹(shù)的長(zhǎng)度
  let count = Math.max(beforeLeaf.children.length, afterLeaf.children.length);
  // 循環(huán)遍歷
  for (let i = 0; i < count; i++) {
    const beforeTag = beforeLeaf.children[i];
    const afterTag = afterLeaf.children[i];
    // 添加 afterTag 節(jié)點(diǎn)
    if (beforeTag === undefined) {
      result.push({type: "add", element: afterTag});
    // 刪除 beforeTag 節(jié)點(diǎn)
    } else if (afterTag === undefined) {
      result.push({type: "remove", element: beforeTag});
    // 節(jié)點(diǎn)名改變時(shí)，刪除 beforeTag 節(jié)點(diǎn)，添加 afterTag 節(jié)點(diǎn)
    } else if (beforeTag.tagName !== afterTag.tagName) {
      result.push({type: "remove", element: beforeTag});
      result.push({type: "add", element: afterTag});
    // 節(jié)點(diǎn)不變而內(nèi)容改變時(shí)，改變節(jié)點(diǎn)
    } else if (beforeTag.innerHTML !== afterTag.innerHTML) {
      if (beforeTag.children.length === 0) {
        result.push({
          type: "changed",
          beforeElement: beforeTag,
          afterElement: afterTag,
          html: afterTag.innerHTML
      });
      } else {
        // 遞歸比較
        diffLeafs(beforeTag, afterTag);
      }
    }
  }
  return result;
}

因此，如果想要將 diff 思想引入 Virtual DOM，就需要設(shè)計(jì)一種穩(wěn)定高效的 diff 算法，而 React 做到了！

那么，React diff 到底是如何實(shí)現(xiàn)的呢？

傳統(tǒng) diff 算法的復(fù)雜度為 O(n³)，顯然這是無(wú)法滿足性能要求的。React 通過(guò)制定大膽的策略，將 O(n³) 復(fù)雜度的問(wèn)題轉(zhuǎn)換成 O(n) 復(fù)雜度的問(wèn)題。

Web UI 中 DOM 節(jié)點(diǎn)跨層級(jí)的移動(dòng)操作特別少，可以忽略不計(jì)。

擁有相同類的兩個(gè)組件將會(huì)生成相似的樹(shù)形結(jié)構(gòu)，擁有不同類的兩個(gè)組件將會(huì)生成不同的樹(shù)形結(jié)構(gòu)。

對(duì)于同一層級(jí)的一組子節(jié)點(diǎn)，它們可以通過(guò)唯一 id 進(jìn)行區(qū)分。

基于以上三個(gè)前提策略，React 分別對(duì) tree diff、component diff 以及 element diff 進(jìn)行算法優(yōu)化，事實(shí)也證明這三個(gè)前提策略是合理且準(zhǔn)確的，它保證了整體界面構(gòu)建的性能。

tree diff

component diff

element diff

本文中源碼 ReactMultiChild.js

基于策略一，React 對(duì)樹(shù)的算法進(jìn)行了簡(jiǎn)潔明了的優(yōu)化，即對(duì)樹(shù)進(jìn)行分層比較，兩棵樹(shù)只會(huì)對(duì)同一層次的節(jié)點(diǎn)進(jìn)行比較。

既然 DOM 節(jié)點(diǎn)跨層級(jí)的移動(dòng)操作少到可以忽略不計(jì)，針對(duì)這一現(xiàn)象，React 通過(guò) updateDepth 對(duì) Virtual DOM 樹(shù)進(jìn)行層級(jí)控制，只會(huì)對(duì)相同顏色方框內(nèi)的 DOM 節(jié)點(diǎn)進(jìn)行比較，即同一個(gè)父節(jié)點(diǎn)下的所有子節(jié)點(diǎn)。當(dāng)發(fā)現(xiàn)節(jié)點(diǎn)已經(jīng)不存在，則該節(jié)點(diǎn)及其子節(jié)點(diǎn)會(huì)被完全刪除掉，不會(huì)用于進(jìn)一步的比較。這樣只需要對(duì)樹(shù)進(jìn)行一次遍歷，便能完成整個(gè) DOM 樹(shù)的比較。

updateChildren: function(nextNestedChildrenElements, transaction, context) {
  updateDepth++;
  var errorThrown = true;
  try {
    this._updateChildren(nextNestedChildrenElements, transaction, context);
    errorThrown = false;
  } finally {
    updateDepth--;
    if (!updateDepth) {
      if (errorThrown) {
        clearQueue();
      } else {
        processQueue();
      }
    }
  }
}

分析至此，大部分人可能都存在這樣的疑問(wèn)：如果出現(xiàn)了 DOM 節(jié)點(diǎn)跨層級(jí)的移動(dòng)操作，React diff 會(huì)有怎樣的表現(xiàn)呢？是的，對(duì)此我也好奇不已，不如試驗(yàn)一番。

如下圖，A 節(jié)點(diǎn)（包括其子節(jié)點(diǎn)）整個(gè)被移動(dòng)到 D 節(jié)點(diǎn)下，由于 React 只會(huì)簡(jiǎn)單的考慮同層級(jí)節(jié)點(diǎn)的位置變換，而對(duì)于不同層級(jí)的節(jié)點(diǎn)，只有創(chuàng)建和刪除操作。當(dāng)根節(jié)點(diǎn)發(fā)現(xiàn)子節(jié)點(diǎn)中 A 消失了，就會(huì)直接銷毀 A；當(dāng) D 發(fā)現(xiàn)多了一個(gè)子節(jié)點(diǎn) A，則會(huì)創(chuàng)建新的 A（包括子節(jié)點(diǎn)）作為其子節(jié)點(diǎn)。此時(shí)，React diff 的執(zhí)行情況：create A -> create B -> create C -> delete A。

由此可發(fā)現(xiàn)，當(dāng)出現(xiàn)節(jié)點(diǎn)跨層級(jí)移動(dòng)時(shí)，并不會(huì)出現(xiàn)想象中的移動(dòng)操作，而是以 A 為根節(jié)點(diǎn)的樹(shù)被整個(gè)重新創(chuàng)建，這是一種影響 React 性能的操作，因此 React 官方建議不要進(jìn)行 DOM 節(jié)點(diǎn)跨層級(jí)的操作。

注意：在開(kāi)發(fā)組件時(shí)，保持穩(wěn)定的 DOM 結(jié)構(gòu)會(huì)有助于性能的提升。例如，可以通過(guò) CSS 隱藏或顯示節(jié)點(diǎn)，而不是真的移除或添加 DOM 節(jié)點(diǎn)。

React 是基于組件構(gòu)建應(yīng)用的，對(duì)于組件間的比較所采取的策略也是簡(jiǎn)潔高效。

如果是同一類型的組件，按照原策略繼續(xù)比較 virtual DOM tree。

如果不是，則將該組件判斷為 dirty component，從而替換整個(gè)組件下的所有子節(jié)點(diǎn)。

對(duì)于同一類型的組件，有可能其 Virtual DOM 沒(méi)有任何變化，如果能夠確切的知道這點(diǎn)那可以節(jié)省大量的 diff 運(yùn)算時(shí)間，因此 React 允許用戶通過(guò) shouldComponentUpdate() 來(lái)判斷該組件是否需要進(jìn)行 diff。

如下圖，當(dāng) component D 改變?yōu)?component G 時(shí)，即使這兩個(gè) component 結(jié)構(gòu)相似，一旦 React 判斷 D 和 G 是不同類型的組件，就不會(huì)比較二者的結(jié)構(gòu)，而是直接刪除 component D，重新創(chuàng)建 component G 以及其子節(jié)點(diǎn)。雖然當(dāng)兩個(gè) component 是不同類型但結(jié)構(gòu)相似時(shí)，React diff 會(huì)影響性能，但正如 React 官方博客所言：不同類型的 component 是很少存在相似 DOM tree 的機(jī)會(huì)，因此這種極端因素很難在實(shí)現(xiàn)開(kāi)發(fā)過(guò)程中造成重大影響的。

當(dāng)節(jié)點(diǎn)處于同一層級(jí)時(shí)，React diff 提供了三種節(jié)點(diǎn)操作，分別為：INSERT_MARKUP（插入）、MOVE_EXISTING（移動(dòng)）和 REMOVE_NODE（刪除）。

INSERT_MARKUP，新的 component 類型不在老集合里， 即是全新的節(jié)點(diǎn)，需要對(duì)新節(jié)點(diǎn)執(zhí)行插入操作。

MOVE_EXISTING，在老集合有新 component 類型，且 element 是可更新的類型，generateComponentChildren 已調(diào)用 receiveComponent，這種情況下 prevChild=nextChild，就需要做移動(dòng)操作，可以復(fù)用以前的 DOM 節(jié)點(diǎn)。

REMOVE_NODE，老 component 類型，在新集合里也有，但對(duì)應(yīng)的 element 不同則不能直接復(fù)用和更新，需要執(zhí)行刪除操作，或者老 component 不在新集合里的，也需要執(zhí)行刪除操作。

function enqueueInsertMarkup(parentInst, markup, toIndex) {
  updateQueue.push({
    parentInst: parentInst,
    parentNode: null,
    type: ReactMultiChildUpdateTypes.INSERT_MARKUP,
    markupIndex: markupQueue.push(markup) - 1,
    content: null,
    fromIndex: null,
    toIndex: toIndex,
  });
}

function enqueueMove(parentInst, fromIndex, toIndex) {
  updateQueue.push({
    parentInst: parentInst,
    parentNode: null,
    type: ReactMultiChildUpdateTypes.MOVE_EXISTING,
    markupIndex: null,
    content: null,
    fromIndex: fromIndex,
    toIndex: toIndex,
  });
}

function enqueueRemove(parentInst, fromIndex) {
  updateQueue.push({
    parentInst: parentInst,
    parentNode: null,
    type: ReactMultiChildUpdateTypes.REMOVE_NODE,
    markupIndex: null,
    content: null,
    fromIndex: fromIndex,
    toIndex: null,
  });
}

如下圖，老集合中包含節(jié)點(diǎn)：A、B、C、D，更新后的新集合中包含節(jié)點(diǎn)：B、A、D、C，此時(shí)新老集合進(jìn)行 diff 差異化對(duì)比，發(fā)現(xiàn) B != A，則創(chuàng)建并插入 B 至新集合，刪除老集合 A；以此類推，創(chuàng)建并插入 A、D 和 C，刪除 B、C 和 D。

React 發(fā)現(xiàn)這類操作繁瑣冗余，因?yàn)檫@些都是相同的節(jié)點(diǎn)，但由于位置發(fā)生變化，導(dǎo)致需要進(jìn)行繁雜低效的刪除、創(chuàng)建操作，其實(shí)只要對(duì)這些節(jié)點(diǎn)進(jìn)行位置移動(dòng)即可。

針對(duì)這一現(xiàn)象，React 提出優(yōu)化策略：允許開(kāi)發(fā)者對(duì)同一層級(jí)的同組子節(jié)點(diǎn)，添加唯一 key 進(jìn)行區(qū)分，雖然只是小小的改動(dòng)，性能上卻發(fā)生了翻天覆地的變化！

新老集合所包含的節(jié)點(diǎn)，如下圖所示，新老集合進(jìn)行 diff 差異化對(duì)比，通過(guò) key 發(fā)現(xiàn)新老集合中的節(jié)點(diǎn)都是相同的節(jié)點(diǎn)，因此無(wú)需進(jìn)行節(jié)點(diǎn)刪除和創(chuàng)建，只需要將老集合中節(jié)點(diǎn)的位置進(jìn)行移動(dòng)，更新為新集合中節(jié)點(diǎn)的位置，此時(shí) React 給出的 diff 結(jié)果為：B、D 不做任何操作，A、C 進(jìn)行移動(dòng)操作，即可。

那么，如此高效的 diff 到底是如何運(yùn)作的呢？讓我們通過(guò)源碼進(jìn)行詳細(xì)分析。

首先對(duì)新集合的節(jié)點(diǎn)進(jìn)行循環(huán)遍歷，for (name in nextChildren)，通過(guò)唯一 key 可以判斷新老集合中是否存在相同的節(jié)點(diǎn)，if (prevChild === nextChild)，如果存在相同節(jié)點(diǎn)，則進(jìn)行移動(dòng)操作，但在移動(dòng)前需要將當(dāng)前節(jié)點(diǎn)在老集合中的位置與 lastIndex 進(jìn)行比較，if (child._mountIndex < lastIndex)，則進(jìn)行節(jié)點(diǎn)移動(dòng)操作，否則不執(zhí)行該操作。這是一種順序優(yōu)化手段，lastIndex 一直在更新，表示訪問(wèn)過(guò)的節(jié)點(diǎn)在老集合中最右的位置（即最大的位置），如果新集合中當(dāng)前訪問(wèn)的節(jié)點(diǎn)比 lastIndex 大，說(shuō)明當(dāng)前訪問(wèn)節(jié)點(diǎn)在老集合中就比上一個(gè)節(jié)點(diǎn)位置靠后，則該節(jié)點(diǎn)不會(huì)影響其他節(jié)點(diǎn)的位置，因此不用添加到差異隊(duì)列中，即不執(zhí)行移動(dòng)操作，只有當(dāng)訪問(wèn)的節(jié)點(diǎn)比 lastIndex 小時(shí)，才需要進(jìn)行移動(dòng)操作。

以上圖為例，可以更為清晰直觀的描述 diff 的差異對(duì)比過(guò)程：

從新集合中取得 B，判斷老集合中存在相同節(jié)點(diǎn) B，通過(guò)對(duì)比節(jié)點(diǎn)位置判斷是否進(jìn)行移動(dòng)操作，B 在老集合中的位置 B._mountIndex = 1，此時(shí) lastIndex = 0，不滿足 child._mountIndex < lastIndex 的條件，因此不對(duì) B 進(jìn)行移動(dòng)操作；更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex)，其中 prevChild._mountIndex 表示 B 在老集合中的位置，則 lastIndex ＝ 1，并將 B 的位置更新為新集合中的位置 prevChild._mountIndex = nextIndex，此時(shí)新集合中 B._mountIndex = 0，nextIndex++ 進(jìn)入下一個(gè)節(jié)點(diǎn)的判斷。

從新集合中取得 A，判斷老集合中存在相同節(jié)點(diǎn) A，通過(guò)對(duì)比節(jié)點(diǎn)位置判斷是否進(jìn)行移動(dòng)操作，A 在老集合中的位置 A._mountIndex = 0，此時(shí) lastIndex = 1，滿足 child._mountIndex < lastIndex的條件，因此對(duì) A 進(jìn)行移動(dòng)操作enqueueMove(this, child._mountIndex, toIndex)，其中 toIndex 其實(shí)就是 nextIndex，表示 A 需要移動(dòng)到的位置；更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex)，則 lastIndex ＝ 1，并將 A 的位置更新為新集合中的位置 prevChild._mountIndex = nextIndex，此時(shí)新集合中 A._mountIndex = 1，nextIndex++ 進(jìn)入下一個(gè)節(jié)點(diǎn)的判斷。

從新集合中取得 D，判斷老集合中存在相同節(jié)點(diǎn) D，通過(guò)對(duì)比節(jié)點(diǎn)位置判斷是否進(jìn)行移動(dòng)操作，D 在老集合中的位置 D._mountIndex = 3，此時(shí) lastIndex = 1，不滿足 child._mountIndex < lastIndex的條件，因此不對(duì) D 進(jìn)行移動(dòng)操作；更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex)，則 lastIndex ＝ 3，并將 D 的位置更新為新集合中的位置 prevChild._mountIndex = nextIndex，此時(shí)新集合中 D._mountIndex = 2，nextIndex++ 進(jìn)入下一個(gè)節(jié)點(diǎn)的判斷。

從新集合中取得 C，判斷老集合中存在相同節(jié)點(diǎn) C，通過(guò)對(duì)比節(jié)點(diǎn)位置判斷是否進(jìn)行移動(dòng)操作，C 在老集合中的位置 C._mountIndex = 2，此時(shí) lastIndex = 3，滿足 child._mountIndex < lastIndex 的條件，因此對(duì) C 進(jìn)行移動(dòng)操作 enqueueMove(this, child._mountIndex, toIndex)；更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex)，則 lastIndex ＝ 3，并將 C 的位置更新為新集合中的位置 prevChild._mountIndex = nextIndex，此時(shí)新集合中 A._mountIndex = 3，nextIndex++ 進(jìn)入下一個(gè)節(jié)點(diǎn)的判斷，由于 C 已經(jīng)是最后一個(gè)節(jié)點(diǎn)，因此 diff 到此完成。

以上主要分析新老集合中存在相同節(jié)點(diǎn)但位置不同時(shí)，對(duì)節(jié)點(diǎn)進(jìn)行位置移動(dòng)的情況，如果新集合中有新加入的節(jié)點(diǎn)且老集合存在需要?jiǎng)h除的節(jié)點(diǎn)，那么 React diff 又是如何對(duì)比運(yùn)作的呢？

以下圖為例：

從新集合中取得 B，判斷老集合中存在相同節(jié)點(diǎn) B，由于 B 在老集合中的位置 B._mountIndex = 1，此時(shí) lastIndex = 0，因此不對(duì) B 進(jìn)行移動(dòng)操作；更新 lastIndex ＝ 1，并將 B 的位置更新為新集合中的位置 B._mountIndex = 0，nextIndex++進(jìn)入下一個(gè)節(jié)點(diǎn)的判斷。

從新集合中取得 E，判斷老集合中不存在相同節(jié)點(diǎn) E，則創(chuàng)建新節(jié)點(diǎn) E；更新 lastIndex ＝ 1，并將 E 的位置更新為新集合中的位置，nextIndex++進(jìn)入下一個(gè)節(jié)點(diǎn)的判斷。

從新集合中取得 C，判斷老集合中存在相同節(jié)點(diǎn) C，由于 C 在老集合中的位置C._mountIndex = 2，此時(shí) lastIndex = 1，因此對(duì) C 進(jìn)行移動(dòng)操作；更新 lastIndex ＝ 2，并將 C 的位置更新為新集合中的位置，nextIndex++ 進(jìn)入下一個(gè)節(jié)點(diǎn)的判斷。

從新集合中取得 A，判斷老集合中存在相同節(jié)點(diǎn) A，由于 A 在老集合中的位置A._mountIndex = 0，此時(shí) lastIndex = 2，因此不對(duì) A 進(jìn)行移動(dòng)操作；更新 lastIndex ＝ 2，并將 A 的位置更新為新集合中的位置，nextIndex++ 進(jìn)入下一個(gè)節(jié)點(diǎn)的判斷。

當(dāng)完成新集合中所有節(jié)點(diǎn) diff 時(shí)，最后還需要對(duì)老集合進(jìn)行循環(huán)遍歷，判斷是否存在新集合中沒(méi)有但老集合中仍存在的節(jié)點(diǎn)，發(fā)現(xiàn)存在這樣的節(jié)點(diǎn) D，因此刪除節(jié)點(diǎn) D，到此 diff 全部完成。

_updateChildren: function(nextNestedChildrenElements, transaction, context) {
  var prevChildren = this._renderedChildren;
  var nextChildren = this._reconcilerUpdateChildren(
    prevChildren, nextNestedChildrenElements, transaction, context
  );
  if (!nextChildren && !prevChildren) {
    return;
  }
  var name;
  var lastIndex = 0;
  var nextIndex = 0;
  for (name in nextChildren) {
    if (!nextChildren.hasOwnProperty(name)) {
      continue;
    }
    var prevChild = prevChildren && prevChildren[name];
    var nextChild = nextChildren[name];
    if (prevChild === nextChild) {
      // 移動(dòng)節(jié)點(diǎn)
      this.moveChild(prevChild, nextIndex, lastIndex);
      lastIndex = Math.max(prevChild._mountIndex, lastIndex);
      prevChild._mountIndex = nextIndex;
    } else {
      if (prevChild) {
        lastIndex = Math.max(prevChild._mountIndex, lastIndex);
        // 刪除節(jié)點(diǎn)
        this._unmountChild(prevChild);
      }
      // 初始化并創(chuàng)建節(jié)點(diǎn)
      this._mountChildAtIndex(
        nextChild, nextIndex, transaction, context
      );
    }
    nextIndex++;
  }
  for (name in prevChildren) {
    if (prevChildren.hasOwnProperty(name) &&
        !(nextChildren && nextChildren.hasOwnProperty(name))) {
      this._unmountChild(prevChildren[name]);
    }
  }
  this._renderedChildren = nextChildren;
},
// 移動(dòng)節(jié)點(diǎn)
moveChild: function(child, toIndex, lastIndex) {
  if (child._mountIndex < lastIndex) {
    this.prepareToManageChildren();
    enqueueMove(this, child._mountIndex, toIndex);
  }
},
// 創(chuàng)建節(jié)點(diǎn)
createChild: function(child, mountImage) {
  this.prepareToManageChildren();
  enqueueInsertMarkup(this, mountImage, child._mountIndex);
},
// 刪除節(jié)點(diǎn)
removeChild: function(child) {
  this.prepareToManageChildren();
  enqueueRemove(this, child._mountIndex);
},

_unmountChild: function(child) {
  this.removeChild(child);
  child._mountIndex = null;
},

_mountChildAtIndex: function(
  child,
  index,
  transaction,
  context) {
  var mountImage = ReactReconciler.mountComponent(
    child,
    transaction,
    this,
    this._nativeContainerInfo,
    context
  );
  child._mountIndex = index;
  this.createChild(child, mountImage);
},

當(dāng)然，React diff 還是存在些許不足與待優(yōu)化的地方，如下圖所示，若新集合的節(jié)點(diǎn)更新為：D、A、B、C，與老集合對(duì)比只有 D 節(jié)點(diǎn)移動(dòng)，而 A、B、C 仍然保持原有的順序，理論上 diff 應(yīng)該只需對(duì) D 執(zhí)行移動(dòng)操作，然而由于 D 在老集合的位置是最大的，導(dǎo)致其他節(jié)點(diǎn)的 _mountIndex < lastIndex，造成 D 沒(méi)有執(zhí)行移動(dòng)操作，而是 A、B、C 全部移動(dòng)到 D 節(jié)點(diǎn)后面的現(xiàn)象。

在此，讀者們可以討論思考：如何優(yōu)化上述問(wèn)題？

建議：在開(kāi)發(fā)過(guò)程中，盡量減少類似將最后一個(gè)節(jié)點(diǎn)移動(dòng)到列表首部的操作，當(dāng)節(jié)點(diǎn)數(shù)量過(guò)大或更新操作過(guò)于頻繁時(shí)，在一定程度上會(huì)影響 React 的渲染性能。

React 通過(guò)制定大膽的 diff 策略，將 O(n³) 復(fù)雜度的問(wèn)題轉(zhuǎn)換成 O(n) 復(fù)雜度的問(wèn)題；

React 通過(guò)分層求異的策略，對(duì) tree diff 進(jìn)行算法優(yōu)化；

React 通過(guò)相同類生成相似樹(shù)形結(jié)構(gòu)，不同類生成不同樹(shù)形結(jié)構(gòu)的策略，對(duì) component diff 進(jìn)行算法優(yōu)化；

React 通過(guò)設(shè)置唯一 key的策略，對(duì) element diff 進(jìn)行算法優(yōu)化；

建議，在開(kāi)發(fā)組件時(shí)，保持穩(wěn)定的 DOM 結(jié)構(gòu)會(huì)有助于性能的提升；

建議，在開(kāi)發(fā)過(guò)程中，盡量減少類似將最后一個(gè)節(jié)點(diǎn)移動(dòng)到列表首部的操作，當(dāng)節(jié)點(diǎn)數(shù)量過(guò)大或更新操作過(guò)于頻繁時(shí)，在一定程度上會(huì)影響 React 的渲染性能。

A Survey on Tree Edit Distance and Related Problems

Reconciliation

如果本文能夠?yàn)槟憬鉀Q些許關(guān)于 React diff 算法的疑惑，請(qǐng)點(diǎn)個(gè)贊吧！