React的贡献在于它提出的组件化、虚拟DOM、帮助整个前端进入工程化、将函数式编程的思想带给前端。
这里记录一下学习过程时关于虚拟DOM算法的实现。

---

一、Virtual DOM

在React中，render 执行的结果得到的并不是真正的 DOM 节点，结果仅仅是轻量级的 JavaScript 对象，我们称之为virtual DOM。
真正的 DOM 元素属性非常多，每次操作很有可能引起回流（Reflow）和重绘（Repaint）。
相对于真正的 DOM 对象，原生的 JavaScript 对象处理起来更快，而且更简单。DOM 树上的结构、属性信息我们都可以很容易地用 JavaScript 对象表示出来：

var element = {
  tagName: 'ul', // 节点标签名
  props: { // DOM的属性，用一个对象存储键值对
    id: 'list'
  },
  children: [ // 该节点的子节点
    {tagName: 'li', props: {class: 'item'}, children: ["Item 1"]}
  ]
}

对应的HTML：

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

所以可以用 JavaScript 对象表示的树结构来构建一棵真正的DOM树。用 JavaScript 对象表示 DOM 信息和结构，当状态变更的时候，重新渲染这个 JavaScript 的对象结构。然后新渲染的对象树去和旧的树进行对比，记录这两棵树差异。记录下来的不同就是我们需要对页面真正的 DOM 操作，然后把它们应用在真正的 DOM 树上，页面就变更了。
Virtual DOM 算法包括几个步骤：

• 用 JavaScript 对象结构表示 DOM 树的结构，用这个树构建一个真正的 DOM 树，插到文档当中。
• 当状态变更的时候，重新构造一棵新的对象树。将新的树和旧的树进行比较，记录两棵树差异。
• 将差异应用到步骤1所构建的真正的DOM树上，视图就更新了。

Virtual DOM 本质上就是在 JS 和 DOM 之间做了一个缓存。因为DOM 很慢，JS只操作Virtual DOM，最后的时候再把变更渲染到DOM。

二、算法实现

2.1. 用JS构建DOM树
JavaScript 来表示一个 DOM 节点只需要记录它的节点类型、属性，还有子节点：
element.js

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 el = require('./element')
var ul = el('ul', {id: 'list'}, [
  el('li', {class: 'item'}, ['Item 1'])
])

ul只是一个 JavaScript 对象表示的 DOM 结构，页面上并没有，我们可以根据这个ul构建真正的<ul>。

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节点，然后设置这个节点的属性，最后递归地把自己的子节点也构建起来。

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

上面的ul是真正的DOM节点，把它塞入文档中，这样body里面就有了真正的<ul>的DOM结构：

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

2.2. 比较两棵DOM树的差异
传统 diff 算法的复杂度为 O(n3)，React 通过制定大胆的策略：

1. Web UI 中 DOM 节点跨层级的移动操作特别少，可以忽略不计。
2. 两个相同组件产生类似的DOM结构，不同的组件产生不同的DOM结构。

• 对于同一层次的一组子节点，它们可以通过唯一的id进行区分。

将 O(n3) 复杂度的问题转换成 O(n) 复杂度的问题。
通过diff策略，React 分别对 tree diff、component diff 以及 element diff 进行算法优化。

1. tree diff
   基于策略一，React 对树的算法进行了简洁明了的优化，即对树进行分层比较，两棵树只会对同一层次的节点进行比较。当发现节点已经不存在，则该节点及其子节点会被完全删除掉，不会用于进一步的比较。这样只需要对树进行一次遍历，便能完成整个 DOM 树的比较。
2. component diff

• 如果是同一类型的组件，按照原策略继续比较 virtual DOM tree。
• 如果不是，则将该组件判断为 dirty component，从而替换整个组件下的所有子节点。
• 对于同一类型的组件，有可能其 Virtual DOM 没有任何变化，如果能够确切的知道这点那可以节省大量的 diff 运算时间，因此 React 允许用户通过 shouldComponentUpdate() 来判断该组件是否需要进行 diff。

3. element diff
   当节点处于同一层级时，React diff 提供了三种节点操作，分别为：INSERT_MARKUP（插入）、MOVE_EXISTING（移动）和 REMOVE_NODE（删除）。

• INSERT_MARKUP：新的 component 类型不在老集合里， 即是全新的节点，需要对新节点执行插入操作。
• MOVE_EXISTING：在老集合有新 component 类型，且 element 是可更新的类型，generateComponentChildren 已调用 receiveComponent，这种情况下 prevChild=nextChild，就需要做移动操作，可以复用以前的 DOM 节点。
• REMOVE_NODE：老 component 类型，在新集合里也有，但对应的 element 不同则不能直接复用和更新，需要执行删除操作，或者老 component 不在新集合里的，也需要执行删除操作。
  React对其进行了优化，当节点相同时，只是由于位置发生变化。允许开发者对同一层级的同组子节点，添加唯一 key 进行区分。
  新老集合进行 diff 差异化对比，通过 key 发现新老集合中的节点都是相同的节点，因此无需进行节点删除和创建，只需要将老集合中节点的位置进行移动，更新为新集合中节点的位置。

2.3把差异应用到真正的DOM树上

具体可参考：
如何实现一个Virtual DOM算法
不可思议的react diff