我的前端故事----React算法又是個什么鬼？

WendySturdi 8年前發布 | 38K 次閱讀前端 React 前端技術

一不小心就過去了半年了，這么久以來都沒有更新博客了，這半年也從開始的頁面仔逐漸的變成一個jser，之前有人和我說前端沒必要看算法。。。那些是后端的事情，前端的需求沒有那么復雜等等。。。但隨著2015年前端圈爆炸式的增長，越來越多的框架開始層出不窮的冒了出來，而對于我們前端人員的要求也從開始的切切圖拼頁面到現在的關注性能，關注工程化了。

而對于2016年，對搶眼的莫過于ReactJS了，從0.11開始關注和使用到現在的v15，版本迭代了多次，API改了無數，但最根本的幾點卻依舊沒變，虛擬DOM，單項數據流，這些從React開始便存在的特點，直到現在都沒有改變過，然而當我在實際項目中使用的時候卻發現雖然這些框架都很好，可是推廣起來卻著實頭疼。。。很多新手發現接手的代碼和自己之前印象里的前端代碼完全不在一個次元。。。

今天，借著這次機會我就總結一下自己對于React的虛擬DOM這部分的理解～說真的。。千萬不要以為數據結構對前端沒用。。。

首先我們來談談什么是虛擬DOM，以及為什么要使用虛擬DOM，其實很多時候我們都在或多或少的有過接觸這個概念，我們知道當我們需要直接操作DOM節點的時候會遇到如下幾個問題：

1，頻繁的對DOM樹進行操作會導致性能下降嚴重。

2，當我們需要一次修改很多地方的時候總會有地方被我們忽略或者忘記修改。

那么針對上面我們最常遇到的兩點問題我們該用什么思路去解決呢？

對于第一點，我們就需要先知道為什么頻繁的操作會導致性能下降，說道這個就要不得不提到前端面試中經常問到的優化方式－－repaint(重繪)和reflow(渲染)，那么對于這一點該具體如何理解和優化這位博友說的很好了，有興趣的同學可以看看他的這篇文章，那么我們今天就要從js上面下手去解決頻繁的操作這個問題了，那么我們該如何減少渲染次數和范圍呢？最簡單直接的方法就是只渲染改動的地方，那么怎么才能知道哪里是改動的地方呢？對于這個問題，熟悉angularJS的同學一定知道angularJS中使用的“臟檢查”機制，就是拿前后的DOM樹去做對比，然而angularJS一直以來被人詬病的也就是這個了，性能差，消耗資源高等等，無一不是硬傷，那么我們該怎么曲線救國呢？React告訴我們的是在內存中維護一顆和頁面一樣的DOM樹，這顆DOM樹不是真正渲染在html中的，而是放在內存中的，因此修改它將會特別的快，并且資源消耗也少很多，當我們render一個頁面的時候首先先將我們最新的DOM去和內存中的這棵虛擬DOM樹去做對比（臟檢查），然后對比出差一點，然后再用這棵虛擬DOM去整體替換html中實際的那個DOM樹，這樣其實我們只是做了一次渲染，無論我們改了多少，改了什么，我們都只是渲染了一次（類似重新渲染一次頁面）。

那么接下來我們知道了思路后就該動手去實踐了，既然說到了虛擬DOM樹是真實DOM樹的一個鏡像，那么我們該如何在內存中保存這棵樹呢？又該用什么方式去存儲呢？這個時候就是數據結構同學上線的時間了，相對于 DOM 對象，原生的 JavaScript 對象處理起來更快，而且更簡單。因此DOM 樹上的結構、屬性信息我們都可以很容易地用 JavaScript 對象表示出來：

var element = {
  tagName: 'ul', // 節點標簽名
  props: { // DOM的屬性，用一個對象存儲鍵值對
    id: 'list'
  },
  children: [ // 該節點的子節點
    {tagName: 'li', props: {class: 'item'}, children: ["Item 1"]},
    {tagName: 'li', props: {class: 'item'}, children: ["Item 2"]},
    {tagName: 'li', props: {class: 'item'}, children: ["Item 3"]},
  ]
}

而這樣一個javascript對象代表的html代碼是什么樣的呢？

<ul id='list'>
  <li class='item'>Item 1</li>
  <li class='item'>Item 2</li>
  <li class='item'>Item 3</li>
</ul>

其實對比過來會發現每一種HTML結構都可以轉變成對應的javascript結構的。這就是所謂的 Virtual DOM 算法。包括幾個步驟：

1，用 JavaScript 對象結構表示 DOM 樹的結構；然后用這個樹構建一個真正的 DOM 樹，插到文檔當中。

2，當狀態變更的時候，重新構造一棵新的對象樹。然后用新的樹和舊的樹進行比較，記錄兩棵樹差異。

3，把2所記錄的差異應用到步驟1所構建的真正的DOM樹上，視圖就更新了。

Virtual DOM 本質上就是在 JS 和 DOM 之間做了一個緩存。這個概念就和我們當初學操作系統一樣，可以類比 CPU 和硬盤，既然硬盤這么慢，我們就在它們之間加個緩存：既然 DOM 這么慢，我們就在它們 JS 和 DOM 之間加個緩存。CPU（JS）只操作內存（Virtual DOM），最后的時候再把變更寫入硬盤（DOM）。

接下來我們說說算法的具體實現吧，既然整個過程大致可以分為三部，那我們就來一步步的講，首先就是第一部，用js對象模擬DOM樹，用javascript來表示一個DOM節點的話只需要記錄它的一個節點類型，屬性以及子節點就可以了。

function Element (tagName, props, children) {
  this.tagName = tagName
  this.props = props
  this.children = children
}

module.exports = function (tagName, props, children) {
  return new Element(tagName, props, children)
}

例如上面剛剛的那個DOM節點就可以用這種結構來表示：

var ul = Element('ul', {id: 'list'}, [
  Element('li', {class: 'item'}, ['Item 1']),
  Element('li', {class: 'item'}, ['Item 2']),
  Element('li', {class: 'item'}, ['Item 3'])
])

現在ul只是一個 JavaScript 對象表示的 DOM 結構，頁面上并沒有這個結構。我們可以根據這個ul構建真正的HTML元素了：

Element.prototype.render = function () {
  var el = document.createElement(this.tagName) // 根據tagName構建
  var props = this.props

  for (var propName in props) { // 設置節點的DOM屬性
    var propValue = props[propName]
    el.setAttribute(propName, propValue)
  }

  var children = this.children || []

  children.forEach(function (child) {
    var childEl = (child instanceof Element)
      ? child.render() // 如果子節點也是虛擬DOM，遞歸構建DOM節點
      : document.createTextNode(child) // 如果字符串，只構建文本節點
    el.appendChild(childEl)
  })

  return el
}

render 方法會根據傳入的 tagName 來構建一個真正的DOM節點的，然后根據這個DOM節點的屬性，遞歸的把自己的子節點也構建出來，因此只需要執行如下代碼即可：

var ulRoot = ul.render()
document.body.appendChild(ulRoot)

上面的 ulRoot 才是真正的DOM節點，最終會在頁面中插入這個真正的DOM樹：

<ul id='list'>
  <li class='item'>Item 1</li>
  <li class='item'>Item 2</li>
  <li class='item'>Item 3</li>
</ul>

第二步：比較兩顆虛擬DOM樹的差異：

當然，對比兩個DOM樹的差異才是最核心的部分，這也就是所謂的diff算法了，兩個DOM的算法是一個 O(n^3) 問題。但是在前端的實際使用種我們很少去跨級的移動整個DOM樹，所以我們可以簡化成一層之間的移動，所以diff算法就變成了一個同級元素對比的算法了（僅僅是說明用，真正的算法實現還是去看React的源代碼吧）。

我的前端故事----React算法又是個什么鬼？

上面的圖片中的移動其實只是同級 div 的對比，第二層級的 div 只會跟第二層級的 div 對比。這樣算法復雜度就可以達到 O(n)。緊接著就是通過深度優先遍歷來記錄差異，在深度優先遍歷的時候，每遍歷到一個節點就把該節點和新的的樹進行對比。如果有差異的話就記錄到一個對象里面（類似權重相加的概念）。

// diff 函數，對比兩棵樹
function diff (oldTree, newTree) {
  var index = 0 // 當前節點的標志
  var patches = {} // 用來記錄每個節點差異的對象
  dfsWalk(oldTree, newTree, index, patches)
  return patches
}

// 對兩棵樹進行深度優先遍歷
function dfsWalk (oldNode, newNode, index, patches) {
  // 對比oldNode和newNode的不同，記錄下來
  patches[index] = [...]

  diffChildren(oldNode.children, newNode.children, index, patches)
}

// 遍歷子節點
function diffChildren (oldChildren, newChildren, index, patches) {
  var leftNode = null
  var currentNodeIndex = index
  oldChildren.forEach(function (child, i) {
    var newChild = newChildren[i]
    currentNodeIndex = (leftNode && leftNode.count) // 計算節點的標識
      ? currentNodeIndex + leftNode.count + 1
      : currentNodeIndex + 1
    dfsWalk(child, newChild, currentNodeIndex, patches) // 深度遍歷子節點
    leftNode = child
  })
}

例如，上面的div和新的div有差異，當前的標記是0，那么：

patches[0] = [{difference}, {difference}, ...] // 用數組存儲新舊節點的不同

同理p是patches[1]，ul是patches[3]，以此類推。那差異類型是什么呢？對DOM操作可能會有下面幾種：

替換掉原來的節點，例如把上面的div換成了section
移動、刪除、新增子節點，例如上面div的子節點，把p和ul順序互換
修改了節點的屬性
對于文本節點，文本內容可能會改變。例如修改上面的文本節點2內容為Virtual DOM 2。

所以我們需要定義幾種差異類型：

var REPLACE = 0
var REORDER = 1
var PROPS = 2
var TEXT = 3

那對于節點的替換就很簡單了，只要判斷新舊節點的 tagName 的和是不是一樣的，如果不一樣就說明需要替換了，例如 div 替換成 section，就記作：

patches[0] = [{
  type: REPALCE,
  node: newNode // el('section', props, children)
}]

如果給 div 新增了屬性 id 為 test ，就記作：

patches[0] = [{
  type: REPALCE,
  node: newNode // el('section', props, children)
}, {
  type: PROPS,
  props: {
    id: "test"
  }
}]

如果是文本節點的話，就記作：

patches[2] = [{
  type: TEXT,
  content: "Virtual DOM2"
}]

那如果把我div的子節點重新排序呢？例如p, ul, div的順序換成了div, p, ul。這個該怎么對比？如果按照同層級進行順序對比的話，它們都會被替換掉。如p和div的tagName不同，p會被div所替代。最終，三個節點都會被替換，這樣DOM開銷就非常大。而實際上是不需要替換節點，而只需要經過節點移動就可以達到，我們只需知道怎么進行移動。接下來是列表對比算法。

假設現在可以英文字母唯一地標識每一個子節點：

舊的節點順序：a b c d e f g h i

現在對節點進行了刪除、插入、移動的操作。新增j節點，刪除e節點，移動h節點：

新的節點順序：a b c h d f g i j

現在知道了新舊的順序，求最小的插入、刪除操作（移動可以看成是刪除和插入操作的結合）。這個問題抽象出來其實是字符串的最小編輯距離問題（Edition Distance），最常見的解決算法是 Levenshtein Distance，通過動態規劃求解，時間復雜度為 O(M * N)。但是我們并不需要真的達到最小的操作，我們只需要優化一些比較常見的移動情況，犧牲一定DOM操作，讓算法時間復雜度達到線性的（O(max(M, N))。具體算法細節比較多，這里不累述。我們能夠獲取到某個父節點的子節點的操作，就可以記錄下來：

patches[0] = [{
  type: REORDER,
  moves: [{remove or insert}, {remove or insert}, ...]
}]

但是要注意的是，因為tagName是可重復的，不能用這個來進行對比。所以需要給子節點加上唯一標識key，列表對比的時候，使用key進行對比，這樣才能復用老的 DOM 樹上的節點。這樣，我們就可以通過深度優先遍歷兩棵樹，每層的節點進行對比，記錄下每個節點的差異了。

接下來就是第三步，把差異應用到真正的DOM樹上！因為步驟一所構建的 JavaScript 對象樹和render出來真正的DOM樹的信息、結構是一樣的。所以我們可以對那棵DOM樹也進行深度優先的遍歷，遍歷的時候從步驟二生成的patches對象中找出當前遍歷的節點差異，然后進行 DOM 操作。

function patch (node, patches) {
  var walker = {index: 0}
  dfsWalk(node, walker, patches)
}

function dfsWalk (node, walker, patches) {
  var currentPatches = patches[walker.index] // 從patches拿出當前節點的差異

  var len = node.childNodes
    ? node.childNodes.length
    : 0
  for (var i = 0; i < len; i++) { // 深度遍歷子節點
    var child = node.childNodes[i]
    walker.index++
    dfsWalk(child, walker, patches)
  }

  if (currentPatches) {
    applyPatches(node, currentPatches) // 對當前節點進行DOM操作
  }
}

applyPatches，根據不同類型的差異對當前節點進行 DOM 操作：

function applyPatches (node, currentPatches) {
  currentPatches.forEach(function (currentPatch) {
    switch (currentPatch.type) {
      case REPLACE:
        node.parentNode.replaceChild(currentPatch.node.render(), node)
        break
      case REORDER:
        reorderChildren(node, currentPatch.moves)
        break
      case PROPS:
        setProps(node, currentPatch.props)
        break
      case TEXT:
        node.textContent = currentPatch.content
        break
      default:
        throw new Error('Unknown patch type ' + currentPatch.type)
    }
  })
}

而virtual DOM 算法主要是實現上面步驟的三個函數：element，diff，patch。然后就可以實際的進行使用：

// 1. 構建虛擬DOM
var tree = el('div', {'id': 'container'}, [
    el('h1', {style: 'color: blue'}, ['simple virtal dom']),
    el('p', ['Hello, virtual-dom']),
    el('ul', [el('li')])
])

// 2. 通過虛擬DOM構建真正的DOM
var root = tree.render()
document.body.appendChild(root)

// 3. 生成新的虛擬DOM
var newTree = el('div', {'id': 'container'}, [
    el('h1', {style: 'color: red'}, ['simple virtal dom']),
    el('p', ['Hello, virtual-dom']),
    el('ul', [el('li'), el('li')])
])

// 4. 比較兩棵虛擬DOM樹的不同
var patches = diff(tree, newTree)

// 5. 在真正的DOM元素上應用變更
patch(root, patches)

至此，全部的渲染過程都完成了，到此為止我想很多新入手的同學多少應該可以理解這個React了這篇博客中的算法實現我也是參考Github上面一位大神的實現，所以在這里我更多的是介紹整個流程的思路，希望對于React還一頭霧水的同學能夠仔細看過這篇說明后有所理解，不是算法不重要，無論是哪個崗位上的程序員，都需要熟悉數據結構，這是作為一個程序員理清思路的必備要素～～接下來的博客我會介紹一些前端工程化上面的理解，希望大家能喜歡～～

來自：http://www.cnblogs.com/fuhuixiang/p/5505848.html

本文由用戶 WendySturdi 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1463885550996.html

前端 React 前端技術

我的前端故事----React算法又是個什么鬼？

相關經驗

相關資訊

相關文檔

目錄