当然，对比两个DOM树的差异才是最核心的部分，这也就是所谓的diff算法了，两个DOM的算法是一个 O(n^3) 问题。 但是在前端的实际使用种我们很少去跨级的移动整个DOM树，所以我们可以简化成一层之间的移动，所以diff算法就变成了一个同级元素对比的算法了（仅仅是说明用，真正的算法实现还是去看React的源代码吧）。

　　上面的图片中的移动其实只是同级 div 的对比，第二层级的 div 只会跟第二层级的 div 对比。这样算法复杂度就可以达到 O(n)。紧接着就是通过深度优先遍历来记录差异，在深度优先遍历的时候，每遍历到一个节点就把该节点和新的的树进行对比。如果有差异的话就记录到一个对象里面（类似权重相加的概念）。

diff (oldTree, newTree) { patches = {} dfsWalk(oldTree, newTree, index, patches) 6 return patches 7 } dfsWalk (oldNode, newNode, index, patches) { patches[index] = [...] 13 14 diffChildren(oldNode.children, newNode.children, index, patches) 15 } diffChildren (oldChildren, newChildren, index, patches) { currentNodeIndex = index 21 oldChildren.forEach(function (child, i) { 22 var newChild = newChildren[i] ? currentNodeIndex + leftNode.count + 1 25 : currentNodeIndex + 1 leftNode = child 28 }) 29 }

例如，上面的div和新的div有差异，当前的标记是0，那么：

1 patches[0] = [{difference}, {difference}, ...] // 用数组存储新旧节点的不同

同理p是patches[1]，ul是patches[3]，以此类推。那差异类型是什么呢？ 对DOM操作可能会有下面几种：

所以我们需要定义几种差异类型：

1 var REPLACE = 0 2 var REORDER = 1 3 var PROPS = 2 4 var TEXT = 3

那对于节点的替换就很简单了，只要判断新旧节点的 tagName 的和是不是一样的，如果不一样就说明需要替换了，例如 div 替换成 section，就记作：

1 patches[0] = [{ 2 type: REPALCE, }]

如果给 div 新增了属性 id 为 test ，就记作：

1 patches[0] = [{ 2 type: REPALCE, }, { 5 type: PROPS, 6 props: { 7 id: "test" 8 } 9 }]

如果是文本节点的话，就记作：

1 patches[2] = [{ 2 type: TEXT, 3 content: "Virtual DOM2" 4 }]

　　那如果把我div的子节点重新排序呢？例如p, ul, div的顺序换成了div, p, ul。这个该怎么对比？如果按照同层级进行顺序对比的话，它们都会被替换掉。如p和div的tagName不同，p会被div所替代。最终，三个节点都会被替换，这样DOM开销就非常大。而实际上是不需要替换节点，而只需要经过节点移动就可以达到，我们只需知道怎么进行移动。接下来是列表对比算法。

假设现在可以英文字母唯一地标识每一个子节点：

旧的节点顺序：a b c d e f g h i 

现在对节点进行了删除、插入、移动的操作。新增j节点，删除e节点，移动h节点：

 新的节点顺序：a b c h d f g i j

　　现在知道了新旧的顺序，求最小的插入、删除操作（移动可以看成是删除和插入操作的结合）。这个问题抽象出来其实是字符串的最小编辑距离问题（Edition Distance），最常见的解决算法是 Levenshtein Distance，通过动态规划求解，时间复杂度为 O(M * N)。但是我们并不需要真的达到最小的操作，我们只需要优化一些比较常见的移动情况，牺牲一定DOM操作，让算法时间复杂度达到线性的（O(max(M, N))。具体算法细节比较多，这里不累述。我们能够获取到某个父节点的子节点的操作，就可以记录下来：

1 patches[0] = [{ 2 type: REORDER, 3 moves: [{remove or insert}, {remove or insert}, ...] 4 }]