React diff算法的实现示例

React diff算法的实现示例

前言

在上一篇文章，我们已经实现了React的组件功能，从功能的角度来说已经实现了React的核心功能了。

但是我们的实现方式有很大的问题：每次更新都重新渲染整个应用或者整个组件，DOM操作十分昂贵，这样性能损耗非常大。

为了减少DOM更新，我们需要找渲染前后真正变化的部分，只更新这一部分DOM。而对比变化，找出需要更新部分的算法我们称之为diff算法。

对比策略

在前面两篇文章后，我们实现了一个render方法，它能将虚拟DOM渲染成真正的DOM，我们现在就需要改进它，让它不要再傻乎乎地重新渲染整个DOM树，而是找出真正变化的部分。

这部分很多类React框架实现方式都不太一样，有的框架会选择保存上次渲染的虚拟DOM，然后对比虚拟DOM前后的变化，得到一系列更新的数据，然后再将这些更新应用到真正的DOM上。

但也有一些框架会选择直接对比虚拟DOM和真实DOM，这样就不需要额外保存上一次渲染的虚拟DOM，并且能够一边对比一边更新，这也是我们选择的方式。

不管是DOM还是虚拟DOM，它们的结构都是一棵树，完全对比两棵树变化的算法时间复杂度是O(n^3)，但是考虑到我们很少会跨层级移动DOM，所以我们只需要对比同一层级的变化。

只需要对比同一颜色框内的节点

总而言之，我们的diff算法有两个原则：

对比当前真实的DOM和虚拟DOM，在对比过程中直接更新真实DOM

只对比同一层级的变化实现

我们需要实现一个diff方法，它的作用是对比真实DOM和虚拟DOM，最后返回更新后的DOM

/**

* @param {HTMLElement} dom 真实DOM

* @param {vnode} vnode 虚拟DOM

* @returns {HTMLElement} 更新后的DOM

*/

function diff( dom, vnode ) {

// ...

}

接下来就要实现这个方法。

在这之前先来回忆一下我们虚拟DOM的结构:

虚拟DOM的结构可以分为三种，分别表示文本、原生DOM节点以及组件。

// 原生DOM节点的vnode

{

tag: 'div',

attrs: {

className: 'container'

},

children: []

}

// 文本节点的vnode

"hello,world"

// 组件的vnode

{

tag: ComponentConstrucotr,

attrs: {

className: 'container'

},

children: []

}

对比文本节点

首先考虑最简单的文本节点，如果当前的DOM就是文本节点，则直接更新内容，否则就新建一个文本节点，并移除掉原来的DOM。

// diff text node

if ( typeof vnode === 'string' ) {

// 如果当前的DOM就是文本节点，则直接更新内容

if ( dom && dom.nodeType === 3 ) { // nodeType: https://developer.mozilla.org/zh-CN/docs/Web/API/Node/nodeType

hUYgfxrbhI if ( dom.textContent !== vnode ) {

dom.textContent = vnode;

}

// 如果DOM不是文本节点，则新建一个文本节点DOM，并移除掉原来的

} else {

out = document.createTextNode( vnode );

if ( dom && dom.parentNode ) {

dom.parentNode.replaceChild( out, dom );

}

}

return out;

}

文本节点十分简单，它没有属性，也没有子元素，所以这一步结束后就可以直接返回结果了。

对比非文本DOM节点

如果vnode表示的是一个非文本的DOM节点，那就要分几种情况了：

如果真实DOM和虚拟DOM的类型不同，例如当前真实DOM是一个div，而vnode的tag的值是'button'，那么原来的div就没有利用价值了，直接新建一个button元素，并将div的所有子节点移到button下，然后用replaceChild方法将div替换成button。

if ( !dom || dom.nodeName.toLowerCase() !== vnode.tag.toLowerCase() ) {

out = document.createElement( vnode.tag );

if ( dom ) {

[ ...dom.childNodes ].map( out.appendChild ); // 将原来的子节点移到新节点下

if ( dom.parentNode ) {

dom.parentNode.replaceChild( out, dom ); // 移除掉原来的DOM对象

}

}

}

如果真实DOM和虚拟DOM是同一类型的，那我们暂时不需要做别的，只需要等待后面对比属性和对比子节点。

对比属性

实际上diff算法不仅仅是找出节点类型的变化，它还要找出来节点的属性以及事件监听的变化。我们将对比属性单独拿出来作为一个方法：

function diffAttributes( dom, vnode ) {

const old = dom.attributes; // 当前DOM的属性

const attrs = vnode.attrs; // 虚拟DOM的属性

// 如果原来的属性不在新的属性当中，则将其移除掉（属性值设为undefined）

for ( let name in old ) {

if ( !( name in attrs ) ) {

setAttribute( dom, name, undefined );

}

}

// 更新新的属性值

for ( let name in attrs ) {

if ( old[ name ] !== attrs[ name ] ) {

setAttribute( dom, name, attrs[ name ] );

}

}

}

setAttribute方法的实现参见第一篇文章

对比子节点

节点本身对比完成了，接下来就是对比它的子节点。

这里会面临一个问题，前面我们实现的不同diff方法，都是明确知道哪一个真实DOM和虚拟DOM对比，但是子节点是一个数组，它们可能改变了顺序，或者数量有所变化，我们很难确定要和虚拟DOM对比的是哪一个。

为了简化逻辑，我们可以让用户提供一些线索：给节点设一个key值，重新渲染时对比key值相同的节点。

// diff方法

if ( vnode.children && vnode.children.length > 0 || ( out.childNodes && out.childNodes.length > 0 ) ) {

diffChildren( out, vnode.children );

}

function diffChildren( dom, vchildren ) {

const domChildren = dom.childNodes;

const children = [];

const keyed = {};

// 将有key的节点和没有key的节点分开

if ( domChildren.length > 0 ) {

for ( let i = 0; i < domChildren.length; i++ ) {

const child = domChildren[ i ];

const key = child.key;

if ( key ) {

keyedLen++;

keyed[ key ] = child;

} else {

children.push( child );

}

}

}

if ( vchildren && vchildren.length > 0 ) {

let min = 0;

let childrenLen = children.length;

for ( let i = 0; i < vchildren.length; i++ ) {

const vchild = vchildren[ i ];

const key = vchild.key;

let child;

// 如果有key，找到对应key值的节点

if ( key ) {

if ( keyed[ key ] ) {

child = keyed[ key ];

keyed[ key ] = undefined;

}

// 如果没有key，则优先找类型相同的节点

} else if ( min < childrenLen ) {

for ( let j = min; j < childrenLen; j++ ) {

let c = children[ j ];

if ( c && isSameNodeType( c, vchild ) ) {

child = c;

children[ j ] = undefined;

if ( j === childrenLen - 1 ) childrenLen--;

if ( j === min ) min++;

break;

}

}

}

// 对比

child = diff( child, vchild );

// 更新DOM

const f = domChildren[ i ];

if ( child && child !== dom && child !== f ) {

if ( !f ) {

dom.appendChild(child);

} else if ( child === f.nextSibling ) {

removeNode( f );

} else {

dom.insertBefore( child, f );

}

}

}

}

}

对比组件

如果vnode是一个组件，我们也单独拿出来作为一个方法:

function diffComponent( dom, vnode ) {

let c = dom && dom._component;

let oldDom = dom;

// 如果组件类型没有变化，则重新set props

if ( c && c.constructor === vnode.tag ) {

setComponentProps( c, vnode.attrs );

dom = c.base;

// 如果组件类型变化，则移除掉原来组件，并渲染新的组件

} else {

if ( c ) {

unmountComponent( c );

oldDom = null;

}

c = createComponent( vnode.tag, vnode.attrs );

setComponentProps( c, vnode.attrs );

dom = c.base;

if ( oldDom && dom !== oldDom ) {

oldDom._component = null;

removeNode( oldDom );

}

}

return dom;

}

下面是相关的工具方法的实现，和上一篇文章的实现相比，只需要修改renderComponent方法其中的一行。

function renderComponent( component ) {

// ...

// base = base = _render( renderer ); // 将_render改成diff

base = diff( component.base, renderer );

// ...

}

完整diff实现看这个文件

渲染

现在我们实现了diff方法，我们尝试渲染上一篇文章中定义

http://

的Counter组件，来感受一下有无diff方法的不同。

class Counter extends React.Component {

constructor( props ) {

super( props );

this.state = {

num: 1

}

}

onClick() {

this.setState( { num: this.state.num + 1 } );

}

render() {

return (

this.onClick()}>add

);

}

}

不使用diff

使用上一篇文章的实现，从chrome的调试工具中可以看到，闪烁的部分是每次更新的部分，每次点击按钮，都会重新渲染整个组件。

使用diff

而实现了diff方法后，每次点击按钮，都只会重新渲染变化的部分。

后话

在这篇文章中我们实现了diff算法，通过它做到了每次只更新需要更新的部分，极大地减少了DOM操作。React实现远比这个要复杂，特别是在React 16之后还引入了Fiber架构，但是主要的思想是一致的。

实现diff算法可以说性能有了很大的提升，但是在别的地方仍然后很多改进的空间：每次调用setState后会立即调用renderComponent重新渲染组件，但现实情况是，我们可能会在极短的时间内多次调用setState。

假设我们在上文的Counter组件中写出了这种代码

onClick() {

for ( let i = 0; i < 100; i++ ) {

this.setState( { num: this.state.num + 1 } );

}

}

那以目前的实现，每次点击都会渲染100次组件，对性能肯定有很大的影响。

下一篇文章我们就要来改进setState方法

这篇文章的代码：https://github.com/hujiulong/simple-react/tree/chapter-3

以

http://

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。