解析vue2.0的diff算法 #2

aooy · 2017-03-19T15:49:08Z

作者：杨敬卓

转载请注明出处

前言

vue2.0加入了virtual dom，有向react靠拢的意思。vue的diff位于patch.js文件中，我的一个小框架aoy也同样使用此算法，该算法来源于snabbdom，复杂度为O(n)。
了解diff过程可以让我们更高效的使用框架。
本文力求以图文并茂的方式来讲明这个diff的过程。

virtual dom

如果不了解virtual dom，要理解diff的过程是比较困难的。虚拟dom对应的是真实dom，使用document.CreateElement 和 document.CreateTextNode创建的就是真实节点。

我们可以做个试验。打印出一个空元素的第一层属性，可以看到标准让元素实现的东西太多了。如果每次都重新生成新的元素，对性能是巨大的浪费。

var mydiv = document.createElement('div');
for(var k in mydiv ){
  console.log(k)
}

virtual dom就是解决这个问题的一个思路，到底什么是virtual dom呢？通俗易懂的来说就是用一个简单的对象去代替复杂的dom对象。
举个简单的例子，我们在body里插入一个class为a的div。

var mydiv = document.createElement('div');
mydiv.className = 'a';
document.body.appendChild(mydiv);

对于这个div我们可以用一个简单的对象mydivVirtual代表它，它存储了对应dom的一些重要参数，在改变dom之前，会先比较相应虚拟dom的数据，如果需要改变，才会将改变应用到真实dom上。

//伪代码
var mydivVirtual = { 
  tagName: 'DIV',
  className: 'a'
};
var newmydivVirtual = {
   tagName: 'DIV',
   className: 'b'
}
if(mydivVirtual.tagName !== newmydivVirtual.tagName || mydivVirtual.className  !== newmydivVirtual.className){
   change(mydiv)
}

// 会执行相应的修改 mydiv.className = 'b';
//最后  <div class='b'></div>

读到这里就会产生一个疑问，为什么不直接修改dom而需要加一层virtual dom呢？

很多时候手工优化dom确实会比virtual dom效率高，对于比较简单的dom结构用手工优化没有问题，但当页面结构很庞大，结构很复杂时，手工优化会花去大量时间，而且可维护性也不高，不能保证每个人都有手工优化的能力。至此，virtual dom的解决方案应运而生，virtual dom很多时候都不是最优的操作，但它具有普适性，在效率、可维护性之间达平衡。

virtual dom 另一个重大意义就是提供一个中间层，js去写ui，ios安卓之类的负责渲染，就像reactNative一样。

分析diff

一篇相当经典的文章React’s diff algorithm中的图，react的diff其实和vue的diff大同小异。所以这张图能很好的解释过程。比较只会在同层级进行, 不会跨层级比较。

举个形象的例子。

<!-- 之前 -->
<div>           <!-- 层级1 -->
  <p>            <!-- 层级2 -->
    <b> aoy </b>   <!-- 层级3 -->   
    <span>diff</Span>
  </P> 
</div>

<!-- 之后 -->
<div>            <!-- 层级1 -->
  <p>             <!-- 层级2 -->
      <b> aoy </b>        <!-- 层级3 -->
  </p>
  <span>diff</Span>
</div>

我们可能期望将直接移动到的后边，这是最优的操作。但是实际的diff操作是移除里的在创建一个新的插到的后边。
因为新加的在层级2，旧的在层级3，属于不同层级的比较。

源码分析

文中的代码位于aoy-diff中，已经精简了很多代码，留下最核心的部分。

diff的过程就是调用patch函数，就像打补丁一样修改真实dom。

function patch (oldVnode, vnode) {
	if (sameVnode(oldVnode, vnode)) {
		patchVnode(oldVnode, vnode)
	} else {
		const oEl = oldVnode.el
		let parentEle = api.parentNode(oEl)
		createEle(vnode)
		if (parentEle !== null) {
			api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl))
			api.removeChild(parentEle, oldVnode.el)
			oldVnode = null
		}
	}
	return vnode
}

patch函数有两个参数，vnode和oldVnode，也就是新旧两个虚拟节点。在这之前，我们先了解完整的vnode都有什么属性，举个一个简单的例子:

// body下的 <div id="v" class="classA"><div> 对应的 oldVnode 就是

{
  el:  div  //对真实的节点的引用，本例中就是document.querySelector('#id.classA')
  tagName: 'DIV',   //节点的标签
  sel: 'div#v.classA'  //节点的选择器
  data: null,       // 一个存储节点属性的对象，对应节点的el[prop]属性，例如onclick , style
  children: [], //存储子节点的数组，每个子节点也是vnode结构
  text: null,    //如果是文本节点，对应文本节点的textContent，否则为null
}

需要注意的是，el属性引用的是此 virtual dom对应的真实dom，patch的vnode参数的el最初是null，因为patch之前它还没有对应的真实dom。

来到patch的第一部分，

if (sameVnode(oldVnode, vnode)) {
	patchVnode(oldVnode, vnode)
}

sameVnode函数就是看这两个节点是否值得比较，代码相当简单：

function sameVnode(oldVnode, vnode){
	return vnode.key === oldVnode.key && vnode.sel === oldVnode.sel
}

两个vnode的key和sel相同才去比较它们，比如p和span，div.classA和div.classB都被认为是不同结构而不去比较它们。

如果值得比较会执行patchVnode(oldVnode, vnode)，稍后会详细讲patchVnode函数。

当节点不值得比较，进入else中

else {
		const oEl = oldVnode.el
		let parentEle = api.parentNode(oEl)
		createEle(vnode)
		if (parentEle !== null) {
			api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl))
			api.removeChild(parentEle, oldVnode.el)
			oldVnode = null
		}
	}

过程如下：

取得oldvnode.el的父节点，parentEle是真实dom
createEle(vnode)会为vnode创建它的真实dom，令vnode.el =真实dom
parentEle将新的dom插入，移除旧的dom
当不值得比较时，新节点直接把老节点整个替换了

最后

return vnode

patch最后会返回vnode，vnode和进入patch之前的不同在哪？
没错，就是vnode.el，唯一的改变就是之前vnode.el = null, 而现在它引用的是对应的真实dom。

var oldVnode = patch (oldVnode, vnode)

至此完成一个patch过程。

patchVnode

两个节点值得比较时，会调用patchVnode函数

patchVnode (oldVnode, vnode) {
    const el = vnode.el = oldVnode.el
    let i, oldCh = oldVnode.children, ch = vnode.children
    if (oldVnode === vnode) return
    if (oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text) {
        api.setTextContent(el, vnode.text)
    }else {
        updateEle(el, vnode, oldVnode)
    	if (oldCh && ch && oldCh !== ch) {
	    	updateChildren(el, oldCh, ch)
	    }else if (ch){
	    	createEle(vnode) //create el's children dom
	    }else if (oldCh){
	    	api.removeChildren(el)
	    }
    }
}

const el = vnode.el = oldVnode.el 这是很重要的一步，让vnode.el引用到现在的真实dom，当el修改时，vnode.el会同步变化。

节点的比较有5种情况

if (oldVnode === vnode)，他们的引用一致，可以认为没有变化。
if(oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text)，文本节点的比较，需要修改，则会调用Node.textContent = vnode.text。
if( oldCh && ch && oldCh !== ch ), 两个节点都有子节点，而且它们不一样，这样我们会调用updateChildren函数比较子节点，这是diff的核心，后边会讲到。
else if (ch)，只有新的节点有子节点，调用createEle(vnode)，vnode.el已经引用了老的dom节点，createEle函数会在老dom节点上添加子节点。
else if (oldCh)，新节点没有子节点，老节点有子节点，直接删除老节点。

updateChildren

updateChildren (parentElm, oldCh, newCh) {
    let oldStartIdx = 0, newStartIdx = 0
    let oldEndIdx = oldCh.length - 1
    let oldStartVnode = oldCh[0]
    let oldEndVnode = oldCh[oldEndIdx]
    let newEndIdx = newCh.length - 1
    let newStartVnode = newCh[0]
    let newEndVnode = newCh[newEndIdx]
    let oldKeyToIdx
    let idxInOld
    let elmToMove
    let before
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
            if (oldStartVnode == null) {   //对于vnode.key的比较，会把oldVnode = null
                oldStartVnode = oldCh[++oldStartIdx] 
            }else if (oldEndVnode == null) {
                oldEndVnode = oldCh[--oldEndIdx]
            }else if (newStartVnode == null) {
                newStartVnode = newCh[++newStartIdx]
            }else if (newEndVnode == null) {
                newEndVnode = newCh[--newEndIdx]
            }else if (sameVnode(oldStartVnode, newStartVnode)) {
                patchVnode(oldStartVnode, newStartVnode)
                oldStartVnode = oldCh[++oldStartIdx]
                newStartVnode = newCh[++newStartIdx]
            }else if (sameVnode(oldEndVnode, newEndVnode)) {
                patchVnode(oldEndVnode, newEndVnode)
                oldEndVnode = oldCh[--oldEndIdx]
                newEndVnode = newCh[--newEndIdx]
            }else if (sameVnode(oldStartVnode, newEndVnode)) {
                patchVnode(oldStartVnode, newEndVnode)
                api.insertBefore(parentElm, oldStartVnode.el, api.nextSibling(oldEndVnode.el))
                oldStartVnode = oldCh[++oldStartIdx]
                newEndVnode = newCh[--newEndIdx]
            }else if (sameVnode(oldEndVnode, newStartVnode)) {
                patchVnode(oldEndVnode, newStartVnode)
                api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)
                oldEndVnode = oldCh[--oldEndIdx]
                newStartVnode = newCh[++newStartIdx]
            }else {
               // 使用key时的比较
                if (oldKeyToIdx === undefined) {
                    oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) // 有key生成index表
                }
                idxInOld = oldKeyToIdx[newStartVnode.key]
                if (!idxInOld) {
                    api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
                    newStartVnode = newCh[++newStartIdx]
                }
                else {
                    elmToMove = oldCh[idxInOld]
                    if (elmToMove.sel !== newStartVnode.sel) {
                        api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
                    }else {
                        patchVnode(elmToMove, newStartVnode)
                        oldCh[idxInOld] = null
                        api.insertBefore(parentElm, elmToMove.el, oldStartVnode.el)
                    }
                    newStartVnode = newCh[++newStartIdx]
                }
            }
        }
        if (oldStartIdx > oldEndIdx) {
            before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el
            addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx)
        }else if (newStartIdx > newEndIdx) {
            removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
        }
}

代码很密集，为了形象的描述这个过程，可以看看这张图。

过程可以概括为：oldCh和newCh各有两个头尾的变量StartIdx和EndIdx，它们的2个变量相互比较，一共有4种比较方式。如果4种比较都没匹配，如果设置了key，就会用key进行比较，在比较的过程中，变量会往中间靠，一旦StartIdx>EndIdx表明oldCh和newCh至少有一个已经遍历完了，就会结束比较。

具体的diff分析

设置key和不设置key的区别：
不设key，newCh和oldCh只会进行头尾两端的相互比较，设key后，除了头尾两端的比较外，还会从用key生成的对象oldKeyToIdx中查找匹配的节点，所以为节点设置key可以更高效的利用dom。

diff的遍历过程中，只要是对dom进行的操作都调用api.insertBefore，api.insertBefore只是原生insertBefore的简单封装。
比较分为两种，一种是有vnode.key的，一种是没有的。但这两种比较对真实dom的操作是一致的。

对于与sameVnode(oldStartVnode, newStartVnode)和sameVnode(oldEndVnode,newEndVnode)为true的情况，不需要对dom进行移动。

总结遍历过程，有3种dom操作：

当oldStartVnode，newEndVnode值得比较，说明oldStartVnode.el跑到oldEndVnode.el的后边了。

图中假设startIdx遍历到1。

当oldEndVnode，newStartVnode值得比较，说明 oldEndVnode.el跑到了newStartVnode.el的前边。（这里笔误，应该是“oldEndVnode.el跑到了oldStartVnode.el的前边”，准确的说应该是oldEndVnode.el需要移动到oldStartVnode.el的前边”）

newCh中的节点oldCh里没有，将新节点插入到oldStartVnode.el的前边。

在结束时，分为两种情况：

oldStartIdx > oldEndIdx，可以认为oldCh先遍历完。当然也有可能newCh此时也正好完成了遍历，统一都归为此类。此时newStartIdx和newEndIdx之间的vnode是新增的，调用addVnodes，把他们全部插进before的后边，before很多时候是为null的。addVnodes调用的是insertBefore操作dom节点，我们看看insertBefore的文档：parentElement.insertBefore(newElement, referenceElement)
如果referenceElement为null则newElement将被插入到子节点的末尾。如果newElement已经在DOM树中，newElement首先会从DOM树中移除。所以before为null，newElement将被插入到子节点的末尾。

newStartIdx > newEndIdx，可以认为newCh先遍历完。此时oldStartIdx和oldEndIdx之间的vnode在新的子节点里已经不存在了，调用removeVnodes将它们从dom里删除。

下面举个例子，画出diff完整的过程，每一步dom的变化都用不同颜色的线标出。

a,b,c,d,e假设是4个不同的元素，我们没有设置key时，b没有复用，而是直接创建新的，删除旧的。

当我们给4个元素加上唯一key时，b得到了的复用。

这个例子如果我们使用手工优化，只需要3步就可以达到。

总结

尽量不要跨层级的修改dom
设置key可以最大化的利用节点
diff的效率并不是每种情况下都是最优的

The text was updated successfully, but these errors were encountered:

userand · 2017-03-23T09:57:43Z

@

fengmiaosen · 2017-03-24T09:54:10Z

mark

cshenger · 2017-03-24T10:38:26Z

配图好评，看代码绝对会晕的

ascoders · 2017-03-24T11:29:50Z

和 react 的几乎一样

aooy · 2017-03-24T13:59:50Z

@ascoders 是的

ghost · 2017-03-25T08:17:15Z

React 的 diff 算法

mofengfly · 2017-04-09T10:26:37Z

赞，mark

iterry · 2017-04-12T06:30:36Z

详细，点赞

wangweida · 2017-04-26T16:01:59Z

写的很好，点个赞。
当oldEndVnode，newStartVnode值得比较，说明 oldEndVnode.el跑到了newStartVnode.el的前边。
这句话估计你写笔误了吧...

aooy · 2017-04-27T01:02:30Z

@wangweida 是的笔误了，谢谢提醒。

zengwenfu · 2017-04-27T01:53:31Z

赞，有一处需要指出的是：
function sameVnode(oldVnode, vnode){
return vnode.key === oldVnode.key && vnode.sel === oldVnode.sel
}
vue中sameVnode不会比较vnode.sel===oldVnode.sel，按照定义，这里的sel是选择器，如果选择器不一致就不值得比较的话，那么vue里面的v-bind:class动态绑定class就变得完全不提倡使用了，事实上vue并没有做这个比较：
function sameVnode (a, b) {
return (
a.key === b.key &&
a.tag === b.tag &&
a.isComment === b.isComment &&
isDef(a.data) === isDef(b.data) &&
sameInputType(a, b)
)
}

aooy · 2017-04-27T02:23:04Z

@zengwenfu 谢谢指正，本文从原始算法去解读vue的diff，没有完全契合vue，vue实际情况会更复杂，它考虑到了class的动态绑定和input的type值，对sameVnode进行了修改。

dean5277 · 2017-06-09T02:30:32Z

配图满分，很好理解

linzb93 · 2017-06-27T15:03:34Z

有个疑问，假如一个节点是根节点的好几层子节点，那么它对应的vnode的el属性应该怎么表示？是从根节点一层层套下去吗？我看了你的代码还没明白。

aooy · 2017-07-03T09:19:03Z

@linzb93 一层一层套的是vnode的children属性，el存的是此vnode渲染出来的Element对象，也就是真实节点。
例如：

<body>
 <div></div>
<body>
//对应的vnode
{
  el:  document.body,
  children: [
        {
            el:  document.body.children[0],
            children: [],
            ...
        }
  ], 
  ...
}

linzb93 · 2017-07-04T01:14:22Z

@aooy 我也有这么想过，就是会担心性能问题（我怎么会担心这个→_→），看来真的是这样的。谢谢了。。

liz282907 · 2017-07-22T12:41:32Z

react diff 几乎一样...

aooy · 2017-07-23T06:15:23Z

@liz282907 这篇文章学习过的，有借鉴的地方。vue和react的diff就当是黑猫白猫吧

zhoujiamin · 2017-08-03T02:43:17Z

react虚拟DOM算法和vue 的这个有什么不同呢？

wqzwh · 2017-08-30T08:20:31Z

学习了

HanYif · 2017-09-18T15:57:28Z

mark

lkdghzh · 2018-02-02T18:38:20Z

mark

alabihula · 2018-02-07T12:38:07Z

有一点疑问搜了好多也没有特别明白的回答，就是后面说的三个优化点，具体能有个例子么，尤其是手动优化diff

aooy · 2018-02-09T09:47:04Z

@alabihula 我觉得之前第三点的说法不妥当，所以改啦，很多时候明显自己操作dom会快很多，但是框架本身就是为了方便开发和协作的，跳出框架去做这些优化反而会增加维护的成本。

cunjieliu · 2018-02-24T06:14:29Z

👍

caoyongqiang · 2018-11-07T11:30:51Z

@aooy 赞！感谢分享，有一处需要指正
对updateChildren函数中的 oldStartIdx > oldEndIdx 情况的分析是不够准确的

此时newStartIdx和newEndIdx之间的vnode是新增的，调用addVnodes，把他们全部插进before的后边，before很多时候是为null的

看一下before的定义
before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el
before并不是很多时候是null的，只要newEndIdex发生过左移，newCh[newEndIdx + 1]就不是null，因此before就不是null。同时before不为null的情况下，也不是插在before的后面，而是插在before的前面。
举个例子：oldCh = [a, b]，newCh = [a, c, b]。updateChildren中的while循环对比结束后，before指向的是b。插入操作是把c插入到b前面。

sandlover · 2018-12-02T02:44:53Z

对着源码看了下，豁然洞开，赞👍

136shine · 2019-01-19T12:42:05Z

请问，patchVnode 中的 updateEle(el, vnode, oldVnode) 的含义是啥，看了下该函数，应该是为节点设置class、ID、data等属性，谢谢

Ray-56 · 2019-02-12T08:39:46Z

mark

opop007 · 2019-02-19T08:14:28Z

mark,感谢

mumofa · 2019-04-11T07:04:58Z

看完了一开始看得很头疼特别是updateChildren 那里
不过慢慢啃下来有种豁然开朗的感觉
谢谢up~

1003047593 · 2019-05-15T03:41:52Z

题主对diff算法解析的真是到位，虽然diff不是最优解，但是综合来看，易推广

haaling · 2019-07-11T07:22:44Z

感谢@aooy分享，很赞的文章~~

不过这里有个小问题，这张图里的第4步应该没有移动的操作，只是移动了idx, c的位置是在第5步中a, b节点删除掉之后，自然地跟在了d的后面~

第四步逻辑大概就是newCh的newStartIdx， newEndIdx在c元素上发生了重叠，然后在下一次循环中进入了else if(sameVnode(oldEndVnode, newEndVnode))这个逻辑：
patchVnode(oldEndVnode, newEndVnode)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
不知道我的理解对不~~

我也是这样理解的第四步应该不用插入操作，因为比较的是oldEndVnode和newEndVnode。
然后oldEndIdx前移，结束，将oldEnd和oldStart之间的元素（含）remove。不对还请指正

对于与sameVnode(oldStartVnode, newStartVnode)和sameVnode(oldEndVnode,newEndVnode)为true的情况，不需要对dom进行移动。

niujiangyao · 2019-07-11T08:46:51Z

这个b不会复用这块，看源码如果没有设置key的话他也会去遍历oldch找到b然后复用的吧，只是有没有key查找的速度不一样有key的话是map映射查找比遍历快

YeYongFen · 2019-07-11T09:50:14Z

感谢@aooy分享，很赞的文章~~
不过这里有个小问题，这张图里的第4步应该没有移动的操作，只是移动了idx, c的位置是在第5步中a, b节点删除掉之后，自然地跟在了d的后面~

第四步逻辑大概就是newCh的newStartIdx， newEndIdx在c元素上发生了重叠，然后在下一次循环中进入了else if(sameVnode(oldEndVnode, newEndVnode))这个逻辑：
patchVnode(oldEndVnode, newEndVnode)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
不知道我的理解对不~~
我也是这样理解的~~第四步应该不用插入操作，因为比较的是oldEndVnode和newEndVnode。然后oldEndIdx前移，结束，将oldEnd和oldStart之间的元素（含）remove。不对还请指正~~

对于与sameVnode(oldStartVnode, newStartVnode)和sameVnode(oldEndVnode,newEndVnode)为true的情况，不需要对dom进行移动。

同意你的观点，这时候应该是 oldEndVnode== newEndVnode 这种情况。不需要移动 dom节点

YeYongFen · 2019-07-11T10:34:54Z

你好，我发现你的第一个例子，也就是不带key的例子有点不合理

idxInOld = isDef(newStartVnode.key)
          ? oldKeyToIdx[newStartVnode.key]
          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)

  function findIdxInOld (node, oldCh, start, end) {
    for (let i = start; i < end; i++) {
      const c = oldCh[i]
      if (isDef(c) && sameVnode(node, c)) return i
    }
  }

由于没有key ，那么肯定是走 findIdxInOld。

例如第一个点 b，通过 sameVnode 它还是可以找到 oldch 里面的 d 的啊，所以第一步不会是插入。

这是我的代码

    <head>
        <meta charset="UTF-8">
        <title></title>
        <script type="text/javascript" src="vue.js"></script>
    </head>
    <body>
        <div id="app" @click="change">
            <component :is="'h'+mm[n]" v-for="n in arr" >{{n}}</component>
        </div>
    </body>
    <script type="text/javascript">
        let s = 1;
        var app = new Vue({
            el: '#app',
            data() {
                return {
                    arr: ["a","b","c","d"],
                    tag:"span",
                    mm:{
                        "a":1,"b":2,"c":3,"d":4,"e":5
                    }
                }
            },
            methods: {
                change() {
                    this.arr = ["b","e","d","c"];
                    //this.tag = "h"+ s++;
                }
            }

        })
    </script>

xubaifuCode · 2019-08-04T14:10:14Z

idxInOld = oldKeyToIdx[newStartVnode.key]
if (!idxInOld) {
    api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
    newStartVnode = newCh[++newStartIdx]
}

idxInOld 有可能是0吧？

另外我结合大佬的文章和国外一个讲虚拟DOM的把两者结合实现了一个可直观感受且跑得通得DEMO。请看：https://github.com/xubaifuCode/virtual-dom-and-diff-implementation

hdulsh · 2019-08-12T14:19:48Z

感谢@aooy分享，很赞的文章~~

不过这里有个小问题，这张图里的第4步应该没有移动的操作，只是移动了idx, c的位置是在第5步中a, b节点删除掉之后，自然地跟在了d的后面~

第四步逻辑大概就是newCh的newStartIdx， newEndIdx在c元素上发生了重叠，然后在下一次循环中进入了else if(sameVnode(oldEndVnode, newEndVnode))这个逻辑：
patchVnode(oldEndVnode, newEndVnode)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
不知道我的理解对不~~

大佬加上key的那张图 c是不是也不需要移动啊

haoolii · 2019-08-15T03:53:18Z

感谢@aooy分享，很赞的文章~~
不过这里有个小问题，这张图里的第4步应该没有移动的操作，只是移动了idx, c的位置是在第5步中a, b节点删除掉之后，自然地跟在了d的后面~

第四步逻辑大概就是newCh的newStartIdx， newEndIdx在c元素上发生了重叠，然后在下一次循环中进入了else if(sameVnode(oldEndVnode, newEndVnode))这个逻辑：
patchVnode(oldEndVnode, newEndVnode)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
不知道我的理解对不~~
大佬加上key的那张图 c是不是也不需要移动啊

一開始看圖真的看不懂直接看源碼還清楚些一直碎碎念為何C要移動
原來家都有這疑惑哈哈

GitHdu · 2019-08-24T08:21:54Z

你好，我发现你的第一个例子，也就是不带key的例子有点不合理

idxInOld = isDef(newStartVnode.key)
          ? oldKeyToIdx[newStartVnode.key]
          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)

  function findIdxInOld (node, oldCh, start, end) {
    for (let i = start; i < end; i++) {
      const c = oldCh[i]
      if (isDef(c) && sameVnode(node, c)) return i
    }
  }

由于没有key ，那么肯定是走 findIdxInOld。

例如第一个点 b，通过 sameVnode 它还是可以找到 oldch 里面的 d 的啊，所以第一步不会是插入。

这是我的代码

    <head>
        <meta charset="UTF-8">
        <title></title>
        <script type="text/javascript" src="vue.js"></script>
    </head>
    <body>
        <div id="app" @click="change">
            <component :is="'h'+mm[n]" v-for="n in arr" >{{n}}</component>
        </div>
    </body>
    <script type="text/javascript">
        let s = 1;
        var app = new Vue({
            el: '#app',
            data() {
                return {
                    arr: ["a","b","c","d"],
                    tag:"span",
                    mm:{
                        "a":1,"b":2,"c":3,"d":4,"e":5
                    }
                }
            },
            methods: {
                change() {
                    this.arr = ["b","e","d","c"];
                    //this.tag = "h"+ s++;
                }
            }

        })
    </script>

vue版本不一样，楼主分析的是老版本，还没有这个函数

Inakiz · 2019-11-13T15:42:48Z

Mark

wolongfeitian · 2020-01-30T14:07:14Z

为什么不设key，newCh和oldCh只会进行头尾两端的相互比较，这样怎么保证更新的dom正确呢？

xsfxtsxxr · 2020-07-31T01:45:24Z

对于vnode.key的比较，会把oldVnode = null

请问这句话怎么理解啊？

uaoin · 2022-09-15T09:06:36Z

@aooy 赞！感谢分享，有一处需要指正对updateChildren函数中的 oldStartIdx > oldEndIdx 情况的分析是不够准确的

此时newStartIdx和newEndIdx之间的vnode是新增的，调用addVnodes，把他们全部插进before的后边，before很多时候是为null的

看一下before的定义 before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el before并不是很多时候是null的，只要newEndIdex发生过左移，newCh[newEndIdx + 1]就不是null，因此before就不是null。同时before不为null的情况下，也不是插在before的后面，而是插在before的前面。举个例子：oldCh = [a, b]，newCh = [a, c, b]。updateChildren中的while循环对比结束后，before指向的是b。插入操作是把c插入到b前面。

newStartIdx和newEndIdx之间新增的节点为什么要插入在newEndIdx之后呢?
不应该是插入到它们之间?

仔细想了想确实应该插入到newEndIdx之后,因为循环结束后包括newStartIdx和newEndIdx都是新增的节点

RED523 · 2024-01-13T15:36:22Z

你好，我发现你的第一个例子，也就是不带key的例子有点不合理

idxInOld = isDef(newStartVnode.key)
          ? oldKeyToIdx[newStartVnode.key]
          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)

  function findIdxInOld (node, oldCh, start, end) {
    for (let i = start; i < end; i++) {
      const c = oldCh[i]
      if (isDef(c) && sameVnode(node, c)) return i
    }
  }

由于没有key ，那么肯定是走 findIdxInOld。

例如第一个点 b，通过 sameVnode 它还是可以找到 oldch 里面的 d 的啊，所以第一步不会是插入。

这是我的代码

    <head>
        <meta charset="UTF-8">
        <title></title>
        <script type="text/javascript" src="vue.js"></script>
    </head>
    <body>
        <div id="app" @click="change">
            <component :is="'h'+mm[n]" v-for="n in arr" >{{n}}</component>
        </div>
    </body>
    <script type="text/javascript">
        let s = 1;
        var app = new Vue({
            el: '#app',
            data() {
                return {
                    arr: ["a","b","c","d"],
                    tag:"span",
                    mm:{
                        "a":1,"b":2,"c":3,"d":4,"e":5
                    }
                }
            },
            methods: {
                change() {
                    this.arr = ["b","e","d","c"];
                    //this.tag = "h"+ s++;
                }
            }

        })
    </script>

看了评论有很多人提出来这个问题，其实是尤雨溪在解决 issues/6502 的时候添加的。文章作者写的时候这个问题还存在。

aooy added the javascript label Apr 4, 2017

wangweida mentioned this issue Oct 11, 2017

分享准备 wangweida/blog#9

Open

zhoubhin mentioned this issue Nov 16, 2017

vue早期源码学习系列之八：列表渲染与diff算法 youngwind/blog#91

Open

wolfdu mentioned this issue Mar 19, 2018

面试问题集 wolfdu/Blog#39

Open

zoro-web mentioned this issue Mar 20, 2018

vue源码学习--模板渲染 zoro-web/blog#5

Open

Zephylaci mentioned this issue Mar 1, 2019

第 1 题：写 React / Vue 项目时为什么要在列表组件中写 key，其作用是什么？ Advanced-Frontend/Daily-Interview-Question#1

Open

jin5354 mentioned this issue Mar 7, 2019

现代前端科技解析 —— Virtual DOM jin5354/404forest#71

Open

zhuping mentioned this issue Apr 2, 2019

Vue diff 算法分析 zhuping/blog#7

Open

zonglang mentioned this issue Jul 10, 2019

列表组件中为什么要用key zonglang/code#16

Open

bobohuochai mentioned this issue Jul 11, 2019

第 97 题：React 和 Vue 的 diff 时间复杂度从 O(n^3) 优化到 O(n) ，那么 O(n^3) 和 O(n) 是如何计算出来的？ Advanced-Frontend/Daily-Interview-Question#151

Open

Dliling mentioned this issue May 24, 2020

【Vue】为什么要在列表组件中写key，其作用是什么？ Dliling/Blob#4

Open

xiuyuan66 mentioned this issue Oct 23, 2020

浅谈Vue的Diff算法 xiuyuan66/xiuyuan.github.io#4

Open

madfour mentioned this issue Feb 18, 2021

vue项目列表组件中，key的作用是什么？ madfour/blog-docs#8

Open

zptime mentioned this issue Oct 4, 2021

前端基础知识之Vue篇 zptime/blog#21

Open

GpingFeng mentioned this issue Aug 14, 2022

深入浅出 Vue 中的 key 值 GpingFeng/gopal-blog#66

Open

解析vue2.0的diff算法 #2

解析vue2.0的diff算法 #2

Comments

aooy commented Mar 19, 2017 • edited Loading

目录

前言

virtual dom

读到这里就会产生一个疑问，为什么不直接修改dom而需要加一层virtual dom呢？

分析diff

源码分析

patchVnode

updateChildren

具体的diff分析

下面举个例子，画出diff完整的过程，每一步dom的变化都用不同颜色的线标出。

总结

userand commented Mar 23, 2017

fengmiaosen commented Mar 24, 2017

cshenger commented Mar 24, 2017

ascoders commented Mar 24, 2017 • edited Loading

aooy commented Mar 24, 2017

ghost commented Mar 25, 2017 • edited by liuliangsir Loading

mofengfly commented Apr 9, 2017

iterry commented Apr 12, 2017

wangweida commented Apr 26, 2017 • edited Loading

aooy commented Apr 27, 2017

zengwenfu commented Apr 27, 2017

aooy commented Apr 27, 2017

dean5277 commented Jun 9, 2017

linzb93 commented Jun 27, 2017

aooy commented Jul 3, 2017

linzb93 commented Jul 4, 2017

liz282907 commented Jul 22, 2017

aooy commented Jul 23, 2017

zhoujiamin commented Aug 3, 2017

wqzwh commented Aug 30, 2017

HanYif commented Sep 18, 2017

lkdghzh commented Feb 2, 2018

alabihula commented Feb 7, 2018

aooy commented Feb 9, 2018

cunjieliu commented Feb 24, 2018

caoyongqiang commented Nov 7, 2018

sandlover commented Dec 2, 2018

136shine commented Jan 19, 2019

Ray-56 commented Feb 12, 2019

opop007 commented Feb 19, 2019

mumofa commented Apr 11, 2019

1003047593 commented May 15, 2019

haaling commented Jul 11, 2019

niujiangyao commented Jul 11, 2019

YeYongFen commented Jul 11, 2019

YeYongFen commented Jul 11, 2019

xubaifuCode commented Aug 4, 2019

hdulsh commented Aug 12, 2019

haoolii commented Aug 15, 2019

GitHdu commented Aug 24, 2019

Inakiz commented Nov 13, 2019

wolongfeitian commented Jan 30, 2020

xsfxtsxxr commented Jul 31, 2020

对于vnode.key的比较，会把oldVnode = null

uaoin commented Sep 15, 2022 • edited Loading

RED523 commented Jan 13, 2024

aooy commented Mar 19, 2017 •

edited

Loading

ascoders commented Mar 24, 2017 •

edited

Loading

ghost commented Mar 25, 2017 •

edited by liuliangsir

Loading

wangweida commented Apr 26, 2017 •

edited

Loading

uaoin commented Sep 15, 2022 •

edited

Loading