如何理解虚拟DOM

  • 1 对前端应用状态管理的思考
  • 2 Virtual DOM算法
  • 3 算法实现
    • 3.1 步骤一： 用JS对象模拟虚拟DOM树
    • 3.2 步骤二： 比较两棵虚拟DOM树的差异
    • 3.3 步骤三： 把差异运用到真正的DOM树上
  • 4 结语
  • 5 参考 References

1 对前端应用状态的思考

假如现在需要写一个像下面表格的应用程序，这个表格可以根据不同的字段进行升序、降序的展示。
Virtual DOM - 图1根据这个程序，在JavaScript代码里面存储这样的数据：

  1. var sortKey = "new";    //排序的字段，新增（new）、取消（cancel）、净关注（gain）、累积（cumlate）
  2. var sortType = 1;     //升序or降序
  3. var data = [{..}, {..}, {..}, ..];    //表格数据

用三个字段分别存储当前排序的字段、排序方向和表格数据；然后给表格头部加点击事件：当用户点击特定的字段的时候，根据上面几个字段存储的内容来对内容进行排序，然后用JS或者jQuery操作DOM，更新页面的排序状态。

此上操作导致的后果：随着应用程序越来复杂，需要在JS里面维护的字段也越来越多，需要监听事件和在事件回调用更新页面的DOM也越来越多，应用程序会变得难维护。使用MVC、MVP的架构模式，希望从代码组织方式来降低维护这类复杂应用程序的难度。但是MVC架构也无法减少所维护的状态，也没有降低状态更新需要对页面的更新操作（前端来说就是DOM操作），需要操作的DOM还是需要操作，只是换了个地方。

状态改变了要操作相应的DOM元素，让试图和和状态绑定，状态变更了视图自动更新。MVVM模式由此而生，只要在模板中声明视图组件是和什么状态绑定的，双向绑定引擎就会在状态更新的时候自动更新视图。

关于MV*模式的内容，可浏览这篇介绍。

MVVM可以很好的降低我们维护状态 —> 视图的复杂程度（减少代码中的视图更新逻辑）。但是这不是唯一的方法，还有更直观的方法，可以大大降低视图更新的操作：一旦状态发生了变化，就用模板引擎重新渲染整个视图，然后用新的视图更换旧的视图。就像上面的表格，当用户点击的时候，还是在JS里面更新状态，但是页面更新就不用手动操作DOM了，直接把整个表格用模板引擎重新渲染一遍，然后设置一下innerHTML即可。

但是这样的问题就会导致很慢，即使一个小小的状态变更都要构造整棵DOM，性价比太低；而且这样做的话，input和textarea就会失去原有的焦点。最后的结论：对于局部的小视图的更新，没有问题；但是对于大型视图，如全局应用状态变更的时候，需要更新页面较多局部视图的时候，这样的做法不可取。

这里需要明白和记住这样的做法，因为后面你会发现，其实Virtual DOM就是这么做的，只是加了一些特别的步骤来避免了整棵DOM树变更。

另外，上面提供的几种方法，其实都是在解决同一个问题：维护状态，更新视图。在一般的应用当中，如果能够有好的方案来应对这个问题，那么就几乎降低了大部分复杂性。

2 Virtual DOM算法

DOM是很慢的。如果我们把一个简单的div元素的属性都打印出来，你会看到：
image.png
注：F12，换行键：shift+enter

而这仅仅是第一层。真正的DOM元素非常庞大，这是因为标准就是这么设计的。而且操作它们的时候需要小心翼翼，轻微的触碰可能就会导致页面重排，这可是杀死性能的罪魁祸首。

相对于DOM对象，原生的JavaScript对象处理起来更快、更简单。DOM树上的结构、属性信息我们都可以很容易地用JavaScript对象表示出来：

  1. var element = {
  2.     tagName: 'ul',    //    节点标签名
  3.   props: {    //    DOM的属性，用一个对象存储键值对
  4.       id: 'list'
  5.   },
  6.   children: [
  7.     {    tagName: 'li', props: {class: 'item', children: ['Item 1']}    },
  8.     {    tagName: 'li', props: {class: 'item', children: ['Item 2']}    },
  9.     {    tagName: 'li', props: {class: 'item', children: ['Item 3']}    }
  10.   ]
  11. }

上面对应的HTML写法是：

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

既然原来DOM树的信息都可以用JavaScript对象来表示，反之可以根据这个用JS对面表示的树结构来构建一棵真正的DOM树。

状态变更—>重新渲染整个视图的方式可以稍微修改一下：用JavaScript对象表示DOM信息和结构，当状态变更的时候，重新渲染整个JavaScript的对象结构。这样做其实也没用，因为真正的页面其实并没有改变。

但可以用新渲染的对象树和旧的树进行对比，记录这两棵树的差异。记录下来的不同就是需要对页面真正的DOM操作，然后把它们应用在真正的的DOM树上，页面就变更了。这样就可以做到：视图的结构确实是整个全新渲染了，但是最后操作DOM的时候确实只变更有不同的地方。

这就是所谓的Virtual DOM算法。包括几个步骤：

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

Virtual DOM本质上就是在JS和DOM之间做了一个缓存。可以类比CPU和硬盘，既然硬盘这么慢，我们就在它们之间加个缓存：既然DOM这么慢，我们就在它们JS和DOM之间加个缓存。CPU（JS）只操作内存（Virtual DOM）,最后的时候再把变更写入硬盘（DOM）。

3 算法实现

3.1 步骤一： 用JS对象模拟DOM树

用JavaScript来表示一个DOM节点是很简单的事情，只需要记录它的节点类型、属性，还有子节点：

element.js

  1. function Element (tagName, props, children) {
  2.   this.tagName = tagName;
  3.   this.props = props;
  4.   this.children = children;
  5. }
  7. module.exports = function (tagName, props, children) {
  8.     return new Element(tagName, props, children);
  9. }

例如上面的DOM结构就可以简单的表示：

  1. var el = require('./element');
  3. var ul = el('ul', {id: 'list'}, [
  4.     el('li', {class: 'item'}, ['Item 1']),
  5.     el('li', {class: 'item'}, ['Item 2']),
  6.     el('li', {class: 'item'}, ['Item 3'])
  7. ])

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

    :

    1. Element.prototype.render = function () {
    2.   var el = document.createElement(this.tagNanme);    //    根据tagName构建
    3.   var props = this.props;
    5.   for (var propName in props) {    //设置节点的DOM属性
    6.         var propValue = props[propName];
    7.     el.setAttribute(propName, propValue);
    8.   }  
    10.   var children = this.children || [];
    12.   children.forEach(function (child) {
    13.       var childEl = (child instanceof Element)
    14.         ? child.render()    //    如果子节点也是虚拟DOM，递归构建DOM节点
    15.         : document.createTextNode(child);    //    如果字符串，只构建文本节点
    16.     el.appendChild(childEl);
    17.   })
    19.   return el;
    20. }
    1.  render方法会根据tagName构建一个真正的DOM节点，然后设置这个节点的属性，最后递归的把自己的子节点也构建起来。所以只需要：
    var ulRoot = ul.render();
document.body.appendChild(ulRoot);

    上面的ulRoot是真正的DOM节点，把它塞入文档中，这样body里面就有了真正的

      的DOM 结构：

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

      完整代码可见element.js。

      3.2 步骤二： 比较两棵虚拟树的差异核心

      比较两棵DOM树的差异就Virtual算法最核心的部分，这也是所谓的Virtual DOM的diff算法。两棵树的完全的diff算法是一个时间复杂度为O（n^3）的问题。但是在前端当中，你很少会跨越层级地移动DOM元素。所以Virtual DOM元素。所以Virtual DOM只会对同一个层级的元素进行对比：
      Virtual DOM - 图3

      上面的div只会和同一层级的div对比，第二层级地只会跟第二层级对比。这样算法复杂度就可以达到O(n)。

      3.2.1 深度优先遍历，记录差异

      在实际的代码中，会对新旧两棵树进行一个深度优先的遍历，这样每个节点都会有一个唯一的标记：
      Virtual DOM - 图4
      在深度优先遍历的时候，每遍历到一个节点就把该节点和新的树进行对比。如果有差异的话就记录到一个对象里面。

      //    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;
      dsfWalk(child, newChild, currentNodeIndex, patches);    //    s深度遍历子节点
      leftNode = child;
    })
  }
}

      例如，上面的div和新的div有差异，当前的标记是0，那么：

      patches[0] = [{difference}, {difference}, ...];    //    用数组存储新旧节点的不同

      同理p是patches[1]，ul是pathches[3]，类推。

      3.2.2 差异类型

      上面说的节点的差异指的是什么呢？对DOM操作可能会：

      1. 替换掉原来的节点，例如把上面的div换成section；
      2. 移动、删除、新增子节点，例如上面div的子节点，把p和ul顺序互换；
      3. 修改了节点的属性；
      4. 对于文本节点，文本内容可能会改变。例如修改上面的文本节点2内容为Virtual DOM2。

      所以我们定义了几种差异类型：

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

      对于节点替换，判断新旧节点的tagName是不是一样的，若不同的说明需要替换掉。如div换成section，就记录如下：

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

      如果给div新增属性id为container，就记录下：

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

      如果是文本节点，如上面文本节点2，就记录下：

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

      那如果把我div的子节点重新排序呢？例如p，ul，div的顺序换成了div，p， ul。这个改怎么对比？如果按照同层级进行顺序对比的话，它们都会被替换掉。如p和div的tagName不同，p会被div所替代。最终，三个节点都会被替换，这样DOM的开销就非常大。而实际是不需要替换节点，则只需要经过节点移动就可以达到，我们只需要知道怎么进行移动。
      这牵涉到两个列表的对比算法。

      3.2.3 列表对比算法

      假设现在可以英文字母唯一地标识每一个子节点：
      旧的节点顺序：

      a b c d e f g h i

      现在知道了新旧的顺序，求最小的插入、删除操作（移动可以看成是删除和插入操作的结合）。这个问题抽象出来其实是字符串的最小编码距离问题（Editon 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树上的节点。
      这样，我们就可以通过深度优先遍历两棵树，每层的节点进行对比，记录下每个节点的差异了。完成的diff算法代码可见diff.js。

      3.3 步骤三： 把差异应用到真正的DOM树上

      因为步骤一所构建的JavaScript对象树和render出来真正的DOM树的信息、结构是一样的。所以我们可以对那棵DOM树也进行深度优先的遍历，遍历的时候从步骤二生成的patches对象中赵楚当前遍历的节点差异，然后进行DOM操作。

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

function dsfWalk (node, walker, patches) {
    var currentPatches = patches[walk.index]    //    从patches拿出当前的差异

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

  if (currentPatches) {
      applyPatches(nodes, currentPatches);    //    对当前节点进行DOM操作
  }
}

      applyPatches，根据不同差异对当前节点进行DOM操作：

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

      完成代码可见patch.js。

      4 结语

      Virtual DOM算法主要是实现上面步骤的三个函数：element，diff，patch。然后就可以实际的进行使用：

      //    1.    构建虚拟DOM
var tree =  el('div', {'container'}, [
      el('el', {style: 'color: blue'}, ['simple virtual 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 virtual dom']),
      el('p', ['Hello, vitual-dom']),
      el('ul', [el('li'), el('li')])
]);

//    4.    比较两棵虚拟DOM树的不同
var patches = diff(tree, newTree);

//    5.    在真正的DOM元素上应用变更
patch(root, patches);

      以上是非常粗糙的实践，实际中还需要处理事件的监听等；生成虚拟DOM的时候也可以加入JSX语法。这些事件都做了的话，就可以构造一个简单的ReactJS了。

      5 References

      virtual-dom/diff.js at master · Matt-Esch/virtual-dom · GitHub

      本文源自知乎：如何理解虚拟DOM？