React基础——虚拟DOM和Diff算法_react虚拟dom diff算法

目录

一、虚拟DOM和Diff算法

    1、为什么需要虚拟DOM

    2、什么是虚拟DOM

    3、用JS对象模拟DOM树

    4、Diff算法比较两棵虚拟DOM树的差异

    5、将差异应用到真正的DOM树

    6、总结

React起源于Facebook的内部项目，用来架设Instagram（照片交友）网站。在2013年5月开源。React的设计思想极其独特，属于革命性创新，性能出众，代码逻辑却非常简单，它可能是将来Web开发的主流工具。

前端三大主流框架（https://2018.stateofjs.com/front-end-frameworks/overview/）：
Angular.js：较早。学习曲线比较陡，Ng1学起来比较麻烦，Ng2~5进行了一系列的改革（1和2像是两套框架），提供了组件化开发的概念，支持使用TypeScript。
Vue.js：最火（关注的人多）。中国人开发。
React.js：最流行（用的多）。设计很优秀。

React与Vue：
组件化：Vue通过.vue文件创建对应的组件，template、script、style；React没有组件模板文件，一切都是以JS来表现。
开发团队：Vue以尤雨溪为主导的开源小团队；React是由FaceBook前端官方团队，技术实力比较雄厚。
社区方面：Vue是近两年才火起来的；React诞生较早，社区强大，常见的问题、最优解决方案、文档、博客较全面。
移动APP开发：Weex目前只是一个小玩具，并没有很成功的大案例；ReactNative提供了无缝迁移到移动App的开发体验，用的最多。

模块化：从代码的角度，把一些可复用的代码抽离为单个的模块，便于项目的维护和开发。
组件化：从UI界面的角度，把一些可复用的UI元素抽离为单独的组件，便于项目的维护和开发。

一、虚拟DOM和Diff算法

Why Virtual DOM

如何理解虚拟DOM?-EMayej Bee的回答-知乎

深度剖析：如何实现一个Virtual DOM算法

深入浅出React（四）：虚拟DOM Diff算法解析

虚拟DOM介绍

1、为什么需要虚拟DOM

浏览器的工作流程几乎是相似的。How Browsers Work

（1）创建DOM树：浏览器收到HTML文件后，渲染引擎就会对其进行解析并创建一个DOM树节点，这些节点与HTML元素具有一对一的关系。

（2）创建渲染（Render）树：解析来自外部CSS文件和内联的样式，样式信息和DOM树中的节点用于创建渲染树。在WebKit中，DOM树中的所有节点都有attach方法，它接收计算出的样式信息并返回一个渲染对象。

（3）布局（也称回流）：渲染树中的每个节点都有屏幕坐标，使其出现在屏幕上的确切位置。

（4）绘画：绘制渲染对象。遍历渲染树并调用每个节点的paint()方法，在屏幕上显示内容。

虚拟Dom快，有两个前提：（1）Javascript很快。Julia Micro-Benchmarks可看到Javascript跟Java基本是一个量级，是C语言的几倍。（2）DOM很慢。用document.createElement()创建一个空元素时，有以下东西要实现HTMLElement的属性和方法 Element的属性和方法 GlobalEventHandlers的属性和方法，还有不少嵌套引用，DOM设计得太复杂。原生及很多框架在调用DOM的API的时候做得不好，导致整个过程更加慢。每次更改DOM时，所有创建DOM树至渲染对象都将重做，假设一个接一个地修改了30个节点，可能30次重新计算布局、重新渲染等。

目的是为了实现页面元素的高效更新。

2、什么是虚拟DOM

虚拟DOM是对DOM的“双缓冲”应用，可以在脱机DOM树中执行每个更改，之后将所有更改存储为真正的DOM，布局渲染到页面上（类似硬盘和缓存），只执行一次，减少了计算的数量。虚拟DOM自动化和抽象DOM片段的管理，不必手动执行，不必手动跟踪哪部分已改变需要刷新。通过放弃对自身的DOM操作，允许代码的不同组件或部分请求DOM修改而不必相互交互，避免在修改DOM的所有部分之间进行同步。

React虚拟DOM的运作是透明的，根本没有DOM这个概念。只需提供component和数据，无需担心性能问题，由虚拟DOM来确保只对界面上真正变化的部分进行实际的DOM操作。

虚拟DOM并没有完全实现DOM，只保留了Element之间的层次关系和一些基本属性。创建新的虚拟DOM时速度很快，每个component的render函数就是给新的虚拟dom提供input。（1）用JavaScript对象表示DOM树的结构，构建一个真正的DOM树，插到文档当中；（2）当状态变更时，重新构造一棵新的JS对象树，将新旧树进行比较，记录差异；（3）将差异应用到步骤1所构建的真正的DOM树上，实现视图更新。

例子如下：通常是先把0, 1, 2元素删除，再加3, 4, 5, 6新元素，有3次删除元素和4次添加元素。而React会把这两个虚拟DOM树做Diff，只修改innerHTML和添加一个元素6。

<ul>
  <li>0</li>
  <li>1</li>
  <li>2</li>
</ul>
<!-- 更改后 -->
<ul>
  <li>3</li>
  <li>4</li>
  <li>5</li>
  <li>6</li>
</ul>

JS对象只需要记录DOM树的节点类型、属性和子节点。DOM树和JavaScript对象可以互相转换。

<!-- HTML写法 -->
<ul id='list'>
  <li class='item'>Item 1</li>
  <li class='item'>Item 2</li>
  <li class='item'>Item 3</li>
</ul>

// 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"]},
  ]
}

3、用JS对象模拟DOM树

（1）构建JS对象

// element.js
function Element(tagName, props, children) {
    if (!(this instanceof Element)) {
        return new Element(tagName, props, children);
    }
 
    this.tagName = tagName;
    this.props = props || {};
    this.children = children || [];
    this.key = props ? props.key : undefined;
 
    let count = 0;
    this.children.forEach((child) => {
        if (child instanceof Element) {
            count += child.count;
        }
        count++;
    });
    this.count = count;
}
 
module.exports = function (tagName, props, children) {
  return new Element(tagName, props, children)
}

var el = require('./element')
// 目前ul只是一个JavaScript对象表示的DOM结构
var ul = el('ul', {id: 'list'}, [
  el('li', {class: 'item'}, ['Item 1']),
  el('li', {class: 'item'}, ['Item 2']),
  el('li', {class: 'item'}, ['Item 3'])
])

（2）根据JS对象构建真正的DOM树 

render方法根据tagName构建一个真正的DOM节点，设置这个节点的属性，递归地把子节点也构建起来。

// 根据JS对象构建真正的DOM树
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
}

（3）将真正的DOM树渲染至页面中

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

4、Diff算法比较两棵虚拟DOM树的差异

新旧虚拟DOM树需要进行Diff算法分析，找到差异。 标准的Diff算法复杂度需要O(n^3)，Facebook工程师结合Web界面的特点做出两个简单的假设，使得Diff算法复杂度直接降低到O(n)。算法上的优化是React整个界面Render的基础。（1）两个相同组件产生类似的DOM结构，不同的组件产生不同的DOM结构；（2）对于同一层次的一组子节点，可以通过唯一的id进行区分。

（1）逐层进行节点比较

tree diff：逐层对比；
component diff：进行Tree Diff时，每一层中，组件级别的对比；
element diff：进行组件对比时，如果两个组件类型相同，则需要进行元素级别的对比。

在React中比较两个虚拟DOM节点，分为两种情况：
节点类型不同 。当在树中的同一位置前后输出了不同类型的节点，直接删除之前的节点，创建并插入新的节点。注意，该删除的节点的子节点也会被完全删除，它们也不会用于后面的比较。同样的逻辑也被用在React组件的比较，这正是应用了第一个假设。
节点类型相同，但是属性不同。对属性进行重设从而实现节点的转换。虚拟DOM的style属性稍有不同，其值并不是一个简单字符串而必须为一个对象。

在React中，树的算法非常简单，两棵树只会对同一层次的节点进行比较，即同一个父节点下的所有子节点。当发现节点已经不存在，则该节点及其子节点会被完全删除掉，不会用于进一步的比较。这样只需要对树进行一次遍历，便能完成整个DOM树的比较。

这一假设至今为止没有导致严重的性能问题。在实现自己的组件时，保持稳定的DOM结构有助于性能的提升，例如可以通过CSS隐藏或显示某些节点，而不是真的移除或添加DOM节点。

例如下面的DOM结构转换：A节点被整个移动到D节点下，DOM Diff操作如下。

深度优先遍历，记录差异，每个节点都会有一个唯一的标记。patches是一个对象，用来记录每个节点的差异。

// 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
  })
}

差异类型如下。

var REPLACE = 0 // 替换掉原来的节点
var REORDER = 1 // 移动、删除、新增子节点
var PROPS = 2 // 修改了节点的属性
var TEXT = 3 // 对于文本节点，文本内容改变

{
    0: [{ type: REPALCE, node: newNode }, { type: PROPS,  props: { id: "container" }}],
    2: [{ type: TEXT, content: "Virtual DOM2" }]
}

（2）列表节点的比较

React在遇到列表时却又找不到key时提示警告，通常意味着潜在的性能问题。对于列表节点提供唯一的key属性可以帮助React定位到正确的节点进行比较，从而大幅减少DOM操作次数，提高了性能。

列表节点的操作通常包括添加、删除和排序。（列表节点不只由v-for生成，指的是同一级的节点）

假设用英文字母唯一地标识每一个子节点，旧的节点顺序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}, ...] }]

5、将差异应用到真正的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)
    }
  })
}

6、总结

Virtual DOM算法主要实现三个函数：element, diff, patch，之后就可以进行使用。

下面是最简单的实践，实际中还需要处理事件监听、加入JSX语法等，完整代码见simple-virtual-dom。

// 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)