每天⼀点⾯试题（8）------------diff算法详解
diff算法的作⽤
计算出Virtual DOM中真正变化的部分，并只针对该部分进⾏原⽣DOM操作，⽽⾮重新渲染整个页⾯。
传统diff算法
通过循环递归对节点进⾏依次对⽐，算法复杂度达到 O(n^3) ，n是树的节点数，这个有多可怕呢？——如果要展⽰1000个节点，得执⾏上亿次⽐较。。即便是CPU快能执⾏30亿条命令，也很难在⼀秒内计算出差异。
React的diff算法
（1）什么是调和？
将Virtual DOM树转换成actual DOM树的最少操作的过程 称为 调和 。
（2）什么是React diff算法？
diff算法是调和的具体实现。
diff策略
React⽤ 三⼤策略 将O(n^3)复杂度 转化为 O(n)复杂度
diff函数
策略⼀（tree diff）：
Web UI中DOM节点跨层级的移动操作特别少，可以忽略不计。
策略⼆（component diff）：
拥有相同类的两个组件 ⽣成相似的树形结构，
拥有不同类的两个组件 ⽣成不同的树形结构。
策略三（element diff）：
对于同⼀层级的⼀组⼦节点，通过唯⼀id区分。
tree diff
（1）React通过updateDepth对Virtual DOM树进⾏层级控制。
（2）对树分层⽐较，两棵树 只对同⼀层次节点 进⾏⽐较。如果该节点不存在时，则该节点及其⼦节点会被完全删除，不会再进⼀步⽐较。
（3）只需遍历⼀次，就能完成整棵DOM树的⽐较。
那么问题来了，如果DOM节点出现了跨层级操作,diff会咋办呢？
答：diff只简单考虑同层级的节点位置变换，如果是跨层级的话，只有创建节点和删除节点的操作。
如上图所⽰，以A为根节点的整棵树会被重新创建，⽽不是移动，因此 官⽅建议不要进⾏DOM节点跨层级操作，可以通过CSS隐藏、显⽰节点，⽽不是真正地移除、添加DOM节点。
component diff
React对不同的组件间的⽐较，有三种策略
（1）同⼀类型的两个组件，按原策略（层级⽐较）继续⽐较Virtual DOM树即可。
（2）同⼀类型的两个组件，组件A变化为组件B时，可能Virtual DOM没有任何变化，如果知道这点（变换的过程中，Virtual DOM没有改变），可节省⼤量计算时间，所以 ⽤户 可以通过 shouldComponentUpdate() 来判断是否需要 判断计算。
（3）不同类型的组件，将⼀个（将被改变的）组件判断为dirty component（脏组件），从⽽替换 整个组件的所有节点。
注意：如果组件D和组件G的结构相似，但是 React判断是 不同类型的组件，则不会⽐较其结构，⽽是删除 组件D及其⼦节点，创建组件G 及其⼦节点。
element diff
当节点处于同⼀层级时，diff提供三种节点操作：删除、插⼊、移动。
插⼊：组件 C 不在集合（A,B）中，需要插⼊
删除：（1）组件 D 在集合（A,B,D）中，但 D的节点已经更改，不能复⽤和更新，所以需要删除 旧的 D ，再创建新的。
（2）组件 D 之前在 集合（A,B,D）中，但集合变成新的集合（A,B）了，D 就需要被删除。
移动：组件D已经在集合（A,B,C,D）⾥了，且集合更新时，D没有发⽣更新，只是位置改变，如新集合（A,D,B,C），D在第⼆个，⽆须像传统diff，让旧集合的第⼆个B和新集合的第⼆个D ⽐较，并且删除第⼆个位置的B，再在第⼆个位置插⼊D，⽽是 （对同⼀层级的同组⼦节点） 添加唯⼀key进⾏区分，移动即可。
重点说下移动的逻辑：
情形⼀：新旧集合中存在相同节点但位置不同时，如何移动节点
（1）看着上图的 B，React先从新中取得B，然后判断旧中是否存在相同节点B，当发现存在节点B后，就去判断是否移动B。
B在旧 中的index=1，它的lastIndex=0，不满⾜ index < lastIndex 的条件，因此 B 不做移动操作。此时，⼀个操作是，lastIndex= (index,lastIndex)中的较⼤数=1.
注意：lastIndex有点像浮标，或者说是⼀个map的索引，⼀开始默认值是0，它会与map中的元素进⾏⽐较，⽐较完后，会改变⾃⼰的值的（取index和lastIndex的较⼤数）。
（2）看着 A，A在旧的index=0，此时的lastIndex=1（因为先前与新的B⽐较过了），满⾜index<lastIndex，因此，对A进⾏移动操作，此时lastIndex=max(index,lastIndex)=1。
（3）看着D，同（1），不移动，由于D在旧的index=3，⽐较时，lastIndex=1，所以改变lastIndex=max(index,lastIndex)=3
（4）看着C，同（2），移动，C在旧的index=2，满⾜index<lastIndex（lastIndex=3），所以移动。
由于C已经是最后⼀个节点，所以diff操作结束。
情形⼆：新集合中有新加⼊的节点，旧集合中有删除的节点
（1）B不移动，不赘述，更新l astIndex=1
（2）新集合取得 E，发现旧不存在，故在lastIndex=1的位置 创建E，更新lastIndex=1
（3）新集合取得C，C不移动，更新lastIndex=2
（4）新集合取得A，A移动，同上，更新lastIndex=2
（5）新集合对⽐后，再对旧集合遍历。判断 新集合 没有，但 旧集合 有的元素（如D，新集合没有，旧集合有），发现 D，删除D，diff操作结束。
diff的不⾜与待优化的地⽅
看图的 D，此时D不移动，但它的index是最⼤的，导致更新lastIndex=3，从⽽使得其他元素A,B,C的index<lastIndex，导致A,B,C都要去移动。
理想情况是只移动D，不移动A,B,C。因此，在开发过程中，尽量减少类似将最后⼀个节点移动到列表⾸部的操作，当节点数量过⼤或更新操作过于频繁时，会影响React的渲染性能。
源码部分
diff.js
zzvar _ =require('./util')
var patch =require('./patch')
var listDiff =require('list-diff2')
function diff(oldTree, newTree){
var index =0
var patches ={}
dfsWalk(oldTree, newTree, index, patches)
return patches
}
function dfsWalk(oldNode, newNode, index, patches){
var currentPatch =[]
// 节点被移除Node is removed.
if(newNode ===null){
// Real DOM node will be removed when perform reordering,
// so has no needs to do anthings in here
//节点为⽂本内容改变TextNode content replacing
}else if(_.isString(oldNode)&& _.isString(newNode)){
if(newNode !== oldNode){
currentPatch.push({ type: patch.TEXT, content: newNode })
}
//节点类型相同遍历属性和孩⼦
/
/ Nodes are the same, diff old node's props and children
}else if(
oldNode.tagName === newNode.tagName &&
oldNode.key === newNode.key
){
// Diff props 遍历属性
var propsPatches =diffProps(oldNode, newNode)
if(propsPatches){
if(propsPatches){
currentPatch.push({ type: patch.PROPS, props: propsPatches })
}
/
/ Diff children. If the node has a `ignore` property, do not diff children
// 遍历孩⼦
if(!isIgnoreChildren(newNode)){
diffChildren(
oldNode.children,
newNode.children,
index,
patches,
currentPatch
)
}
/
/ 节点类型不同新节点直接替换旧节点Nodes are not the same, replace the old node with new node }else{
currentPatch.push({ type: patch.REPLACE, node: newNode })
}
//index是每个节点都有的⼀个索引每个！
if(currentPatch.length){
patches[index]= currentPatch
}
}
//为什么这⾥要把⼦节点的递归单独写出来⽽不直接写在dfswalk函数⾥⾯呢？
//我认为其实⾮要写也是可以写进dfswalk⾥⾯的，但是为了功能分离、解耦所以单独提出来写function diffChildren(oldChildren, newChildren, index, patches, currentPatch){
//该key就指的是循环绑定上的key值
var diffs =listDiff(oldChildren, newChildren,'key')
newChildren = diffs.children
ves.length){
var reorderPatch ={ type: patch.REORDER, moves: ves }
currentPatch.push(reorderPatch)
}
var leftNode =null
var currentNodeIndex = index
_.each(oldChildren,function(child, i){
var newChild = newChildren[i]
currentNodeIndex =(leftNode && unt)
//index当前的节点的标志。因为在深度优先遍历的过程中，每个节点都有⼀个index
//count为⼦节点个数
//为什么这⾥是+unt, 因为每次diffChildren是遍历该节点的⼦节点按照顺序来
//⾃⼰的第⼀个⼦节点是⾃⼰的index再加上和左边节点的⼦节点数也就是leftNode.index
//第⼀次进diffchildren函数肯定是第⼀个节点，不存在有左边的节点，所以...
? currentNodeIndex + unt +1
//
: currentNodeIndex +1
dfsWalk(child, newChild, currentNodeIndex, patches)
leftNode = child
})
}
function diffProps(oldNode, newNode){
var count =0
var oldProps = oldNode.props
var newProps = newNode.props
var key, value
var propsPatches ={}
// Find out different properties

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。