什么是 Virtual DOM ？

在前端技術(shù)蓬勃發(fā)展的上古時代，前端開發(fā)主要是一些靜態(tài)頁面，使用 ajax、jQuery 等命令式的完成一些對 DOM 的操作，而伴隨著前端工程化的不斷發(fā)展，涌現(xiàn)了諸如 angular、react 等一系列 MVVM 模式的前端框架，這些框架公有的特點就是不再關心具體 DOM 的操作，而是把重點放在了基于數(shù)據(jù)狀態(tài)的操作，一旦數(shù)據(jù)更改，跟它綁定的那個地方的 DOM 也會跟著變化。這種聲明式的開發(fā)方式極大的增加了開發(fā)體驗，更好的幫助我們完成組件復用、邏輯解耦等。

借助于上面提到的前端框架，我們不用再主動的對 DOM 進行操作，框架在背后已經(jīng)替我們做了，我們只需要關心應用的數(shù)據(jù)即可。而Virtual DOM（虛擬 DOM）的概念就是在此期間由于其在React框架中的使用而變得流行起來。那么到底什么是Virtual DOM呢？

引用 react 官網(wǎng)上的介紹：

Virtual DOM 是一種編程概念。在這個概念里， UI 以一種理想化的，或者說“虛擬的”表現(xiàn)形式被保存于內(nèi)存中，并通過如 ReactDOM 等類庫使之與“真實的” DOM 同步。這一過程叫做協(xié)調(diào)。

這種方式賦予了 React 聲明式的 API：您告訴 React 希望讓 UI 是什么狀態(tài)，React 就確保 DOM 匹配該狀態(tài)。這使您可以從屬性操作、事件處理和手動 DOM 更新這些在構(gòu)建應用程序時必要的操作中解放出來。

總結(jié)來說，理解 Virtual DOM 的含義主可以從以下幾點出發(fā)：

虛擬 DOM 并不是真實的 DOM，它跟原生 DOM 本質(zhì)上沒什么關系。
本質(zhì)上 Virtual DOM 對應的是一個 JavaScript 對象，它描述的是視圖和應用狀態(tài)之間的一種映射關系，是某一時刻真實 DOM 狀態(tài)的內(nèi)存映射。
在視圖顯示方面，Virtual DOM 對象的節(jié)點跟真實 DOM Tree 每個位置的屬性一一對應。
我們不再需要直接的操作 DOM，只需要關注應用的狀態(tài)即可，操作 DOM 的事情有框架替我們做了。

為什么要用 Virtual DOM ？

我們經(jīng)常會說到真實的 DOM 操作代價昂貴，操作頻繁還會引起頁面卡頓影響用戶體驗，而虛擬 DOM 就是為了解決這個瀏覽器性能問題才被創(chuàng)造出來。

在介紹 Virtual DOM 有什么好處以及為什么要使用它之前，我們先來了解下為什么會說 DOM 操作是耗費性能的？

操作 DOM 是耗費性能的

首先我們要明白一點，DOM 并不屬于 JavaScript 語言的一部分，它是 JavaScript 的運行平臺（瀏覽器）提供的，比如在 nodejs 中就沒有 DOM。瀏覽器中的 DOM 對應的是 HTML 頁面中的元素節(jié)點，它本身和 JS 對象沒有什么關聯(lián)，但是 webkit 渲染引擎和 JS 引擎之間通過 V8 Binding 在 V8 內(nèi)部會把原生 DOM 對象映射為 JS 對象，我們稱之為 Wrapper objects（包裝對象）。因此，我們平時在寫代碼時，操作 DOM 對象就是操作的這種包裝對象，和操作 JS 對象是一樣的。下圖為瀏覽器和 JS 引擎的關系（以 Chrome 和 V8 舉例，其他瀏覽器也大同小異）。

由于 JS 是可操縱 DOM 的，如果在修改這些元素屬性同時渲染界面（即 JS 線程和渲染線程同時運行），那么渲染線程前后獲得的元素數(shù)據(jù)就可能不一致了。因此為了防止渲染出現(xiàn)不可預期的結(jié)果，瀏覽器設置 渲染線程 與 JS 引擎線程 為互斥的關系，當 JS 引擎執(zhí)行時渲染線程會被掛起，GUI 更新則會被保存在一個隊列中等到 JS 引擎線程空閑時立即被執(zhí)行。

因此我們在操作 DOM 時，任何 DOM API 調(diào)用都要先將 JS 數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)為 DOM 數(shù)據(jù)結(jié)構(gòu)，再掛起 JS 引擎線程并啟動渲染引擎線程，執(zhí)行過后再把可能的返回值反轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)，重啟 JS 引擎繼續(xù)執(zhí)行。這種兩個線程之間的上下文切換勢必會很耗性能。

另外很多 DOM API 的讀寫都涉及頁面布局的 重繪（repaint）和回流（reflow），這會更加的耗費性能。

綜上所述，單次 DOM API 調(diào)用性能就不夠好，頻繁調(diào)用就會迅速積累上述損耗，但我們又不可能不去操作 DOM，因此解決問題的本質(zhì)是要 減少不必要的 DOM API 調(diào)用。

Virtual DOM 有什么優(yōu)勢？

很多人一談到 Virtual DOM 的優(yōu)勢就會說 “原生 DOM 操作太慢了，virtual DOM 更快些”，首先我們要認識到一點：沒有任何框架可以比純手動的優(yōu)化 DOM 操作更快，因為框架的 DOM 操作層需要應對任何上層 API 可能產(chǎn)生的操作，它的實現(xiàn)必須是普適的。框架的意義在于為你掩蓋底層的 DOM 操作，讓你用更聲明式的方式來描述你的目的，從而讓你的代碼更容易維護。

React 也從來沒有說過 “React 比原生操作 DOM 快”。并不是說 Virtual DOM 操作一定是比原生 DOM 操作快，這和具體的頁面模板大小和數(shù)據(jù)的變動量都有關系的但是相比于操作 DOM，原生的 js 對象操作起來的確是會更快、更簡單。

React.js 相對于直接操作原生 DOM 最大的優(yōu)勢在于 batching 和 diff。為了盡量減少不必要的 DOM 操作， Virtual DOM 在執(zhí)行 DOM 的更新操作后，不會直接操作真實 DOM，而是根據(jù)當前應用狀態(tài)的數(shù)據(jù)，生成一個全新的 Virtual DOM，然后跟上一次生成的 Virtual DOM 去 diff，得到一個 Patch，這樣就可以找到變化了的 DOM 節(jié)點，只對變化的部分進行 DOM 更新，而不是重新渲染整個 DOM 樹，這個過程就是 diff。還有所謂的batching就是將多次比較的結(jié)果合并后一次性更新到頁面，從而有效地減少頁面渲染的次數(shù)，提高渲染效率。batching 或者 diff, 說到底，都是為了盡量減少對 DOM 的調(diào)用。簡要的示意圖如下：

因此總結(jié)下關于 Virtual DOM 的優(yōu)勢有哪些：

為函數(shù)式的 UI 編程方式打開了大門，我們不需要再去考慮具體 DOM 的操作，框架已經(jīng)替我們做了，我們就可以用更加聲明式的方式書寫代碼。
減少頁面渲染的次數(shù)，提高渲染效率。
提供了更好的跨平臺的能力，因為 virtual DOM 是以 JavaScript 對象為基礎而不依賴具體的平臺環(huán)境，因此可以適用于其他的平臺，如 node、weex、native 等。

附上知乎上尤雨溪對于 Virtual DOM 的優(yōu)勢的回答^[1]

Virtual DOM 是如何實現(xiàn)的

引用 React 官網(wǎng)關于 Virtual DOM 的一段話：

與其將 “Virtual DOM” 視為一種技術(shù)，不如說它是一種模式，人們提到它時經(jīng)常是要表達不同的東西。在 React 的世界里，術(shù)語 “Virtual DOM” 通常與React 元素^[2]關聯(lián)在一起，因為它們都是代表了用戶界面的對象。而 React 也使用一個名為 “fibers” 的內(nèi)部對象來存放組件樹的附加信息。上述二者也被認為是 React 中 “Virtual DOM” 實現(xiàn)的一部分。

下面的部分我們就來分別看看 ReactElement 和 Fiber 是什么東西。

ReactElement

我們前面說了本質(zhì)上 Virtual DOM 對應的是一個 JavaScript 對象，那么 React 是如何通過一個 js 對象將 Virtual DOM 和真實 DOM 對應起來的呢？這里面的關鍵就是 ReactElement。

ReactElement 即 react 元素，描述了我們在屏幕上所看到的內(nèi)容，它是構(gòu)成 React 應用的最小單元。比如下面的 jsx 代碼：

const element = <h1 id="hello">Hello, world</h1>

上面的代碼經(jīng)過編譯后其實生成的代碼是這樣的：

React.createElement("h1", {
  id: "hello"
}, "Hello, world");

執(zhí)行 React.createElement 函數(shù)，會返回類似于下面的一個 js 對象，這個對象就是我們所說的 React 元素：

const element = {
  type: 'h1',
  props: {
    id: 'hello',
    children: 'hello world'
  }
}

React 元素也可以是用戶自定義的組件：

function Button(props) {
  return <button style={{ color }}>{props.children}</button>;
}

const buttonComp = <Button color="red">點擊我</Button>

編譯后的代碼如下：

React.createElement("Button", {
  color: "red"
}, "點擊我");

因此我們就可以說 React 元素其實就是一個普通的 js 對象(plain object)，這個對象用來描述一個 DOM 節(jié)點及其屬性或者組件的實例，當我們在 JSX 中使用 Button 組件時，就相當于調(diào)用了React.createElement()方法對組件進行了實例化。由于組件可以在其輸出中引用其他組件，當我們在構(gòu)建復雜邏輯的組件時，會形成一個樹形結(jié)構(gòu)的組件樹，React 便會一層層的遞歸的將其轉(zhuǎn)化為 React 元素，當遇見 type 為大寫的類型時，react 就會知道這是一個自定義的組件元素，然后執(zhí)行組件的 render 方法或者執(zhí)行該組件函數(shù)（根據(jù)是類組件或者函數(shù)組件的不同），最終返回描述 DOM 的元素進行渲染。

我們來看下 React 源碼中關于 ReactElement 和 createElement 方法的實現(xiàn)：

var ReactElement = function (type, key, ref, self, source, owner, props) {
  var element = {
    // This tag allows us to uniquely identify this as a React Element
    $typeof: REACT_ELEMENT_TYPE,
    // Built-in properties that belong on the element
    type: type,
    key: key,
    ref: ref,
    props: props,
    // Record the component responsible for creating this element.
    _owner: owner
  };

  // do somethings ....

  return element;
 }

 function createElement(type, config, children) {
  var propName; // Reserved names are extracted
  var props = {};
  var key = null;
  var ref = null;
  var self = null;
  var source = null;


  if (config != null) {
    if (hasValidRef(config)) {
      ref = config.ref;
      {
        warnIfStringRefCannotBeAutoConverted(config);
      }
    }
    if (hasValidKey(config)) {
      key = '' + config.key;
    }

    self = config.__self === undefined ? null : config.__self;
    source = config.__source === undefined ? null : config.__source; // Remaining properties are added to a new props object

    for (propName in config) {
      if (hasOwnProperty.call(config, propName) && !RESERVED_PROPS.hasOwnProperty(propName)) {
        props[propName] = config[propName];
      }
    }

  } // Children can be more than one argument, and those are transferred onto

  // the newly allocated props object.


  //....


  return ReactElement(type, key, ref, self, source, ReactCurrentOwner.current, props);

從上面的源碼中可以看出：

ReactElement 是通過 createElement 函數(shù)創(chuàng)建的。
createElement 函數(shù)接收 3 個參數(shù)，分別是 type, config, children

type 指代這個 ReactElement 的類型，它可以是 DOM 元素類型，也可以是 React 組件類型。
config 即是傳入的元素上的屬性組成的對象。
children 是一個數(shù)組，代表該元素的子元素。

為了更加清楚的表示，我們通過在控制臺打印出整個 ReactElement 對象來看看它的真實的結(jié)構(gòu)：

<div className="box" id="name" key="uniqueKey" ref="boxRef">
    <h1>header</h1>
    <div className="content">content</div>
    <div>footer</div>
</div>

它最終會生成下面這樣的一個對象：

$$typeof 是一個常量 REACT_ELEMENT_TYPE，所有通過 React.createElement 生成的元素都有這個值，用來表示這是一個 React 元素。它還有一個取值，通過 createPortals 函數(shù)生成的 $$typeof 值就是 REACT_PORTAL_TYPE。
key 和 ref 從 config 對象中作為一個特殊的配置，被單獨抽取出來，放在 ReactElement 下。
props 包含了兩部分，第一部分是去除了 key 和 ref 的 config，第二部分是 children 數(shù)組，數(shù)組的成員也是通過 React.createElement 生成的對象。
_owner 就是 Fiber，這個我們后面會講到。

通過上面這些屬性，React 就可以用 js 對象把 DOM 樹上的結(jié)構(gòu)信息、屬性信息輕易的表達出來了。

React Fiber

Stack reconciler

React 15 及更早的 reconciler 架構(gòu)可以分為兩層：

Reconciler（協(xié)調(diào)器）: 負責找出變化的組件，通常將這時候的 reconciler 稱為 stack reconciler。
Renderer（渲染器）: 負責將變化的組件渲染到頁面上。

每當有狀態(tài)更新時，Reconciler會做如下工作：

調(diào)用函數(shù)組件、或 class 組件的 render 方法，將返回的 JSX 轉(zhuǎn)化為 Virtual DOM。
將 Virtual DOM 和上次更新時的 Virtual DOM 對比。
通過對比找出本次更新中變化的 Virtual DOM
通知 Renderer 將變化的 Virtual DOM 渲染到頁面上，由于 React 支持跨平臺，所以不同平臺有不同的 Renderer。

它的工作流程很像是函數(shù)調(diào)用的方式，一旦 setState 之后，便開始從父節(jié)點開始遞歸的進行遍歷，找出 Virtual DOM 的不同。在將所有的 Virtual DOM 遍歷完成之后，React 才能給出當前需要更新的 DOM 信息。這個過程是個同步的過程。對于一些特別龐大的組件來說，js 執(zhí)行會占據(jù)很長的主線程時間，這樣會導致頁面響應速度變慢，出現(xiàn)卡頓等現(xiàn)象，尤其是在動畫顯示上，很可能會出現(xiàn)丟幀的現(xiàn)象。

那么為什么 Stack reconsiler 會導致丟幀呢？我們來看一下一幀都做了什么

在上面的圖中，我們可以看出一幀包括了用戶的交互行為的處理、js 的執(zhí)行、requestAnimationFrame 的調(diào)用、layout 布局、paint 頁面重繪等工作，假如某一幀里面要執(zhí)行的任務不多，在不到 16ms（1000/60=16)的時間內(nèi)就完成了上述任務的話，頁面就會正常顯示不會出現(xiàn)卡頓的現(xiàn)象，但是如果一旦 js 執(zhí)行時間過長，超過了 16ms，這一幀的刷新就沒有時間執(zhí) layout 和 paint 部分了，就可能會出現(xiàn)頁面卡頓的現(xiàn)象。

Fiber reconciler

我們仔細考慮，其實對于視圖來說，同步的改變并不是一種好的解決方案，主要有以下幾點考慮：

并不是所有的狀態(tài)更新都需要立即同步顯示，比如可視范圍之外的部分的更新。
不同類型的更新的優(yōu)先級是不一樣的，比如對用戶輸入的響應一般是要比 ajax 請求的響應優(yōu)先級高的。
理想情況下，對于某些高優(yōu)先級的操作，應該是可以打斷低優(yōu)先級的操作執(zhí)行的，比如用戶輸入時，頁面的某個評論還在 reconciliation，應該優(yōu)先響應用戶輸入。

為了解決上面的 stack reconciler 中固有的問題，react 團隊重寫了核心算法 --reconciliation^[3]，即 fiber reconciler（兩者之間效果對比更直觀的感受可以看下這個demo^[4]）。fiber reconciler 的架構(gòu)在原來的基礎上增加了 Scheduler（調(diào)度器）的概念：

Scheduler（調(diào)度器）: 調(diào)度任務的優(yōu)先級，高優(yōu)任務優(yōu)先進入Reconciler。

上面我們在講一幀的過程的時候提到，假如某一幀里面要執(zhí)行的任務不多，在不到 16 ms 的時間內(nèi)就完成了任務，那么這一幀就有空閑時間，我們就可以利用這個空閑時間用來執(zhí)行低優(yōu)先級的任務，瀏覽器有個 api 叫requestIdleCallback，就是指在瀏覽器的空閑時段內(nèi)調(diào)用的一些函數(shù)的回調(diào)。React 實現(xiàn)了功能更完備的 requestIdleCallbackpolyfill，這就是Scheduler。除了在空閑時觸發(fā)回調(diào)的功能外，Scheduler還提供了多種調(diào)度優(yōu)先級供任務設置。Scheduler 主要決定應該在何時做什么，它在接收到更新后，首先看看有沒有其它高優(yōu)先級的更新需要先執(zhí)行，如果有就先執(zhí)行高優(yōu)先級的任務，等到空閑期再執(zhí)行此次更新；如果沒有則將此次任務交給 reconciler 。

Fiber Nodes

還記得前面在講 ReactElement 時在控制臺打印出的對象里面有個 _owner 對象嗎，它就是我們說到的 Fiber 節(jié)點。當一個 React Element 第一次被轉(zhuǎn)換為 fiber 節(jié)點的時候， React 將會從 React Element 中提取數(shù)據(jù)并在在createFiberFromTypeAndProps^[5]函數(shù)中創(chuàng)建一個新的 fiber 節(jié)點。Fiber 的主要目標是使 React 能夠利用調(diào)度。具體來說，我們需要能夠

暫停工作，稍后回來
給不同類型的工作分配優(yōu)先級
重用之前已經(jīng)完成的工作
當工作不再需要時取消

為了做到這一點，我們首先需要一種將工作分解為單元的方法。從某種意義上說，這就是 Fiber。Fiber 代表一種工作單位。React 會為每個得到的 React Element 創(chuàng)建 fiber，這些 fiber 節(jié)點被連接起來組成 fiber tree。每個 fiber 對應一個 React Element，保存了該元素的類型、對應的 DOM 節(jié)點、本次更新中的該元素改變的狀態(tài)、要執(zhí)行的任務（刪除、插入、更新）等信息

我們看一下 React 源碼中 FiberNode 構(gòu)造函數(shù)的部分：

type 和 key 與 React 元素的用途相同，React 通過它們來判斷 Fiber 是否可以重復使用。
stateNode 是 Fiber 對應的真實 DOM 節(jié)點。
多個 fiber 節(jié)點中是怎么連接形成 fiber tree 的呢？主要靠以下三個屬性：

return：指向父級 Fiber 節(jié)點；
child：指向子級 fiber 節(jié)點；
sibling：指向右邊第一個兄弟 fiber 節(jié)點；

在 React Fiber 中，一次更新過程會分成多個分片完成，所以完全有可能一個更新任務還沒有完成，就被另一個更高優(yōu)先級的更新過程打斷，這時候，優(yōu)先級高的更新任務會優(yōu)先處理完，而低優(yōu)先級更新任務所做的工作則會完全作廢，然后等待機會重頭再來。因為一個更新過程可能被打斷，所以 React Fiber 一個更新過程被分為兩個階段(Phase)：第一個階段Reconciliation Phase****和第二階段Commit Phase。在第一階段 Reconciliation Phase，React Fiber 會找出需要更新哪些 DOM，這個階段是可以被打斷的；但是到了第二階段 Commit Phase，那就一鼓作氣把 DOM 更新完，絕不會被打斷。

雙緩沖 Fiber tree

在 React 中最多會同時存在兩棵fiber tree。當前屏幕上顯示內(nèi)容對應的fiber tree稱為current fiber tree，正在內(nèi)存中構(gòu)建的fiber tree稱為workInProgress fiber tree。current fiber tree 中的 Fiber 節(jié)點被稱為 current fiber，workInProgress fiber tree 中的 Fiber 節(jié)點被稱為 workInProgress fiber，他們通過 alternate 屬性連接。

currentFiber.alternate === workInProgressFiber;

workInProgressFiber.alternate === currentFiber;

React 應用的根節(jié)點通過current指針在不同fiber tree的rootFiber間切換來實現(xiàn)fiber tree的切換。雙緩沖具體指的是當workInProgress fiber tree構(gòu)建完成交給Renderer渲染在頁面上后，應用根節(jié)點的current指針指向workInProgress fiber tree，此時workInProgress fiber tree就變?yōu)?code style="font-size: 14px;word-wrap: break-word;border-top-left-radius: 4px;border-top-right-radius: 4px;border-bottom-right-radius: 4px;border-bottom-left-radius: 4px;font-family: 'Operator Mono', Consolas, Monaco, Menlo, monospace;word-break: break-all;color: rgb(55, 125, 202);background-color: rgb(255, 245, 227);padding: 3px;margin: 3px;">current fiber tree。每次狀態(tài)更新都會產(chǎn)生新的workInProgress fiber tree，通過current與workInProgress的替換，完成 DOM 更新。這樣做的好處是：

能夠復用內(nèi)部對象（fiber）
節(jié)省內(nèi)存分配、GC 的時間開銷

總結(jié)

前面我們了解了 ReactElement 和 React Fiber，現(xiàn)在總結(jié)一下整個 Virtual DOM 的工作流程。

初始化渲染，調(diào)用函數(shù)組件、或 class 組件的 render 方法，將 JSX 代碼編譯成 ReactELement 對象，它描述當前組件內(nèi)容的數(shù)據(jù)結(jié)構(gòu)。
根據(jù)生產(chǎn)的 ReactELement 對象構(gòu)建 Fiber tree，它包含了組件 schedule、reconciler、render 所需的相關信息。
一旦有狀態(tài)變化，觸發(fā)更新，Scheduler 在接收到更新后，根據(jù)任務的優(yōu)先級高低來進行調(diào)度，決定要執(zhí)行的任務是什么。
接下來的工作交給 Reconciler 處理，Reconciler 通過對比找出變化了的 Virtual DOM ，為其打上代表增/刪/更新的標記，當所有組件都完成 Reconciler 的工作，才會統(tǒng)一交給Renderer。
Renderer 根據(jù) Reconciler 為 Virtual DOM 打的標記，同步執(zhí)行對應的 DOM 更新操作。

Diff 算法

在調(diào)用 React 的 render() 方法，會創(chuàng)建一棵由 React 元素組成的樹。在下一次 state 或 props 更新時，相同的 render() 方法會返回一棵不同的樹。React 需要基于這兩棵樹之間的差別來進行比較，這個比較的過程就是俗稱的 diff 算法，換成前面我們講的 React Fiber 的概念來說，就是將當前組件與該組件在上次更新時對應的 Fiber node 比較，將比較的結(jié)果生成新的 Fiber 節(jié)點。為了方便理解，我們列舉下這個更新的 DOM 節(jié)點在某一時刻會有這么幾個概念與其相關：

current Fiber：如果該 DOM 節(jié)點已在頁面中，current Fiber 代表該 DOM 節(jié)點對應的 Fiber node。
workInProgress Fiber: workInProgress Fiber 代表了正在內(nèi)存中構(gòu)建的 Fiber 節(jié)點，如果該 DOM 節(jié)點即將在本次更新中渲染到頁面中，則 workInProgress Fiber 代表該 DOM 節(jié)點對應的 Fiber 節(jié)點，就是最后更新的結(jié)果。
ReactElement 對象：即前面講到的 Class 組件 render 方法或者調(diào)用函數(shù)組件的結(jié)果經(jīng)過 React.createElement 生成的對象。

Diff 算法的本質(zhì)就是對比 1 和 3，生成 2。

Diff 策略

React 文檔中提到，即使在最前沿的算法中^[6]，將前后兩棵樹完全比對的算法的復雜程度為 O(n 3 )，其中 n 是樹中元素的數(shù)量。如果在 React 中使用了該算法，那么展示 1000 個元素所需要執(zhí)行的計算量將在十億的量級范圍。這個開銷實在是太過高昂，顯然無法滿足性能要求，于是 React 在以下兩個假設的基礎之上提出了一套 O(n) 的啟發(fā)式算法：

只對同級元素進行 Diff，如果某一個節(jié)點在一次更新中跨域了層級，React 不會復用該節(jié)點，而是重新創(chuàng)建生成新的節(jié)點。
兩個不同類型的元素會產(chǎn)生出不同的樹，如果元素由 div 變?yōu)?p，React 會銷毀 div 及其子孫節(jié)節(jié)點，并新建 p 及其子孫節(jié)點。
開發(fā)者可以通過 key prop 來暗示哪些子元素在不同的渲染下能保持穩(wěn)定；

如上圖所示，React 只會對相同顏色框內(nèi)的 DOM 節(jié)點進行比較，即同一個父節(jié)點下的所有子節(jié)點。當發(fā)現(xiàn)節(jié)點已經(jīng)不存在，則該節(jié)點及其子節(jié)點會被完全刪除掉，不會用于進一步的比較。這樣只需要對樹進行一次遍歷，便能完成整個 DOM 樹的比較。當有下面的情況時（A 節(jié)點直接被整個移動到 D 節(jié)點下）

因為 React 只會對同級節(jié)點進行比較，這時候 React 發(fā)現(xiàn)的是 A 節(jié)點不見了，就會直接銷毀 A 節(jié)點，在 D 節(jié)點那里發(fā)現(xiàn)多了一個新的子節(jié)點 A，則會創(chuàng)建一個新的 A 節(jié)點作為子節(jié)點。

上面的例子是對于在不同層級的節(jié)點的比較，對于同一層級的節(jié)點，React 引入了 key 屬性來來給每一個節(jié)點添加唯一標識，這樣 React 就能匹配到原有的節(jié)點，提高轉(zhuǎn)換效率，如下面的例子：

// 更新前
<ul>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

// 更新后
<ul>
  <li key="2014">Connecticut</li>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

如果沒有 key 值，React 會重新創(chuàng)建每一個子元素，因為在比較 ul 的第一個子元素時發(fā)現(xiàn)兩者不同，即開始重建，但當子元素擁有 key 時，React 使用 key 來匹配原有樹上的子元素以及最新樹上的子元素，現(xiàn)在 React 知道只有帶著 '2014' key 的元素是新元素，帶著 '2015' 以及 '2016' key 的元素僅僅移動了。

所以我們在寫代碼時遇到列表渲染的時候，一定要記得給列表的每一項加上 key 屬性，這個 key 不需要全局唯一，但在列表中需要保持唯一。

Diff 算法的實現(xiàn)

我們從 Diff 的入口函數(shù) reconcileChildFibers 出發(fā)，該函數(shù)會根據(jù) newChild（即 ReactElement 對象）類型調(diào)用不同的處理函數(shù)。其中幾個參數(shù)的含義如下：

newChild：即當前更新新生成的 ReactElement 對象。
returnFiber：代表當前 Diff 的節(jié)點的父級 Fiber 節(jié)點，也就是上次更新時的 Fiber 節(jié)點。
currentFirstChild：即與 newChild 進行 diff 的節(jié)點，也是 returnFiber 的第一個子節(jié)點。

我們可以從同級的節(jié)點數(shù)量將 Diff 分為兩類：

當 newChild 類型為 object、number、string，代表同級只有一個節(jié)點
當 newChild 類型為 Array，同級有多個節(jié)點

單節(jié)點 Diff

對于單個節(jié)點，我們以類型 object 為例，會進入 reconcileSingleElement 函數(shù)里，這個函數(shù)主要做了以下事情：

reconcileSingleElement 方法的部分代碼如下：

function reconcileSingleElement(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  element: ReactElement
): Fiber {

  const key = element.key;

  let child = currentFirstChild;

  // 首先判斷是否存在對應DOM節(jié)點

  while (child !== null) {
    // 上一次更新存在DOM節(jié)點，接下來判斷是否可復用

    // 首先比較key是否相同
    if (child.key === key) {

      // key相同，接下來比較type是否相同
      switch (child.tag) {
        // ...省略case

        default: {
          if (child.elementType === element.type) {
            // type相同則表示可以復用
            // 返回復用的fiber
            return existing;
          }
          // type不同則跳出循環(huán)
          break;
        }
      }

      // 代碼執(zhí)行到這里代表：key相同但是type不同
      // 將該fiber及其兄弟fiber標記為刪除
      deleteRemainingChildren(returnFiber, child);
      break;
    } else {
      // key不同，將該fiber標記為刪除
      deleteChild(returnFiber, child);
    }
    child = child.sibling;
  }


  // 創(chuàng)建新Fiber，并返回 ...省略

}

多節(jié)點 Diff

當 ReactElement 的 children 屬性不是單一節(jié)點的話，如下面結(jié)構(gòu)：

 <ul>
    <li key="0">0</li>
    <li key="1">1</li>
    <li key="2">2</li>
    <li key="3">3</li>
 </ul>

此時它返回的對象的 children 是包含 4 個對象的數(shù)組：

{

  $typeof: Symbol(react.element),
  key: null,
  props: {
    children: [
      {$typeof: Symbol(react.element), type: "li", key: "0", ref: null, props: {…}, …}
      {$typeof: Symbol(react.element), type: "li", key: "1", ref: null, props: {…}, …}
      {$typeof: Symbol(react.element), type: "li", key: "2", ref: null, props: {…}, …}
      {$typeof: Symbol(react.element), type: "li", key: "3", ref: null, props: {…}, …}
    ]
  },
  ref: null,
  type: "ul"
}

這種情況下，reconcileChildFibers的newChild參數(shù)類型為Array，對應的處理函數(shù)是reconcileChildrenArray里的newChildren，在比較時，和newChildren里的每一個child比較的是current fiber，即newChildren[0]與fiber比較，newChildren[1]與fiber.sibling比較。

多節(jié)點 diff 的情況比較多比較復雜，大致可以分為以下幾個方面：

節(jié)點更新

節(jié)點屬性變化
節(jié)點類型變化

節(jié)點增加或減少
節(jié)點位置發(fā)生變化

React 團隊發(fā)現(xiàn)，在日常開發(fā)中，相較于新增和刪除，更新組件發(fā)生的頻率更高。所以 Diff 會優(yōu)先判斷當前節(jié)點是否屬于更新。基于以上原因，Diff 算法的整體邏輯會經(jīng)歷兩輪：

第一輪遍歷：處理更新的節(jié)點。
第二輪遍歷：處理剩下的不屬于更新的節(jié)點。

第一輪遍歷的步驟如下：

遍歷 newChildren，將 newChildren[i] 與 oldFiber 比較，判斷 DOM 節(jié)點是否可復用。
如果可復用，i++，繼續(xù)比較 newChildren[i] 與 oldFiber.sibling，可以復用則繼續(xù)遍歷。
如果不可復用，立即跳出整個遍歷，第一輪遍歷結(jié)束。
如果 newChildren 遍歷完（即 i === newChildren.length - 1）或者 oldFiber 遍歷完（即 oldFiber.sibling === null），跳出遍歷，第一輪遍歷結(jié)束。

第一輪遍歷結(jié)束后，有以下幾種結(jié)果：

newChildren 與 oldFiber 同時遍歷完：這說明新舊節(jié)點數(shù)量一樣，只是組件發(fā)生了更新。此時 Diff 結(jié)束。
newChildren 沒遍歷完，oldFiber 遍歷完：這說明舊的節(jié)點遍歷完了，但是還有新加入的節(jié)點，我們只需要遍歷剩下的 newChildren 為生成的 workInProgress fiber 依次標記上 Placement。
newChildren 遍歷完，oldFiber 沒遍歷完：這說明本次更新比之前的節(jié)點數(shù)量變少了，有節(jié)點被刪除了，所以要遍歷剩下的 oldFiber，依次標記 Deletion。
newChildren 與 oldFiber 都沒遍歷完：這意味著有節(jié)點在這次更新中改變了位置，這時候需要通過 key 來標記節(jié)點是否移動。

等上面所有的節(jié)點都遍歷完成后，都已經(jīng)打上了增/刪/更新的標記，此時就生成了 workInProgress Fiber，剩下的工作就是交個 renderer 處理了。

參考資料

[1]

尤雨溪對于 Virtual DOM 的優(yōu)勢的回答: https://www.zhihu.com/question/31809713/answer/53544875

[2]

React 元素: https://zh-hans.reactjs.org/docs/rendering-elements.html

[3]

reconciliation: https://reactjs.org/docs/reconciliation.html

[4]

demo: https://claudiopro.github.io/react-fiber-vs-stack-demo/

[5]

createFiberFromTypeAndProps: https://github.com/facebook/react/blob/769b1f270e1251d9dbdce0fcbd9e92e502d059b8/packages/react-reconciler/src/ReactFiber.js#L414

[6]

最前沿的算法中: http://grfia.dlsi.ua.es/ml/algorithms/references/editsurvey_bille.pdf

你不知道的 React Virtual DOM