从零开始实现一个React（三）：diff算法

[hujiulong]

前言

在上一篇文章，我们已经实现了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
        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节点下。

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的属性
    const attrs = vnode.attrs;     // 虚拟DOM的属性

    for ( let i = 0 ; i < dom.attributes.length; i++ ) {
        const attr = dom.attributes[ i ];
        old[ attr.name ] = attr.value;
    }

    // 如果原来的属性不在新的属性当中，则将其移除掉（属性值设为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 ) {
                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 {
                    // 注意insertBefore的用法，第一个参数是要插入的节点，第二个参数是已存在的节点
                    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 );

    // ...
   
   // 去掉这部分
   // if ( component.base && component.base.parentNode ) {
   //     component.base.parentNode.replaceChild( base, component.base );
   // }

    // ...
}

完整diff实现看这个文件

渲染

现在我们实现了diff方法，我们尝试渲染上一篇文章中定义的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 (
            <div>
                <h1>count: { this.state.num }</h1>
                <button onClick={ () => this.onClick()}>add</button>
            </div>
        );
    }
}

不使用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

从零开始实现React系列

React是前端最受欢迎的框架之一，解读其源码的文章非常多，但是我想从另一个角度去解读React：从零开始实现一个React，从API层面实现React的大部分功能，在这个过程中去探索为什么有虚拟DOM、diff、为什么setState这样设计等问题。

整个系列大概会有四篇，我每周会更新一到两篇，我会第一时间在github上更新，有问题需要探讨也请在github上回复我~

博客地址: https://github.com/hujiulong/blog
关注点star，订阅点watch

上一篇文章

从零开始实现一个React（二）：组件和生命周期

下一篇文章

从零开始实现一个React（四）：异步的setState

[shihangbo]

等了好几天，终于上新了。。

[GreyHanky]

先评论了再看

[hujiulong]

@shihangbo 哈哈，上周偷懒了没写

[hujiulong]

@GreyHanky 好习惯~

[qinkangwu]

你揭开了diff算法的石榴裙

[xjylyh]

先评论再看

[hujiulong]

@qinkangwu 这个描述有点怪怪的..

[mqyqingfeng]

赞， (๑•̀ㅂ•́)و✧，期待下一篇~

[hujiulong]

@mqyqingfeng 哈哈，被大佬看到了，很早以前就关注你的blog了

[mqyqingfeng]

@hujiulong 最近在准备 React 系列的内容，正好就搜到了这里来，多多交流哈，接下来可能会叨扰你一些问题呀 😀

[hujiulong]

@mqyqingfeng 好，多交流~

[ervinewell]

先订阅了再说！

[xwchris]

diffAttributes中的这一段好像不太对

for ( let name in old ) {

        if ( !( name in attrs ) ) {
            setAttribute( dom, name, undefined );
        }

    }

for...in循环数组循环的是index而不是数组的值，应该用for...of吧，还有name in attrs也是数组的index吧，要找name有没有在attrs是不是应该用attrs.indexOf(name) !== -1呐

[aliwalker]

Pretty comprehensible! I've scanned through it roughly. Does this diffing algorithm resemble to Preact's one?

[hujiulong]

@alieeeeen 是的，很多实现参考了preact和anu

[hujiulong]

@xwchris 谢谢指出，这里确实写错了，我待会修改一下

[huangw1]

跟着楼主重温了下 react，相比 react 的 diff 算法，感觉楼主的 diff 算法有点粗暴啊 😄

[hujiulong]

@huangw1 diff算法本来就不复杂呀，简单才会高效

[p2227]

居然是对比真实的dom和新的vdom，有比较过不同的框架分别是怎么做的么

[hujiulong]

@p2227 大部分react-like框架都是对比两个虚拟DOM，例如inferno和react-lite，它们会对比新旧虚拟DOM树，然后得到一个补丁（patches），然后再将补丁更新到真实dom树上。这篇文章是采用preact的做法，对比真实dom和虚拟dom，并且在对比的过程中直接更新真实dom

[yzbaoo]

对比新旧虚拟dom，得到补丁的dom对象，和拿虚拟dom跟上一次的实际dom对比，直接更新真实dom，哪个效率会高一些

[hujiulong]

@yzbaoo 理论上用虚拟dom和真实dom比较效率更高，占用的内存也更少，但是这个可能并不是性能瓶颈，差别不会很大。对比两个虚拟DOM的好处是不依赖浏览器环境，这样可以用于别的环境，例如native或者node(SSR)。

[Vibing]

文字的组织、排版、代码及注释都很不错，容易阅读和理解，对react又进一步了解，谢谢楼主的分享，期待更多类似文章

[jiunacaikang]

对于在render()函数中map生成的jsx 好像不能渲染

[qianferry]

由于开发环境特殊性，准备在您框架基础上完善一些特性，优化后用于生产环境，您会给哪些建议呢？

[hujiulong]

@442331311 不要用于生产环境，觉得react太大可以用preact

[daweilv]

两个问题请教下：

1. 对比子节点的时候有一个 keyedLen 是拿来干嘛的？没看到定义的地方

if ( child && child !== dom && child !== f ) {
    if ( !f ) {
        dom.appendChild(child);
    } else if ( child === f.nextSibling ) {// 这一步判断是做什么用的？为什么跟 nextSibling 比较？
        removeNode( f );
    } else {
        dom.insertBefore( child, f );// 这一步又是为什么呢
    }
}

[hujiulong]

@ShawnWu20147 这里应该是我写错了，我找时间改一下

[ShawnWu20147]

@hujiulong 又发现一个问题 关于diffChildren的
如果virtual DOM的孩子少于actual DOM的孩子，那么后面应该把actual DOM的孩子给删掉，即

for (let i = vchildren.length; i < domChildren.length; i++) {
        const f = domChildren[i];
        removeNode(f);
    }

想测试这一点很容易
在Counter的render里面根据num奇偶性 render不同的 如

return (
            <div>
                <h1>count</h1>
                <h1>{this.state.num}</h1>
                <button onClick={ () => this.onClick()}>add</button>
                {this.state.num % 2 === 0 && <h2>test</h2>}
            </div>
        );

那么每次点击button后 这个test应该交替出现，而不是一直出现。

[LiuXiao89]

发现一个小问题. 类似于
<ul> <li key={1}>1</li> <li key={2}>2</li> <li key={3}>3</li> <li key={4}>4</li> <li key={5}>5</li> <li key={6}>6</li> <li key={7}>7</li> </ul>
这样的组件, 在每次进行 setState 的 diff 算法过后, 只要是包含 key 的节点, 会不断的复制. 而且会在 html node 中新增一个 key="xxx" 属性.

需要在 setAttribute 中
if ( name in dom /* 增加 || name === 'key' */ ) { dom[ name ] = value || ''; }
增加这一段, 因为 'key'键 本身是不在 dom 中的..

[wangyiman]

diffChildren和diffAttributes的顺序有区别么？个人感觉没区别，不过写代码的话潜意识可能会把diffAttributes放到前面。

[wangyiman]

diffNode方法中的后面一段是不是注释掉比较好呢？

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

毕竟!isSameNodeType(dom, outnode)的情况下，没必要移动下面的children。

[hanruto]

isSameNodeType这个怎么实现的呢

[AnthonyYY]

@hujiulong 可以帮忙解释下这两行代码吗？

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

我知道这两行是为了减小遍历长度。在children数组尾部找到sameNodeType的之后就不会遍历到尾部，在children头部找到sameNodeType之后就不会来遍历头部。那么为什么不采用找到的时候从这个children数组中移除找到的sameNodeType的child。这样在头尾之间找到sameNodeType的时候也能降低遍历长度。

[AnthonyYY]

我也是闲的... 发现这里有个小哥 @soWhiteSoColl 基本抄袭了 @hujiulong 的react博客代码在自己的 dodo-react 项目 https://github.com/soWhiteSoColl/dodo-react 去骗start。😂 我懒得fork它的项目来留证了。

[hujiulong]

isSameNodeType这个怎么实现的呢

isSameNodeType

[hujiulong]

我也是闲的... 发现这里有个小哥 @soWhiteSoColl 基本抄袭了 @hujiulong 的react博客代码在自己的 dodo-react 项目 https://github.com/soWhiteSoColl/dodo-react 去骗start。😂 我懒得fork它的项目来留证了。

我看到过很多了。提醒下这位小哥，任何基于本文的修改、转换都要遵循CC BY-SA 4.0，都要写出原作者的名字和给出链接。我很乐意看到我的文章能启发更多人，但是请遵守规则。

[AnthonyYY]

@hujiulong 有空帮忙解答下吗 #6 (comment)

[hanruto]

我也是闲的... 发现这里有个小哥 @soWhiteSoColl 基本抄袭了 @hujiulong 的react博客代码在自己的 dodo-react 项目 https://github.com/soWhiteSoColl/dodo-react 去骗start。😂 我懒得fork它的项目来留证了。

我看到过很多了。提醒下这位小哥，任何基于本文的修改、转换都要遵循CC BY-SA 4.0，都要写出原作者的名字和给出链接。我很乐意看到我的文章能启发更多人，但是请遵守规则。

好吧，抱歉，我自己看了之后尝试着自己写了一份，借鉴了这个项目比较多，已经删除了我的代码，并且会推荐这个项目和这个博客。

[hujiulong]

@hujiulong 可以帮忙解释下这两行代码吗？

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

我知道这两行是为了减小遍历长度。在children数组尾部找到sameNodeType的之后就不会遍历到尾部，在children头部找到sameNodeType之后就不会来遍历头部。那么为什么不采用找到的时候从这个children数组中移除找到的sameNodeType的child。这样在头尾之间找到sameNodeType的时候也能降低遍历长度。

@AnthonyYY 你是问为什么不直接把它从数组中移除，而是将这一项设为undefined?
数组是内存上一块连续的空间，如果移除数组中某一个元素，那所有它后面的元素都要前移，这个代价是很大的，所以要避免做这种事情。

[AnthonyYY]

@hujiulong 好的 感谢帮忙解惑

[ghost]

@alieeeeen 是的，很多实现参考了preact和anu

preact，10.0.0版本改动非常大

[canxuemianbao]

class App extends React.Component {
    constructor(props) {
        super(props);
        this.state = {open:true, count:0};
        this.change = () => this.setState({open:false, count:1})
    }
    
    render() {
        return (
            <div>
                <h1>Hello,World! {this.state.count}</h1>
                <button onClick={this.change}>改变</button>
                {this.state.open && <div>123</div>}
            </div>
        );
    }
}

@hujiulong ，你好，diff这边貌似不能够删除旧的节点，这边点击了按钮之后 123 依旧会存在？因为我看代码貌似没有处理旧的节点长度大于新节点长度的情况，就拉了master试了一下。

[kissbugs]

赞， (๑•̀ㅂ•́)و✧，期待下一篇~
@mqyqingfeng
老哥，一直(期/等)待您的React系列呢😄

[Gloomysunday28]

// 注意insertBefore的用法，第一个参数是要插入的节点，第二个参数是已存在的节点 dom.insertBefore( child, f );} 这里为什么要插在它前面

2. 为什么优先寻找相同类型的DOM，没找到后也没有下一个寻找方式

[Gloomysunday28]

// 更新DOM const f = domChildren[ i ]; if ( child && child !== dom && child !== f ) { // 如果更新前的对应位置为空，说明此节点是新增的 if ( !f ) { dom.appendChild(child); // 如果更新后的节点和更新前对应位置的下一个节点一样，说明当前位置的节点被移除了 } else if ( child === f.nextSibling ) { removeNode( f ); // 将更新后的节点移动到正确的位置 } else { // 注意insertBefore的用法，第一个参数是要插入的节点，第二个参数是已存在的节点 dom.insertBefore( child, f ); } } 这一块 如果原子节点的数量是大于新子节点的数量, 那么你insertBefore之后 多余的原子节点还是存在的

[zkytech]

diffChildren函数肯定是有问题的，比如[a,b,c,d] => [a,d] 按照你写的删除逻辑根本无法删除b、c

[XYH1996]

受createComponent的影响，无状态子组件直接使用props.XXX并不能成功渲染出后续更新的props，当然使用this.props.XXX则没问题

`
function createComponent( component, props ) {

let inst;

if ( component.prototype && component.prototype.render ) {
    inst = new component( props );
} else {
    inst = new MyComponent( props );
    inst.constructor = component;
     // 此处，无论后续如何更改，根据作用域链，constructor里面的props仍是第一次初始化时候的props
    inst.render = function() {
        return this.constructor( props );
    }
}

return inst;

}

`

[bluesalt168]

大神

[JS-Even-JS]

腾讯课堂有一个视频教程一模一样的https://ke.qq.com/course/452506
也是楼主的吗

[JS-Even-JS]

我也是闲的... 发现这里有个小哥 @soWhiteSoColl 基本抄袭了 @hujiulong 的react博客代码在自己的 dodo-react 项目 https://github.com/soWhiteSoColl/dodo-react 去骗start。😂 我懒得fork它的项目来留证了。

我看到过很多了。提醒下这位小哥，任何基于本文的修改、转换都要遵循CC BY-SA 4.0，都要写出原作者的名字和给出链接。我很乐意看到我的文章能启发更多人，但是请遵守规则。

你应该也是看了腾讯课堂上的视频教程写的吧

[JS-Even-JS]

react源码里面用的应该是 对比的虚拟Dom 然后找到差异 放到队列中
然后 用patch方法循环队列渲染到真实队列上的吧 ？

楼主实现的是 虚拟dom节点与真实dom的对比

我没有记错吧

哈哈，视频教程里是这样写的

[hujiulong]

腾讯课堂有一个视频教程一模一样的https://ke.qq.com/course/452506
也是楼主的吗

这个不是我的，我也没有出过任何视频课程。
顺便说下，可以在我作品的基础上做加工创作，不限制用途，拿去卖课也没问题，但是一定要注明原作者名字并给出文章链接。这种基础原理类的知识还是鼓励免费分享

[weichaozhan]

mark

[weijiababi]

`child = diffNode(child, vchild)

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

我觉得你这一段是有问题的，如果由第一句diffNode返回的child是null，那么就无法走接下去的逻辑，但是按正常逻辑来说，child是null应该是代表需要卸载节点才对吧，我改写了一下

`let resultChild = diffNode(correspondChild, vChild)
let oldDomChild = domChildren[i]

  if (!isSameDom(resultChild, oldDomChild)) {
    // 原先位置为空，直接插入节点
    if (!oldDomChild) {
      out.appendChild(resultChild)
    } else if (!resultChild || resultChild === oldDomChild.nextSibling) {
      removeNode(oldDomChild)
    } else {
      out.replaceChild(resultChild, oldDomChild)
    }
  }`

[leonyh7]

您好，您的邮件我已收到。