1.Virtual Dom 算法 DOM 是慢的,我在控制台把一个简单的 div 属性打印出来见下图:
这仅仅是第一层,真正的DOM元素非常庞大,我们在操作的DOM的时候都是小心翼翼的,轻微的改变可能就会引起浏览器重排,这可是杀死性能的罪魁祸首。
相比于 DOM 对象,原生的 JS 对象处理起来的更快更简单,DOM 树的结构和属性信息我们可以很简单的用 JS 对象标识:
1 2 3 4 5 6 7 8 9 10 const element = { tagName: 'ul' , props: { id : 'list' }, children: [ { tagName : 'li' , props : { class : 'item' }, children : ['Item 1' ] }, { tagName : 'li' , props : { class : 'item' }, children : ['Item 1' ] }, { tagName : 'li' , props : { class : 'item' }, children : ['Item 1' ] } ] }
对应的 HTML:
1 2 3 4 5 <ul id ="list" > <li class ="item" > Item 1li > <li class ="item" > Item 2li > <li class ="item" > Item 3li > ul >
既然可以用 JS 对象可以表示 DOM 树,那么之前说的状态变更->重新渲染整个视图的方式可以稍微修改一下:当状态变更的时候,重新渲染这个 JS 的对象结构,然后用新渲染的对象树去和旧的树进行对比,记录这两棵树差异。记录下来的不同就是我们需要对页面真正的 DOM 操作,然后把它们应用在真正的 DOM 树上,页面就变更了。这样就可以做到:视图的结构确实是整个全新渲染了,但是最后操作 DOM 的时候确实只变更有不同的地方。
简要概括为以下三个步骤:
1. 用 JS 对象结构表示 DOM 树的结构;然后用这个树构建一个真正的 DOM 树,插到文档当中。
2. 当状态变更的时候,重新构造一棵新的对象树。然后用新的树和旧的树进行比较,记录两棵树差异。
3. 把 2 所记录的差异应用到步骤 1 所构建的真正的 DOM 树上,视图就更新了。
Virtual DOM 的本质其实是在 JS 和 DOM 之间做了一个缓存,可以类比 CPU 和硬盘,硬盘这么慢,就在它们之间加了一个缓存。CPU(JS)只操作内存(
Virtual DOM),最后再把变更写入硬盘(DOM)。
### 2.算法实现
上面说了
Virtual Dom 主要有三个步骤,那么下面就简述一下三个步骤的具体实现:
#### 2.1 用 JS 对象模拟 DOM 树
用 JS 表示一个 DOM 节点很简单,只需要记录它的节点类型、属性,还有子节点:
element.js
1 2 3 4 5 6 7 8 9 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) }
那么 2 里面的 DOM 结构我们可以这样表示:
1 2 3 4 5 6 7 const el = require ('./element' )const ul = el('ul' , { id : 'list' }, [ el('li' , { class : 'item' }, ['Item 1' ]), el('li' , { class : 'item' }, ['Item 2' ]), el('li' , { class : 'item' }, ['Item 3' ]) ])
现在 ul 只是一个 JS 对象表示的 DOM 结构,页面上并没有这个结构。我们可以根据这个 ul 构建真正的 ul:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 Element.prototype.render = function ( ) { const el = document .createElement(this .tagName) const props = this .props for (const propName in props) { const propValue = props[propName] el.setAttribute(propName, propValue) } const children = this .children || [] children.forEach(function (child ) { const childEl = child instanceof Element ? child.render() : document .createTextNode(child) el.appendChild(childEl) }) return el }
render 方法会根据 tagName 构建一个真正的 DOM 节点,然后设置这个节点的属性,最后递归地把自己的子节点也构建起来。所以只需要:
1 2 const ulRoot = ul.render()document .body.appendChild(ulRoot)
上面的 ulRoot 是真正的 DOM 节点,把它塞入文档中,这样 body 里面就有了真正的 ul 的 DOM 结构:
1 2 3 4 5 <ul id ="list" > <li class ="item" > Item 1li > <li class ="item" > Item 2li > <li class ="item" > Item 3li > ul >
#### 2.2 比较两棵虚拟 DOM 树的差异
比较两棵 DOM 树的差异是 Virtual DOM 算法最核心的部分,也就是所谓的 Virtual Dom 的 diff 算法,两个树的完全的 diff 算法是一个时间复杂度为 O(n ^ 3)的问题。但是在前端实际操作中很少会跨越层级地移动 DOM 元素。所以 Virtual DOM 只会对同一个层级的元素进行对比:
上面的 div 只会跟同一层级的 div 进行对比,第二层级只会跟第二层级对比,这样的话算法的时间复杂度可以降到 O(n)。
2.2.1 深度优先遍历,记录差异
对新旧两棵树进行一个深度优先的遍历,这样每个节点都会有一个唯一的标记:
在深度优先遍历的时候,每遍历到一个节点就把该节点和新的的树进行对比。如果有差异的话就记录到一个对象里面。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 function diff (oldTree, newTree ) { const index = 0 ; const patches = {}; dfsWalk(oldTree, newTree, index, patches); return patches; } function dfsWalk (oldNode, newNode, index, patches ) { patches[index] = [...]; diffChildren(oldNode.children, newNode.children, index, patches); } function diffChildren (oldChildren, newChildren, index, patches ) { let leftNode = null ; let currentNodeIndex = index; oldChildren.forEach(function (child, i ) { const newChild = newChildren[i]; currentNodeIndex = (leftNode && leftNode.count) ? currentNodeIndex + leftNode.count + 1 : currentNodeIndex + 1 ; dfsWalk(child, newChild, currentNodeIndex, patches); leftNode = child; }) }
例如,上面的 div 和新的 div 有差异,当前的标记是 0,那么:
1 patches[0 ] = [{difference}, {difference}, ...]
那么以此类推,p 就是 patches[1],ul 就是 patches[2]。
2.2.2 差异类型
上面说的节点差异指什么?对 DOM 的操作可能会: 1.替换掉原来的节点。 2.移动、删除、新增子节点。 3.修改了节点的属性。 4.对于文本节点,文本内容可能会改变。
所以定义了几个类型:
1 2 3 4 const REPLACE = 0 const REORDER = 1 const PROPS = 2 const TEXT = 3
针对第一点,判断新旧节点的 tagName 和是不是一样的,如果不一样的说明需要替换掉:
1 2 3 4 5 6 patches[0 ] = [ { type: REPALCE, node: newNode } ]
针对第三点,如果新增了属性 id 为 container:
1 2 3 4 5 6 7 8 patches[0 ] = [ { type: PROPS, props: { id: 'container' } } ]
针对第四点,记录为文本节点:
1 2 3 4 5 6 patches[0 ] = [ { type: TEXT, content: 'NEW TEXT' } ]
第二点的排序: 例如 p, ul, div 的顺序换成了 div, p, ul。这个该怎么对比?如果按照同层级进行顺序对比的话,它们都会被替换掉。如 p 和 div 的 tagName 不同,p 会被 div 所替代。最终,三个节点都会被替换,这样 DOM 开销就非常大。而实际上是不需要替换节点,而只需要经过节点移动就可以达到。这个问题抽象出来其实是字符串的最小编辑距离问题,然后可以这样记录:
1 2 3 4 patches[0 ] = [{ type: REORDER, moves: [{remove or insert}, {remove or insert}, ...] }]
是要注意的是,因为 tagName 是可重复的,不能用这个来进行对比。所以需要给子节点加上唯一标识 key,列表对比的时候,使用 key 进行对比,这样才能复用老的 DOM 树上的节点。
这样,我们就可以通过深度优先遍历两棵树,对每层的节点进行对比,记录下每个节点的差异了。
2.3 把差异应用到真正的 DOM 树上: 因为步骤一所构建的 JS 对象树和 render 出来真正的 DOM 树的信息、结构是一样的。所以我们可以对那棵 DOM 树也进行深度优先的遍历,遍历的时候从步骤二生成的 patches 对象中找出当前遍历的节点差异,然后进行 DOM 操作。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 function patch (node, patches ) { const walker = { index : 0 } dfsWalk(node, walker, patches) } function dfsWalk (node, walker, patches ) { const currentPatches = patches[walker.index] const len = node.childNodes ? node.childNodes.length : 0 for (var i = 0 ; i < len; i++) { const child = node.childNodes[i] walker.index++ dfsWalk(child, walker, patches) } if (currentPatches) { applyPatches(node, currentPatches) } }
applyPatches,根据不同类型的差异对当前节点进行 DOM 操作:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 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) } }) }
5.小结 Virtual Dom 算法主要分为三个步骤:
1.create element
2.diff
3.patch
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 var tree = el('div' , {'id' : 'container' }, [ el('h1' , {style : 'color: blue' }, ['simple virtal dom' ]), el('p' , ['Hello, virtual-dom' ]), el('ul' , [el('li' )]) ]) const root = tree.render();document .body.appendChild(root);const newTree = el('div' , {'id' : 'container' }, [ el('h1' , {style : 'color: red' }, ['simple virtal dom' ]), el('p' , ['Hello, virtual-dom' ]), el('ul' , [el('li' ), el('li' )]) ]); const patches = diff(tree, newTree);patch(root, patches);
6.Vue Virtual Dom VS React Virtual Dom Vue 官网上贴了这样一段话:
尤大也在知乎上给出了答案:
Vue 和 React 的 diff 算法几乎一样,每 state 改变时,Vue 会根据依赖找到最上层的 vdom 并以该组件为根,重新渲染整个 VDom 树而 React 会根据调用 setState 这个方法的这个组件, 以该组件为根重新渲染整个 VDom 树。
当项目比较小的时候,Vue 的依赖追踪可以比 React 做更少的工作,而 React 要达到相同的效果需要在每个组件内用 shouldComponentUpdate 或者是使用 PureComponent 因此相比 Vue 比较繁复。
当项目变得庞大的时候,Vue 的 re-render 相比 React 可以利用 PureComponent 或者 shouldComponentUpdate 方法优化的情况下,将变得重复且多余。