react中diff算法的理解
diff算法用来计算出virtual dom中改变的部分，然后针对该部分进行dom操作，而不用重新渲染整个页面，渲染整个dom结构的过程中开销是很大的，需要浏览器对dom结构进行重绘与回流，而diff算法能够使得操作过程中只更新修改的那部分dom结构而不更新整个dom，这样能够最小化操作dom结构，能够最大程度上减少浏览器重绘与回流的规模。
虚拟dom
diff算法的基础是virtual dom，virtual dom是一棵以javascript对象作为基础的树，在react中通常是通过jsx编译而成的，每一个节点称为vnode，用对象属性来描述节点，实际上它是一层对真实dom的抽象，最终可以通过渲染操作使这棵树映射到真实环境上，简单来说virtual dom就是一个js对象，用以描述整个文档。
在浏览器中构建页面时需要使用dom节点描述整个文档。
<div class="root" name="root">
<p>1</p>
<div>11</div>
</div>
如果使用js对象去描述上述的节点以及文档，那么便类似于下面的样子，当然这不是react中用以描述节点的对象，react中创建一个react元素的相关源码在react/src/reactelement.js中，文中的react版本是16.10.2。
{
type: "div",
props: {
classname: "root"
name: "root",
children: [{
type: "p",
props: {
children: [{
type: "text",
props: {
text: "1"
}
}]
}
},{
type: "div",
props: {
children: [{
type: "text",
props: {
text: "11"
}
}]
}
}]
}
}
实际上在react16中启用了全新的架构fiber，fiber核心是实现了一个基于优先级和requestidlecallback的循环任务调度算法，相关问题不在文章中讨论，相关的问题大致在于虚拟dom由树结构转变成链表结构，原来的vdom是一颗由上至下的树，通过深度优先遍历，层层递归直下，然而这个深度优先遍历最大的毛病在于不可中断，因此我们在diff + patch又或者是mount巨大节点的时候，会造成较大的卡顿，react16的vdom不再是一颗由上至下那么简单的树，而是链表形式的虚拟dom，链表的每一个节点是fiber，而不是在16之前的虚拟dom节点，每个fiber节点记录着诸多信息，以便走到某个节点的时候中断，fiber的思路是把渲染/更新过程(递归diff)拆分成一系列小任务，每次检查树上的一小部分，做完看是否还有时间继续下一个任务，有的话继续，没有的话把自己挂起，主线程不忙的时候再继续。fiber在diff阶段，做了如下的操作，实际相当于在15的diff算法阶段，做了优先级的任务调度控制。
- 把可中断的工作拆分成小任务。
- 对正在做的工作调整优先次序、重做、复用上次(未完成)工作。
diff阶段任务调度优先级控制。
操作虚拟dom与操作原生dom的比较
在这里直接引用了尤大的话(2016-02-08年的回答，此时vue2.0还未发布，vue2.0于2016-10-01左右发布，vue2.0才加入虚拟dom)，相关链接为https://www.zhihu.com/question/31809713，建议结合链接中的问题阅读，也可以看看问题中比较的示例，另外下面的回答也都非常的精髓。
原生 dom 操作 vs 通过框架封装操作
这是一个性能vs可维护性的取舍，框架的意义在于为你掩盖底层的dom操作，让你用更声明式的方式来描述你的目的，从而让你的代码更容易维护，没有任何框架可以比纯手动的优化dom操作更快，因为框架的dom操作层需要应对任何上层api可能产生的操作，它的实现必须是普适的，针对任何一个benchmark，我都可以写出比任何框架更快的手动优化，但是那有什么意义呢?在构建一个实际应用的时候，你难道为每一个地方都去做手动优化吗?出于可维护性的考虑，这显然不可能，框架给你的保证是，你在不需要手动优化的情况下，我依然可以给你提供过得去的性能。
对 react 的 virtual dom 的误解
react从来没有说过react比原生操作dom快，react的基本思维模式是每次有变动就整个重新渲染整个应用，如果没有virtual dom，简单来想就是直接重置innerhtml，很多人都没有意识到，在一个大型列表所有数据都变了的情况下，重置innerhtml其实是一个还算合理的操作，真正的问题是在全部重新渲染的思维模式下，即使只有一行数据变了，它也需要重置整个innerhtml，这时候显然就有大量的浪费。
我们可以比较一下innerhtml vs virtual dom的重绘性能消耗：
innerhtml:render html string o(template size)+ 重新创建所有dom元素o(dom size)virtual dom:render virtual dom + diff o(template size)+ 必要的dom更新o(dom change)。
virtual dom render + diff显然比渲染html字符串要慢，但是!它依然是纯js层面的计算，比起后面的dom操作来说，依然便宜了太多，可以看到，innerhtml的总计算量不管是js计算还是dom操作都是和整个界面的大小相关，但virtual dom的计算量里面，只有js计算和界面大小相关，dom操作是和数据的变动量相关的，前面说了，和dom操作比起来，js计算是极其便宜的，这才是为什么要有virtual dom:它保证了 1)不管你的数据变化多少，每次重绘的性能都可以接受; 2)你依然可以用类似innerhtml的思路去写你的应用。
mvvm vs virtual dom
相比起react，其他mvvm系框架比如angular, knockout以及vue、avalon采用的都是数据绑定:通过directive/binding对象，观察数据变化并保留对实际dom元素的引用，当有数据变化时进行对应的操作，mvvm的变化检查是数据层面的，而react的检查是dom结构层面的，mvvm的性能也根据变动检测的实现原理有所不同: angular的脏检查使得任何变动都有固定的o(watcher count)的代价; knockout/vue/avalon都采用了依赖收集，在js和dom层面都是o(change):
- 脏检查：
scope digest o(watcher count)+ 必要dom更新o(dom change)。 - 依赖收集：重新收集依赖
o(data change)+ 必要dom更新o(dom change)。
可以看到，angular最不效率的地方在于任何小变动都有的和watcher数量相关的性能代价，但是!当所有数据都变了的时候，angular其实并不吃亏，依赖收集在初始化和数据变化的时候都需要重新收集依赖，这个代价在小量更新的时候几乎可以忽略，但在数据量庞大的时候也会产生一定的消耗。
mvvm渲染列表的时候，由于每一行都有自己的数据作用域，所以通常都是每一行有一个对应的viewmodel实例，或者是一个稍微轻量一些的利用原型继承的scope对象，但也有一定的代价，所以mvvm列表渲染的初始化几乎一定比react慢，因为创建viewmodel / scope实例比起virtual dom来说要昂贵很多，这里所有mvvm实现的一个共同问题就是在列表渲染的数据源变动时，尤其是当数据是全新的对象时，如何有效地复用已经创建的viewmodel实例和dom元素，假如没有任何复用方面的优化，由于数据是全新的，mvvm实际上需要销毁之前的所有实例，重新创建所有实例，最后再进行一次渲染!这就是为什么题目里链接的angular/knockout实现都相对比较慢，相比之下，react的变动检查由于是dom结构层面的，即使是全新的数据，只要最后渲染结果没变，那么就不需要做无用功。
顺道说一句，react渲染列表的时候也需要提供key这个特殊prop，本质上和track-by是一回事。
性能比较也要看场合
在比较性能的时候，要分清楚初始渲染、小量数据更新、大量数据更新这些不同的场合，virtual dom、脏检查mvvm、数据收集mvvm在不同场合各有不同的表现和不同的优化需求，virtual dom为了提升小量数据更新时的性能，也需要针对性的优化，比如shouldcomponentupdate或是immutable data。
- 初始渲染：
virtual dom> 脏检查 >= 依赖收集。 - 小量数据更新：依赖收集 >>
virtual dom+ 优化 > 脏检查(无法优化) >virtual dom无优化。 - 大量数据更新：脏检查 + 优化 >= 依赖收集 + 优化 >
virtual dom(无法/无需优化) >>mvvm无优化。
不要天真地以为virtual dom就是快，diff不是免费的，batching么mvvm也能做，而且最终patch的时候还不是要用原生api，在我看来virtual dom真正的价值从来都不是性能，而是它 1)为函数式的ui编程方式打开了大门; 2)可以渲染到dom以外的backend，比如reactnative。
总结
以上这些比较，更多的是对于框架开发研究者提供一些参考，主流的框架+合理的优化，足以应对绝大部分应用的性能需求，如果是对性能有极致需求的特殊情况，其实应该牺牲一些可维护性采取手动优化:比如atom编辑器在文件渲染的实现上放弃了react而采用了自己实现的tile-based rendering; 又比如在移动端需要dom-pooling的虚拟滚动，不需要考虑顺序变化，可以绕过框架的内置实现自己搞一个。
diff算法
react在内存中维护一颗虚拟dom树，当数据发生改变时(state & props)，会自动的更新虚拟dom，获得一个新的虚拟dom树，然后通过diff算法，比较新旧虚拟dom树，找出最小的有变化的部分，将这个变化的部分patch加入队列，最终批量的更新这些patch到实际的dom中。
时间复杂度
首先进行一次完整的diff需要o(n^3)的时间复杂度，这是一个最www.887551.com辑距离的问题，在比较字符串的最www.887551.com辑距离时使用动态规划的方案需要的时间复杂度是o(mn)，但是对于dom来说是一个树形结构，而树形结构的最www.887551.com辑距离问题的时间复杂度在30多年的演进中从o(m^3n^3)演进到了o(n^3)，关于这个问题如果有兴趣的话可以研究一下论文https://grfia.dlsi.ua.es/ml/algorithms/references/editsurvey_bille.pdf。
对于原本想要提高效率而引入的diff算法使用o(n^3)的时间复杂度显然是不太合适的，如果有1000个节点元素将需要进行十亿次比较，这是一个昂贵的算法，所以必须有一些妥协来加快速度，对比较通过一些策略进行简化，将时间复杂度缩小到o(n)，虽然并不是最www.887551.com辑距离，但是作为编辑距离与时间性能的综合考量是一个比较好的解决方案，是一种比较好的折中方案。
diff策略
上边提到的o(n)时间复杂度是通过一定策略进行的，react文档中提到了两个假设：
- 两个不同类型的元素将产生不同的树。
- 通过渲染器附带
key属性，开发者可以示意哪些子元素可能是稳定的。
通俗点说就是：
- 只进行统一层级的比较，如果跨层级的移动则视为创建和删除操作。
- 如果是不同类型的元素，则认为是创建了新的元素，而不会递归比较他们的孩子。
- 如果是列表元素等比较相似的内容，可以通过
key来唯一确定是移动还是创建或删除操作。
比较后会出现几种情况，然后进行相应的操作：
- 此节点被添加或移除
->添加或移除新的节点。 - 属性被改变
->旧属性改为新属性。 - 文本内容被改变
->旧内容改为新内容。 - 节点
tag或key是否改变->改变则移除后创建新元素。
分析
在分析时会简单引用一下在react的源码，起辅助作用的代码，实际源码是很复杂的，引用的是一部分片段帮助理解，本文的源码tag为16.10.2。
关于if (__dev__){...}相关代码实际上是为更好的开发者体验而编写的，react中的友好的报错，render性能测试等等代码都是写在if (__dev__)中的，在production build的时候，这些代码不会被打包，因此我们可以毫无顾虑的提供专为开发者服务的代码，react的最佳实践之一就是在开发时使用development build，在生产环境使用production build，所以我们实际上可以先跳过这部分代码，专注于理解较为核心的部分。
我们分析diff算法是从reconcilechildren开始的，之前从 setstate -> enqueuesetstate(updatequeue) -> scheduleupdate -> performwork -> workloop -> beginwork -> finishclasscomponent -> reconcilechildren相关的部分就不过多介绍了，需要注意的是beginwork会将一个一个的fiber来进行diff，期间是可中断的，因为每次执行下一个fiber的比对时，都会先判断这一帧剩余的时间是否充足，链表的每一个节点是fiber，而不是在16之前的虚拟dom节点，每一个fiber都有react16的diff策略采用从链表头部开始比较的算法，是链式的深度优先遍历，即已经从树形结构变成了链表结构，实际相当于在15的diff算法阶段，做了优先级的任务调度控制。此外，每个fiber都会有一个child、sibling、return三大属性作为链接树前后的指针；child作为模拟树结构的结构指针；effecttag一个很有意思的标记，用于记录effect的类型，effect指的就是对dom操作的方式，比如修改，删除等操作，用于到后面进行commit(类似数据库)；firsteffect、lasteffect等玩意是用来保存中断前后effect的状态，用户中断后恢复之前的操作以及tag用于标记。
reconcilechildren实现的就是江湖上广为流传的virtul dom diff，其实际上只是一个入口函数，如果首次渲染，current空null，就通过mountchildfibers创建子节点的fiber实例，如果不是首次渲染，就调用reconcilechildfibers去做diff，然后得出effect list。
// react-reconciler/src/reactchildfiber.js line 1246
export function reconcilechildren(
current: fiber | null,
workinprogress: fiber,
nextchildren: any,
renderexpirationtime: expirationtime,
) {
if (current === null) { // 首次渲染 创建子节点的`fiber`实例
workinprogress.child = mountchildfibers(
workinprogress,
null,
nextchildren,
renderexpirationtime,
);
} else { // 否则调用`reconcilechildfibers`去做`diff`
workinprogress.child = reconcilechildfibers(
workinprogress,
current.child,
nextchildren,
renderexpirationtime,
);
}
}
对比一下mountchildfibers和reconcilechildfibers有什么区别，可以看出他们都是通过childreconciler工厂函数来的，只是传递的参数不同而已，这个参数叫shouldtracksideeffects，他的作用是判断是否要增加一些effecttag，主要是用来优化初次渲染的，因为初次渲染没有更新操作。childreconciler是一个超级长的工厂(包装)函数，内部有很多helper函数，最终返回的函数叫reconcilechildfibers，这个函数实现了对子fiber节点的reconciliation。
// react-reconciler/src/reactchildfiber.js line 1370
export const reconcilechildfibers = childreconciler(true);
export const mountchildfibers = childreconciler(false);
function childreconciler(shouldtracksideeffects) {
// ...
function deletechild(){
// ...
}
function usefiber(){
// ...
}
function placechild(){
// ...
}
function placesinglechild(){
// ...
}
function updatetextnode(){
// ...
}
function updateelement(){
// ...
}
function updateportal(){
// ...
}
function updatefragment(){
// ...
}
function createchild(){
// ...
}
function updateslot(){
// ...
}
function updatefrommap(){
// ...
}
function warnoninvalidkey(){
// ...
}
function reconcilechildrenarray(){
// ...
}
function reconcilechildreniterator(){
// ...
}
function reconcilesingletextnode(){
// ...
}
function reconcilesingleelement(){
// ...
}
function reconcilesingleportal(){
// ...
}
function reconcilechildfibers(){
// ...
}
return reconcilechildfibers;
}
reconcilechildfibers就是diff部分的主体代码，相关操作都在childreconciler函数中，在这个函数中相关参数，returnfiber是即将diff的这层的父节点，currentfirstchild是当前层的第一个fiber节点，newchild是即将更新的vdom节点(可能是textnode、可能是reactelement，可能是数组)，不是fiber节点。expirationtime是过期时间，这个参数是跟调度有关系的，跟diff没有太大关系，另外需要注意的是，reconcilechildfibers 是reconcile(diff)的一层结构。
首先看textnode的diff，他是最简单的，对于diff textnode会有两种情况：
currentfirstnode是textnode。currentfirstnode不是textnode。
分两种情况原因就是为了复用节点，第一种情况，xxx是一个textnode，那么就代表这这个节点可以复用，有复用的节点，对性能优化很有帮助，既然新的child只有一个textnode，那么复用节点之后，就把剩下的aaa节点就可以删掉了，那么div的child就可以添加到workinprogress中去了。usefiber就是复用节点的方法，deleteremainingchildren就是删除剩余节点的方法，这里是从currentfirstchild.sibling开始删除的。
if (currentfirstchild !== null && currentfirstchild.tag === hosttext) {
// we already have an existing node so let's just update it and delete
// the rest.
deleteremainingchildren(returnfiber, currentfirstchild.sibling); // 删除兄弟
const existing = usefiber(currentfirstchild, textcontent, expirationtime);
existing.return = returnfiber;
return existing; // 复用
}
第二种情况，xxx不是一个textnode，那么就代表这个节点不能复用，所以就从currentfirstchild开始删掉剩余的节点，其中createfiberfromtext就是根据textcontent来创建节点的方法，此外删除节点不会真的从链表里面把节点删除，只是打一个delete的tag，当commit的时候才会真正的去删除。
// the existing first child is not a text node so we need to create one // and delete the existing ones. // 创建新的fiber节点，将旧的节点和旧节点的兄弟都删除 deleteremainingchildren(returnfiber, currentfirstchild); const created = createfiberfromtext( textcontent, returnfiber.mode, expirationtime, );
接下来是react element的diff，此时我们处理的是该节点的父节点只有此节点一个节点的情况，与上面textnode的diff类似，他们的思路是一致的，先找有没有可以复用的节点，如果没有就另外创建一个。此时会用到上边的两个假设用以判断节点是否可以复用，即key是否相同，节点类型是否相同，如果以上相同，则可以认为这个节点只是变化了内容，不需要创建新的节点，可以复用的。如果节点的类型不相同，就将节点从当前节点开始把剩余的都删除。在查找可复用节点的时候，其并不是只专注于第一个节点是否可复用，而是继续在该层中循环找到一个可以复用的节点，最顶层的while以及底部的child = child.sibling;是为了继续从子节点中找到一个key与tag相同的可复用节点，另外删除节点不会真的从链表里面把节点删除，只是打一个delete的tag，当commit的时候才会真正的去删除。
// react-reconciler/src/reactchildfiber.js line 1132
const key = element.key;
let child = currentfirstchild;
while (child !== null) {
// todo: if key === null and child.key === null, then this only applies to
// the first item in the list.
if (child.key === key) {
if (
child.tag === fragment
? element.type === react_fragment_type
: child.elementtype === element.type ||
// keep this check inline so it only runs on the false path:
(__dev__
? iscompatiblefamilyforhotreloading(child, element)
: false)
) {
deleteremainingchildren(returnfiber, child.sibling); // 因为当前节点是只有一个节点，而老的如果是有兄弟节点是要删除的，是多余的
const existing = usefiber(
child,
element.type === react_fragment_type
? element.props.children
: element.props,
expirationtime,
);
existing.ref = coerceref(returnfiber, child, element);
existing.return = returnfiber;
// ...
return existing;
} else {
deleteremainingchildren(returnfiber, child);
break;
}
} else {
deletechild(returnfiber, child); // 从child开始delete
}
child = child.sibling; // 继续从子节点中找到一个可复用的节点
}
接下来就是没有找到可以复用的节点因而去创建节点了，对于fragment节点和一般的element节点创建的方式不同，因为fragment本来就是一个无意义的节点，他真正需要创建fiber的是它的children，而不是它自己，所以createfiberfromfragment传递的不是element，而是element.props.children。
// react-reconciler/src/reactchildfiber.js line 1178
if (element.type === react_fragment_type) {
const created = createfiberfromfragment(
element.props.children,
returnfiber.mode,
expirationtime,
element.key,
);
created.return = returnfiber;
return created;
} else {
const created = createfiberfromelement(
element,
returnfiber.mode,
expirationtime,
);
created.ref = coerceref(returnfiber, currentfirstchild, element);
created.return = returnfiber;
return created;
}
diff array算是diff中最复杂的一部分了，做了很多的优化，因为fiber树是单链表结构，没有子节点数组这样的数据结构，也就没有可以供两端同时比较的尾部游标，所以react的这个算法是一个简化的双端比较法，只从头部开始比较，在vue2.0中的diff算法在patch时则是直接使用的双端比较法实现的。
首先考虑相同位置进行对比，这个是比较容易想到的一种方式，即在做diff的时候就可以从新旧的数组中按照索引一一对比，如果可以复用，就把这个节点从老的链表里面删除，不能复用的话再进行其他的复用策略。此时的newchildren数组是一个vdom数组，所以在这里使用updateslot包装成newfiber。
// react-reconciler/src/reactchildfiber.js line 756
function reconcilechildrenarray(
returnfiber: fiber,
currentfirstchild: fiber | null,
newchildren: array<*>,
expirationtime: expirationtime,
): fiber | null {
// 机翻注释
// 这个算法不能通过两端搜索来优化，因为我们在光纤上没有反向指针。我想看看我们能用这个模型走多远。如果最终不值得权衡，我们可以稍后再添加。
// 即使是双端优化，我们也希望在很少有变化的情况下进行优化，并强制进行比较，而不是去寻找地图。它想探索在前进模式下首先到达那条路径，并且只有当我们注意到我们需要很多向前看的时候才去地图。这不能处理反转以及两个结束的搜索，但这是不寻常的。此外，要使两端优化在iterables上工作，我们需要复制整个集合。
// 在第一次迭代中，我们只需在每次插入/移动时都碰到坏情况（将所有内容添加到映射中）。
// 如果更改此代码，还需要更新reconcilechildreniterator()，它使用相同的算法。
let oldfiber = currentfirstchild;
let lastplacedindex = 0;
let newidx = 0;
let nextoldfiber = null;
// 第一个for循环，按照index一一对比，当新老节点不一致时退出循环并且记录退出时的节点及oldfiber节点
for (; oldfiber !== null && newidx < newchildren.length; newidx++) {
if (oldfiber.index > newidx) { // 位置不匹配
nextoldfiber = oldfiber; // 下一个即将对比的旧节点
oldfiber = null; // 如果newfiber也为null(不能复用)就退出当前一一对比的for循环
} else {
nextoldfiber = oldfiber.sibling; //正常的情况下 为了下轮循环，拿到兄弟节点下面赋值给oldfiber
}
// //如果节点可以复用(key值匹配)，就更新并且返回新节点，否则返回为null，代表节点不可以复用
const newfiber = updateslot( // 判断是否可以复用节点
returnfiber,
oldfiber,
newchildren[newidx],
expirationtime,
);
// 节点无法复用 跳出循环
if (newfiber === null) {
// todo: this breaks on empty slots like null children. that's
// unfortunate because it triggers the slow path all the time. we need
// a better way to communicate whether this was a miss or null,
// boolean, undefined, etc.
if (oldfiber === null) {
oldfiber = nextoldfiber; // 记录不可以复用的节点并且退出对比
}
break; // 退出循环
}
if (shouldtracksideeffects) {
// 没有复用已经存在的节点，就删除掉已经存在的节点
if (oldfiber && newfiber.alternate === null) {
// we matched the slot, but we didn't reuse the existing fiber, so we
// need to delete the existing child.
deletechild(returnfiber, oldfiber);
}
}
// 本次遍历会给新增的节点打 插入的标记
lastplacedindex = placechild(newfiber, lastplacedindex, newidx);
if (previousnewfiber === null) {
// todo: move out of the loop. this only happens for the first run.
resultingfirstchild = newfiber;
} else {
// todo: defer siblings if we're not at the right index for this slot.
// i.e. if we had null values before, then we want to defer this
// for each null value. however, we also don't want to call updateslot
// with the previous one.
previousnewfiber.sibling = newfiber;
}
previousnewfiber = newfiber;
oldfiber = nextoldfiber; // 重新给 oldfiber 赋值继续遍历
}
在updateslot方法中定义了判断是否可以复用，对于文本节点,如果key不为null，那么就代表老节点不是textnode，而新节点又是textnode，所以返回null，不能复用，反之则可以复用，调用updatetextnode方法，注意updatetextnode里面包含了首次渲染的时候的逻辑，首次渲染的时候回插入一个textnode，而不是复用。
// react-reconciler/src/reactchildfiber.js line 544
function updateslot(
returnfiber: fiber,
oldfiber: fiber | null,
newchild: any,
expirationtime: expirationtime,
): fiber | null {
// update the fiber if the keys match, otherwise return null.
const key = oldfiber !== null ? oldfiber.key : null;
if (typeof newchild === 'string' || typeof newchild === 'number') {
// 对于新的节点如果是 string 或者 number，那么都是没有 key 的，
// 所有如果老的节点有 key 的话，就不能复用，直接返回 null。
// 老的节点 key 为 null 的话，代表老的节点是文本节点，就可以复用
if (key !== null) {
return null;
}
return updatetextnode(
returnfiber,
oldfiber,
'' + newchild,
expirationtime,
);
}
// ...
return null;
}
newchild是object的时候基本上与reactelement的diff类似，只是没有while了，判断key和元素的类型是否相等来判断是否可以复用。首先判断是否是对象，用的是typeof newchild === object&&newchild!== null，注意要加!== null，因为typeof null也是object，然后通过$$typeof判断是react_element_type还是react_portal_type，分别调用不同的复用逻辑，然后由于数组也是object，所以这个if里面也有数组的复用逻辑。
// react-reconciler/src/reactchildfiber.js line 569
if (typeof newchild === 'object' && newchild !== null) {
switch (newchild.$$typeof) {
case react_element_type: { // reactelement
if (newchild.key === key) {
if (newchild.type === react_fragment_type) {
return updatefragment(
returnfiber,
oldfiber,
newchild.props.children,
expirationtime,
key,
);
}
return updateelement(
returnfiber,
oldfiber,
newchild,
expirationtime,
);
} else {
return null;
}
}
case react_portal_type: {
// 调用 updateportal
// ...
}
}
if (isarray(newchild) || getiteratorfn(newchild)) {
if (key !== null) {
return null;
}
return updatefragment(
returnfiber,
oldfiber,
newchild,
expirationtime,
null,
);
}
}
让我们回到最初的遍历，当我们遍历完成了之后，就会有两种情况，即老节点已经遍历完毕，或者新节点已经遍历完毕，如果此时我们新节点已经遍历完毕，也就是没有要更新的了，这种情况一般就是从原来的数组里面删除了元素，那么直接把剩下的老节点删除了就行了。如果老的节点在第一次循环的时候就被复用完了，新的节点还有，很有可能就是新增了节点的情况，那么这个时候只需要根据把剩余新的节点直接创建fiber就行了。
// react-reconciler/src/reactchildfiber.js line 839
// 新节点已经更新完成，删除多余的老节点
if (newidx === newchildren.length) {
// we've reached the end of the new children. we can delete the rest.
deleteremainingchildren(returnfiber, oldfiber);
return resultingfirstchild;
}
// 新节点已经更新完成，删除多余的老节点
if (oldfiber === null) {
// if we don't have any more existing children we can choose a fast path
// since the rest will all be insertions.
for (; newidx < newchildren.length; newidx++) {
const newfiber = createchild(
returnfiber,
newchildren[newidx],
expirationtime,
);
if (newfiber === null) {
continue;
}
lastplacedindex = placechild(newfiber, lastplacedindex, newidx);
if (previousnewfiber === null) {
// todo: move out of the loop. this only happens for the first run.
resultingfirstchild = newfiber;
} else {
previousnewfiber.sibling = newfiber;
}
previousnewfiber = newfiber;
}
return resultingfirstchild;
}
接下来考虑移动的情况如何进行节点复用，即如果老的数组和新的数组里面都有这个元素，而且位置不相同这种情况下的复用，react把所有老数组元素按key或者是index放map里，然后遍历新数组，根据新数组的key或者index快速找到老数组里面是否有可复用的，元素有key就map的键就存key，没有key就存index。
// react-reconciler/src/reactchildfiber.js line 872
// add all children to a key map for quick lookups.
// 从oldfiber开始将已经存在的节点的key或者index添加到map结构中
const existingchildren = mapremainingchildren(returnfiber, oldfiber);
// keep scanning and use the map to restore deleted items as moves.
// 剩余没有对比的新节点，到旧节点的map中通过key或者index一一对比查看是否可以复用。
for (; newidx < newchildren.length; newidx++) {
// 主要查看新旧节点的key或者index是否有相同的，然后再查看是否可以复用。
const newfiber = updatefrommap(
existingchildren,
returnfiber,
newidx,
newchildren[newidx],
expirationtime,
);
if (newfiber !== null) {
if (shouldtracksideeffects) {
if (newfiber.alternate !== null) {
// the new fiber is a work in progress, but if there exists a
// current, that means that we reused the fiber. we need to delete
// it from the child list so that we don't add it to the deletion
// list.
existingchildren.delete( // 在map中删除掉已经复用的节点的key或者index
newfiber.key === null ? newidx : newfiber.key,
);
}
}
lastplacedindex = placechild(newfiber, lastplacedindex, newidx);
// 添加newfiber到更新过的newfiber结构中。
if (previousnewfiber === null) {
resultingfirstchild = newfiber;
} else {
previousnewfiber.sibling = newfiber;
}
previousnewfiber = newfiber;
}
}
// react-reconciler/src/reactchildfiber.js line 299
// 将旧节点的key或者index，旧节点保存到map结构中，方便通过key或者index获取
function mapremainingchildren(
returnfiber: fiber,
currentfirstchild: fiber,
): map<string | number, fiber> {
// add the remaining children to a temporary map so that we can find them by
// keys quickly. implicit (null) keys get added to this set with their index
// instead.
const existingchildren: map<string | number, fiber> = new map();
let existingchild = currentfirstchild;
while (existingchild !== null) {
if (existingchild.key !== null) {
existingchildren.set(existingchild.key, existingchild);
} else {
existingchildren.set(existingchild.index, existingchild);
}
existingchild = existingchild.sibling;
}
return existingchildren;
}
至此新数组遍历完毕，也就是同一层的diff过程完毕，我们可以把整个过程分为三个阶段:
- 第一遍历新数组，新老数组相同
index进行对比，通过updateslot方法找到可以复用的节点，直到找到不可以复用的节点就退出循环。 - 第一遍历完之后，删除剩余的老节点，追加剩余的新节点的过程，如果是新节点已遍历完成，就将剩余的老节点批量删除
;如果是老节点遍历完成仍有新节点剩余，则将新节点直接插入。 - 把所有老数组元素按
key或index放map里，然后遍历新数组，插入老数组的元素，这是移动的情况。
每日一题
https://github.com/windrunnermax/everyday
参考
https://github.com/sisteran/blog/issues/22
https://github.com/advanced-frontend/daily-interview-question/issues/47
https://github.com/jianjiachenghub/react-deeplearn/blob/master/%e5%ad%a6%e4%b9%a0%e7%ac%94%e8%ae%b0/react16%e6%ba%90%e7%a0%81%e8%a7%a3%e6%9e%906-fiber%e9%93%be%e5%bc%8fdiff%e7%ae%97%e6%b3%95.md
以上就是深入浅析react中diff算法的详细内容，更多关于react中diff算法的资料请关注www.887551.com其它相关文章！
