本篇文章给大家带来的内容是关于虚拟dom怎么实现？（代码示例），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。
本文通过对virtual-dom的源码进行阅读和分析，针对virtual dom的结构和相关的diff算法进行讲解，让读者能够对整个数据结构以及相关的diff算法有一定的了解。
virtual dom中diff算法得到的结果如何映射到真实dom中，我们将在下一篇博客揭晓。
本文的主要内容为：
virtual dom的结构virtual dom的diff算法
注：这个virtual dom的实现并不是react virtual dom的源码，而是基于virtual-dom)这个库。两者在原理上类似，并且这个库更加简单容易理解。相较于这个库，react对virtual dom做了进一步的优化和调整，我会在后续的博客中进行分析。
virtual dom的结构
virtualnode
作为virtual dom的元数据结构，virtualnode位于vnode/vnode.js文件中。我们截取一部分声明代码来看下内部结构：
function virtualnode(tagname, properties, children, key, namespace) {    this.tagname = tagname    this.properties = properties || noproperties //props对象，object类型    this.children = children || nochildren //子节点，array类型    this.key = key != null ? string(key) : undefined    this.namespace = (typeof namespace === string) ? namespace : null        ...    this.count = count + descendants    this.haswidgets = haswidgets    this.hasthunks = hasthunks    this.hooks = hooks    this.descendanthooks = descendanthooks}virtualnode.prototype.version = version //virtualnode版本号，isvnode()检测标志virtualnode.prototype.type = virtualnode // virtualnode类型，isvnode()检测标志
上面就是一个virtualnode的完整结构，包含了特定的标签名、属性、子节点等。
vtext
vtext是一个纯文本的节点，对应的是html中的纯文本。因此，这个属性也只有text这一个字段。
function virtualtext(text) {    this.text = string(text)}virtualtext.prototype.version = versionvirtualtext.prototype.type = virtualtext
vpatch
vpatch是表示需要对virtual dom执行的操作记录的数据结构。它位于vnode/vpatch.js文件中。我们来看下里面的具体代码：
// 定义了操作的常量，如props变化，增加节点等virtualpatch.none = 0virtualpatch.vtext = 1virtualpatch.vnode = 2virtualpatch.widget = 3virtualpatch.props = 4virtualpatch.order = 5virtualpatch.insert = 6virtualpatch.remove = 7virtualpatch.thunk = 8module.exports = virtualpatchfunction virtualpatch(type, vnode, patch) {    this.type = number(type) //操作类型    this.vnode = vnode //需要操作的节点    this.patch = patch //需要操作的内容}virtualpatch.prototype.version = versionvirtualpatch.prototype.type = virtualpatch
其中常量定义了对vnode节点的操作。例如：vtext就是增加一个vtext节点，props就是当前节点有props属性改变。
virtual dom的diff算法
了解了虚拟dom中的三个结构，那我们下面来看下virtual dom的diff算法。
这个diff算法是virtual dom中最核心的一个算法。通过输入初始状态a（vnode）和最终状态b（vnode），这个算法可以得到从a到b的变化步骤（vpatch），根据得到的这一连串步骤，我们就可以知道哪些节点需要新增，哪些节点需要删除，哪些节点的属性有了变化。在这个diff算法中，又分成了三部分：
vnode的diff算法props的diff算法vnode children的diff算法
下面，我们就来一个一个介绍这些diff算法。
vnode的diff算法
该算法是针对于单个vnode的比较算法。它是用于两个树中单个节点比较的场景。具体算法如下，如果不想直接阅读源码的同学也可以翻到下面，会有相关代码流程说明供大家参考：
function walk(a, b, patch, index) {    if (a === b) {        return    }    var apply = patch[index]    var applyclear = false    if (isthunk(a) || isthunk(b)) {        thunks(a, b, patch, index)    } else if (b == null) {        // if a is a widget we will add a remove patch for it        // otherwise any child widgets/hooks must be destroyed.        // this prevents adding two remove patches for a widget.        if (!iswidget(a)) {            clearstate(a, patch, index)            apply = patch[index]        }        apply = appendpatch(apply, new vpatch(vpatch.remove, a, b))    } else if (isvnode(b)) {        if (isvnode(a)) {            if (a.tagname === b.tagname &&                a.namespace === b.namespace &&                a.key === b.key) {                var propspatch = diffprops(a.properties, b.properties)                if (propspatch) {                    apply = appendpatch(apply,                        new vpatch(vpatch.props, a, propspatch))                }                apply = diffchildren(a, b, patch, apply, index)            } else {                apply = appendpatch(apply, new vpatch(vpatch.vnode, a, b))                applyclear = true            }        } else {            apply = appendpatch(apply, new vpatch(vpatch.vnode, a, b))            applyclear = true        }    } else if (isvtext(b)) {        if (!isvtext(a)) {            apply = appendpatch(apply, new vpatch(vpatch.vtext, a, b))            applyclear = true        } else if (a.text !== b.text) {            apply = appendpatch(apply, new vpatch(vpatch.vtext, a, b))        }    } else if (iswidget(b)) {        if (!iswidget(a)) {            applyclear = true        }        apply = appendpatch(apply, new vpatch(vpatch.widget, a, b))    }    if (apply) {        patch[index] = apply    }    if (applyclear) {        clearstate(a, patch, index)    }}
代码具体逻辑如下：
如果a和b这两个vnode全等，则认为没有修改，直接返回。
如果其中有一个是thunk，则使用thunk的比较方法thunks。
如果a是widget且b为空，那么通过递归将a和它的子节点的remove操作添加到patch中。
如果b是vnode的话，
如果a也是vnode，那么比较tagname、namespace、key，如果相同则比较两个vnode的props（用下面提到的diffprops算法），同时比较两个vnode的children（用下面提到的diffchildren算法）；如果不同则直接将b节点的insert操作添加到patch中，同时将标记位置为true。
如果a不是vnode，那么直接将b节点的insert操作添加到patch中，同时将标记位置为true。
如果b是vtext的话，看a的类型是否为vtext，如果不是，则将vtext操作添加到patch中，并且将标志位设置为true；如果是且文本内容不同，则将vtext操作添加到patch中。
如果b是widget的话，看a的类型是否为widget，如果是，将标志位设置为true。不论a类型为什么，都将widget操作添加到patch中。
检查标志位，如果标识为为true，那么通过递归将a和它的子节点的remove操作添加到patch中。
这就是单个vnode节点的diff算法全过程。这个算法是整个diff算法的入口，两棵树的比较就是从这个算法开始的。
prpps的diff算法看完了单个vnode节点的diff算法，我们来看下上面提到的diffprops算法。
该算法是针对于两个比较的vnode节点的props比较算法。它是用于两个场景中key值和标签名都相同的情况。具体算法如下，如果不想直接阅读源码的同学也可以翻到下面，会有相关代码流程说明供大家参考：
function diffprops(a, b) {    var diff    for (var akey in a) {        if (!(akey in b)) {            diff = diff || {}            diff[akey] = undefined        }        var avalue = a[akey]        var bvalue = b[akey]        if (avalue === bvalue) {            continue        } else if (isobject(avalue) && isobject(bvalue)) {            if (getprototype(bvalue) !== getprototype(avalue)) {                diff = diff || {}                diff[akey] = bvalue            } else if (ishook(bvalue)) {                 diff = diff || {}                 diff[akey] = bvalue            } else {                var objectdiff = diffprops(avalue, bvalue)                if (objectdiff) {                    diff = diff || {}                    diff[akey] = objectdiff                }            }        } else {            diff = diff || {}            diff[akey] = bvalue        }    }    for (var bkey in b) {        if (!(bkey in a)) {            diff = diff || {}            diff[bkey] = b[bkey]        }    }    return diff}
代码具体逻辑如下：
遍历a对象。
当key值不存在于b，则将此值存储下来，value赋值为undefined。当此key对应的两个属性都相同时，继续终止此次循环，进行下次循环。当key值对应的value不同且key值对应的两个value都是对象时，判断prototype值，如果不同则记录key对应的b对象的值；如果b对应的value是hook的话，记录b的值。上面条件判断都不同且都是对象时，则继续比较key值对应的两个对象（递归）。当有一个不是对象时，直接将b对应的value进行记录。遍历b对象，将所有a对象中不存在的key值对应的对象都记录下来。整个算法的大致流程如下，因为比较简单，就不画相关流程图了。如果逻辑有些绕的话，可以配合代码食用，效果更佳。
vnode children的diff算法下面让我们来看下最后一个算法，就是关于两个vnode节点的children属性的diffchildren算法。这个个diff算法分为两个部分，第一部分是将变化后的结果b的children进行顺序调整的算法，保证能够快速的和a的children进行比较；第二部分就是将a的children与重新排序调整后的b的children进行比较，得到相关的patch。下面，让我们一个一个算法来看。
reorder算法该算法的作用是将b节点的children数组进行调整重新排序，让a和b两个children之间的diff算法更加节约时间。具体代码如下：
function reorder(achildren, bchildren) {    // o(m) time, o(m) memory    var bchildindex = keyindex(bchildren)    var bkeys = bchildindex.keys  // have key prop，object    var bfree = bchildindex.free  //don't have key prop，array    // all children of b don't have key    if (bfree.length === bchildren.length) {        return {            children: bchildren,            moves: null        }    }    // o(n) time, o(n) memory    var achildindex = keyindex(achildren)    var akeys = achildindex.keys    var afree = achildindex.free    // all children of a don't have key    if (afree.length === achildren.length) {        return {            children: bchildren,            moves: null        }    }    // o(max(n, m)) memory    var newchildren = []    var freeindex = 0    var freecount = bfree.length    var deleteditems = 0    // iterate through a and match a node in b    // o(n) time,    for (var i = 0 ; i < achildren.length; i++) { var aitem = achildren[i] var itemindex if (aitem.key) { if (bkeys.hasownproperty(aitem.key)) { // match up the old keys itemindex = bkeys[aitem.key] newchildren.push(bchildren[itemindex]) } else { // remove old keyed items itemindex = i - deleteditems++ newchildren.push(null) } } else { // match the item in a with the next free item in b if (freeindex < freecount) { itemindex = bfree[freeindex++] newchildren.push(bchildren[itemindex]) } else { // there are no free items in b to match with // the free items in a, so the extra free nodes // are deleted. itemindex = i - deleteditems++ newchildren.push(null) } } } var lastfreeindex = freeindex >= bfree.length ?        bchildren.length :        bfree[freeindex]    // iterate through b and append any new keys    // o(m) time    for (var j = 0; j < bchildren.length; j++) { var newitem = bchildren[j] if (newitem.key) { if (!akeys.hasownproperty(newitem.key)) { // add any new keyed items // we are adding new items to the end and then sorting them // in place. in future we should insert new items in place. newchildren.push(newitem) } } else if (j >= lastfreeindex) {            // add any leftover non-keyed items            newchildren.push(newitem)        }    }    var simulate = newchildren.slice()    var simulateindex = 0    var removes = []    var inserts = []    var simulateitem    for (var k = 0; k < bchildren.length;) { var wanteditem = bchildren[k] simulateitem = simulate[simulateindex] // remove items while (simulateitem === null && simulate.length) { removes.push(remove(simulate, simulateindex, null)) simulateitem = simulate[simulateindex] } if (!simulateitem || simulateitem.key !== wanteditem.key) { // if we need a key in this position... if (wanteditem.key) { if (simulateitem && simulateitem.key) { // if an insert doesn't put this key in place, it needs to move if (bkeys[simulateitem.key] !== k + 1) { removes.push(remove(simulate, simulateindex, simulateitem.key)) simulateitem = simulate[simulateindex] // if the remove didn't put the wanted item in place, we need to insert it if (!simulateitem || simulateitem.key !== wanteditem.key) { inserts.push({key: wanteditem.key, to: k}) } // items are matching, so skip ahead else { simulateindex++ } } else { inserts.push({key: wanteditem.key, to: k}) } } else { inserts.push({key: wanteditem.key, to: k}) } k++ } // a key in simulate has no matching wanted key, remove it else if (simulateitem && simulateitem.key) { removes.push(remove(simulate, simulateindex, simulateitem.key)) } } else { simulateindex++ k++ } } // remove all the remaining nodes from simulate while(simulateindex < simulate.length) { simulateitem = simulate[simulateindex] removes.push(remove(simulate, simulateindex, simulateitem && simulateitem.key)) } // if the only moves we have are deletes then we can just // let the delete patch remove these items. if (removes.length === deleteditems && !inserts.length) { return { children: newchildren, moves: null } } return { children: newchildren, moves: { removes: removes, inserts: inserts } }}
下面，我们来简单介绍下这个排序算法：
检查a和b中的children是否拥有key字段，如果没有，直接返回b的children数组。如果存在，初始化一个数组newchildren，遍历a的children元素。
如果achildren存在key值，则去bchildren中找对应key值，如果bchildren存在则放入新数组中，不存在则放入一个null值。如果achildren不存在key值，则从bchildren中不存在key值的第一个元素开始取，放入新数组中。遍历bchildren，将所有achildren中没有的key值对应的value或者没有key，并且没有放入新数组的子节点放入新数组中。将bchildren和新数组逐个比较，得到从新数组转换到bchildren数组的move操作patch（即remove+insert）。返回新数组和move操作列表。通过上面这个排序算法，我们可以得到一个新的b的children数组。在使用这个数组来进行比较厚，我们可以将两个children数组之间比较的时间复杂度从o(n^2)转换成o(n)。具体的方法和效果我们可以看下面的diffchildren算法。
diffchildren算法function diffchildren(a, b, patch, apply, index) { var achildren = a.children var orderedset = reorder(achildren, b.children) var bchildren = orderedset.children var alen = achildren.length var blen = bchildren.length var len = alen > blen ? alen : blen    for (var i = 0; i < len; i++) {        var leftnode = achildren[i]        var rightnode = bchildren[i]        index += 1        if (!leftnode) {            if (rightnode) {                // excess nodes in b need to be added                apply = appendpatch(apply,                    new vpatch(vpatch.insert, null, rightnode))            }        } else {            walk(leftnode, rightnode, patch, index)        }        if (isvnode(leftnode) && leftnode.count) {            index += leftnode.count        }    }    if (orderedset.moves) {        // reorder nodes last        apply = appendpatch(apply, new vpatch(            vpatch.order,            a,            orderedset.moves        ))    }    return apply}
通过上面的重新排序算法整理了以后，两个children比较就只需在相同下标的情况下比较了，即achildren的第n个元素和bchildren的第n个元素进行比较。然后较长的那个元素做insert操作（bchildren）或者remove操作（achildren）即可。最后，我们将move操作再增加到patch中，就能够抵消我们在reorder时对整个数组的操作。这样只需要一次便利就得到了最终的patch值。
总结
整个virtual dom的diff算法设计的非常精巧，通过三个不同的分部算法来实现了vnode、props和children的diff算法，将整个virtual dom的的diff操作分成了三类。同时三个算法又互相递归调用，对两个virtual dom数做了一次（伪）深度优先的递归比较。
以上就是虚拟dom怎么实现？（代码示例）的详细内容。